Anyone who has ever tried to build an AI for a Tic Tac Toe game has come across the Minimax algorithm. This algorithm simply iterates through the children of a node and returns the maximum value. This is perfect for Tic Tac Toe because it will iterate through every possible board and return the highest scoring option. This allows you to build a AI that is unbeatable. By design this algorithm uses forward recursion to traverse the tree of boards. This allows you to see all the options available to you and then choose the best one. On a normal 3x3 Tic Tac Toe board, this will work fine. However, when I tried to run the forward recursing Minimax on a 4x4, I quickly received a wonderful stack overflow error. So, lets take a look at it.
Note: this is a very naive implementation. It does not apply a heuristic score or perform any sort of branch trimming. Nonetheless, it runs quickly on a 3x3 board. However, with a 4x4 board, it will overflow. My first idea was to try memoizing the recursive call. This did improve the speed of the calls significantly, but it still crashed on a 4x4 board. So, it looks like the best option is to convert this into a tail recursive algorithm. Essentially, we are attempting to perform a in order traversal of an unbalanced tree. Unfortunately, with the current implementation, we have no way to return to our parent once we reach a leaf node. So, I believe we are going to need a basic data structure to hold our tree. Something, like this should suffice.
This simple object will maintain our tree structure and allow us to traverse the tree without losing our parent. In Clojure this looks like,
Using this data structure, we can implement the tail recursive version of Minimax.
As you can see, this method is slightly more verbose. If this is a little overwhelming, here's the pseudocode version,
Unfortunately, during my testing I discovered that the tail recursive version is significantly slower. However, it will run on a 4x4 board with out crashing.