Combinatorial games 
Combinatorial games by definition are 2-player games with alternating turns, no hidden information, and no chance, e.g. Go and GIPF.
Combinatorial games are often called "abstract games", which is an ambigouous term since "abstract" is also often used to mean "themeless". Theme or lack of theme is irrelevant to whether a game is combinatorial. Played 2-player, games like Stephensons Rocket and König von Siam are combinatorial games, but many gamers would not call them abstract, due to their historical themes.
The term comes from mathematics (famously developed by Elwyn R. Berlekamp, John Conway, and Richard K. Guy in their book Winning Ways for Your Mathematical Plays) which analyzes such games. Traditionally the first player who cannot make a move is the loser in combinatorial games, but the theory is generalizable to include other types of end condition such as score or capture of a specific piece.
Combinatorial Game Theory has been used to analyze and even improve AI computer players of some classic games.
Traditionally the 2 players are called Left and Right. (Basically the same as saying Black and White in chess, for example.)
In the strictest definition, a combinatorial game is guaranteed to terminate with one player winning (no ties/draws possible). Under that assumption, one of the basic theorems (which is not hard to prove) of CGT is that every game (i.e. game position) falls into one of these 4 classes:
N = fuzzy : the Next player to play (whether they are Left or Right) can force a win
P = zero : the Previous player who played (or 2nd to play) can force a win
L = positive : Left can force a win, regardless of who moves first
R = negative : Right can force a win, regardless of who moves first
It is easy to think of trivial examples of games for any of these categories. E.g. consider a trivial game where both players have some chips. On their turn a player must give up 1 or more of their chips. If a player have no chips to give up, then they lose. Obviously the optimal strategy is to give up only 1 chip each turn. What type of game is this? If both players start with an equal number of chips, then whoever moves next will lose eventually, running out of chips just before the opponent. If Left has more chips, then Left can force a win, regardless of who moves next. If Right has more chips, then Right can force a win.
See:
|
