Page 92 - DCAP108_DIGITAL_CIRCUITS_AND_LOGIC_DESIGNS

Unit 5: Combinational Circuits

It restricts itself to games whose position is public to both players, and in which the set of Notes
available moves is also public (perfect information). Combinatorial games include well-known
games like chess, checkers, Go, Arimaa, Hex, and Connect6. They also include one-player
combinatorial puzzles, and even no-player automata, like Conway’s Game of Life.[2] In CGT,
the moves in these games are represented as a game tree.

Game theory in general includes games of chance, games of imperfect knowledge, and games
in which players can move simultaneously, and they tend to represent real-life decision-making
situations. CGT has a different emphasis than “traditional” or “economic” game theory, which
was initially developed to study games with simple combinatorial structure, but with elements
of chance (although it also considers sequential moves, see extensive-form game). Essentially,
CGT contributed new methods for analyzing game trees, for example using surreal numbers,
which are a subclass of all two-player perfect-information games. The type of games studied
by CGT is also of interest in artificial intelligence, particularly for automated planning and
scheduling. In CGT there has been less emphasis on refining practical search algorithms (like
the alpha-beta pruning heuristic, included in most artificial intelligence textbooks today), but
more emphasis on descriptive theoretical results, like measures of game complexity or proofs
of optimal solution existence without necessarily specifying an algorithm (see strategy-stealing
argument, for instance).

An important notion in CGT is that of solved game (which has several flavours), meaning
for example that one can prove that the game of tic-tac-toe results in a draw if both players
play optimally. While this is a trivial result, deriving similar results for games with rich
combinatorial structures is difficult. For instance, in 2007 it was announced that checkers has
been (weakly, but not strongly) solved—optimal play by both sides also leads to a draw—but
this result was a computer-assisted proof. 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). Applying CGT to a position attempts to determine the optimum sequence of
moves for both players until the game ends, and by doing so discover the optimum move in
any position. In practice, this process is tortuously difficult unless the game is very simple.

History
CGT arose in relation to the theory of impartial games, in which any play available to one
player must be available to the other as well. One very important such game is nim, which
can be solved completely. Nim is an impartial game for two players, and subject to the normal
play condition, which means that a player who cannot move loses. In the 1930s, the Sprague-
Grundy theorem showed that all impartial games are equivalent to heaps in nim, thus showing
that major unifications are possible in games considered at a combinatorial level (in which
detailed strategies matter, not just pay-offs).
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. Their results were published in their book Winning Ways
for Your Mathematical Plays in 1982. However, the first book published on the subject was
Conway’s On Numbers and Games, also known as ONAG, which introduced the concept of
surreal numbers and the generalization to games. On Numbers and Games was also a fruit
of the collaboration between Berlekamp, Conway, and Guy.
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. One of the most
Contd...

LOVELY PROFESSIONAL UNIVERSITY 87