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.

PCPlus logoRather 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.

Album cover for It's My LifeNow playing:
Talk Talk - It's My Life
(from It's My Life)


Loading similar posts...   Loading links to posts on similar topics...

No Responses

Feel free to add a comment...

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

  •  Emphasize with italics: surround word with underscores _emphasis_
  •  Emphasize strongly: surround word with double-asterisks **strong**
  •  Link: surround text with square brackets, url with parentheses [text](url)
  •  Inline code: surround text with backticks `IEnumerable`
  •  Unordered list: start each line with an asterisk, space * an item
  •  Ordered list: start each line with a digit, period, space 1. an item
  •  Insert code block: start each line with four spaces
  •  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...
Preview of response