Combinatorial Game Theory / Discussion

Use this page for remarks about CGT

Evpsych: Is there anybody who has not read the books who understands the page? (i.e. should I try much harder?) Or is there a more elementary page for those of us who have not read the books?

Thanks.

Bill: These pages are tangential to go. They arose because several SL deshis are interested in the math. If you are interested in CGT, I'd say get Winning Ways, recently republished. It's a good introduction.

For a more practical orientation about how CGT applies to go, read Temperature, Difference Game, Miai, Tedomari, Miai Counting, Chilling, and the pages about Go Infinitesimals.

Evpsych: Thanks, but I'm still interested to know if anybody got an understanding of CGT from SL alone. I have the general idea, but the notation discussions seem to be missing some basic stuff. That could be wrong; SL could be sufficient.

Randall: I haven't read all of the pages on SL yet, but I almost understand what's being said. I suspect there is adequate information if you have a background in game theory -- I knew the concept of minimax and I had heard of CGT before coming across it here. I'm sure you could make it more accessible if you want -- probably by doing no more than asking questions where things don't make sense (or should I say that you can help others make it more accessible).

tywin: I get a splitting headache every time I read one of Bill's pages, but it's gradually starting to come clear. The information currently on SL is sufficient, barely, if you throw enough time at it.

Bill: Sorry about that.

As for CGT proper, I have not focused on that, but on its practical aspects for playing go, and have not dealt much with thermography. So from my writings alone on SL, I don't think you will get much CGT. I do hope that you will get some go knowledge, however.

Matti Siivola: I have found CGT values of points in normal yose and CGT values of eye spaces. However I haven't seen anything about CGT values of connections on this Wiki.

Bill: By the way, there are also CGT values for liberties in semeai. Martin Mueller and Nakamura Teigo have both studied them.

KarlKnechtel: You've got to be kidding me. And you can get non-integer values and infinitesimals and all that icky stuff there, too? I'd like to see that...

Bill: See Capturing Race Exercise 7 for an example.

JanDeWit: Yesterday, I borrowed a copy of Winning Ways, volume 1' and I'll start reading it this weekend. So hopefully soon I will have no more stupid questions, just intelligent ones.

Bill: Enjoy Winning Ways. :-) As for stupid questions, I haven't seen any. :-)

Jan: It sure is an enjoyable book! And it helped my understanding of the subject matter a lot, which helped me improve my program. It can reduce games to canonical forms now (and sometimes even print them nicely), perform arithmetic and compute the stops. So pretty soon it should be able to do Chilling and maybe even draw thermographs.

Bill, am I correct in saying that every normal (non-loopy) game can be represented as a tree, which either is a rational number or contains two non-empty lists (left and right options) of trees? This is not made explicit in 'Winning Ways' but would help enormously in working with thermographs...

And could you check what I've written on Chilling, please?

BillSpight: With finite games you only have to worry about dyadic rationals and infinitesimals. I believe that if there are no Left options or if there are no Right options, the game is an integer. For instance, {^ | } = 1.

On the Chilling page you have written about cooling. The two are (subtly) different. You should move what you have written to a Cooling page. I'll make a few comments. :-)

JanDeWit: OK, what is Chilling then?

That { ^ | } = 1 follows from the Simplicity Rule, right?

Evand: I have a CGT question. Excluding ko, is the correct play for a whole board position always the locally correct play at some temperature? I know there can be multiple locally correct plays at different temperatures; is the globally best play guaranteed to be one of them?

Bill: That's easy. No. For instance, it may be right to make a losing sente, which is never locally correct. As an example, suppose that there are only two plays left, a simple 5 point gote and a more complex position that is a 3 point gote, but you can play it as a 1 point losing sente, where the sente threat is worth 10 points. If you play the losing sente and then the gote, you net 4 points (5 - 1). If you simply take the gote, you net only 2 points (5 - 3).

Evand: Hmm. In that case, I think I'm misunderstanding something else... If we look at that same losing sente with a 5 point tax per move, then playing it as a losing sente gives 1 point; playing it as a 3 point gote gives -2 points. How is this different from saying that the correct local play at temperature 5 is the 1 point losing sente? I think normally one would say that the correct play locally for a 3 point gote at temperature 5 is tenuki, but what is the argument that the losing sente is wrong at temperature 5? Thanks.

Bill: The game tree for a 3 point gote cum 1 point losing sente as described might look like this:

                  A
                 / \
             ___/   -3
            /  /
           3  /
             B
            / \
          19   -1

I hope that's clear. Black has two options, either to play the gote to a position worth 3 points, or to play the losing sente, which will take him back to -1 point. The local count is 0.

Correct local play is for Black to play gote or tenuki. At temperature 5, if Black plays tenuki the local count remains 0; if he plays the losing sente it goes to -1.

Evand: OK, that's clear now. Thanks. I think I was confused by the use of the term losing sente at Do inferior plays have values, which would suggest that a "1 point losing sente" is a sente play that leaves the local count at 1, not -1.

Bill: Thanks. I see that I have not been consistent about the size of a losing sente. Here I meant that the sente loses 1 point, there I meant that it gains 3 points by comparison with letting the opponent play. Measuring it that way, this would be a 2 point losing sente.

Hmmm. Maybe it is better to measure a losing sente by how much it loses. ??? I don't know.

Evand: Maybe calling it a sente play losing 1 point (or just a sente losing 1 point) would be clearer? That is, it's sente, and it loses one point?

And on a related note... should we perhaps have a CGT questions? page?