Catalogue of Artificial Intelligence Techniques
Combinatorial game theory
Keywords: cgt, combinatorial, game, theory
Categories: Game Theory
Author(s): Brian MacLellan
Combinatorial game theory can be applied to two player games where each player takes turns to change the state of the game and try to achieve a defined winning condition, such as chess, Go, Nim and connect four. Games of chance, such as poker or black jack, are not studied under CGT(since no randomness or hidden information are permitted in CGT). A game is known to be called impartial if two players (Left and Right) are treated identically, that is each player has the same moves available from the same game position(e.g. Nim); otherwise the game is called partisan (e.g. Chess). Most combinatorial games are partisan. 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, however, unless the game is simple the process is extremely difficult. The theory most widely used for combinatorial games is the following: the game can be described by a rooted tree, each node having zero or more left branches correspond to options for the player Left to move and zero or more right branches corresponding to the options for player Right to move; leaves corresponding to finished games, the winner being determined by either the last player unable to move winning or losing (depending on what the rules of the game are). There are many different ways to analyse the trees produced using this method such as the Sprague-Grundy theory(states that every finite impartial game is equivalent to an instance of the game Nim, characterised by a single natural number n) and Conway's Surreal Numbers(a vast generalization of the real and ordinal number systems) .
- E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for your Mathematical Plays.
- Richard Nowakowski, ed., Games of No Chance.
- Richard Nowakowski, ed., More Games of No Chance.