Mike Knepper

MiniMax Lessons and Reminders

March 7, 2014

Creating a Tic-Tac-Toe game that implements the MiniMax algorithm is something of a rite of passage at 8th Light. It has been without question the most difficult thing I’ve worked on as an apprentice, and frankly I’m still not 100% certain my current solution is sufficient, but I have at least made some progress and my tests are passing. Along the way I’ve learned and remembered several important lessons to help the process.

Comprehension to recreation is a multi-step process

One great advantage of working on open-source projects is the abundance of helpful resources available to you. At this stage of my career, odds are someone has already run into the same problem I’m facing and has shared a solution online. After wrapping my head around MiniMax conceptually, I found several blog posts, gists, and stack overflow Q&As outlining various implementations of MiniMax in Tic-Tac-Toe, in Ruby no less! Yet despite being able to comprehend the code I found online, it was very difficult to actually recreate the implementations in my own codebase. Sure, some of this was invariably due to differences in how we set up other components of the game, but more importantly, solutions posted online only show the final outcome and not the steps taken to get there.

Consider some katas. In the Gilded Rose Kata, for example, there is a dramatic difference between the original code and the refactored solution. Given a cursory glance at the two, one would probably guess they were from completely different contexts responsible for completely different tasks. While both code snippets can be read and comprehended, they cannot be immediately transposed back and forth–the refactoring process requires a lot of time, changes, and decision-making. Katas like the Gilded Rose and Prime Factors remind me that elegant solutions are not conjured out of thin air, but rather evolve from small beginnings. (There’s a joke about Creationism in here somewhere, I’m sure of it!)

So, despite numerous MiniMax solutions available to read, reference, steal, what have you, implementing the algorithm into my own codebase required real time, thought, effort, and patience on my end.

Avoid boxing yourself in

Knowing the ending inevitably changes your approach to the story along the way. I knew ahead of time (spoilers?) that Hamlet dies at the end, that it was Earth all along, that Tyler Durden is a split personality, that Rosebud is a sled, etc. Sometimes knowing the ending ahead of time isn’t a big deal, and other times it completely ruins the experience. In the case of implementing MiniMax, seeing some solutions ahead of time was somewhere in-between–helpful in some respects, but dangerous as well. More than once I got stuck in a situation where I had gotten one piece to work right, and I thought I knew a step down the line I wanted to get to, but I had trouble figuring out the path from A to B. It’s easy to get boxed in to a certain mindset, to convince yourself that a particular answer must be the right answer and any stray direction is the wrong direction, but in fact this is not true. I should have realized by virtue of seeing a few different solutions that there are multiple ways to implement MiniMax–there isn’t just one correct answer. It’s OK to have a specific goal in mind, but it’s also OK to explore alternatives born of tangent ideas.

Don’t be afraid to toast everything and start over

rm -rf. git reset --hard. gg v G d. These commands aren’t fun to use. It sucks when you get to this point. But sometimes the clean slate they provide is exactly what you need. Malcolm Newsome, an apprentice at 8th Light, gave a great smalltalk presentation recently about the value of starting over from scratch. The worst that can happen is really not that bad. I ended up blowing up my MiniMax progress and starting over twice, and while the decisions weren’t easy ones to make and seemed born of desperation in the moment, things went smoother and better after both times. These commands may erase the code, but not the lessons learned from the experience.

Several smaller methods > One large method

Hey, I had to throw at least one technical detail in this post, right? One of my most critical breakthroughs working on MiniMax involved extracting out some functionality from one overly-large method into a separate method. This helped in so many ways–testing became easier because the tests and methods were more focused, I was able to return values and objects that were easier to work with, and the code became more readable to others. Several times I’ve walked into IPMs with Rylan thinking I did a good job of following the Single Responsibility Principle, only to have him ask me if such-and-such really needs to know about this-thing, or if it might be better off somewhere else. The line here is often ambiguous, but one way to help identify that line is by describing what your methods and classes do out loud, even if just to yourself. At the risk of suggesting a hard rule that I end up breaking, I’ll say that it probably shouldn’t require more than a single sentence to explain.

tl;dr

The MiniMax algorithm is a tough beast, but not impossible. The key to implementing something this complex is simply sticking to the fundamentals–be patient, start small, test test test, and keep things tight and under control.