Chopsticks Game

A childhood favorite, I knew I would be able to solve it. This project is noteworthy because I discovered a new way to implement the minimax algorithm on a game with a small enough number of states. I wasn't satisfied by how long the recursive approach took to run on my laptop. I proved that If I could save all of the possible game states in a lookup table, I could start by calculating all of the leaf nodes of the tree first, and then work backwards from there, one layer of depth at a time. This optimized the algorithm from running in exponential time to linear time (with respect to depth). I was able to prove that all possible winning tactics were found. Then, I implemented a simple heuristic which counted all possible wins stemming from a certain position, weighted by a exponential decay factor. This also utilized the same iterative approach that the minimax search was based upon.

The search algorithm was implemented in Python, and the web application merely looks up the best move from my lookup table.