I.2: Winning Strategies

In Introduction to “Simple Games”, I introduced the concept of a Simple game, and the example of Kayles. If you’re interested in playing Kayles, at least in a circle (instead of in a line), you can do so at cut-the-knot. In general, Kayles can be pretty tricky, but if you’re starting from a full row of pins, it’s comparatively easy. You may want to take some time now to figure out a strategy for that special case, before reading on.

Spoiler for Kayles when played on a complete row:
If the row is empty, you have no moves and you’ve lost. If the row is non-empty, then take the middle pin if the row has odd length, or the middle two pins if the row has even length. This splits the game into two separate identical non-interacting rows of pins. When your opponent moves in one, you mirror their move in the other. When they eliminate one of the equal rows, you’ll take the remaining pins and they’ll lose.

(If, as in the cut-the-knot game, the pins are in a circle, then after the first person takes a pin or two, the circle is just like a row of pins, so for three or more in a circle, the second player can always win.)

There’s a basic theorem of CGT that’s intuitively obvious to some, but bears explicit stating:
In a Simple game, one of the players has a winning strategy.

Now, if you want to be really rigorous about things, you have to lay out even more carefully what a Simple game is, and what a “strategy” is, but for now I’ll just say this: A “strategy” is like a partial lookup table that tells you what moves to make if you’re in a certain position. A “winning strategy” is a strategy that makes you definitely win the game, no matter what moves your opponent does.

I’ll sketch why this theorem is true, intuitively. Suppose that a position is such that the next player to move has no winning strategy. This means that no matter what strategy they employ, they can’t guarantee a win. If they can’t guarantee a win for any strategy, then after any first move, the second player must have some move that doesn’t let the first player guarantee a win. As long as the second player keeps playing these sorts of “blocking” moves, the first player won’t get a chance to win (since the game is non-loopy). This constitutes a winning strategy for the second player.

With this theorem in hand, we can say that every Simple game position is either an “N-position” (where the player to move next has a winning strategy), or a “P-position” (where the player who moved previously, or at least isn’t the one moving next, has a winning strategy).

This still works the same way even when the game is not “short”; it could have infinitely many reachable positions, as long as the game still ends in finite time. (And for similar reasons, if we drop “no ties”, then someone can at least force a tie, etc.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s