Parity game
From Wikipedia, the free encyclopedia
In combinatorial game theory, the term parity game describes a game where winning is dependent only on the game position. By contrast chess and go are not parity games, because each player's strategy takes into account what colour they are (black or white in these cases). In a parity game like nim or sprouts a winning position is a winning position for either player.
Such a game is usually lost by the first player who is unable to play. Sometimes a game is won by that player but this makes no odds, the key fact is that it is the total number of moves that are made in the game that will eventually determine who wins and who loses. So in this sense, the players are vying for the "parity" of the game to be in their favour. If it is not in their favour they try to hasten or delay the end of the game until it is.
[edit] Examples
[edit] Nim
Nim is a game often played with matches or similar small objects in which they are divided into a number of heaps. On their turn a player must take some matches from one heap, they may take any number but they must take at least one. The objective is to be the player who cannot play first i.e. to be left with no matches.
[edit] Sprouts
Sprouts is a pencil and paper game developed at Cambridge University in 1967 by John Horton Conway and Michael S. Paterson. It is begun by drawing a number of blobs on the paper. On their turn the player must draw a line starting and finishing at a blob and not intersecting any other line or going through any blob on the way. The line may not cause the start blob or the end blob to have more than three valencies ("connections"), and the player must then draw a new blob in the middle of their line.
Gradually the restriction on valencies means that fewer and fewer lines are available and sooner or later one player will be unable to play and that player loses. Sprouts is notoriously complicated to analyse and gets the attention of many budding combinatorial game theorists.
