Author: Chris Carson
Date: 10:34:02 04/23/02
Go up one level in this thread
On April 23, 2002 at 12:40:09, Robert Hyatt wrote: >Here is an endgame position posted a week or so: > >[D]1b6/8/8/7p/6k1/6P1/8/6K1 w - - 0 1 > >This endgame causes some problems to Crafty because it doesn't recognize >stalemate in the q-search. > >The problem here is that black can't win, obviously. Bishop + wrong rook >pawn. But if black could somehow zugzwang white into moving his g-pawn so >that black could play hxg4, then this becomes an easy win for black. > >Crafty's endgame evaluation understands that with the wrong rook pawn, this >is drawn, and here it concludes "black can't win" which is correct. However, >as the search progresses, the trick to break my eval term is to get the white >king on h1, with the black king at h3, and the black bishop at a7. Now the >white king can't move and white is forced to play g4 where black follows up >with hxg4 and the eval now says black wins. The problem with this position >is that white is _still_ stalemated (white king at h1, black king at h3, >black bishop attacking g1 so that the king can't move. It becomes easy for >a full-width search to shuffle pieces around, then force the zugzwang (almost- >zugzwang) to happen so that hxg4 happens at the last ply of full-search, or >at the first ply of the q-search. Either case results in a stalemate, but >since I don't try all legal moves in the q-search, I don't notice this. > >The fix was to add some special-case stalemate detection in the evaluation so >that in such positions, the evaluation sees that the king is stalemated and that >the opponent can't possibly win this position as a result. The old version of >Crafty looked like this on the position: > > nss depth time score variation (1) > 1 0.00 0.00 1. Kh2 > 1-> 0.00 0.00 1. Kh2 > 2 0.00 0.00 1. Kh2 Bxg3+ 2. Kg2 > 2-> 0.00 0.00 1. Kh2 Bxg3+ 2. Kg2 > 3 0.01 -- 1. Kh2 > 3 0.01 -5.21 1. Kh2 h4 2. Kg2 hxg3 > 3 0.01 0.00 1. Kg2 Bxg3 2. Kh1 > 3-> 0.01 0.00 1. Kg2 Bxg3 2. Kh1 > 4 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 > 4-> 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 > 5 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 > 5-> 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 > 6 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 > 6-> 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 > 7 0.02 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 4. > Kg2 > 7-> 0.02 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 4. > Kg2 > 8 0.03 -- 1. Kg2 > 8 0.05 -4.38 1. Kg2 Be5 2. Kf2 Kh3 3. Kf3 Bxg3 4. > Ke4 <HT> > (2) 8-> 0.07 -4.38 1. Kg2 Be5 2. Kf2 Kh3 3. Kf3 Bxg3 4. > Ke4 h4 <HT> > 9 0.12 -4.32 1. Kg2 Be5 2. Kf2 Kh3 3. Kf3 Bxg3 4. > Ke4 Kg2 5. Kf5 > 9-> 0.12 -4.32 1. Kg2 Be5 2. Kf2 Kh3 3. Kf3 Bxg3 4. > Ke4 Kg2 5. Kf5 > 10 0.13 -- 1. Kg2 > 10 0.20 -4.72 1. Kg2 Be5 2. Kf2 Kh3 3. Kf3 Bd6 4. > Kf2 Bc5+ 5. Kf3 Be3 6. Ke4 Kxg3 > 10-> 0.21 -4.72 1. Kg2 Be5 2. Kf2 Kh3 3. Kf3 Bd6 4. > Kf2 Bc5+ 5. Kf3 Be3 6. Ke4 Kxg3 > > >Obviously at depth=8, the search has enough "room" to force the almost-zug >position and break the evaluation. Current version, with the slightly modified >eval (stalemate is simple to detect in such cases using bitmaps) looks like >this: > > 1 0.00 0.00 1. Kh2 > 1-> 0.00 0.00 1. Kh2 > 2 0.00 0.00 1. Kh2 Bxg3+ 2. Kg2 > 2-> 0.00 0.00 1. Kh2 Bxg3+ 2. Kg2 > 3 0.00 -- 1. Kh2 > 3 0.00 -5.21 1. Kh2 h4 2. Kg2 hxg3 > 3 0.00 0.00 1. Kg2 Bxg3 2. Kh1 > 3-> 0.00 0.00 1. Kg2 Bxg3 2. Kh1 > 4 0.00 0.00 1. Kg2 Bxg3 2. Kh1 Be1 > 4-> 0.00 0.00 1. Kg2 Bxg3 2. Kh1 Be1 > 5 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 > 5-> 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 > 6 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 > 6-> 0.01 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 > 7 0.02 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 4. > Kg2 > 7-> 0.02 0.00 1. Kg2 Bxg3 2. Kh1 Be1 3. Kh2 h4 4. > Kg2 > 8 0.04 -0.20 1. Kg2 Be5 2. Kh1 Kh3 3. Kg1 Bd4+ 4. > Kh1 Bg1 5. Kxg1 > 8-> 0.05 -0.20 1. Kg2 Be5 2. Kh1 Kh3 3. Kg1 Bd4+ 4. > Kh1 Bg1 5. Kxg1 > 9 0.09 -0.50 1. Kg2 Be5 2. Kh1 Kh3 3. Kg1 Bd4+ 4. > Kh1 Bg1 5. Kxg1 Kg4 > 9-> 0.10 -0.50 1. Kg2 Be5 2. Kh1 Kh3 3. Kg1 Bd4+ 4. > Kh1 Bg1 5. Kxg1 Kg4 > 10 0.21 -0.40 1. Kg2 Be5 2. Kh1 Kh3 3. Kg1 Bd4+ 4. > Kh1 Bg1 5. Kxg1 Kg4 6. Kh2 > 10-> 0.23 -0.40 1. Kg2 Be5 2. Kh1 Kh3 3. Kg1 Bd4+ 4. > Kh1 Bg1 5. Kxg1 Kg4 6. Kh2 > >Stalemate is one of "those things" that is best found by the search, obviously, >but this kind of position offers some exceptions that have to be handled in >another way. > >it is also very illustrative of the problem that a full-width search causes. If >you have a "hole" in the evaluation somewhere, the search will appear to strive >to reach positions where the problem is exposed... > >This will be in version 18.15, out soon...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.