Combinatorial Games - Definition
A combinatorial game is a two player game that satisfies the following conditions:
- The game is deterministic: there is no randomization mechanism such as flipping a coin or rolling a die.
- There is perfect information in the game: each player knows all the information about the state of the game, and nothing is hidden.
Solving these games is analyzed in combinatorial games - winning positions.
Contents
Well-known Examples
Well-known examples of combinatorial games are Tic-tac-toe, checkers, chess, Go, Dots and Boxes, and Nim.
A finite combinatorial game will always end; there is no sequence of moves that will lead to an infinite game. This means chess, in its basic form, is not finite, while Tic-tac-toe is finite.
Dan and Sam play a game on a convex polygon of 100001 sides. Each one draws a diagonal on the polygon in his turn.
When someone draws a diagonal, it cannot have common points (except the vertices of the polygon) with other diagonals already drawn.
The game finishes when someone can't draw a diagonal on the polygon following the rules; that person is the loser. If Dan begins, who will win? This means, who has a winning strategy?
Clarification: The diagonals of a polygon are straight lines that join non-adjacent vertices.
This is the fourteenth problem of the set Winning Strategies.
A combinatorial game with normal play convention is a game where the first player unable to make a move loses. (If both players can keep making moves, it's considered a draw; naturally this can only happen if the game is not finite.) Chess, in some sense, is normal play, but many games such as Tic-tac-toe, Go, or Dots and Boxes, aren't normal.
Dan and Sam play a game on a \(5\times3\) board. Dan places a White Knight on a corner and Sam places a Black Knight on the nearest corner. Each one moves his Knight in his turn to squares that have not been already visited by any of the Knights at any moment of the match.
For example, Dan moves, then Sam, and Dan wants to go to Black Knight's initial square, but he can't, because this square has been occupied earlier.
When someone can't move, he loses. If Dan begins, who will win, assuming both players play optimally?
This is the seventeenth problem of the set Winning Strategies.
A combinatorial game with misère play convention is a game that reverses outcomes; if a player would have lost in a normal game, they won instead. Perhaps the most common misère game is misère Nim (in normal Nim, the player that cannot move loses; in misère Nim, the player that cannot move wins).
Dan and Sam play a game in which the first to start says the number 1, the next says 2, and the one who's next must say an integer number strictly between, (not including the endpoints), the number previously said and its square. Also, the said number can't be greater than the goal number, that is, 10000.
For example, Dan begins saying 1, then Sam says 2, and then Dan can say whichever number he wants between 2 and 4; as the only integer between 2 and 4 is 3, he must say \(3\). Then, Sam can choose any number between 3 and 9; that is, he can say either 4, 5, 6, 7 or 8.
The game finishes when someone reaches 10000 (who is the loser). If Dan begins, who will win? This means, who has a winning strategy?
This is the eighth problem of the set Winning Strategies.
Impartial Games
Impartial games are combinatorial games where there is no difference between the two players (the game is impartial), except that one starts the game. Formally, for a game to be impartial, it must satisfy two additional conditions.
1) The moves available depend only on the position of the game and not on which player’s turn it is.
2) The value of any particular move is the same for both players.
Condition 1 excludes many common games such as Tic-tac-toe, checkers, chess, and Go as impartial games. In all of them, one player can only move/place one kind of pieces (white) while the other can only move/place another kind (black).
The most well-known impartial game is the game of Nim. The game of Nim is played by 2 players and uses \(k\) piles of stones, with sizes \((a_1, a_2, \ldots, a_k)\). During a turn, a player is allowed to remove any number of stones from a single pile. The game ends when there are no stones left and the person whose turn it is to move will lose the game.
Dan and Sam play a game on a \(8\times8\) grid, on which each one chooses and puts, in his turn, a single piece like these:
The pieces must not overlap and can't be partially outside of the grid.
The game finishes when someone can't put a piece on the board in his turn following the rules (who is the loser). If Dan begins, who will win? This means, who has a winning strategy?