Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games

Combinatorial game theory refers primarily to the study of finite two-player turn-based perfect information games. The goal of the players is different in different games.

A widely studied example is when a player loses if she has no available move on her turn. Games of this type form a partially ordered abelian group under disjunctive sum, and individual combinatorial games, such as Nim, Amazons, Domineering, and Hackenbush, specify subgroups whose properties can be studied. Another popular example is when the players put marks and the goal is to collect a winning set (first). Such games include Tic-Tac-Toe, 5-in-a-row, Hex. There are a number of other variations, including infinite games, so-called misère play where a player wins if she has no available move, and games with other ending conditions.

One type of question of interest about games involves studying particular classes of positions for a specified game. Other questions of interest include computability results, like showing that such calculations are PSPACE-complete or NP-complete for some class of positions.

history | excerpt history