The project can be viewed here: http://fcc-tic-tac-toe.jeremyc.me
TLDR: Minmax is hard, it’ll make you want to quit. Don’t give up!
This is more of a journal entry for me, so if you’re not interested just stick with the TLDR
Today I finally finished my tic tac toe zipline. It was without a doubt, the most challenging, and frustrating project I’ve ever worked on. There was times of triumph, and times when I just wanted to pick up the computer and throw it out the window in disgust because the AI wasn’t working. There were points where this project really got into my head to the point that I was seriously doubting my ability to become a programmer.
From the outset I knew that I wanted the ai to use a minmax algorithm to determine it’s next move but proved to be ‘challenging’ to say the least. In total I ended up going through 3 iterations of it to get it to it’s current form. The first attempt was a miserable failure, which we won’t discuss .
The second was based off of this article: Case Study on Tic-Tac-Toe Part 2: With AI. With this newfound “knowledge” I set off to make the next Skynet. So I had a created a class that I could pass the current board into and the marker the represented the player and get the best move out. As it turned out, there was a mistake in the recursive minimax algorithm that caused it to error past a certain recursion depth. To top it off it was also pretty dumb, as it in self destructive to the point where I think it was trying to lose on purpose.
Round 3: Fight! This time I didn’t want to go with a class based architecture because I already had all of the information that I needed in the games state object and the perfect tool to manipulate that state in the redux reducer. After some further research I found this article Tic Tac Toe: Understanding The Minimax Algorithm and the answer to this SO question Implementing the minimax. With the help of these I finally had a better grasp of exactly what it was that the minmax algorithm was actually doing and how the scoring system actually worked. So with this I set out to write utility functions that could be used by the AI to determine it’s best move by using the reducer and it’s action dispatchers to manipulate the state and pass it around. The full source for the reducer, dispatchers, and utility functions is here.
It may not be the most efficient solution but it works and I’m happy with how it came out. Even though it was the product of several re-writes and refactors it was a rewarding experience, which gave me a better understanding of recursion. There are still things that need to be fixed especially with some of the react components but that will have to wait a little while
If anyone is trying to write, or thinking of writing a minmax I really suggest tat you check out the articles that were linked as well as the accompanying source code. You’ll have to decipher some java and ruby code but it’s worth it.