Introduction to Combinatorial Game Theory

Table of contents Introduction to Combinatorial Game Theory Goal of this page Defining some terms Notation Defining Zero in CGT

Introduction to Combinatorial Game Theory

Goal of this page

The primary goal for this page is to define the basics of Combinatorial game Theory (CGT) that are needed to understand CGT as applied to Weiqi (Go).

• Correctly defining CGT terms is a high priority.

• Correctly portraying the history of CGT is a very low priority.

Defining some terms

perfect information : games in which the state of the entire game is known to all players. Go and chess are examples of perfect information games. The card game bridge is example of a game that is not perfect information because some cards are hidden from the players.

two person: There are two players competing.

zero sum: A game ends with one player winning and one player losing.

Most games that have been analyzed by CGT have been perfect information, two person, zero sum games.

game: while many of us use the term game to refer to things like "chess", "Go" or "bridge", CGT also uses the term game to refer to positions.

Additional properties of CGT:

• Players alternate making moves in a game.
• Playing a move is an obligation. The first player who can not make a legal move when it is their turn loses.

Notation

Given a game (e.g. a board position in Go) there are a number of legal moves left could make if it was left's turn and there are a number of legal moves right could make if it was right's turn. This can be represented

     A =   { B, C, D | E, F, G }

where A is the current game, B, C and D are the new games (i.e. positions) that left can move to while E, F and G are the new positions right can move to.

The simplest game possible is

  {|}

This game in which neither left nor right have a legal move.

  { {|} | }

is the game in which left can move to the game {|} while right has no legal move.

Similarly

  { | {|} }

is the game in which right can move to the game {|} while left has no legal move.

Merk: Do { {|} | } and { | {|} } simplify to {|}? Because { | {|} } seems like "Left has no options, but Right has the option of choosing the set of no options."

Bill: { {|} | } = 1, and { | {|}} = -1. In the first case Left has a move, but Right does not, and the opposite is true in the second case.

Merk: Ah, I think I see. So, in the first case, Left could play a move that would make the current game {|}? And since Right has no response, he loses that game?

Bill: Correct! :-)

Merk: Yay, thanks for the help! =D

Defining Zero in CGT

CGT defines 0 (the zero game) as a second player win. The simplest (canonical) form of 0 is

       {|}

that is, the game in which neither player has a legal move. Whoever's turn it is to move in the zero game loses and their opponent wins.

jfc red blue hackenbush is really the ideal game for illustrating these fundamental games because it is easy to construct these assymetrical games in red blue hackenbush. <Sigh> if only SL had the ability to notate RB hackenbush.

ilanpi: Just use black white hackenbush played on a go board and "hack" away!

jfc : excellent idea!

ilanpi: Thanks! How about calling this version of the game "Hackengo".

Authors: jfc.