PCPlus 291: Behind the minimax theorem

For February 2010’s issue, it was time for a more heavy-duty algorithm together with what my editor called a fun element. So, enter minimax and two-player zero-sum games.

Rather than use noughts and crosses (or tic-tac-toe), the standard game to illustrate minimax, I went for the little known game of Nim. In Nim, the players face n piles of stones with m stones in each pile. Each player takes it in turn to play by removing from a single pile anything from one stone to the entire pile. The loser is the one who is forced to remove the final stone from the final pile, leaving all n piles empty. I would play a few rounds with yourself to get the feel for the game and the tactics.

I illustrated with 3 piles of 5 stones and showed how, even with this small configuration, you could build a fairly large game tree. I then personalized it a little by calling the players Max and Minnie, and that we should view the tree (and game) from Max’ viewpoint: he would always play to maximize his winnings. Minnie, in the other hand, would always play rationally to maximize hers, and by implication, minimize Max’. From that it’s but a small step to start calculate the winnings for Max at each node in the tree. I built the full game tree for a single pile of 5 stones (with the additional rule that you can only remove 1, 2, or 3 stones each play) and showed with minimax that the second player would always win.

I also talked about tree pruning, depth restriction and the like. In the end, quite a fun little article.

This article first appeared in issue 291, February 2010.

You can download the PDF here.

  Loading links to posts on similar topics...