Home
> urticator.net
Search
About This Site
> Domains
Glue
Stories
Computers
Driving
Games
Humor
Law
> Math
Numbers
Science
Continued Fractions
> Game Theory (Section)
Group Theory
Probability
Miscellaneous
> Combinatorial Game Theory
Game Theory
The Prisoner's Dilemma
Evolutionarily Stable Strategies
|
|
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.
- Some games are numbers. If a < b, the value of the game {a|b} is the simplest number between a and b.
- 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.
- 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 *.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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)
|