I.1: Introduction to “Simple Games”

In What is Combinatorial Game Theory?, combinatorial games were defined. However, it’s beyond impractical to talk about all combinatorial games at once, so we’ll add some more conditions to get to what I’ll call a “Simple game” (this is not a standard term). For clarity, a combinatorial game has a fixed starting “position”, and after each move it’s in another position (possibly the same as some previous position). A Simple game:

  1. is two-player.
  2. is “normal play”, meaning when someone has no legal moves, they lose. (If a player with no legal moves were to win instead, it would be “misère play”.)
  3. has no ties; the only way for the game to end is for someone to lose/win.
  4. is “non-loopy”, meaning the game definitely ends; it can’t go on forever.
  5. is “impartial”, meaning that for a given position all players would have the same available moves. (The opposite of “impartial” is “partizan”.)

Occasionally, we may also ask that the game is “short”, so that there are only finitely many positions reachable. With all of these conditions, we’ve seriously restricted our concept of game, so that almost every game you’ve heard of (unless you’ve heard of Nim or looked into CGT before) is not a simple game. One of the easiest simple games to explain is “Kayles”. The starting position has a bunch of bowling pins in fixed spots in a row (perhaps with gaps). The players take turns throwing balls at the pins. The players are perfect bowlers who can hit any one pin they want, or any pair of pins in adjacent spots. If there are no pins to hit on your turn, you have no moves, and you lose.

An example game (I’ll use “i” to denote a spot with a pin and “.” to denote a spot without one): There are three pins in a row (iii), and I go first. If I hit a pair of pins (e.g. to make it i..), my opponent would hit the remaining pin and I lose. If I hit one of the outer pins (e.g. to make it ii.), my opponent would probably hit both remaining pins and I’d lose. Therefore, I hit the middle pin (leaving i.i). Since the remaining two pins aren’t adjacent, my opponent will only hit one and then I’ll hit the other and win.

It’s a good exercise to try and figure out what perfect play is like when the game starts with n pins in a row (so no gaps). It’s basically impossible to figure out what perfect play is like in all setups (e.g. ii.i.iiii.iii.ii) without CGT, but with a theorem we’ll get to, it’s totally doable!

Even though common games are generally not Simple games, some common games are almost Simple games. For instance, Tic-Tac-Toe is traditionally partizan (there’s a player who gets to place X’s and a player who gets to place O’s), isn’t normal play (the ending condition has to do with getting three in a row), and has ties (in case no one gets a three in a row). All of this can be fixed:

If you add a toggle switch next to the board, with one side labeled “write an O next” and the other labeled “write an X next” and ask that people flip the switch after each move (and have it start in the O position at the beginning of the game), then the game becomes impartial. If you say that “if there’s a three-in-a-row of X’s and the switch is in the ‘O’ position (or vice versa), then no move is legal” and “ties go to first player” (so if the board is full and it’s your turn then you lose, as in normal play), then there are no more ties and the game is normal play.

In this way, Tic-Tac-Toe can be turned into a Simple game. Similar tricks can be done for many other common games like Chess and Go (you may have to impose special conditions so the game doesn’t go on forever) or misère games, but this sort of conversion doesn’t usually help you analyze these other games. In short, the theory of Simple games is different than the theory of other games.

In upcoming posts, we’ll talk about “winning strategies”, and the game of Nim, the most famous Simple game.

Advertisements

One thought on “I.1: Introduction to “Simple Games”

  1. Pingback: II.1: Introduction to Partizan “Conway Games” | Combinatorial Games

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