Wythoff's Nim

Wythoff's Nim is a small board game for two players. The idea is rather simple; thus, it is called a "nim". The goal of each player is to be the first to reach the coordinates (0, 0). Once there, the opponent naturally loses because there are no other possible moves. The rules governing the movement of the pieces are as follows: A player may either move a single piece any distance or both pieces the same distance. This Java applet is actually my first shot at AI. You don't get to play against another person but against the computer. This may seem tricky at first (unless, of course, you are given a really easy starting position), but once you master the mathematics involved in this game, you'll realize it's really easy to win most of the time.

Define the sequences an and bn as follows:

  • a0 = 0, b0 = 0
  • For each n > 0,
    • let an = the smallest positive integer number not in {a0, b0, a1, b1, a2, b2, a3, b3,..., an-1, bn-1}, and
    • let bn = an + n.

All ordered pairs (an, bn) are losing positions.

Download executable JAR: WythoffsNim.jar

Wythoff's Nim board layout
Screen shot of Wythoff's Nim.