Chopsticks Game

One of my favorite games to play in elementary school, I decided that it would be a fun game to solve with programming. What made chopsticks different from connect four and checkers was that there is a relatively small number of positions. As a result, I saw two major shortcuts when programming an algorithm to play the best move.

The first and most obvious is that I can pre-compute everything and store it in a large table. Then at runtime, the program is very simple and efficient, also I can generate everything in python (way more fun).

I didn't realize the second shortcut until I had already programmed the first version of the python code. Like the connect four and checkers code, I was recursively branching over all possible moves from every individual starting position. As a result, I had to cap the depth of the search so my laptop wouldn't catch fire. I wasn't confident that my program was getting the absolute perfect results. After some head-scratching, I realized that since I was branching over a relatively small set, I could just start by computing the heuristic rating function (or whatever base case I wanted), and iterate over the table applying one step of the minimax search at a time. After some testing, I found that I was receiving the same results as the conventional recursive search. However, increasing the depth of the search could now be accomplished in linear time, and I was able to search as deep as I needed to be sure the program was finding every possible forced win.

Even though searching 100+ levels deep is extreme overkill for chopsticks, it was an interesting experiment to discover a way more efficient way of implementing the minimax algorithm. I can be 100% sure that my program is unbeatable on its hardest difficulty.