« back

Solve for Minimax

09 Aug 2012


+1 for me.

When I received my initial assignment of Tic-Tac-Toe, a craftsman suggested checking out minimax. I poured over every bit of pseudo-code I could find and started drawing game trees. I watched lectures on youtube. I was pretty sure I understood the concept. I was determined that I could just "solve minimax". I thought I would sit down, and type it out because I got the concept in my head. By the time I had most of the pieces of the game in place and showed it to my mentor, he told me with the code that I had, I had two choices: 1. I could start over if I wanted to use minimax.(I was off the mark) 2. I could use the code that I had to check for "forks" as a way to find or block best moves accordingly. I chose to test for forks. I used recursion for this and was able to build an unbeatable Tic-Tac-Toe.

For the second round, moving to the command line, minimax was required. Again, pseudo code and game trees. After really not "getting it" I was so frustrated because I was convinced that I understood it in theory. I would sit down and I didn't even know what tests to write. it 'should return the best move'? That would surely fail. Then I decided I should probably just move on to getting the basics of the Tic-Tac-Toe game working. Not a day would go by that I would not be thinking of minimax though. What was wrong with me. Why could I not get this!!!!!

Part way into my game, it was back to minimax. I couldn't stay away. Pseudo code and game trees. Again, no luck. I didn't know where to start. I couldn't think of a decent test to write that would not require the whole thing to be solved. Testing was fairly new to me as well. So frustrating. Seriously, I knew I understood the concept. I decided to just finish the rest of the game with the computer returning a random move.

After that, all there was left was minimax. Using the pseudo code and game trees as a guide, I began again. I struggled to even write a test. I knew it had to be something other than it 'should return the best move'. Then I heard Uncle Bob's voice saying to do the next simplest case. I also was gaining test writing experience through building my game. I wrote a test, then another, and another. I had a lot of the code I needed already just from building my game.

This really helped me internalize the fact that you really should only be writing the code you need at the time. I didn't need minimax to build my game but I needed my game to build minimax. I was focused on things in the wrong order.

Now I do not want to make it seem like minimax was easy, I spent countless hours thinking about it, but I can say this... When I finally got my game in place and then focused on minimax in little chunks instead of thinking I could tackle the whole thing at once, it was manageable. Pry also helped. :) When I was tweaking the last bit of code, I had a rush, I couldn't stop smiling. I knew it was correct before I hit enter to run my tests. I knew what every little piece was doing and I knew that I had snapped the last one into place.

Instead of trying to master everything in my head before writing my code, in the future it will be important to approach my problems in small steps. If I lay one brick at a time and focus on that, when I look up I will have built a house.

comments powered by Disqus