Author: Robert Hyatt
Date: 09:40:09 04/23/02
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.01 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.