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 as “ ``{" 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.
Outcome classes
There are four possible “outcome classes” for a game ``G``, depending on who wins under optimal play given who starts:
Outcome class | Definition | Notation | Examples | Comments |
---|---|---|---|---|
``G`` is zero | The second player can win | ``G=0`` | ``0={|}`` | There are neither left nor right options, so whoever is to move first loses. |
``G`` is fuzzy | The first player can win | ``G ∥ 0``^{[3]} | ``ast={0|0}`` | (See STAR.) Whoever starts can only move to the zero game; that leaves the second player no options, so they lose. (Remember that “``{0|0}``” is shorthand for “``{ {|} | {|} }``”. ) |
``G`` is positive | Left can win | ``G>0`` | ``1={0|}`` | If Left moves first, they move to the zero game, and Right loses. If Right starts, they have no options and lose immediately. Hence Left wins ``{0|}`` regardless of who starts. |
``G`` is negative | Right can win | ``G<0`` | ``-1={|0}`` | Is similarly a win for Right regardless of who starts. |
These notations may be combined, yielding the following symbols: | ||||
`` G > 0 or G = 0 `` | ``G ⩾ 0`` ^{[4]} | ``0, 1`` | i.e. Left can win when playing second | |
`` G > 0 or G ∥ 0 `` | ``G ⧐ 0`` ^{[5]} | ``ast, 1`` | i.e. Left can win when playing first | |
`` G < 0 or G = 0 `` | ``G ⩽ 0`` ^{[4]} | ``0, -1`` | i.e. Right can win when playing second | |
`` G < 0 or G ∥ 0 `` | ``G ⧏ 0`` ^{[5]} | ``ast, -1`` | i.e. Right can win when playing first |
The various relationships (``{:<:} {:=:} {:>:} {:∥:} {:⩾:} {:⧐:} {:⩽:} {:⧏:}``) between ``G`` and ``0`` are extended to relations between arbitrary games by definitions like ``G<H <=> G-H < 0``; see also Ordering of Games and Equality of Games.
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.
[3] Note that, in MathJax, “``G" || "H``” should be coded as “``G" || "H``”) to ensure that the symbol is formatted as two bars close together.
- Alternatively, code “`` G ∥ H ``”, yielding “`` G ∥ H ``”, making the code less readable, but the result somewhat better.
- “ ∥ ” is the “parallel to” symbol on the Unicode page “Mathematical Operators”.
- LaTeX codes “ \| \parallel \textbardbl h ” appear not to be supported by AsciiMath/MathJax.
[4] Here “ ⩽ ⩾ ”, yielding “`` ⩽ ⩾ ``”, are the “less-than or slanted equal to” and “greater-than or slanted equal to” symbols, as used in ONAG.
- We do not currently know AsciiMath/MathJax codes for them.
- They may be approximated to in MathJax with “`` <= >= ``”, yielding “`` <= >= ``” with more readable code but less attractive results.
[5] Here “ ⧏ ⧐ ”, yielding “`` ⧏ ⧐ ``”, are the “left triangle beside vertical bar” and “vertical bar beside right triangle” symbols on the Unicode page “Miscellaneous Mathematical Symbols-B”.