Catalogue of Artificial Intelligence Techniques


Jump to: Top | Entry | References | Comments

View Maths as: Images | MathML

Combinatorial game theory

Aliases: CGT

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) .



Add Comment

No comments.