Combinatorial game theory

In combinatorial game theory there has been less emphasis on refining practical search algorithms (such as the alpha–beta pruning heuristic included in most artificial intelligence textbooks), but more emphasis on descriptive theoretical results (such as measures of game complexity or proofs of optimal solution existence without necessarily specifying an algorithm, such as the strategy-stealing argument).

Deriving similar results for games with rich combinatorial structures is difficult.

For instance, in 2007 it was announced that checkers has been weakly solved—optimal play by both sides also leads to a draw—but this result was a computer-assisted proof.

[4] Other real world games are mostly too complicated to allow complete analysis today, although the theory has had some recent successes in analyzing Go endgames.

[6] Tic-tac-toe is still used to teach basic principles of game AI design to computer science students.

In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, in which the requirement that a play available to one player be available to both is relaxed.

Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining.

It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies.

This way of combining games leads to a rich and powerful mathematical structure.

Conway stated in On Numbers and Games that the inspiration for the theory of partisan games was based on his observation of the play in Go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players a choice of sides and then defeat them either way.

In 1953 Alan Turing wrote of the game, "If one can explain quite unambiguously in English, with the aid of mathematical symbols if required, how a calculation is to be done, then it is always possible to programme any digital computer to do that calculation, provided the storage capacity is adequate.

[9] Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess endgame tablebases, which shows the result of perfect play for all end-games with seven pieces or less.

A game, in its simplest terms, is a list of possible "moves" that two players, called left and right, can make.

We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner.

Checkers, for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares.

Switch games can be added to numbers, or multiplied by positive ones, in the expected fashion; for example, 4 ± 1 = {5|3}.

The Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber.