CGT path

Table of contents Theory Application Notes Chat

CGT is an acronym for Combinatorial Game Theory, which is a mathematical theory of abstract games, i.e. two-player, alternate turn-taking games with perfect information, no element of chance and no infinite sequences of turns. CGT often analyses such games by reducing them to sums of simpler games, as happens in the endgame of go. A game of go, however, even when it separates into “independent” positions, is often not a sum of such games, because the positions may include kos and thus have the potential for an infinite sequence of moves.^[1]

This page supplies a path through many of the articles about CGT on this site.

Theory

• Introductions
  • Combinatorial Game Theory — An introduction to the theory and notation
  • Game - Theory Interface — A sketch of an introduction to CGT for go players
  • Tom's Technical Introduction to CGT — An introduction to CGT by Tom taking the standpoint that it is technical and should be presented as such
  • Tree Representation — Introduction to a graphical representation of games as trees of possible moves
• Basic elements of the theory
  • Surreal Numbers — An introduction to a some special abstract games which behave like the members of many mathematical number systems such as integers, rationals reals, transfinite ordinals, infinitesimal numbers
  • Negative of a Game — An abstract game with the roles of the players reversed
  • Disjunctive Sums — How two games are combined to form a third, analogous to independent positions on a go board
  • Ordering of Games — How games may be partially ordered in terms of how favourable they are to one side or the other, depending on the outcome class of their difference game.
    • Equality of games — A special case of the ordering, when two games are equally favourable (or unfavourable) to a given player (and hence also to the other)
  • Canonical form — An abstract game may be reduced to a canonical form by removing dominated options and eliding reversible options; short games in canonical form are only equal when they have the same structure
    • Dominated Option — An option of a game which may be eliminated because another option for the same player is at least as favourable to them
    • Reversible — A play or option is reversible if the opponents best answer leaves the position no better for the first player than it was originally; such a move should normally only be played if one also plays the follow-up, or because of a situation beyond the scope of basic CGT, such as a ko or to get another byo-yomi period
• More advanced topics
  • Temperature (CGT) — The technical definition in CGT of the temperature of a game, a measure of the urgency of playing in it
    • Temperature — The usage of “temperature” in go in general
    • Environment — A way of studying temperature in go by offering players points for forgoing moves
      • Environmental go — A go variant where a player must choose between a board play and taking the top card of a pile of cards giving their holder points
    • Thermography — A way of drawing a diagram to indicate many important features of a game when cooled by various temperatures
      • Mast — The vertical line at the top part of thermograph, where the game has been cooled to a number
      • Colored Mast — The mast may be colored to show ambient temperatures at which either player will make a loss by playing in the game, indicating sente, gote and ambiguous positions
    • Cooling — An operation on an abstract game to reduce its temperature by charging for the privilege of playing in it
  • Orthodox — (In the CGT sense:) Informally, locally optimal play at a given ambient temperature; tedomari is an example when orthodox play is incorrect
  • Atomic weight — (a.k.a. “uppitiness”) — The number of ↑s best approximating an infinitesimal game, giving a measure of who can win it; similar to the external liberty count in a semeai
• Further reading
  • CGT references — A collection of papers and books on CGT
  • Winning Ways — (alias WW) — A ground-breaking book by Berlekamp, Conway & Guy introducing CGT and its application to many games
• Related topics
  • Game theory — An overview of game theory in the broader sense, including probabilistic elements, imperfect information and simultaneous turn-taking.
  • Minimax — A placeholder, probably intended to describe an algorithm? to find the best move allowing for all one’s opponent’s possible reactions

Application

• Techniques applicable to go
  • Tedomari — Getting the last play in some stage of the game, in particular before a drop in temperature
  • Difference game — The difference between the resulting positions can be used to determine if one move is always better than another
  • Chilling — A way of making a game like go easier to analyse with CGT, approximately equivalent to cooling by 1
  • Chilled go — Charging one point for each move, used in Mathematical Go as an analytical tool
• Ambiguous Position, /Discussion — A position that is not simply sente or gote, either because it has options of both types or because it has an ambiguous option (a maximal option that does not change the temperature)
• Particular positions as described by CGT
  • Zero in CGT terms — About go positions that are equal to the zero game, or that yield the same score regardless of who plays first
  • Corridor — A line of yet to be played out points leading into the territory of one side; the value in chilled go is a number or infinitesimal
  • Room — An area of yet to be played out points more complex than a corridor
  • Numbers — Positions which chill to (surreal) numbers, often referred to simply as “numbers”
    • Another number — A position that chills to ``-1/2``
      
    • Yet another number — A position that chills to ``+1/4``
      
    • One more number — A position that chills to ``+1{:3/8:}``
      
  • Infinitesimals are games which may be favourable to one side although they are smaller than all non-zero integers or fractions
    • Introduction to infinitesimals
    • Go infinitesimals — How they arise in go
    • Infinitesimals discussion — Some discussion about an exercise in evaluating a position
    • Playing infinitesimals — The theory of the correct priority of plays in infinitesimals
    • Infinitesimals Optimal Play — Practical rules for the correct priority of plays when only infinitesimals are left and these are ``ast``, ``↑``, ``↓``, Tinies and Minies.
    • More infinitesimals — Some infinitesimals in chilled go where at least one player has more than one live option
  • Endgame Problem 40 / Discussion — On using difference games to determine the priority of plays in the endgame
  • Clamp connection comparison — Using a difference game to compare ways of responding to a clamp; since the first player wins, both are sometimes better
• The theory as it applies to ko fights
  • Komaster — A player who can win a given ko fight without ignoring a ko threat
  • Koloser — The opponent of a komaster (if I have understood right, PJT)
  • Komonster — A komaster who can use additional threats for a greater gain
  • Hyperactive position — A position whose count depends on who is komaster
• Applying CGT techniques to other parts of the game than gaining points …
  • CGT values of connections — … connecting chains
  • CGT values of eyes — … making eyes
  • CGT values in semeai — … race to capture
• CGT applied to other games
  • Combinatorial Game Theory and Contract Bridge
  • Numbers in Gone — (a.k.a. “anti-atari go”, “NoGo” or “No-capture Go”)
  • Infinitesimals in Gone

Notes

[1] Although the rules forbid repetitions, this applies at the level of the whole game, and cannot be formulated exclusively in terms of the sequence of moves in one part of the board.

Chat

• CGT / discussion — Questions (from various people) and Answers (mainly from Bill)