> urticator.net

  About This Site
> Domains

> Math

> Game Theory Section
  A Theorem on Finite Abelian Groups

> Combinatorial Game Theory
  Game Theory
  The Prisoner's Dilemma
  Evolutionarily Stable Strategies

> An Outline

An Outline

Recently I started reading about combinatorial game theory again, in connection with go, and I had so much trouble locating the basic facts that I thought I'd make myself an outline for future reference. Then I thought I might as well put it online, and here it is. It's not meant to make sense by itself, it's just a guide, a framework that you can add to as you read.

  1. Some games are numbers. If a < b, the value of the game {a|b} is the simplest number between a and b.
  2. The value of an impartial game like Nim is a nimber *n, with n a nonnegative integer. *0 = { | } is the same as the number 0; *1 = {0|0} is so common that we give it the special name *. Nimbers add using XOR, so knowing binary is useful; in particular, * + * = 0. The value of an arbitrary game can be computed recursively using the “Minimal EXcluded” rule.
  3. The game ↑ = {0|*} is a positive infinitesimal. It generates a whole range of games n·↑; the first few are normally written using special symbols. There are games that behave like fractional multiples of ↑, but they're not constructed the same way as fractional numbers. ↑ and * are tiny things you can add to integers, so n↑ means n + ↑, not n·↑, and similarly for *.
  4. The games +x = {0|{0|-x}} for positive x are infinitesimal with respect to ↑ and to each other, with larger x being more infinitesimal. +x represents a threat by R to gain x moves; it's positive (advantageous to L) because L has the option of removing the threat before it occurs.
  5. A game is positive if L wins no matter who goes first, negative if R wins, zero if whoever goes first loses, and fuzzy if whoever goes first wins. As a result, g >= 0 if L wins when R goes first, and g <= 0 if R wins when L goes first.
  6. If a > b, the game {a|b} is hot. Making a move in a number just uses up one of your moves, but making a move in a hot game gains you some new moves, so both players will be eager to move. Here, whoever moves gains (a-b)/2 new moves above the mean value of (a+b)/2, so we say the game has temperature (a-b)/2. There are many other kinds of hot games.
  7. A hot game is fuzzy with respect to a range of numbers. Let's see how that works for {a|b}. To compare {a|b} to c, we compare {a|b} - c = {a-c|b-c} to zero as discussed in point 5. If b > c, both options are positive, so L always wins; therefore {a|b} > c. Similarly, if c > a, then c > {a|b}. If c = b, L can move to a-c = a-b > 0 and win, but R can move to b-c = 0 and leave L with no options. So, whoever goes first wins, and {a|b} is fuzzy with respect to b; and similarly with respect to a and to all numbers in between.
  8. A hot game isn't always fuzzy with respect to its endpoints. If we compare the game {a|b*} to c = b, then L can win as before, but now R can only move to b*-c = *, which gives L the last move. So, {a|b*} isn't fuzzy with respect to b, it's strictly greater.
  9. As far as numbers are concerned, the game * is only fuzzy with respect to 0, but if we compare it to the games n·↑ we find that it's fuzzy with respect to a range, from -↑ to ↑ (inclusive). I don't think it's useful to think of it as infinitesimally hot, though. On the same scale, the larger nimbers are only fuzzy with respect to 0.
  10. Hot games are generally not very tractable. If you take a sum of hot games or construct a game that has hot games as options, you usually get a new hot game that can't be expressed in any simpler way than what you started with. You can find a reasonable move in a sum of hot games by examining the thermographs of the parts, but to construct the thermographs you have to take into account the entire game tree of each part.

There's a lot more to know, of course, but that's a good starting point.

Finally, I have one more book to add to the four I mentioned in the parent essay, namely, The Dots and Boxes Game.


  See Also

@ February (2010)