Tom's technical introduction to CGT

Table of contents Introduction Set theory Game-forms Games Conclusion

Table of diagrams {|}

Introduction

Some people have commented that it is difficult for the uninitiated to get an understanding of what Combinatorial Game Theory is from the pages about it on Sensei's Library. I, Tom, take this as evidence for an opinion of mine: that it is not possible to get a proper understanding of technical subjects without some familiarity with the technicalities of those subjects.

I am aware that I'm in a minority in holding this opinion. For this reason, and because I find that technical pages can lose their focus from having too many people contributing, I have personalised this page.

It seems a bit against the spirit of wiki to personalise a reference page. If anyone thinks I'm wrong to take this approach, please add a comment to that effect. Also, if you have any other comments or corrections please add them in, but be prepared to be edited! I am particularly interested in comments from those who have been unable to understand something on this page.

I think the first thing to say about CGT is that it is mathematics. In order to understand it, I think it is necessary to understand some of the mathematics it uses. The good news is that for a practical understanding of CGT, the main bit of mathematics you need is a very basic understanding of set theory.

Set theory

A 'set' is the mathematical formalisation of the everyday concept of a 'collection of objects'. A set is determined by the objects it contains in the sense that sets A and B are equal if and only if they contain the same objects.

If the set A contains the objects a,b and c and no others then we write A={a,b,c}. We call a,b and c the 'elements' or 'members' of A. Since a set is determined by the objects it contains,

{a,b,c}={a,c,b} and {a,b,c}={a,a,b,c}.

In order for set theory to be interesting, it is necessary that some objects exist, which can be members of our sets. It turns out that set theory can lift itself by its own bootstraps in this respect. There is a set containing no elements. We can tell that there is only one, because sets are determined by their elements. We call this set the empty set and write it {}.

Once we know the empty set exists, we can produce others. For example {{}}: the set containing only the empty set. Then {{{}}} and {{},{{}}}. Once we get started, there are loads of sets.

Game-forms

A game-form G is a pair of sets: GL and GR of game-forms. We call GL the set of left options of G and GR the set of right options^[4]. If GL={a,b,c} and GR={d,e,f} then we can represent G using the shorthand G={a,b,c|d,e,f}^[1] or even G= a,b,c|d,e,f.

Informally, G is supposed to represent a two player game in which either of the two players 'left' and 'right' (for go read 'black' and 'white') may have the first move. If left has first move, for example, he chooses one of elements gL of GL. After left's move, the game gL remains in which either of the two players may have the first move etc^[2]. Although we have found it convenient to set things up to allow for non-alternating play, in CGT, for a single game, we suppose that play alternates and that the winner is the last player to make a move^[13].

The definition of 'game-form' may seem a bit incestuous. If you skipped the section on set theory, it may be hard to see how it gets off the ground. Since the empty set is a set of game-forms (it has no elements, so all its elements are game-forms), there is a game-form {|} which we call 0^[3].

Once we know the zero game-form exists, we can produce others, for example {0|}, {|0} and {0|0}. We call these game-forms 1, -1 and * respectively. Now we can produce more game forms, some of which we also name^[5]:

• {1|} = 2
• {0|1} = 1/2
• {1|-1}
• {-1|0}=-1/2
• {|-1}=-2
• {0|*}=up
• {1|1}.

You can see that once we get started, there are loads of game-forms.

We introduce the notion of the opposite: -G of a game-form G. This opposite is also a game form. If G={a,b,c|d} then we define -G={-d|-a,-b,-c}. For simplicity, an example rather than the general form has been given, but the general form should be clear^[6].

You might think that we now have to define what we mean by -a,-b etc, but since a,b etc are themselves game forms, we can apply the defintion recursively to these. Continuing in this way, we will eventually have to define the set of opposites of the elements of the empty set. Since there are no such elements, there are no such opposites, so the set of opposites is itself the empty set.

Informally, -G is the game G but with the players: left and right, reversed^[7].

It is easy to show that -(-G) is the same as G. This pattern of defining an operation or a predicate on a game or games in terms of the same operation or predicate on its left or right options^[8] occurs ubiquitously in CGT.

We introduce the notion of the sum G+H of two game-forms G and H. This sum is also a game-form. For simplicity again, only an example will be given, but the general form should be clear. In order to define G+H, it is sufficient to define its set of left options and its set of right options. If G={gl1,gl2|gr1,gr2} and H={hl1,hl2|hr1} then the set of left options of G+H is {gl1+H,gl2+H,G+hl1,G+hl2} and the set of right options is {G+hr1,gr1+H,gr2+H}.

Informally, G+H represents the players playing the games G and H simultaneously. A move in the sum game is a move in one of the two summands. It is not coincidence that this is reminicent of the situation in a go endgame, where there are typically several distinct independent areas on the board, and at each move, a player can play a move in only one of them. It is not necessarily the case that when the game G+H is played, the moves in the game G will be alternatley by left and right. This is why CGT is set up to allow non-alternating play in a game.

It is easy to show that G+H=H+G.

We introduce a relation 'greater than or equal to' (written >=) between two game-forms. We say G>=H if for no left options hL of H, is hL>=G and for no right options gR of G is H>= gR.^[9]

Informally, left's position in G is at least as good as it is in H. More precisely, left wins^[10] if right starts in the game G+(-H) It is easy to show that G>=G, and more challanging to show that if G>=H and H>=K then G>=K.

Games

We are now in a position to define what we mean by a 'game' in the sense of combinatorial game theory. There is more information than we need in the structure of a game-form. We will treat two game-forms G and G' as equivalent, if for all game-forms H, and with either left or right starting, with optimal play, the games G+H and G'+H have the same winner. It turns out that game forms G and G' are equivalent in this sense if and only if both G>=G' and G'>=G.

Formally, a game is a set of all game-forms equivalent to some particular game-form. In practise, game-forms are mostly interesting because they can be used to define games, so we confound the game-forms with the games. Thus we tend not to distinguish between two equivalent game forms and write for example {-2|}=0.

We define opposites, sums and 'greater than or equal to' for games in terms of the equivalent notions for game-forms. For example, if G and H are game forms corresponding to the games G and H then G+H is defined to be the game corresponding to the game form G+H.

It is not obvious 'a priori' that these definitions make any sense. It seems possible that these concepts might depend on which representative game form corresponding to the relevent game is chosen. It happens that one can prove that this concern is unfounded.

It also turns out to be justifiable to express a game in terms of sets of left and right options which are themselves games. In other words, if game-form representatives of those options are chosen and used to define a game form, that game form is equivalent to that which would be defined by other representatives.

After all this work, we can prove lots of powerful things about games, for instance, for all G, H and K.

• G+0=G.

• G+H=H+G.
• G+(H+K)=(G+H)+K.
• G+(-G)=0.
• G>=G.
• G>=H and H>=G implies G=H.
• G>=H and H>=K implies G>=K.
• G>=H implies G+K >= H+K.^[11]

Conclusion

If you have understood all that, congratulations! You deserve a pizza (entitlement exchangeable for a curry, or any other dish with a similar level of unhealthyness)^[12]. I think you now have a good understanding of what combinatorial game theory is about. I hope it helps you to understand the pages on SL explaining its applications to go.

Thanks to the following for helpful comments and corrections

deg,Bill

[1] Bildstein: I'm going to comment as I work through. Here is my first comment: So G is not a set! Even though it is written with '{' and '}'. Cool. I didn't understand that.

Tom: Thanks for reading, and for your comments and questions. Right, G is not a set. At the risk of being confusing, I think I've read John Conway noticing that games are quite like sets though, and could be treated as fundamental objects in the same way sets are.

[2] Bildstein: My understanding: So G (a 'game') is a pair of sets, and each set is a set of 'games'.

Tom: Mine too :) In fact, I'll only comment if I disagree, or to answer questions.

[3] Bildstein: So this 0 that you have defined as {|} means a game where Black's (left's) options are the empty set, as are White's (right's) options. I.e. no one has any options are for what to do next.

[4] Bildstein: But how can we call the empty set a set of options? Here's a hypothetical dialog designed to illustrate my point:

Tom: Please make a choice.
Bildstein: What are my options?
Tom: You don't have any.
Bildstein: Oh.

Tom: In maths, it tends to be less hassle to define things in an inclusive way. For example, in everyday english, someone might say 'that isn't a rectangle, it's a square'. In maths, a square is a rectangle. It means you can say 'any four sided shape with only right angles is a rectangle. In the same way, the empty set is a set. It means I can refer to the set of people who like me, and not have to worry ;)

Bildstein: Perhaps I didn't explain myself very well. It's not that I don't understand how you can have an empty set, it's that I don't understand how you can have an empty set of options. But I guess it makes a little more sense if you think of it as "your only option is to admit defeat", because when you have no options, you have lost.

Bill (Later than next comment): You are using option in "your only option is to admit defeat" in a different sense than the technical meaning. An option, in that technical sense, is a game that is a member of the Left or Right set of another game.

Bill: The set of all 100 feet tall men is the empty set. The set of all current emperors of Rome is the empty set. The set of all two-horned unicorns is the empty set. Etc., etc. The empty set is the set of anything of which there are none.

Bildstein: Let me put it another way: How can you have no options? I can't think of a simpler way to put it than this.

Bill: The members of the right and left sets of a game are its options. You can think of a move in a game as a play from the game to one of its options. { | } has no options.

Jeff: Bildstein, have you played chess? In one game, on your move, you put me in checkmate. What are my options? In our next game against each other, I'm losing again, but I manage to get put in a position called "Stalemate" which means I have no more legal moves and so cannot legally take my turn. Or in tic-tac-toe (knots and crosses), after you score 3-in-a-row, how many legal moves do I have for my next move? Does any of that make sense?

Bildstein: Yes, I understand what you're saying, but I disagree. If you put me in checkmate, the game is over. I am not in a position where I have to choose from an empty set of options.

Bill: Oh, but you are in a position with an empty set of options, in the technical sense. If you are in checkmate you have no legal move. As for choice, that requires at least two options.

Tom: I'll have a go at your other comments when I get more time, but I don't think there is much to discuss with this one. In the game of nim, for instance, the rules are that at each turn the player whose turn it is must remove some matches from one of a few piles of matches. When there are no matches left, whoever's turn it is next, loses. You can re-express this rule by saying that if it is your turn, and you have no options, then you lose. This is the same as saying that if it is left's turn and the set of left options is the empty set, then left loses; and the same for right.

You could argue that re-expressing the rule in this way gives a subtely different game. One in which the same moves are allowed, and where the same plays lead to the same winner. In fact the only difference is that at the end of the first game, the loser loses because there are no matches left, while in the second, he loses because he has no options. If you wanted to be picky, you could argue that CGT only applies directly to the second game. However, in practise people are going to be slightly sloppy and not distinguish between the two games. I think this is a sensible attitude.

By the way, Jeff's examples are less helpful I think, particularly the stalemate example. The subjects of CGT are games where you lose if you can't make a move. Chess gives a draw for stalemate.

Bildstein: I think it's time for some clarification. Formally, I understand what the left and right sets are, and what it means for them to be empty. Informally, I understand when someone says that the members of a set represent the possibilities for the next move. I think the discussion about options is sort of semantic, but I accept that I started it. Informally, I don't think it makes sense to talk about options when there are none, but I want to stress that this is not because I don't understand the nature of the empty set. I think other people will probably want to make me see it their way, and I understand because I feel the same about making them see it my way, but I think the time has come to "agree to disagree". If anyone does want to tell me I don't understand, I ask them first to read this footnote's discussion thoroughly, and also the discussion under footnote 10.

Bill: Not to belabor anything, but I am curious. What do you see as the disagreement? Thanks.

Davos: In my understanding the empty set for left means that left has no legal moves in this game. But this game could be a term in a sum game (a local endgame in a game of go for example). It does not neccessarily mean that left has lost the sum (global) game. It just means that locally left has no legal move (because of the ko rule or the suicide rule in go for example), or it could mean that the local game is over (in that case, right too has no options).

[5] Bildstein: How do we decide what to name them? I think I understand why we call {|} "0", but after that, it seems less intuitive.

Tom: I don't think there is a simple answer to this. Roughly speaking, if a game is a number, it is the number of free moves left gets. I suppose we want 0, 1, 1+1, 1+1+1 etc. to be different, and once 1 is defined, that narrows the choice for 1/2.

Tirian The specific games are associated with the numbers when it is the proper extension of the defined + operator for games once we define 0 = {|} and 1 = {0|}. For instance, if we consider the game A = {0,1|}, we see that the game 1 + 1 - A is a win for the second player, in other words 1 + 1 - A == 0 and therefore it makes sense to call A "two". In a similar way, if we take B = {0|1/2}, we might initially think that B would be 1/3, but then we play B + B - 1/2 and see that it is also a second-player win, so B is 1/4.

Is there a Hackenbush page around? That would be a better illustration of how games and numbers are associated.

[6] Bildstein: My understanding of the general form: For a game form: -G = {-GR|-GL}; For a set: -{option1, option2, ...} = {-option1, -option2, ...}.

Tom: The negation of a set is not normally a meaningful concept. You could try and make your definition, but that might make you worry about what -option1 means, if option1 is a bar of chocolate for example. It doesn't bare thinking about. If I accidentally put it in my cupboard, I might have no bars of chocolate!

Bildstein: How about we say I'm defining the negation of a set of game forms specificly, but providing no negation operation for a sets generally? Is that allowed in mathematics? I'm thinking through this with my part-mathematics-understanding, mostly-programming-understanding brain, and in computer programming, this is a very meaningful thing to want do.

Bill: In ONAG Conway says, "If x = {L|R} we write x^L for the typical member of L, and x^R for the typical member of R. For x itself we then write {x^L|x^R} (p. 4). Then he defines -x this way (p. 5). -x = {-x^R|-x^L}.

That may be a little confusing logically, but he does not negate the sets, only their members.

[7] Bildstein: Hmm. What would it mean to reverse the players? If G is a set of options for left and a different set of options for right, I suppose -G is a game form where, if left gets to choose, he chooses from right's (original) set, and if right get's to choose, he chooses from left's (original) set. But then why do we negate the options as well as swapping the sets? Actually, we were talking about what -G means informally, so while we're on that note, what does -a mean, informally?

Tom:Imagine G as a concrete position on a go board (please ignore the fact that go positions aren't quite games because of ko). To get -G, take another board, and set up the same position as on the first board, except that black stones are replaced by white, and vice versa. Now think about left's options in -G, they are black moves on the second board. Every black move on the second board corresponds to a white move on the first board, and the position after the black move on the second board is the colour reversal (ie negation) of the position after the white move on the first board. Therefore, the left options of -G are the negations of the right options of G. What -a means for an arbitrary thing 'a', is not a meaningful question I don't think. I only talk about -G here, for G a game.

[8] Bildstein: While at the same time swapping GL and GR?

[9] Bildstein: I'm thinking aloud here... This is a "yes or no" relation. G>=H or it isn't. What does it mean to say hL>=G? G is a game form. hL is a game form, which is one of left's options in H. So we're comparing apples with apples, at least. So here is my interpretation: G is greater than all of H's left options, and all of G's right options are greater than H.

Tom: Thanks for asking this one, it raises an important point. I might alter the page. You are quite sensibly equating these statements:

• it is false that hL >= G;
• G>hL.

No, I'm defining the '>' operator as G>hL iff not hL>=G. You didn't use it anywhere in this page; at least locally, it wasn't defined; so I defined it in a convenient way. I can't conceive of any problem with this (prima facie). Is there a real definition?

This would be true in something called a 'totally ordered set', but games only form a 'partially ordered set'. Think of something like the set of subsets of the set of days of the week. We could define >= for such sets, by saying that two such subsets S and T satisfy S>=T if and only if every day that is in T is in S. With this definition, the following are true:

• for all subsets S, S>=S;
• for all subsets S and T, if S>=T and T>=S then S=T;
• for all subsets S, T and U, if S>=T and T>=U then S>=U.

These three are the conditions for a partially ordered set. However it is not true that

• for all subsets S and T, either S>=T or T>=S or both.

It isn't true for games either.

Bill: ONAG definition (p. 4):

"We say x >= y iff (no x^R <= y and x <= no y^L), and x <= y iff y >= x."

That's not very helpful, but Conway goes on to say, "All the definitions are inductive, so that to decide, for instance, whether x >= y we must consider a number of similar questions about the pairs x^R, y and x, y^L, but these problems are all simpler than the given one. . . . Ultimately we are reduced to problems about members of the empty set. (p. 5)"

Example: 1 >= 0.

No right option of 1 <= 0, because 1 has no right option, and 1 <= no left option of 0, because 0 has no left option. QED.

[10] Bildstein: This is the first time you've talked about "winning". What does it mean to "win"? I suppose "left wins" means "left has an option that leads to a win", which is recursive, and that's okay, but what does the final winning position look like? Can you show an example of a game form where left "wins"?

Tom: I do actually say what I mean by winning near the top of the section on game-forms. I admit that this statement is not very prominent, but that's because it is the taking part that is important.

Bildstein: Ahhh. So to win is to make the last move. {|} = 0 means that the only options left to either player is to resign (so you better hope it's not your turn). 2 means that left has two more moves he can make than right, and so will win (locally). And we're talking about a game with the same rules as go except territory counts for nothing, prisoners have no value and all that matters is making the last move. Damn, that makes tedomari worth a lot, doesn't it?

{|}  

[11] Cory: Ok, all of that makes sense, but here I am confused: How do you find the value of a set in combinitorial games. Every introduction I have ever seen has just confused me more. I read that the value is "the simplest number between a and b" if the set is {a|b}. This tells me nothing. I have looked at examples of the sets, examples of the games, and other things, but I still don't understand what this means. One instance comes to mind- the set {2 5/8|5}=3. Is this because the 3 is the lowest prime integer between 2 5/8, and 5, making it the "simplest" number? If so, I don't understand how finding the simplest number gets the correct result every time. Any info would be great, and I'm sorry if this is in the wrong place.

Tirian We inductively define the "birthday" of a number (or game) in the following way. Zero was born on "the first day". For every subsequent ordinal number "n'th", the numbers born on the n'th day are the ones whose options are chosen only from numbers born on previous days. The Simplicity Theorem tells us that between any two numbers there is exactly one that is born earliest.

In a nutshell, here is how you can calculate {a|b} for any numbers. If there is an integer between a and b, then {a|b} is the integer with the smallest absolute value. If not, then {a|b} is the unique number p/(2^m) between them for the smallest possibly value of m.

jfc: caveats with Tirian's statement above:

• if a is equal to b (e.g. {7|7} then the value of the game is *a (e.g. *7)

xela: Shouldn't this be a* (that is, the number a added to STAR)? I've seen the notation *a used to represent "nim-heaps", which is something quite different.

• if a > b then {a|b} is not a number.

so {13 | 22 } = 14, but {22 | 13} is not a number.

Cory: Thanks! That helps a lot. Everything makes bit more sense now.

Merk: Ok, so basically it's the smallest integer between gL and gR that's greater than gL (except for the {k|k} cases)? I guess the concept was simpler than it seemed =p And I just wanted to say, I found this guide very helpful, I've been trying to learn about CGT for a while but never really got it; this cleared up a bunch of things for me.

xela: Close. Two things to watch out for:

"Smallest absolute value": you need to be a little bit careful with negative numbers. For instance, {2 | 5} = 3, and {-5 | -2} = -3 (not -4). Also, {-1000 | 4} = 0 (not -999).

Fractions: {0 | 1} = 1/2, {0 | 1/2} = 1/4, {0 | 0.4378906} also equals 1/4, because 1/4 is the "simplest" fraction (smallest birthday) between those two numbers.

[12] Bildstein: On that note, I think it's lunch time. I'm going to have a few tacos, some potato salad and a mini sticky date pudding.

Tom: Richly deserved I think. Thanks for your comments, it's nice to know that people read this page.

[13] NickGeorge: is GL of gL empty, full of options that will never come to light, or is it irrelevent? Perhaps it matters for sente/gote? I'll read on and delete this if my question is answered.

Bill: gL is one of the options of GL. Once it is chosen, the other options have become irrelevant.

(Note that options are not the same as plays on a go board. Making one play does not always keep you from making another one later.)

NickGeorge: right, but gL has a GL itself. That's what I'm asking about. As I understand it, it's black's options right after black plays.

Bill: OIC. That's gLL, BTW. If G is the only game, then play alternates, White plays (if possible), and Black never plays any of the options of gLL.

However, the point of combinatorial game theory is to deal with combinations of games, where G is not the only one. Then White might play in a different game, and then Black can play in gL. The endgame in go tends to break up into independent local regions, each of which is a separate game. That is what makes CGT pertinent to go.