Book Club: Mathematical Go, Chilling Gets the last point by Elwyn Berlekamp and David Wolfe

[shinuito]

@Feijoa

What if we use Chinese rules? Since stones count, we have to decide which ones to consider, and I think it makes the most sense to measure the score relative to the starting position, assuming all stones were alive. Then Black just gains one additional point by playing first, while White converts a black stone to white territory and gains one stone, getting to -3. So the game becomes { 1 | -3 }, apparently an even hotter game.

I tried writing down a few reponses and ideas, none of which really made sense in the end. Probably to get to the bottom of it, it makes sense to just take final positions of a game, where one knows what the winner should be, and then try to extrapolate from there.

Let’s say this was a game, where both players have played 20 moves each (which they have), only black played in white’s area a lot, before playing twice in their own, and white removed all the prisoners. There have been no passes. White has 10 more prisoners, and no komi.

Territory scoring would say 19 points to white, and 12 to black. If they play it out with stone scoring and prisoner return, then white does win by 7.

We expect the score with area scoring to be the same, since both played the same number of stones, 28 to 21. I think then to make it combinatorial, you need to some how turn that score of 1 point per stone, and 1 point per area, into moves (ignoring prisoners).

Maybe when it comes to filling in territory you can think of it like each player takes turns placing a neutral (red/grey) stone into each point of their territory, and when they’ve finished doing that, they take turns removing their stones from the board.

The reason is to come up with rules of a game, which is effectively just the counting process.

@Feijoa

       ⚫⚪⚪⚪
       ⚫➕⚫⚪
       ⚫⚪⚪⚪
  Black ↙      ↘ White
⚫⚪⚪⚪    ⚫⚪⚪⚪
⚫⚫⚫⚪    ⚫⚪⬛⚪
⚫⚪⚪⚪    ⚫⚪⚪⚪
     -2           -6

That way the numbers kind of make sense, if we modify them to the above.

On the left, Black and white would take turns removing stones, and white would have two extra left over.

On the right, White would first place a netural coloured stone (red or grey or something) into the open area, while black removes a stone. Then both continue to remove stones and White has 6 extra left.

At least the result of the game then is the actual area score?

[martin3141]

@Feijoa

To represent Go as a combinatorial game, we consider all the reasonable moves (ignoring for simplicity unnecessarily filling in your own eyes or playing dead stones in the opponent’s territory). We also assume (for now at least) that there is no ko, since otherwise the games would not combine properly, and there might be cycles. Then we get a tree like the one above.

I think of it as a directed graph, with nodes being the possible game states, and edges being all possible game state transitions (moves). Some nodes are terminal, no outgoing edges, i.e. the game ends. Those nodes carry a result of the game.
I think thats all the assumptions you need.

[shinuito]

@martin3141

I think thats all the assumptions you need.

I suppose that is technically all you need, but with the terminal positions (for one or both players), you do have to define why the value is what it is. I suppose it can be arbitrary, but not when you’re trying to match it to Go specifically.

To make it look like a combinatorial game, more so than just the game tree means interpreting the final scores, where neither side no longer wishes to play. Equally, there’s no passing in combinatorial games so you have to deal with that.

So that’s what’s prompting the whole discussion of Japanese vs Chinese rules, their mathematical versions where you use prisoner return, no passing, and a special way to fill in eyes in order to turn scoring into part of the game.

Then when you say B+3 in the “terminal” position, it translates to Black have three more moves left than white, as well as being interpreted in Go as having three more points.

[martin3141]

@shinuito

Equally, there’s no passing in combinatorial games so you have to deal with that.

Ok, I believe we are working with different definitions for “combinatorial game”. Sorry for interrupting.

But I am curious as to how your definition works. In my mind, “pass” is just another possible move option.

[shinuito]

@martin3141

Ok, I believe we are working with different definitions for “combinatorial game”. Sorry for interrupting.

I wouldn’t say you’re interrupting People can feel free to jump in any time. I just like to keep the thread active

@martin3141

But I am curious as to how your definition works. In my mind, “pass” is just another possible move option.

The problem with pass, is that the game immediatley becomes loopy, which makes it harder to work with. The game is no longer short then either, because there’s no rule generally that says “two passes” end a game, so you don’t have a finite number of positions in the game.

So I would think, at least with trying to apply it to Go, and not like infinite chess or something, one would use:

G is finite : it has just finitely many subpositions.
G is loop free: it admits no infinite run → there is no sequence of moves proceding from G that repeats a position.

It becomes a bit strange mathematically to have G as an element of its left or right options, which then again must have G as an element of its left or right options, … etc.

Just for clarity, at least in the Berlekamp book, the work with G being finite and loopfree page 46, section 3.5.1, with G={G^L | G^R}, the game G is a pair of sets, the left set being left’s moves from G, and the right set being right’s moves. Typically L is assigned the colours bLack, bLue etc in game, and right gets assinged white Red etc.

I mean they make it work somehow in CGT, I just haven’t started reading those sections yet. (I’ll have a glance now).

@martin3141

I think of it as a directed graph,

Right I see what you’re saying. You’re already thinking of it more generally, allowing for possibilities of loops and other things, not just as a game tree like you might do in a finite game.

[martin3141]

One can enforce that the graph is a tree by defining it such that each game state is uniquely defined by a path starting from a start state (think of the game state as including all the game history, e.g all previous moves), and fixing one start state.
For a finite game we’d need to require the graph to be finite.
As far as I know, with japanese rules go is not a finite game, since board-state-loops are allowed.

[Feijoa]

I think a major problem with passes in combinatorial game theory is that they would eliminate the possibility of a “zero game”, in which the first player loses.

Without a zero game, the set of games no longer forms a group, so you can’t do stuff like comparing games by analyzing G - H, right?

[martin3141]

If by pass you mean a move that transitions a game state S into S, i.e. a single-edge loop, then yes.
However, in Go a pass is not like that. Note that the board state alone is not sufficient to represent the game state in Go.

[shinuito]

@martin3141

One can enforce that the graph is a tree by defining it such that each game state is uniquely defined by a path starting from a start state (think of the game state as including all the game history, e.g all previous moves), and fixing one start state.

Certainly a tree is a kind of graph, even a directed graph. The graph approach sounds more general, it’s just maybe not necessarily needed, unless one wants to treat ko properly I would think? Since then as you said, that involves potential loops. Ko, send two return one without a superko etc.

@martin3141

However, in Go a pass is not like that.

But in game theory it is, which is the problem. Games don’t seem to encode whose move it is, so when you pass you just get the exact same game state.

[martin3141]

@shinuito

Games don’t seem to encode whose move it is, so when you pass you just get the exact same game state.

You get the same board state, but board state is not equivalent to game state.

[shinuito]

@martin3141

You get the same board state, but board state is not equivalent to game state.

Except it is in the examples of combinatorial game theory we’ve been working with. I’m including things like prisoners in that. So if you passed like in AGA rules, where you gift a prisoner, then sure, the game state changes, but like in Chinese and Japanese rules, the game state looks identical.

Players can take two moves in a row in the mathematical formulation without the other player passing, also something that isn’t legal in Go

[martin3141]

@Feijoa

Without a zero game, the set of games no longer forms a group, so you can’t do stuff like comparing games by analyzing G - H, right?

Ah interesting, I think I’m starting to understand where this is coming from. We split the board position into multiple local positions (e.g. in the endgame), and view each position as a single game. Right?

[shinuito]

@martin3141

We split the board position into multiple local positions (e.g. in the endgame), and view each position as a single game. Right?

I think this is indeed supposed to be the utility of this formulation, particularly for Go endgame, and other games (Amazons endgame, certain chess positions involving King and pawns and zugzwang etc), that the game splits up into several smaller games that you can calculate separately. Then you sum them back up to figure out who wins in the overall game.

[hoctaph]

I don’t see any general solution for non-trivial loops
​- since for example, these could combine into triple-ko -
but when passes are the only loops, it seems to me that one still gets a zero game:
​
​
​
Each game consists of

a finite set of positions
and
an element of that set ​ (the starting position)
and
two sets of directed edges, neither of which has an edge whose start and end vertices are equal
(Black’s non-pass moves and White’s non-pass moves)
and
three functions to scores, each from a different one of
the set of positions ​ , ​ the set of black non-pass moves ​ , ​ the set of white non-pass moves

.
​
​
Play ends when both players pass consecutively. ​ When that happens, the overall score is

the sum of scores of the ending positions ​ (in the component games)
plus
the sum of the scores for the moves made ​ (this is how one can account for captures)

.
​
​
The zero game is the one such that

its set of positions is {{}}
and
the score of its position is zero

.

[Feijoa]

Well in any case, I think that passing doesn’t add much except in some unusual situations that also involve ko.

Usually the passes won’t happen until the end of a game, and then the final pass-pass can just be reduced to a zero. So why bother with them at all?

If you want to use combinatorial game theory, you also need to do away with the concept of a score that is separate from the game tree, but it works fine to just put the scores at the leaves like I was saying, and I think that corresponds to how it works in the book. Maybe you need to think a little about how half-point komi or a tie gets represented, but it’s not a big deal.

@shinuito

That way the numbers kind of make sense, if we modify them to the above.

By the way, for my diagrams, I wasn’t intending to imply that the stones shown were the entire game in any sense. There could be any number of live stones connected to them, and I was just drawing a minimal number of alive stones around the edges so that you can know what’s going on with the contested region in the middle.

To analyze an whole-board position you’ll always need to add in some extra points to account for all the other stones/territory/captures/komi that are already resolved and not part of the regions under analysis. So it’s simpler to leave out as much as possible and keep the scores for those regions close to zero.

I think that’s how they do it in the book, but Japanese rules makes it a little more straightforward since you only have to worry about the territory part and all those stones around the border don’t matter.

[shinuito]

@hoctaph

three functions to scores, each from a different one of
the set of positions ​ , ​ the set of black non-pass moves ​ , ​ the set of white non-pass moves

Are your two functions to score in edges (the “moves”) in order to define move values? They don’t seem necessary otherwise. Surely you only need to score terminal positions?

What kinds of scores do the functions map unsettled positions to and what’s their purpose otherwise? Do you want to score unfinished Go game positions?

I think essentially, I’m sure it’s possible. The idea of treating a game as a directed graph seems more general, and it’ll work for some loopy games, but the point is it’s not needed for Go without ko.

[shinuito]

@Feijoa

So it’s simpler to leave out as much as possible and keep the scores for those regions close to zero.

It might be simpler, but then is it actually accurate to the idea of what the “game” is though?

Playing the game should reflect the score in some way. And playing the combinatorial game shouldn’t disagree with playing the Go game.

At that’s why I think one should probably include the stones as points if one really wants to do area scoring and not just territory scoring.

[Feijoa]

@shinuito

It might be simpler, but then is it actually accurate to the idea of what the “game” is though?

Well we might be done already with analyzing Chinese rules games so there’s not much point in debating further, but yes, as long as you have a clear way of combining the regions to form a whole-board game it should be okay to shift the scores for the regions any amount in any direction.

Any offset also doesn’t affect optimal play either, so worst case you can always just play out the optimal solution and then score the whole board normally.

EDIT: sorry, I must have forgotten briefly that we’re on OGF debating a small piece of an obscure topic, we should keep it up!

[hoctaph]

@shinuito

Are your two functions to score in edges (the “moves”) in order to define move values?

I had not realized that my ​ no non-trivial loops ​ condition made those two unnecessary.
However, for Japanese rules, they can let game-descriptions be
overall significantly smaller. ​ (via a reduced number of positions)
​
​
(Also, they would be necessary for more complicated loops,
and even for basic kos if one doesn’t make those a special case.)

[gennan]

@shinuito

Players can take two moves in a row in the mathematical formulation without the other player passing, also something that isn’t legal in Go

A pass in a subgame may not be a global pass, but just a tenuki (playing in a different subgame). So considering sequences where a player gets several moves in a row in a particular subgame is not illegal or even abnormal I think.

@shinuito

the game splits up into several smaller games that you can calculate separately. Then you sum them back up to figure out who wins in the overall game.

I’ll just note that the proper “summation” of subgames is not as straightforward as summation of regular numbers, as it may involve tree recursion (sort of like MiniMax) from surreal numbers.