A few months ago, when I had decided that I wanted to quit my job as a C++ developer and become a web developer, I applied to the Flatiron School to immerse myself in web technologies. During the application process, I was assigned a code challenge, to create a game of Tic-Tac-Toe, played either by two humans or a human against an AI player, in the language of my choosing. To challenge myself, I chose Ruby, a language I had never used before but figured that there was never a better moment to start. I applied all of the object-oriented programming fundamentals I knew from my time coding in C++ and Java, and ended up with somethiing I was pretty proud of.
After the class was over, only four months after I wrote my first Ruby code, I went back to build upon what I had previously done. It’s fun to see how much better you’ve gotten at something, in my opinion. It was funny to see all of the non-Rubylike things I had done:
- Accessing data elements outside of a class’s initialize method. For example, inside of my
1 2 3
This I changed to
1 2 3
- Using explicit return statements at the end of methods. I was used to the world of C++ in which best practice is to be as explicit as possible, otherwise your code is really difficult to read. Again, from the
1 2 3
I changed this method to
1 2 3
- Unconventional method naming. What was with the question marks and exclamation points? I had written stuff like this (from
1 2 3 4 5 6 7
Also, what’s with those if and else statements? I was used to the C++ world in which that kind of logic ends up so verbose. I fixed it to look like this:
1 2 3 4
Much more compact and readable, and better error checking!
Designing an AI
Once I had fixed my code to fit with Ruby conventions, I had a larger task to accomplish: make the AI unbeatable. I felt confident, as I had written an AI before for Battleship. However, it turns out that designing a Battleship strategy is different from Tic-Tac-Toe. A lot different, in fact, and it tripped me up.
When I designed the AI for Battleship, I created a board of probabilites, based on the likelihood of a ship being in a certain position on the board. I tried to do the same for Tic-Tac-Toe, even creating a
ProbabilitiesBoard class that was initialized to look like this
1 2 3 4 5 6 7 8 9
in which each number represents the number of different ways a player can win, based on the number of rows that interesect a position. Unfortunately, as I played out a few games and tried to recalculate my probabilities, I realised my calculation wasn’t robust enough. It didn’t take into account enough different possibilites of gameplay. Because, in Tic-Tac-Toe, unlike Battleship, you also have to block another player.
Tic-Tac-Toe is not like Battleship
So I was back to square one. I started to think about the game in certain types of moves. Certain moves won the game by making three in a row, certain moves blocked another player, certain moves created a dual threat, and so on. I had distilled the types of moves into a hierarchy as well, which looked something like this:
- If you have two in a row, add a third to the row to win the game.
- If your opponent has two in a row, add a third to the row to block him or her from winning.
- Place your mark on the board strategically, bringing you closer to winning.
This was something. I quickly implemented two methods in the
find_blocking_move. Because I found that I need to iterate over all of the different rows in the board, I decided to store them in my
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Now, I could iterate though all of the rows and see if any of them had two ‘X’s or ‘O’s in a row:
1 2 3 4 5 6 7 8
As you see, I created a separate method in the
ComputerPlayer class called
find_two_in_a_row, which iterates though all of the rows and tries to find two in a row of a mark passed in as a parameter. As soon as it finds a row, it returns with the empty position in the row.
A Hierarchical Strategy
I had created two crucial methods whith made the AI a lot smarter, but I was lost on the rest of the strategy. I decided to ask the Internet for some inspiration, and I found some help on Wikihow and Quora. However, I found it difficult to find patterns. I didn’t want to add a lot of
else statements which check for things like “if the AI player went first and then the opponent moved in a corner” then “the AI player should put a mark in the opposite corner”. It didn’t feel right, and I felt like I could do better.
I had an aha moment when I came across this answer to a StackExchange question. It states that a Tic-Tac-Toe strategy is based on a hierarchy of types of moves. Of course! I had gotten halfway there when I realized that winning was more important than blocking which was more important that other types of moves, but I hadn’t been able to pin down the other types of moves. The hierarchy of moves is
The following algorithm will allow you (or the AI) to always deny your opponent victory:
Win: If you have two in a row, you can place a third to get three in a row.
Block: If the opponent has two in a row, you must play the third to block the opponent.
Fork: Create an opportunity where you have two threats to win (two non-blocked lines of 2).
Blocking an opponent’s fork: If there is a configuration where the opponent can fork, you must block that fork.
Center: You play the center if open.
Opposite corner: If the opponent is in the corner, you play the opposite corner.
Empty corner: You play in a corner square.
Empty side: You play in a middle square on any of the 4 sides.
Pick the highest possible on the list
I was able to knock out most of these methods pretty quickly, except for finding forks and blocking an opponent’s forks. These turned out to be trickier than I expected.
In the case of finding a fork, I realized that a player only needed to find one in order to create a dual threat (and therefore win the game). I managed to map out an algorithm:
Iterate through all rows on the board if a row contained only one of the player’s mark, and nothing else, then iterate thorough all overlapping rows if an overlapping row contained only one of the player’s mark, and nothing else if it’s not the position in which the two rows overlap, then you’ve found a fork return the position in which the two rows overlap
I already knew how to iterate though all of the rows, but how do you find all of the overlapping rows? It turns out this is easier than I expected. I wrote a method for the
Board class called
overlapping_rows which takes a row as a parameter.
1 2 3
All this method does is select the rows that contain a position that is also in the row passed in, just as long as it is not the same row. The actual code in the
ComputerPlayer class ended up looking like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
The method returns the position to create a fork as soon as it finds the first fork.
Blocking All Forks, Not Just One
At first, I thought that after I had implemented a method that created forks, I could use the same code to block forks. I figured out there was a problem when I was testing with the following game:
In the process of blocking one fork, the AI had left another one open. Therefore, it wasn’t just as simple as finding the first fork. The AI had to find them all, and then choose the optimal place to block. First, finding all forks:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
The only problem with this method is that as it iterates over all rows, it inserts duplicate forks in a different order. Thus, the last line of the method removes these duplicates.
Then, I had to figure out a way to pick the proper blocking spot. I tried things like finding the position that occurs the most in the rows, but it turns out there was no correlation. I finally realized that the way to find the proper blocking move is to look ahead, by checking all moves that would block a fork. I did this in a method called
select_blocking_fork_move, which takes a list of possible forks as a parameter. The line
creates an array of possible moves by selecting all position on the board that are open and are on the forking rows.
Then, while iterating over all possible moves, the AI had to look ahead. The possible move is placed on a copy of the board
1 2 3 4 5
and then, the AI checks for one of two scenarios. First, it checks that if the blocking move creates two in a row, and then the opponent moves to block, it doesn’t create another fork for the opponent. That’s a lot, but I think it makes more sense if you look at the code:
1 2 3 4 5 6 7 8 9 10
As you see, I wrote a method called
contains_fork? which checks the board for forks. The else statement within the loop checks if the possible move does, in fact, block all possible forks:
1 2 3 4 5 6 7 8 9 10
The body of the else statement first removes the test opponent mark that had been put on the board, and then checks if there are any possible forks. If there aren’t, even though this move doesn’t create two in a row, it blocks the opponent from creating a fork.
And then, putting it all together:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Of course, there are some things that I’m not happy about in terms of how my code turned out.
- Breaking from loops using return statements
For this project, I am a big offender of breaking out of loops using a return statement. For example, from my
1 2 3 4 5 6 7 8
It’s not very Ruby-like, I know. Because of my C++ and Java background, in which it’s totally kosher to do that, it is one of my first instincts. I did try to refactor and figure out another way, but I think the way I have it now is the most clear, at least to me.
Command-line interface I find it to be a little annoying to use. I guess I could refactor it to be a web application, but that’s a lot more work, and the point of this was to create an unbeatable AI.
Storing rows in
Boardclass The “row” is the only part of this application that’s not object-oriented, which I’m not happy about. In my case, a row is an array of length three that holds three positions on the board. I hardcoded these values and stored them as part of the board. I also dislike how the method
overlapping_rowstakes a row as an argument, which is just an array. It’s just not right.
In the future, I would figure out how to make a row an object and not just data.
Check Out My Code
Now you know how to solve Tic-Tac-Toe! Yay!
If you want to try to find possible flaws in my logic, or look more at my implementation of Tic-Tac-Toe, please check out the
heuristic-solution branch on my Github repository. Or, if you know of a better way to solve this, let me know.