I mean I definitely am interested in this sort of thing eventually, but at least for the moment we were just trying to nail down what the book was doing in terms of scoring the game, and turning from a game about scoring to a game where it’s the last player to move wins (which is the normal play convention of combinatorial games).
Well one that confused me for instance was that offsetting the score probably won’t be like offsetting the position. As in you’d think it should be like doing 2+{0|-2} ?= {2|0} but that doesn’t quite work. So adding in two black stones = 2 more points to black, didn’t seem to be as simple as just adding on a game where black had two additional moves.
That was one of several things that was confusing me when trying to initially respond to your post about area scoring.
I’ve seen some special case calculations where you just add three copies of a ko to work out its value.
I can try read a bit more into Siegels book, they do have a section on loopy games, and how to calculate their values in some cases.
But yeah, I also want to figure out some more basic calculations in Go, and maybe the cooling (maybe the warming if it’s tractable) too.
Except the sub game is also a game in its own right. And it can be the only game too, in which case it’s illegal, but still useful as a calculation tool, precisely because as you said it can be a sub game of a bigger game. ( I would still argue a tenuki is very much mathematically distinct from a pass though)
Of course,
But the good news is that in a lot of cases the sums do basically simplify if you only care about their values because of dominated and reversible options etc. (Some discussions about equivalence classes of games and so on)
So do I understand this correctly…?
0 is a game where the second to make a move wins
* is a game where the first to make a move wins
↑ is a game where player “left” wins regardless of who plays first
↓ is a game where player “right” wins regardless of who plays first
When are two combinatorial games equivalent? (Or put differently: What is the underlying equivalence relation?)
This was the version l liked/ thought was clear enough but maybe a tad cumbersome
(Maybe now I’m not sure why I commented about a generic reader, probably people will understand it better than I will, but I guess it just depended on what people’s background was that wanted to engage in the thread, read the book etc)
But the short cut is that with two games G and H if the game G-H is a second player win, then G is equivalent to H.
0 is the equivalence class say of games which are second player wins.
Yes, that’s it. Generally positive games G>0 are wins for left no matter who wins first. Negative games G<0 are games where right wins no matter who goes first. G=0 (equivalent but the equals sign is typically used) if it’s a second player win, and a first player win is more complicated. G≹0 so not G>=0 or G<=0.
Probably you can prove it too with reversible options too, one of the discussions for simplifying games to a canoncial form. Though I have a feeling then when you do the reversible options calculation, you end up just proving that {↓|}≥0 and {↓|}≤0 and hence {↓|}=0. So probably one could start with doing that instead either if one wanted.
Apparently that does work XD I think then what I was confused about was that it didn’t fit with the calculation like
because I guess this relative way of calculating score is trying to ignore most stones entirely, but in area scoring they are worth something, exactly as much as an empty space in area scoring.
⚫⚪⚪⚪
⚫➕⚫⚪
⚫⚪⚪⚪
Black ↙ ↘ White
⚫⚪⚪⚪ ⚫⚪⚪⚪
⚫⚫⚫⚪ ⚫⚪⬛⚪
⚫⚪⚪⚪ ⚫⚪⚪⚪
-2 -6
while in this way I’m factoring in each stone being worth a point. So if in the second way we remove two white stones, it would be like adding +2 onto the position in some sense (2 points to black)
⚫⚪⚪➕
⚫➕⚫⚪
⚫⚪⚪➕
Black ↙ ↘ White
⚫⚪⚪➕ ⚫⚪⚪➕
⚫⚫⚫⚪ ⚫⚪⬛⚪
⚫⚪⚪➕ ⚫⚪⚪➕
0 -4
assuming the removed stones aren’t in white’s territory, otherwise the score doesn’t change, and two dame would cancel out anyway.
And in fact 2+{-2|-6} = {0|-4}.
I think that feels to me, like it’s going in the right direction, having the properties you want, if you really wanted to do it with area scoring over territory.
I think this is an example of a more general thing called the Number Translation Theorem, (Thm 3.21 in Siegel).
Suppose x is equal to a number and G is not, then
G+x={GL+x|GR+x}
So I think that as long as you score positions in the right way with area scoring (like I’m mentioning above), then this number translation theorem allows you to add or remove any number of stones from a position, and it will simply just translate the score/game by a fixed amount.
So some of the basics of what’s happening in chapter 4 and thoughts from glancing over it:
The whole random tangent of chilling * and warming * feels very out of place and confusing.
Capturing/saving a single white stone is {2|0}. Adding a black marking taxes away a point and so the game is {2 |0} -1 = { 1 | - 1}. Chilling this by 1 is * ( I think numbers being cold means they can’t be chilled and you just subtract 1 from the left and add 1 to the right). Some comment about the warming ∫* = { 1 | -1 }.
A chilled corridor where black can make one point has value 1/2, which seems to agree with examples in Ch 1
and a comment that the warming of 1/2, ∫1/2 = {1|*}.
I won’t pretend I understand, but power through, hope the book is just written in a bad order, and see which parts make sense.
More named games are randomly introduced - I guess they show up often enough:
0n| G = { 0 || 0n-1 | G if n> 0
{ G if n=0
G | 0n= -{ 0^n | -G } whatever that means?
and some examples that
0n| 1 = 1/2^n
0n| 0 = { (n-1)↑ if n is even
{ (n-1)↑* if n is odd
0n| -G = ⧾G = { 0 | {0|-G } }, also written as {0 || 0 | -G }
It goes through more endgame positions with chilling in section 4.2
Unless people want to go through it, I might hold off calculating it.
It talks about calculating corridors in the chilled game, which with appropriate markings have the fractional parts of the above. 21-n was the formula it uses, with n the empty spaces in the corridor. The warmed values are n-2 + ∫21-n, which I bet, has the same mean as the above values that go players would calculate.
After a few more examples of values then I feel like the rest of the chapter really goes off the walls.
Figure 4.5 on sums of corridors, nuts.
The wall of “rooms”, huge numbers of diagrams where a white stone is peeking into a large black area of various shapes and sizes and then their values underneath.
I don’t really feel like checking any of those, unless we want to look at some examples in an endgame.
Groups invading many corridors - nuts.
Sockets - very random.
4.8 and 4.9 more problems and 4.9 is the 9-Dan stumping problem.
4.10 multiple sockets nuts looking
Yeah ch 4 looks crazy.
Ch 5 has some more random discussions, ko etc.
Then it’s all appendices, rules, more problems etc
One thing I would like to do is make the connection between averages that Go players do when estimating sizes of moves with follow up and CGT means of hot games.
So for example in the following position (easier example with no follow-up)
one might write this as G = {4 | -2 }. Now as a game tree one might called the expected outcome here (4+ -2)/2 = 1 the expected amount of points, or 1 point for black. If you played a game for example with two copies of this position, Black would play and get 4 points, while White would play and get 2. Black gets a net of +2 points with two copies of the position, and so it’s like each one is worth +1 to black.
Actually it turns out that in some sense that is exactly what happens when one calculates the mean of a position in CGT.
It’s defined as
m(G) = limn → ∞ L(nG)/n = limn → ∞ R(nG)/n
with L() and R() being the left and right stops.
So the mean is kind of the limiting average of having n copies of the same game.
It also turns out that genuinely in the above case G+G=2.
Another way the mean is calculated is with cooling.
The temperature t(G) is the least such t so that Gt is infinitesimally close to a number. It turns out there’s always one for short games and that Gt =m(G) for t>t(G).
So in the position with G={4 | -2}, a go player might assign a temperature or value of the move as the difference of the outcomes from the mean that was calculated (4 -1) = 3. Or |-2 -1| =3.
It’s also the case that G3 = { 1 | 1} = 1 + *, which is arbitrarily close to the number 1.
So then the mean m(G) =1 and temperature t(G) is 3 which kind of agrees with maybe a go players calculation.
So at least maybe in some gote looking situations probably what the Go player might call an expected territory and a move value, might correspond to the combinatorial mean value and temperature.
I’m glad you posted this since it makes a distinction between numbers and non-numbers, like with the chilling/cooling concepts. I don’t understand those yet, but this seems like a simpler formula with some similar properties.
I think the reason it works is the number avoidance theorem, which says that the optimal move of G + x is not in x. So all the options for moving in x go away and we only consider GL and GR, which are shorthand for all the different possible moves for Left and Right.
An example of how it doesn’t work when x is a number is 1/2 - 1/4, which is 1/4, not {0 - 1/4 | 1 - 1/4} = 0.
However, I was claiming something a little different, which is that when x is an integer and G is not, then G+x = {GL+x | GR+x}. I think that one’s really obvious: it just means that if Left or Right have extra moves, it’s fine to save them for the end.
Values of Go positions and motivation for chilling (~Section 3.6)
I realized there was a little more to say about Go as a combinatorial game. Assuming Japanese rules, what types of games are possible? We have these values:
Hot games (like my examples)
Integers (finished games with a score that can be counted)
Integers plus * (a dame)
In fact these are the only possible values of Go positions possible assuming nothing weird like ko or seki. That seems like kind of an important fact about Go, but strangely it’s hidden in the proof of Lemma 1.2 in Section 3.6.
The dame are not any more interesting than they are in normal Go, since they are worth less than the typical 1/2-point komi. And notably, you do not get 1/2-point positions on the board or any other non-integer numbers.
So the interesting positions are really just the hot ones. But normal combinatorial game theory doesn’t provide a great way to analyze those games. The fun values for combining games are infinitesimals. So we would like it if Go could be improved to have fewer hot values and more interesting infinitesimal values.
Luckily there’s a way to do this in general, called cooling, and the book uses something slightly different called chilling, defined (again strangely for such an important concept) in the proof of Theorem 1. For Go positions, since there are no non-integer numbers, I think chilling is exactly the same as cooling by 1 point.
You can think of chilled Go as a simple modification of Japanese rules: whoever moves loses 1 point. We also skip filling dame (since nobody would want to be the one to fill) and go straight to scoring at the end (that’s the point of "G is of the form n or n* " in the book’s definition).
So here’s where I’m stuck on chilling: is the strategy in a chilled game necessarily the same as for Japanese rules? Does the book even claim that it is anywhere? It seems that there would often be two terminal positions resulting in scores of, say, -1/2 and 1/2, that both chill to -1/2 because they end on different players’ moves, and you would miss the winning play.
I suppose I should be able to think up an example, but I’ve been sitting on this post for too long. Anyone know what I’m missing?
It seems more like an open ended research question. You’d have to figure out fundamental games, indivisible bits maybe, since after a point in the endgame it breaks up into sums. Or maybe you can figure out families of positions.
Also I don’t know, is it unique to go? Do other games that involve scoring not behave similarly? As in you have a phase where you make points and it’s hot, and then a phase when you count which isn’t.
You get hot games that are algebraically similar in that G+G=1. But I guess with prisoner return, it kills fractional parts of otherwise cold positions? In no pass go without prisoner return, you can imagine territories where playing in the opponents area reduces the benefit they get, but it’s still a net positive for them, which is kind of what happens in the fractional games.
Can it be any different? I guess with area scoring with an odd number of dame it might be, excluding ko. There’s an extra star in the position overall somehow.
Probably starting to answer any of these questions involves needing to understand the whole thing better to begin with…
So onto learning what chilling is, and maybe taking some example endgames to solve?
For Go the proof is right there in the book. It’s kind of hard to read, but I think we just know from experience that cold games don’t appear in go. If they did, it would be to both players’ advantage to pass rather than play, and the 1/2 point would never be played out.
Not to be confused with a half-point game! 1/2 is very specifically {0|1}.
(That should not prevent us from adding a 1/2-point komi at the end of the game!)
So for example consider this position:
and suppose Black is comparing these plays:
or
Of course we know the second way is 1 point better under Japanese rules. But with chilling, since Black pays two points of “tax” to White’s one, they come out even. If that 1 point was needed to win under Japanese rules, you might miss it in chilled Go.
I thought maybe this was because the book expects each subgame to already have irrelevant moves eliminated (it should be in “canonical form”). But Sensei’s just says
…if you impose a tax on territory scoring of 1 point per board play, you get a form of scoring such that, aside from exceptional cases involving seki or ko, winning play by it is winning play by territory scoring.
And I don’t know if there’s some clear statement anywhere in the book comparing the outcome of chilled Go to regular (Japanese) Go.
I’m sure I’m missing something since this seems really basic…
I suppose that any game that allows passing will not produce fractions or interesting infinitesimals.
But if a game (without passing) does have fractions, the winning strategy is to play on the fractions before the integers. So eventually you’ll be done with those, and if you can recognize an integer position easily, that’s when you would stop and “count score”.
For example, in Blue-Red-Green Hackenbush you might stop playing once you are left with only a forest of independent red and green stalks, and then just count the score.
I think to understand if and when chilling works or not, how it works or if it has limitations in simple endgame it might be nice to come back to Martins examples along with maybe other examples from the book or elsewhere.
So the last time I looked at Martin’s examples, I didn’t really understand what was going on with chilling and with representing it with games, but I’d like to make a second stab at it.
I think firstly, figuring out local sente and gote and move values will help a bit and their connections to CGT.
So I think there’s a couple of ways to compute move values, with swings, with averaging of future outcomes, and then when comparing sente and gote there ends up being some factors of two in some cases depending on counting conventions, which is of course confusing.
I think there’s a few ways of trying to check if a move is a local sente:
If answering doesn’t lose anything, so for example if the expected territory in the position gotten by averaging future positions is the same or smaller than the outcome of just treating the move as sente.
Stanislaw mentioned if the sure gain made by playing is the same size or smaller than the averaged followup.
Stanislaw also put it like if twice the sure gain is the same or less than the continuation computed as a swing.
So if White plays it’s 9 points, but if black plays it can be reduced to 6 or 0. If one calculates the expected value of territory with averaging future outcomes, one gets (-9±3)/2=-6 for White.
for (1), the expected is 6 points and treating it as sente guarantees 6 points so that checks out.
for (2), the “sure gain” is 3 points, since black takes away at least 3 points by saving the first stone. The followup averaged is also 3 points, so (2) checks out.
for (3) the “sure gain” is 3 points, and the swing count of the follow up is exactly twice this of 3 points.
So I think you can call connecting the one stone sente for Black.
So if White plays it’s 11 points, but if black plays it can be reduced to 8 or 0. If one calculates the expected value of territory with averaging future outcomes, one gets (-11±4)/2=-7.5 for White.
for (1), the expected is 7.5 points and treating it as sente guarantees 8 points so that checks out.
for (2), the “sure gain” is again 3 points. The followup averaged is also 4 points, so (2) checks out.
for (3) the “sure gain” is 3 points, and the swing count of the follow up is 8 points, which is more than twice it.
So I think you can call connecting the one stone sente for Black. It also makes sense, because the follow up is bigger than example 2, while the first move is the same.
So if White plays it’s 9 points, but if black plays it can be reduced to 4 or 0. If one calculates the expected value of territory with averaging future outcomes, one gets (-9±2)/2=-5.5 for White.
for (1), the expected is 5.5 points and treating it as sente guarantees only 4 points it doesn’t pass check (1).
for (2), the “sure gain” is 5 points for saving two stones. The followup averaged is only 2 points, so (2) doesn’t check out.
for (3) the “sure gain” is 5 points, and the swing count of the follow up is only 4 points, which isn’t more than twice it.
So I think connecting the two stones is locally gote for Black. Maybe it makes sense, because some of the follow up value has kind of been transferred into the intial move, so the follow up seems smaller.
A bit on chilling:
That’s whenever the game itself isn’t already a number. Numbers don’t get chilled it seems. xt=x to t>=0 if x is a number.
Also if Gt is arbitrarily close to a number x at some value t, then Gt’=x for all t’>t.
So for the first game, Game 1 (just to distinguish them), with moves A and B, there’s two hot subgames at A = 0 | -8 and at B = 9 || 4| 0 .
Now in terms of trying to understand these, one can calculate their mean and temperatures. The mean of A is m(A)=-4 and t(A)=4, while for B it’s m(B)=11/2 and t(B)= 7/2.
These would agree with the idea of A and B being gote and calculating as in the previous examples. One can also verify this by chilling games.
At= -t | -8+t and when t~4 that’s when the left and right values become the same: A4= -4 | -8+4 = -4 | -4 = -4+ * which is abitrarily close to the number -4.
So this is the mean value m(A)=-4 that the postion cools to, while the temperature is the value of the cooling to reach this number, which is 4, t(A)=4.
The meaning in this case is that the temperature is like an incentive to move, but also, since it’s also the swing from the mean to either of the outcomes, it is also the move value in a Go sense.
For B maybe the cooling is trickier. B = 9 || 4| 0, then Bt= 9-t || {4|0}t+t.
Now {4|0}t = {4-t | t} when t<2, and then for t=2 it’s {2 | 2} and afterward it’s just the number 2. So it’s still a hot game and not a number when t<2.
We know from the number translation theorem though that
So that Bt= 9-t || {4 -t | t} +t is
Bt= 9-t || {4 | 2t } for t<=2,
and
Bt= 9-t || 2+t for t >=2,
So that when t=3.5 or 7/2 then 9-3.5 = 5.5 = 2+3.5, so that B3.5={11/2 | 11/2 } = 11/2 +*.
So this is the mean value m(B)= 11/2, and t(B)=3.5 is the temperature.
So I think during the chilling process the temperature/move value is dropping until the game becomes a number.
In terms of just playing the biggest moves, Black or White should play A since the move value or temperature is t(A)=4 which is bigger than t(B)=3.5
If we want to chill the game, and play the chilled game, work with chilled values etc, we need to tax away a certain number of points. It makes sense then that this corresponds to the temperature of the game, though I’m curious when the temperature is a half integer should you still tax an integer amount? Maybe less, because chilling too much kills the infinitesmals in the position?
So in the above I tax four points to white’s area at A, and 3 to Black’s at B.
Then in the chilled game whoever moves adds a marking. So rather than white getting 8, they get taxed by 5, and black when saving removes a white marking. A => {3 | -3}.
I think, if it’s territory, the white markings cancel out the white territory, but when it’s not, the white markings are like a negative to white.
I’ve also been reading a little https://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-348.pdf where they have a section on Switch games {x|y} with x>y. They mention that you can unbias it by converting it to the form u+{v|-v} where u=(x+y)/2 and v=(x-y)/2. So then it should be -4 +{4|-4}. I guess adding four markings is taxing away the -4, and then chilling the leftover game by 1 is how you end up at {3|-3} above. If you chill by 4 instead of 1 you’d get *.
For B the game with three markings it’s like 5 || 1 | -1, or with four markings 4 || 0 | -2, which it turns out is just the same as subtracting off the number 1. I guess that’s the point in that taxing is just subtracting off a certain amoint of points to begin with, while chilling is the marking per move. Since it’s one marking per move, it’s just chilling by 1.
You could take the game B=9 || 4 | 0, center it by subtracting 11/2, that is 9 || 4 | 0 = 11/2 + 7/2 || -3/2 | -11/2. Then you could chill down the remainder by 7/2 say, so that it’s 7/2 -t || 2+t when t>2 and again I think it cools to * in that case. It’s really just a repetition of the previous things mentioned.
I think my conclusion of looking at this is that chilling doesn’t really help once the games are hot enough and have a high enough temperature?
So the only difference is the additon of C = {0| -4}, which has mean m(C)=-2 and temperature t(C)=2.
So how does that change things? I guess the temperature is one thing, the fact there’s a sequence which has a followup is another.
Sorting by temperature t(A)=4, t(B)=3.5, t(C)=2. When B is played by white the temperature drops to 2, which makes the followup to B miai with C. So taking the highest temperature for black would lead to a draw.
On the other hand taking C, leaves the game A+B from before, which I guess is a tie with white moving first. So then B? I’m not sure there’s any magic indicator.
One could also look at the means. m(A)+m(B)+m(C)=-4+5.5±2=-1/2, while m(A)+m(B)=1.5. Maybe there’s indication of score and rounding there?
Another thing I wanted to come back to, related to mean and temperature, chilling and thermographs was the idea of left and right stops of a game.
I was starting to read Endgame Mathematics by Robert Jasiek, and he mentions the notion of a score of a position of white or black plays first.
That is B(P) is the score of the position if Black plays first and the players alternate with black maximising and White minimising the score.
W(P) is the same but with White moving first.
Then it finally clicked with me when rereading Siegel which he references that this is also what the left and right stops of a game are. He actually says it explicitly under definition 3.16.
That is if you have a game G, L(G) is the score (number) you end up with if the players play alternately with left moving first until the game hits a number.
Similarly R(G) is with right moving first.
So it’s maybe some kind of minimax play on the game tree. I was looking at some examples with fairly randomly constructed game trees.
I want to explore then what means for Go positions and how that bounds the actual values of the positions.
Ideally I want to understand clearly and somewhat partially maybe the connection between how Go players and books count/estimate and the numbers (stops, mean, temperature) from CGT.
Ideally if I can put it in a short summary, even if it’s only partially complete, I’ll be somewhat happy
I’ve seen that described in Robert’s book as well, classifying moves by the relation of their sente and gote counts and move values.
Is ambiguous accurate in a linguistic sense? As in if the move value is three points and the follow-up is three points, then I’d played at the correct timing it is also kind of sente, in that you can answer it as it’s the next biggest move value.
I get the idea in that you could also pick an equally sized move and treat it as a gote follow-up. As in leave it and play another three point move elsewhere.
I know you’ve been trying to do all kinds of computations using various methods but I haven’t understood any of them since I don’t know how chilling works and I assume that’s required as a starting point.
I needed to add one more rule!! If the score is zero, whoever played last wins. That’s basically the title of the book and will be essential for proving something useful:
Claim 1: If a go position with integer komi can be represented as a combinatorial game G > 0, for the chilled game f(G) we also have f(G) > 0.
Proof of Claim 1
No 1/2-point positions implies G ≥ 1. This means Black has a strategy to always eventually get to a final position that is an integer n ≥ 1, no matter what White does.
What happens if Black applies this strategy in the chilled game?
Suppose Black plays first.
If Black ends up in a final position n after an even number of moves, the “tax” each side paid cancels out and score will still be n ≥ 1.
But if Black ends up at a final position n after an odd number of moves, the score will be n - 1 since Black moved one more time than White. It could be as low as 0. But Black still wins, because in chilled Go you win at zero if you played the last move.
Suppose White plays first.
Black can force the game to end eventually at n or n + 1 and still wins.
This is not true with half-integer komi. If the game ends with Black winning by 1/2 point, Black might lose the chilled game by 1/2 point. However we can still compare two positions with the same komi by subtraction. Since the 1/2s cancel out on the difference of two games, we can make this more general statement:
Claim 2: If we have two combinatorial go positions G > H both with 1/2-integer or integer komi, then f(G) > f(H).
I think something like this is actually mentioned briefly in Section 3.5.4. And I don’t think the converse is true. The bottom line is that you can use chilling to find an optimal move, but it might not be the only optimal move. And for our normal half-point komi you need to play out the sequence and check the actual score to find out who wins.
So does this seem correct? Is it in line with how the book applies chilling? Why don’t they say it explicitly somewhere? (Is it obvious?)
or 
