Life In 19x19 http://www.lifein19x19.com/ |
|
Some endgame fun http://www.lifein19x19.com/viewtopic.php?f=15&t=3033 |
Page 1 of 2 |
Author: | topazg [ Fri Jan 28, 2011 3:32 am ] |
Post subject: | Some endgame fun |
Following the discussions of useful endgame analysis, I made this post in response to a post by Numsgil, and thought that, actually, some fun and very practical question exercise could be made from it. So, what's the value of "a" in the following positions: |
Author: | gaius [ Fri Jan 28, 2011 4:28 am ] |
Post subject: | Re: Some endgame fun |
My "solutions" to your problems (assuming that I did not mis-count): |
Author: | daal [ Fri Jan 28, 2011 5:20 am ] |
Post subject: | Re: Some endgame fun |
Before attempting to answer the problems Topazg posed, I would like to share with you a sentence from Winning Go that for many is self-evident, but for me was fog-lifting: "The reader will notice that as long as the initial X's exceed the territories won and lost, their amount is irrelevant and only provide a handy basis for comparisons." The X's that the authors refer to, are the ones you use to count the territory in an endgame problem. For example, when calculating the value of a black move at "a" vs a white move at "b," we play out the sequences and then mark territory with X's. It doesn't matter if we do it like this: or like this: As long as you use the same boundaries when you count the other scenario of white playing at b. So in both cases we get a white difference of 1 + a black difference of 1 = 2 pts |
Author: | gaius [ Fri Jan 28, 2011 5:49 am ] |
Post subject: | Re: Some endgame fun |
^ Following up on that post, you can simplify the procedure even further: - Step 1: determine the results if white plays first and if black plays first, ie. - Step 2: fix these results as "mental images". Then count the "plus points" and "minus points" for both players. In the example above, if black plays first, he gains one point ('a') and white loses one point ('b'). Thus, the move is worth two points. I think that this way of counting is by far the fastest and easiest way there is. Probably most strong players count like this intuitively, but I think it's still worth pointing it out explicitly. Now, as a more interesting example, let's try one of topazg's problems. Try to see how fast you can determine the value of 'a': Solution: |
Author: | daal [ Fri Jan 28, 2011 6:31 am ] |
Post subject: | Re: Some endgame fun |
gaius wrote: - Step 2: fix these results as "mental images". I think that this way of counting is by far the fastest and easiest way there is. Probably most strong players count like this intuitively, but I think it's still worth pointing it out explicitly. fast. For "stronger" players I'm sure, but even in my extremely simple example, I have difficulty comparing the two mental images. When just looking at the diagram below, I even find it hard to see that "a" and "b" are the points gained. If more stones are involved, keeping the mental images in my head seems utterly impossible. Keeping two numbers in my head on the other hand is not so hard. |
Author: | daal [ Fri Jan 28, 2011 7:03 am ] |
Post subject: | Re: Some endgame fun |
topazg wrote: So, what's the value of "a" in the following positions: Position B |
Author: | topazg [ Fri Jan 28, 2011 7:20 am ] |
Post subject: | Re: Some endgame fun |
@daal |
Author: | daal [ Fri Jan 28, 2011 7:27 am ] |
Post subject: | Re: Some endgame fun |
topazg wrote: @daal |
Author: | topazg [ Fri Jan 28, 2011 7:33 am ] |
Post subject: | Re: Some endgame fun |
daal wrote: |
Author: | Bill Spight [ Fri Jan 28, 2011 8:55 am ] |
Post subject: | Re: Some endgame fun |
Numsgil was interested in practical application, so I will direct my remarks to that. ![]() As I said, memory and experience help. I happen to know that a play at "a" by either player gains 3 points. ![]() |
Author: | Bill Spight [ Fri Jan 28, 2011 9:22 am ] |
Post subject: | Re: Some endgame fun |
I happen to know this one, too. But let's pretend that I don't. White first is easy. ![]() Now, Black first: Now, I happen to know that White has a sente here, so let's show the result. If we compare this with the position when White plays first, we see that Black has two points more, one for the marked point and one for the stone captured where the marked stone is, and White has three points less, where the marked stones are. So if this is sente for Black, it is a 5 point sente. That is, the reverse sente by White gains 5 points. (And this diagram then shows the value of the original position. ![]() Assuming that White cannot fight the ko, after Black plays first she has a sente follow-up, shown here. If we compare this position with the one when White responds, we see that Black has 1 point more on the marked point and White has 4 points less where the marked stones are, for a difference of 5 points. So this is a 5 point sente. So what do we have? A 5 point sente which threatens a 5 point sente? Or a gote that gains 5 points? Actually, it is ambiguous. (See http://senseis.xmp.net/?AmbiguousPosition ). Anyway, either player gains 5 points. ![]() |
Author: | flOvermind [ Fri Jan 28, 2011 10:07 am ] |
Post subject: | Re: Some endgame fun |
daal wrote: |
Author: | Bill Spight [ Fri Jan 28, 2011 10:30 am ] |
Post subject: | Re: Some endgame fun |
The next one I didn't know beforehand. ![]() Does White's weakness at "b" matter? White first is familiar. ![]() Here we see that White's defect is telling. It is Black who has the sente. Let's show that. Now, since we know that without the defect this is on the borderline of sente, with the defect it is certainly sente. ![]() Note: In a real game the follow-up position will look like this, so that Black has a ko threat. But as far as the count is concerned, it is all same same. I do not have to concern myself with the exact details of the play. ![]() |
Author: | Bill Spight [ Fri Jan 28, 2011 11:14 am ] |
Post subject: | Re: Some endgame fun |
The next position is problematic. From what we already know, Black first is easy: But what about White first? Suppose that Black replies. So if this is sente, it is a 9 point sente, as a comparison of the diagrams shows. But is it sente? Does White threaten to gain more than 9 points if Black does not reply? Assuming that White lives, this is a humungous threat. However, . . . That assumes that Black's reply secures the corner, and that is questionable. Even this reply, which would make an 11 point sente, is not certain to secure the corner. Maybe "a" is not even the right local play. When Black has no defect, we can treat the corner independently, but not now. Note: Books on the endgame usually contain a number of ill-defined problems. They may be realistic, but their evaluation is problematic. ![]() |
Author: | Numsgil [ Fri Jan 28, 2011 12:31 pm ] |
Post subject: | Re: Some endgame fun |
Bill Spight wrote: Actually, it is ambiguous. (See http://senseis.xmp.net/?AmbiguousPosition ). Ah yes, that was the sort of one I didn't know how to handle. I haven't gone over all your posts but I'm sure they'll be helpful for understanding how to approach problems. 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 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. 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. So we'd naively expect the play to be: Black takes C, White takes B, Black takes A. Final score: Black 13. But if black tries that in-game: Black takes C1 (4 points) White prevents B1 Black takes A1 (4 points) White uses reverse sente to prevent C2. Black takes A2 (1 point). Final score: Black 10. Oops... So maybe we try a different sequence. In this case, black reevaluates using the heuristic after each move. Black takes C1 (4 points) White prevents B1 Black takes C2 (3 points) White uses reverse sente and prevents C3. Black takes A1 (4 points) White uses reverse sente and prevents A2. The final score here would be: Black 11. An improvement, but still 2 points off what our original heuristic gave us. 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. |
Author: | lightvector [ Fri Jan 28, 2011 1:27 pm ] |
Post subject: | Re: Some endgame fun |
Numsgil wrote: Bill Spight wrote: 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. |
Author: | Numsgil [ Fri Jan 28, 2011 2:21 pm ] |
Post subject: | Re: Some endgame fun |
lightvector wrote: (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 ![]() |
Author: | Bill Spight [ Fri Jan 28, 2011 3:07 pm ] |
Post subject: | Re: Some endgame fun |
Numsgil wrote: 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: 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. ![]() Quote: 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. ![]() Quote: 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: 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? Quote: 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: A / \ A1 0 / \ A2 4 / \ Big 5 And B looks like this: Code: B / \ B1 0 / \ B2 5 / \ Big 7 And C looks like this: Code: C / \ C1 0 / \ C2 4 / \ C3 8 / \ Big 13 Is that what you mean? (I am really not sure about C.) Quote: 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? ![]() |
Author: | Numsgil [ Fri Jan 28, 2011 6:25 pm ] |
Post subject: | Re: Some endgame fun |
Quote: Do you mean your error in playing, not your error in calculating? I think both are problems ![]() Quote: 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 Quote: Quote: 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.) Quote: 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 ![]() Quote: 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. Quote: Is that what you mean? (I am really not sure about C.) All are correct, but for C, it should be: Code: 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. Quote: 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: 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? |
Author: | topazg [ Fri Jan 28, 2011 6:28 pm ] |
Post subject: | Re: Some endgame fun |
Wow, I'm guessing people don't really want to answer these then ![]() |
Page 1 of 2 | All times are UTC - 8 hours [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |