Link
Source Code: github.com/jkwok626/ticTacToe
Problem
The goal of tic-tac-toe is to claim all three spots in a row, but many casual players are not aware that the outcome of the game can be decided after both players take their first turn.
Background
Tic-tac-toe looks like a straightforward game at a glance. There are nine spots on the board and two players compete to see who can claim three of the spots in a row. It’s easy to believe that all nine of these spots are equal, but the first spot that the first player chooses actually has a huge effect on how the game is played and its end result. Choosing the right spot opens up strategies that can be used to win.
The Unbeatable Tic-tac-toe Bot was a personal project that I did to practice breaking down a problem into specific cases. When I first started this project, I had just finished taking CSE 21: Mathematics for Algorithms and Systems, which was a class that had a heavy emphasis on breaking down problems into smaller problems. Tic-tac-toe is a game that I remember enjoying very much as a child. I could play it practically anywhere with a friend as long as we had a surface and a writing utensil. This ranged from playing it in class with a piece of paper and a pencil to playing it outside on a dirt path with a stick. So I was excited to combine something that I had just learned with something that I was doing instead of learning.
Design Process
Before I started writing any code, I watched a few videos about common tic-tac-toe strategies. I then sketched out multiple boards and played a practice games with myself so that I could better understand how and why those common strategies worked. I also practiced preventing those strategies from working so that I could make my computer player unbeatable.
Once I started writing code, I decided that I wanted my code to be easily understandable, so I didn't want to make my code too complicated. For example, since a tic-tac-toe board is with nine spots is just a 3x3 grid, I decided to use a 2D array to represent it. For each of the cases, I used if/else statements with comments to show how the computer player was handling each scenario. This made it so that a tic-tac-toe player can read through the code and follow the computer player's actions while playing a real game of tic-tac-toe with someone else.
Issues and Resolutions
I had intended for this entire project to continuously print to a terminal, but this ended up causing some usability issues later on down the line.
One problem that I ran into was figuring out how to capture user input. With the board printing to a terminal, it almost seemed like the user was supposed to click or touch the spots on the board. This wasn't possible so I decided to just include a prompt that told users to choose a number from 1 to 9 with 1 being the top-left spot and 9 being the bottom-right spot.
Another issue came up whenever the board got printed to the terminal. The terminal usually prints continuously by printing on the next newline. However, since I was printing a board after each turn, this meant that there were multiple boards on the user's screen. To fix this issue, I learned how to detect what operating system the user is using (e.g. Windows, MacOS, Linux) and ran the appropriate command to clear the screen before I printed the board each turn.
The last issue that I encountered was that the computer player would perform and complete its turn immediately after the user made their turn. I thought this looked extremely jarring because it didn't give time for the user to process their actions. It also made it seem like it was constantly the user's turn because the computer player would finish its turn in an instant. I ended up adding a small delay of about 2 seconds right after the player's turn so that it made it seem like the computer player was taking time to make a decision.
User Testing and Further Testing
After I felt that I had finished the project, I tested The Unbeatable Tic-tac-toe Bot with some friends to see if they could find any situations where they could actually beat my computer player. I asked them to play how they normally would and when that didn't work, I asked them to try to find patterns in the computer player's moves and try to abuse them. I then further tested my computer player by playing with it using a random number generator so that I could choose random spots. I actually found a case that I didn't cover this way, so I retraced the steps I took using the random number generator and addressed that case.
Case Analysis
The cases in tic-tac-toe are actually based on the types of spots on the board. While there are nine spots, there are really only three types of spots: corner, side, and middle. Even though there are four corners and four sides, it doesn't really matter which of corner or side the first player chooses because you can just rotate the board. The basic premise of every tic-tac-toe strategy is to create two ways to win so that your opponent can't block both at once.
Case 1: Corner
Subcase 1
If you take a corner spot in your first turn and your opponent chooses any spot other than the middle, then you'll want to take the corner spot in a row that lines up with your original corner spot and hasn't been blocked already. To put this into perspective, let's say you took spot 1 as shown on the right. If your opponent took spot 4, then you should take spot 3 because it's a corner spot that lines up with spot 1 and it's in a row that hasn't been blocked. The opponent is forced to take spot 2 to prevent you from winning. Your next move should be taking the corner opposite from your original corner, which is spot 9. This means that you can win using the diagonal row of spots 1, 5, and 9 or using the vertical row of spots 3, 6, and 9. Your opponent can't block both at once so you're guaranteed a win.
Subcase 2
However, this isn't unstoppable. If your opponent takes the middle spot right away, it will prevent the previous strategy from working since it relies on using a diagonal row as one of two ways to victory. In this situation, you should take the corner spot opposite from your original corner spot, so spot 9 if your original spot was spot 1. If your opponent takes one of the remaining corner spots, for example, spot 7, then you can take the last corner spot and still have two ways to win: the horizontal row of spots 1, 2, and 3 or the vertical row of spots 3, 6, and 9. If your opponent decides to take a side spot instead of a corner spot after taking the middle, then the game will most likely end in a tie.
Case 2: Side
Subcase 1
Let's say you take a side spot, like spot 2, in your first turn. If your opponent takes spots 4 or 7, which are on the bottom left of the board, then you should take spot 1 in the top left next. If your opponent takes spots 6 or 9, which are on the bottom right of the board, then you should take spot 3 in the top right next. Your opponent is going to have to spend their next turn blocking you because you're about to win using the horizontal row of spots 1, 2, and 3. If you take the middle spot next, then you'll have two ways to win: one of the diagonal rows or the vertical row of spots 2, 5, and 8.
Subcase 2
What happens if your opponent decides to choose the middle spot during their first turn? In this case, you want to use your next turn to occupy a spot to the left or right of the middle, such as spot 4. On your opponent's next turn, if they decide to go into the three spots in the bottom right, spots 6, 8, and 9, then you can take spot 1. This will allow you to win using the horizontal row of spots 1, 2, and 3 or the vertical row of spots 1, 4, and 6. If your opponent had chose to occupy one of the other corner spots or the middle instead of those 3 bottom right spots, then the game would most likely go back and forth until a tie happens.
Subcase 3
If your opponent decides to choose the side spot opposite from your original spot during their first turn, you'll want to go right next to their spot again. In this example, we'll use spot 7. If your opponent decides to choose spots 4, 5, 6, or 9, then you'll be able to create two ways to win by choosing spots 1 or 3.
Subcase 4
If your opponent chooses the spots to the left or right of you, which are spots 1 or 3 in this case, then you'll want to choose the corner spot under the spot they chose. For example, if they chose spot 3, you'll want to take spot 9 on your next turn. After this, if your opponent chooses to take spots 1, 4, 6, or 7, then you'll be able to create two ways to win by using spots 5 or 8.
Case 3: Middle
Subcase 1
If you take the middle spot in your first turn, and your opponent takes one of the side spots, then you'll want to choose a spot right next to the spot they chose. For example, if they chose spot 4, you can choose spot 1. On your opponent's next turn, they will have to use up their turn to block you. In your next turn, you'll want to create an empty triangle shape. What I mean by this is that you already have two spots on the board, so you need to find a third spot that will form a triangle if you trace over all your spots and there needs to be an empty spot between all three spots. If you chose spot 3, that would complete the empty triangle of spots 1, 3, and 5 with spot 2 being empty. This would give you two ways to win: the horizontal row of spots 1, 2, and 3 or the diagonal row of spots 3, 5, and 7. If you had chosen spot 7 instead of spot 3 to form the triangle, your triangle won't be empty because your opponent claimed spot 4, which means that you won't have two ways to win.
Subcase 2
If your opponent decides to take a corner spot during their first turn instead of a side spot, then you'll want to take the corner that is opposite to the corner they chose. So, for example, if they chose spot 3, you would want to choose spot 7. This move might seem pointless because there's already no way that you can win using the diagonal row of spots 3, 5, and 7, but this move is actually very important, and I'll come back to it later. On your opponent's next turn, if they choose a side spot, then it'll become like the first game where you have to create an empty triangle to get two ways to win. If they don't choose a side spot, then the game will probably go back and forth until it ends in a tie. To go back on why we wanted to choose the opposite corner in our second turn, it's because if we had chosen any other corner spot, we would've had two spots in a row on a diagonal, so the opponent has no choice but to go into a corner spot to block us, which is not what we want because we need them to go into a side spot. If we had chosen a side spot in our second turn, we wouldn't have been able to form the empty triangle to set up our two ways to win.
Becoming Unbeatable
When I was working out the logic for my computer player, I followed the strategies that I highlighted above. While those strategies set up victory for the first player, they often require the second player to choose specific spots so that the first player can set up two ways to win. When I designed my computer player as the second player, I made sure that it didn't go into those specific spots, which meant that it could always block any chance of victory for the first player. Something else I noticed was that aiming for the middle right away was usually the best move for the second player because it closes off four out of the eight ways that the first player can win, so I made my computer player prioritize the middle spot if it was available.
Potential Improvements
There are still some things that I would definitely like to improve with The Unbeatable Tic-tac-toe Bot. First of all, I would like to turn this project into a mobile app or a web app. This would allow me to implement touch and mouse support, which I felt were missing when I originally worked on this project.
I would also like to add another mode that allows the user to go second. Right now, the user always takes the first turn. I think allowing the user to go second could help them better learn how to react to more scenarios. In addition to this, I think it could be helpful to players if I included an option to enable tips in between turns or in between games to help them learn the game better.