|
|
Post by Steve Draper on Oct 5, 2014 14:41:24 GMT -8
Consider the following position in Skirmish(variant), which is Skirmish non-zero-sum - i.e. - chess where the kings are not special and you score something extra for every piece you capture:  Black to play (not black pawns are playing 'up' the board so the two pawns are mutually blocking). Note that the game ends when neither player has a legal move, or after turn 100 (black's turn). What is the optimal result if both players play rationally? I spent some time debugging this, because I thought what happened must be a bug...but it isn't... I'll leave this as a puzzle for a while to give folks a chance to think about it and/or discuss. |
|
|
|
Post by Andrew Rose on Oct 5, 2014 23:41:24 GMT -8
I think this game ought to be a 93-86 win for black and it can do that trivially by taking the white bishop immediately.
White can't take the black pawn where it is. As soon as the black king takes the bishop, the game ends because white can't move. If black instead aims to take the white pawn, white need simply keep his bishop on the diagonal were it protects the pawn. As soon as the black king takes the pawn, he takes the black king. Game over, because black can't move the pawn. That would be a worse result for black (assuming he takes white's score into account - a 93-93 draw is worse than a 93-86 win), so no incentive for black not to do my original plan of just taking the bishop.
But since that's too easy, perhaps some sharper minds would like to comment!
|
|
|
|
Post by alandau on Oct 6, 2014 0:03:39 GMT -8
Well, if black moves to take the pawn, the opponent might screw up and allow the bishop to be taken as well -- this would probably show up in at least a few of the simulations that feed into the evaluation. This means taking the bishop results in a score of exactly 93, while moving to take the pawn results in a score of either 93 or 100, depending on what the opponent does.
The opponent's score wouldn't matter, of course, because this is GGP.
Incidentally, I would assume that the entire game tree to the end of the game couldn't have been fully explored, and some players might not understand the latching nature of the game score. It would be reasonable for these players (though outside the scope of normal UCT) to value the guaranteed 93 slightly more highly, to avoid some unforeseen worse outcome. I understand Sancho does use latch detection, so it can be confident in the minimum score being achieved (once the pawn has been captured).
|
|
|
|
Post by Steve Draper on Oct 7, 2014 13:24:55 GMT -8
Well, at first I assumed that taking the bishop was 'obviously' best, leading to an immediate 93:86 result. At that point I started debuggng (Sancho didn't take the bishop)...
First observation: Black gets the last turn (turn 100) so if the king stays next to the pawn black can ALWAYS make one more capture without conceding one, so there is no pressing need to to immediately capture the bishop (can always achieve at least that score)
Second observation: Actually the optimal result is 100:93! If black does not capture then it is in white's interests to NOT defend the pawn, because once black has played K X P it is mutually beneficial for black to offer the exchange of the pawn for white's bishop, leaving the terminal state with just the black king remaining. This is an unconditionally superior result for black (hence he should NOT capture the bishop), and for white (hence he SHOULD give the pawn up).
Sancho saw this 23 moves from the end. It took me nearly 2 hours analysing a tree dump to figure out what was going on!
|
|
|
|
Post by alandau on Oct 7, 2014 16:51:01 GMT -8
Ah, I see... in other words, black can stall until turn 100 to make the capture without white retaliating, so white expects to get a (losing) score of 86 if it continues protecting the pawn. White can improve this to a (still losing) score of 93, but only by offering its pawn as a sacrifice before the end of the game (by leaving it unprotected) and then allowing black to offer its pawn as part of a mutually beneficial trade.
So then why does the screenshot show the game ending on turn 82? Did black take the pawn even though white was still protecting it? If so, that would seem to contradict your described strategy. (Maybe white's move took it out of the part of the tree where the strategy applied?)
|
|
|
|
Post by Steve Draper on Oct 8, 2014 9:07:53 GMT -8
Ah, I see... in other words, black can stall until turn 100 to make the capture without white retaliating, so white expects to get a (losing) score of 86 if it continues protecting the pawn. White can improve this to a (still losing) score of 93, but only by offering its pawn as a sacrifice before the end of the game (by leaving it unprotected) and then allowing black to offer its pawn as part of a mutually beneficial trade. So then why does the screenshot show the game ending on turn 82? Did black take the pawn even though white was still protecting it? If so, that would seem to contradict your described strategy. (Maybe white's move took it out of the part of the tree where the strategy applied?) They oscillated around a few turns then made the mutual sacrifices nearer the fixed end point. |
|
