Some endgame fun

[lightvector]

Actually, it is ambiguous. (See http://senseis.xmp.net/?AmbiguousPosition ).

Anyway, I think I'm uncomfortable with positions like this because I don't know how to bound my error. The normal endgame counting can fall apart if you just blithely assume you'll get all the sente plays you want. Though I think the normal endgame counting is more managable than I gave it credit for, since you can aggressively prune the decision tree by assuming that sente followups are automatic. But it does fail in some cases dealing with tedomari and ambiguous positions. But it's a good starting point.

...

So how do we actually handle this sort of position in a way that assures us we can play optimally and find the actual final score? If we use the endgame counting heuristic, are we at least assured that the first move we play will be optimal? If so, it's just a matter of recalculating values after each move.

Optimal play in general probably cannot be achieved by any method fundamentally more efficient than actually searching the game tree and reading all the variations. (For the complexity theorists out there: are ko-free Go endgames PSPACE-complete?).

It seems to me that miai counting (or OMeien's method, I see no real difference between them) is basically the best possible that you can do by only considering each local position independently of all the others, and assigning each one a simple number or two, namely, the count and the value of a play. If you want to do any better, you probably can't really avoid using something much more complicated, such as CGT, or brute forcing the game tree.

I seem to recall that miai counting has the very nice property that in the limit, where you have lots of plays of lots of different values, the move with the highest miai value is the optimal move. It's only when things become highly discrete and the number of different plays drops (causing things like tedomari, etc.) that they differ. But still, the miai count (perhaps adjusted by half of the value of the largest remaining move depending on whose turn it is) is a stellar approximation to the optimal value of the game. At least, it's seems better declaring positions "unsettled" and having no idea, or applying other counting methods with lots of ad-hoc rules like "sente is worth double" and being unable to generalize to positions with multiple nested followups, etc.

[Numsgil]

(For the complexity theorists out there: are ko-free Go endgames PSPACE-complete?).

It's been a long time since I studied my complexity classes, but do you mean that it's something like the travelling salesperson problem and less like a polynomial time problem like Dijkstra's algorithm? Hmm, I'm torn on if this is true or not. Certainly the early and middle game of go are crazy complex. But by the time you get to the endgame, you have a pretty strong bound on the size of the largest move.

Comparing to the travelling salesperson problem, it's like you've chosen the basic path of your solution (which would be the early and mid game of go), and now you're just refining to find the local optima.

If we assume that the endgame sequences are entirely independent, and define a "threat size" that is so large that it must be answered (that is, the move that makes the threat is 100% sente (this would break down for weird under-the-stones endgame problems where you have to sacrifice 80 something stones, but that speaks to the fun of go )), I feel like it should be possible to efficiently find the optimal endgame sequence for both players in most normal situations using a method similar to A* (clicky).

[Bill Spight]

Anyway, I think I'm uncomfortable with positions like this because I don't know how to bound my error.

Do you mean your error in playing, not your error in calculating? If so, Berlekamp has a strategy called Sentestrat, which does so when there are no kos. It does require accurate calculation. Simply making the largest play does not bound your error.

Code: Select all

Sentestrat

Start with a variable called the temperature, equal to the miai value of the largest play on the board. Once that play is made, the value of the temperature becomes the miai value of the largest play now on the board, as long as it is the same or smaller than the current temperature. If the largest play on the board has a higher miai value than the current temperature, the value of the temperature remains the same, until the miai value of the largest play drops below it.

A sente play is defined as a play that puts a play on the board with a miai value greater than the current temperature. 

Sentestrat says to answer all of the opponent's sente plays. :)

Sentestrat is not very sophisticated, but it does bound your error.

The normal endgame counting can fall apart if you just blithely assume you'll get all the sente plays you want.

I take it that you mean that sometimes your opponent will get to make reverse sente plays.

So I have an abstract example (I'd try to make an actual position for it, but it's pretty tricky to work backwards from counts to a position).

Let's say I have 3 unrelated endgame sequences to resolve, and then the game is over. Assume that the point values below are all black's gain if he gets the move, and white doesn't gain any points when he plays.

Do you mean score or count? E. g., a position with this game tree,

Code: Select all

                    A
                   / \
                  4   0

where / indicates a Black play and \ indicates a White play, is what you mean by one where Black gains 4 points and White gains nothing?

Sequence A: 4 point gote play (A1) with a 1 point sente followup (A2).
Sequence B: 5 point gote play (B1) with a 2 point sente followup (B2).
Sequence C: 4 point gote play (C1) with a 3 point gote followup (C2), which itself has a 5 point sente followup (C3).

With normal endgame counting, the values would be: A:5, B:7, C:8.

If so, it sounds like the game tree for A looks like this:

Code: Select all

                    A
                   / \
                  A1  0
                 / \
                A2  4
               / \
             Big  5

And B looks like this:

Code: Select all

                    B
                   / \
                  B1  0
                 / \
                B2  5
               / \
             Big  7

And C looks like this:

Code: Select all

                    C
                   / \
                  C1  0
                 / \
                C2  4
               / \
              C3  8
             / \
           Big  13

Is that what you mean? (I am really not sure about C.)

So how do we actually handle this sort of position in a way that assures us we can play optimally and find the actual final score? If we use the endgame counting heuristic, are we at least assured that the first move we play will be optimal?

No, we do not have that assurance. The largest play is not always the best play. And in fact, always making the largest play can have a theoretically unbounded error. Berlekamp's Sentestrat does bound the error.

Now, with the game trees that I have constructed, a play in A gains 2.5 points, a play in B gains 3.5 points, and a play in C gains 4 points. The original count is 10 points. If each player takes the largest play, then

Black plays C, for a count of 14.
White plays C1, for a count of 10.
Black plays B, for a count of 13.5.
White plays A, for a count of 11.
Black plays B1 with sente, for a count of 11.
(You can verify that Black gets 4 in C and 7 in B.)

Can either player do better?

[Numsgil]

Do you mean your error in playing, not your error in calculating?

I think both are problems , but I specifically meant the possible error in my estimation/expected value if actual play violates some of the assumptions I made (such as assuming that no reverse sente plays will be made). I can't always calculate the right answer for the value of an endgame, but I don't mind at all theorizing on perfect play with the assumption that I can.

If so, Berlekamp has a strategy called Sentestrat, which does so when there are no kos. It does require accurate calculation. Simply making the largest play does not bound your error.

Yes! That's the sort of thing I was thinking should exist. I'll have to spend a bit of time playing with the idea in my head. Is it a solid guarantee, with no exceptions in ko-less endgames? Like is there ever a time where responding to a "sente" play with a threat larger than the current temperature is suboptimal?

Also, as I understand it, it does not indicate which order of play is best? It just gives us a hard and fast rule for which plays are actually sente (helps to disambiuate ambiguous.

So yeah, it feels like with this as a hard bound, you should be able to build up the global decision tree and traverse it to the optimal solution using something like A*. I'll have to think about whether you can uses miai as the heuristic

The normal endgame counting can fall apart if you just blithely assume you'll get all the sente plays you want.

I take it that you mean that sometimes your opponent will get to make reverse sente plays.

Yes. Seems to throw a monkey wrench into the normal counting methods some of the time. (I guess this is miai counting I'm talking about? Where you assume sente plays will get made, and when choosing between a sente play and a gote play, you value the sente play at 2x. I learned it from the Elementary Go Kiseido series.)

Do you mean score or count?

Bleh, I can never remember which is which, so for the record I have and probably will butcher these terms, and even use them interchangably. I probably should just suck it up and learn to use the terms with their specific formal meanings

E. g., a position with this game tree,
Code:
A
/ \
4 0


where / indicates a Black play and \ indicates a White play, is what you mean by one where Black gains 4 points and White gains nothing?

Yes. White gains by preventing black's 4 point play, even though he makes no points himself, so it's worth 4 points to either player.

Is that what you mean? (I am really not sure about C.)

All are correct, but for C, it should be:

Code: Select all

                    C
                   / \
                  C1  0
                 / \
                C2  4
               / \
              C3  7
             / \
           Big  13

Also, for labeling the moves, If black wants to play the C sequence, he plays C1. There is no 'C' move. So for the move order you have, I think you need to add 1 to each of the "plays X" to match up with the examples I gave.

Can either player do better?

I don't think so, though I'm not super sure. Assuming it is optimal, here's a better example to play around with (taken from the sensei's tedomari page). (Also note: numbers represent the inherant gain or loss of score, from black's point of view, for a particular node to be reached. It does not represent the miai value of nodes below it, for instance).

Code: Select all

       A
      / \
A1   0  -3

       B
      / \
B1   0  -4

        C
       / \
C1    2   0
        /  \ (sente for white)
C2     0   -3

In this case, playing just the biggest move first leads to the move order:
Black B1 (+0), White C1 (0), Black A1 (0), White C2 (-3) = -3

However this move order is one point better for black:
Black C1 (+2), White B1 (-4), Black A1 (+0) = -2

The tedomari page talks about using infinitestimals to find the right sequence, which I don't know a lot about. But are there endgame sequences where other issues than tedomari prevent the biggest-move-on-the-board-first from reaching the optimal solution (still not counting kos)? Is the loss in points always no more than 1?

[topazg]

Wow, I'm guessing people don't really want to answer these then

[Numsgil]

Sorry, I guess I sort of derailed the thread

[Bill Spight]

Like is there ever a time where responding to a "sente" play with a threat larger than the current temperature is suboptimal?

Yes. You may be interested in Berlekamp's "Economist's view" chapter in Games of No Chance, in which he explains Sentestrat and a lot of other things.

It just gives us a hard and fast rule for which plays are actually sente.

It is a specialized meaning of sente. Go players in general will not understand it.

Do you mean score or count?

Bleh, I can never remember which is which, so for the record I have and probably will butcher these terms, and even use them interchangeably.

You meant score. To call it gain implies that you are starting from zero. Since I use gain starting from any position, we could have a language problem if you mean something else.

All are correct, but for C, it should be:

Code: Select all

                    C
                   / \
                  C1  0
                 / \
                C2  4
               / \
              C3  7
             / \
           Big  13

Please note that C1 is a 3 point sente, not gote. And that the count at C1 is 7, the same as the count at B1.

With the correction to C, there are two orthodox lines of play:

1) Black plays to C1 in C, White plays to 0 in B, then Black plays the sente to 7 in C, and then to 4 in A, as though it were sente. Result: 11.

2) Black plays to B1 in B, White plays to 0 in C, then Black plays the sente to 7 in B, and then to 4 in A, as though it were sente. Result: 11.

Code: Select all

       A
      / \
A1   0  -3

       B
      / \
B1   0  -4

        C
       / \
C1    2   0
        /  \ (sente for white)
C2     0   -3

Note that C is gote.

But are there endgame sequences where other issues than tedomari prevent the biggest-move-on-the-board-first from reaching the optimal solution (still not counting kos)?

Yes. I used to compose problems where the key was what plays were left at the end, before I realized how stupid that was.

Still, tedomari helps humans recognize such sequences.

Is the loss in points always no more than 1?

No, but I like problems where the incorrect play loses only 1 point.

[Numsgil]

Bah, I'm feeling a bit pessimistic about the endgame, then.

Is there anything between the normally espoused endgame counting and just enumerating over every possible move order to arrive at a "perfect" endgame play? I don't even really mind if it's unwieldy to do in your head at this point, I just want to feel like it's possible to stare at a go board with a well defined endgame and figure out the perfect play.

[Bill Spight]

Bah, I'm feeling a bit pessimistic about the endgame, then.

Courage, mon vieux!

Is there anything between the normally espoused endgame counting and just enumerating over every possible move order to arrive at a "perfect" endgame play? I don't even really mind if it's unwieldy to do in your head at this point, I just want to feel like it's possible to stare at a go board with a well defined endgame and figure out the perfect play.

Well, top players in the late 19th century played nearly perfect endgames.

$$W Shusai clinches the game
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . X . . . . . |
$$ | . . O . X . . X . . . O . O . . X . . |
$$ | . . . O X . 1 O . O . O X . O O X . . |
$$ | . . O , X . X X O , . X O O O X . . X |
$$ | . . . . . . X O O . . X X . O X X . O |
$$ | . O O O O . . X O . . . . X O O X . . |
$$ | O X X X X X . . . . . . X O X O . . . |
$$ | . O O X . . . X . . . . . . X . O O . |
$$ | . . O X . . . . . . . X . . . . O X . |
$$ | . X X X O . . O . , . . . X . , . X . |
$$ | . O X X . O . . . . . O . . X . . . . |
$$ | O . O X . . . . . O . . O . . X . X . |
$$ | . . O O O . . O O . . . . O O X . . . |
$$ | . . O X . . . X . . X . . . X O X X . |
$$ | . . O X O O . X O O X . . X . O O O . |
$$ | . O X X X . X . . O X . . . . O . . . |
$$ | . O X . . . . X . O . . . X O . . . . |
$$ | O X X . . X . X O . X . X . X O O . . |
$$ | . . . . . . X O O . . . . . X X O . . |
$$ ---------------------------------------

Click Here To Show Diagram Code

[go]$$W Shusai clinches the game
$$ ---------------------------------------
$$ | . . . . . . . . . . . . . X . . . . . |
$$ | . . O . X . . X . . . O . O . . X . . |
$$ | . . . O X . 1 O . O . O X . O O X . . |
$$ | . . O , X . X X O , . X O O O X . . X |
$$ | . . . . . . X O O . . X X . O X X . O |
$$ | . O O O O . . X O . . . . X O O X . . |
$$ | O X X X X X . . . . . . X O X O . . . |
$$ | . O O X . . . X . . . . . . X . O O . |
$$ | . . O X . . . . . . . X . . . . O X . |
$$ | . X X X O . . O . , . . . X . , . X . |
$$ | . O X X . O . . . . . O . . X . . . . |
$$ | O . O X . . . . . O . . O . . X . X . |
$$ | . . O O O . . O O . . . . O O X . . . |
$$ | . . O X . . . X . . X . . . X O X X . |
$$ | . . O X O O . X O O X . . X . O O O . |
$$ | . O X X X . X . . O X . . . . O . . . |
$$ | . O X . . . . X . O . . . X O . . . . |
$$ | O X X . . X . X O . X . X . X O O . . |
$$ | . . . . . . X O O . . . . . X X O . . |
$$ ---------------------------------------[/go]

In 1907, Tamura Yasuhisa, who later became Shusai Meijin, spent 8 hours gazing at the board, verifying that this move, W148, secured a 2 point victory.

Here is the whole game.

(;SZ[19]FF[3]
PW[Tamura Yasuhisa]
WR[7d]
PB[Nakagawa Senji]
BR[6d]
EV[10-game match]
RO[Game 1]
DT[1907-12-02~16]
PC[Ikaho, Ueno, Tokyo]
KM[0]
OH[-B-]
RE[W+2]
US[GoGoD95]
;B[cp];W[pp];B[ep];W[cd];B[qe];W[pc];B[ec];W[qh];B[qn];W[jq];B[nq];W[pn]
;B[pm];W[qo];B[on];W[po];B[no];W[om];B[pl];W[nm];B[rn];W[oq];B[kp];W[jp]
;B[ko];W[ro];B[ok];W[ml];B[oh];W[pf];B[pe];W[oe];B[qf];W[pg];B[ri];W[rh]
;B[pd];W[od];B[qc];W[oc];B[qb];W[qi];B[nj];W[jo];B[kn];W[lk];B[li];W[jl]
;B[or];W[pr];B[mr];W[im];B[ps];W[qs];B[os];W[qr];B[kr];W[hc];B[nf];W[ng]
;B[og];W[of];B[mg];W[dc];B[ed];W[df];B[ge];W[he];B[hf];W[ie];B[gd];W[jc]
;B[dh];W[cf];B[eg];W[co];B[do];W[cn];B[dl];W[bp];B[cq];W[bq];B[br];W[cl]
;B[ck];W[fo];B[dn];W[cm];B[ho];W[bk];B[hq];W[io];B[hn];W[hm];B[dk];W[dm]
;B[bj];W[em];B[gp];W[ar];B[cr];W[al];B[rj];W[ef];B[fg];W[fk];B[me];W[md]
;B[ld];W[lc];B[mc];W[nd];B[le];W[lb];B[bg];W[bf];B[hh];W[ir];B[hr];W[eo]
;B[dp];W[hs];B[gs];W[is];B[fr];W[hj];B[eb];W[cb];B[na];W[se];B[sd];W[nb]
;B[rl];W[ci];B[di];W[ch];B[cg];W[bh];B[dg];W[ag];B[cj];W[ej];B[dj];W[if]
;B[hd];W[id];B[hb];W[gc];B[gb];W[fc];B[fb];W[hg];B[fd];W[ic];B[gg];W[gf]
;B[ff];W[ee];B[hf];W[kq];B[lq];W[gf];B[fe];W[dd];B[ii];W[pb];B[pa];W[oa]
;B[ob];W[sf];B[rd];W[oa];B[qa];W[ij];B[ob];W[ma];B[so];W[sp];B[sn];W[rp]
;B[ib];W[jb];B[gn];W[fm];B[oa];W[fp];B[fq];W[ki];B[kh];W[ji];B[ig];W[hf]
;B[jh];W[lj];B[km];W[in];B[jf];W[kf];B[je];W[lh];B[mi];W[ke];B[gi];W[kd]
;B[lg];W[ks];B[ls];W[jr];B[js];W[lf];B[mf];W[ks];B[lr];W[oi];B[nh];W[mo]
;B[mn];W[nn];B[mp];W[gj];B[kl];W[hi];B[ih];W[fi];B[gh];W[oo];B[qj];W[np]
;B[lo];W[kk];B[no];W[pi];B[op];W[pq];B[db];W[da];B[mm];W[nk];B[ol];W[nl]
;B[ll];W[mj];B[ni];W[ia];B[ea];W[ca];B[ha];W[ja];B[gm];W[gl];B[el];W[fl]
;B[aj];W[ah];B[ak];W[bl];B[jm];W[jk];B[bs];W[bo];B[pj];W[np];B[bc];W[cc]
;B[op];W[sh];B[re];W[np];B[mo];W[si];B[sj];W[ei];B[ek];W[jd];B[jg];W[op]
;B[js]
)

When composing problems I used to define each play precisely, so that I could guarantee a certain result. Now I find that it is easier and more realistic to create more or less random plays within my parameters, because the largest play is nearly always the right play, and a large enough number of random plays will almost always wash out anomalies.

Nearly perfect endgames are humanly possible, and amateurs can, with persistence and hardly any talent achieve a high level of endgame play.

[Numsgil]

Okay, so certainly normal counting is the start, since it is usually the right move. What then? Especially in something like the game you showed, where a lot is on the line and you have nothing but time, what do you do once you've figured out the count of the endgame moves remaining, and decide it's a really close game. Or let's say it's an important game, and you have nothing but time, and the normal counting method puts you half a point behind. Is there a systematic way to approach the board and see if there's a clever sequence that can net you another point?

[Bill Spight]

Is there a systematic way to approach the board and see if there's a clever sequence that can net you another point?

Yes. If there is a significant drop in the size of plays, you may be able to engineer getting the last play before the drop. My problem that you referred to is an example.

Also, you may be able to make a ko such that you can take and win the ko while your opponent makes smaller plays.