What is Combinatorial Game Theory?

Combinatorial game theory is a branch of theoretical computer science and mathematics that studies sequential games. The study has been mainly confined to two-player games with a position in which players take turn changing. Traditionally, the combinational game theory has not studied games of chance or games that use incomplete or imperfect information, favoring games that provide complete information in which set of available moves and state of the game is always known by both players. As mathematical techniques advance, however, the types of games that can be analyzed mathematically expands, therefore, the boundaries of the field are constantly changing.
Examples of combinatorial games are Go, Checkers, Chess, and Tic-tac-toe. The first three games are categorized as non-trivial while the last one is categorized as trivia. In combinatorial game theory, the moves in these games are represented as a game tree. Some one-player combinatorial puzzles (such as Sudoku) and no-player automata (such as Conway’s Game of Life) are also categorized as combinatorial games.
In general, game theory includes games of imperfect knowledge, games of chance, and games in which player’s moves simultaneously, tending to represent actual decision-making situations.
An important notion in combinatorial game theory is that of solved game. Tic-tac-toe, for example, is considered a solved game because it can be established that if both players play optimally, a game will result in a draw.
References
https://www.ics.uci.edu/~eppstein/cgt/
http://math.uchicago.edu/~ac/cgt.pdf
https://www.math.kth.se/matstat/gru/sf2972/2015/gametheory.pdf

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s