Abstract Game
In combinatorial game theory, the word game has a specific technical meaning; in a broader context we use the term abstract game. The definition seems rather abstract, but sometimes it is useful to be able to discuss the general properties of "games" without referring to any specific real-life game.
Such games may be combined to a sum game, which yields insights when the endgame in go splits into independent regions, though a ko makes its region ‘loopy’, requiring an extension of the theory to make it useful.
A game tree is a graphical representation of an abstract game.
Table of contents |
Definition.
A game is a pair of sets (L, R) with the two properties:
- the elements of L and R are themselves games;
- there is no infinite sequence G_i=(L_i, R_i) where each G_(i+1) is an element of L_i or R_i.
By convention, a game (L, R) is written { elements of L | elements of R} (see tree representation).
At first glance this looks like a circular definition: to make a game, you need to start with two sets of games! However, it is possible for the sets L and R to be empty, so we can start with the zero game, written {|} and build things up from there.
For example, if we use the symbol "0" as an abbreviation for "{|}", we can immediately make three new games: {0|}, {|0} and {0|0}. (See birthday.)
The choice of the symbol "0" is not just arbitrary: there is in fact a large class of games which can be treated as a number system, namely John Conway’s system of surreal numbers, games equivalent^{[1]} to ones in which every move in every reachable position is more advantageous^{[2]} than letting the opponent move. Surprisingly, such numbers model many number systems important to mathematicians (see surreal numbers).
Playing a game
Most real games have players taking turns, and a winner and a loser at the end. For combinatorial games as defined above, we assume that there are two players, called Left and Right. (When CGT is applied to go, Black plays Left.) The set L is called the set of left options, and R is right options. If Left moves first, then Left chooses one of the left options: this is a new game, and now it is Right's turn to play. Eventually one player or other will run out of moves (this is the motivation for part 2 of the definition): the first player unable to move loses the game.
There are four possible "outcome classes" for games:
In the zero game 0={|} there are no left options and no right options, so whoever moves first will lose.
In the game {0|0} (see STAR), whoever moves first has only one option: the zero game. Then the second player has no options, and therefore loses. (Remember that {0|0} is just a short way of writing { {|} | {|} }. )
In the game {0|}, if Left moves first then Left makes one move, resulting in the zero game, and Right loses. If Right moves first, Right has no options and loses immediately. Therefore {0|} is a win for Left regardless of who starts.
Similarly, {|0} is a win for Right regardless of who starts.
For more complex games, the task of deciding which outcome class will result from optimal play can be very difficult!
Application to go
To be added: conversion to last move lose game, etc, loopy games
Representation
One may draw a tree representing the possible moves from each position.
When used for go, it is useful to annotate the nodes of the tree with the values of the moves and/or the resulting positions.
For more examples, see the article Count. (As of 2018-09-12, perhaps worth moving some of those here or to tree representation.)
Notes
[1] Here ‘equivalent’ means yielding the same class of outcome in any sum game.
[2] Here ‘more advantageous’ means in effect that this game can be added to some other game to yield one in which making the move wins while letting the opponent move loses.