Author: Rémi Coulom
Date: 01:47:36 08/21/99
Hello,
I spent some time trying to write code to evaluate pawn races in TCB, and I have
a few comments and questions for programmers.
First, I took a look at the source code of Crafty. I was surprised to find that
the code can fail in many cases and evaluate that a passed pawn can promote when
it can not. My guess is that the gains can outweight the problems, but I tend to
believe that "If you have something that can make a chess program play a stupid
move, it will happen, and it will probably be during the World Championship". I
made up a few positions that trap Crafty's evaluation. They are all cases when
it underestimates the opponent's ability to promote first. It can happen :
1. If the opponent has a check that wins a tempo
2. If the opponent has "hidden passed pawns", which are not taken into
consideration
3. If the opponent has two passed pawns and the King is in both's square
4. If the opponent can protect its passed pawn with his King
I appended four analysis logs that show these problems. I am sure there are many
other kinds of problems that can be found.
I prefered to evaluate passed pawn races more safely in TCB. Of course, there
are problems which Crafty solves faster than TCB because of this, but I prefer
to choose safety. I wonder what others do ?
An idea I got which might be of interest is to evaluate the famous "square of
the king" rule more accurately, taking into consideration the position of both
kings. This would solve the 4th type of problem in Crafty. It also helps a lot
for some problems like WAC #100 which TCB now solves at depth 15 in less than
one minute on a K6 200. I implemented this like a KPK tablebase indicating if
the pawn can run. Here is the code. Programmers should be able to adapt it
easily to their needs if they want to try it. This uses a 0x88 square numbering,
with a8 = 0x00, a7 = 0x10, ... The table takes only 24 kB of memory and the
probing code is very fast.
////////////////////////////////////////////////////////////////////////////
//
// pawnrace.cpp
//
// Table to evaluate pawn races
//
// Remi Coulom
//
// August, 1999
//
////////////////////////////////////////////////////////////////////////////
#include "pawnrace.h"
#include "lowlevel.h"
#include "attacks.h"
static int sqWPG = 0;
static int tCanRun[64 * 48 * 2]; // int must be at least 32 bit wide
static int CanPawnRunWTM(int sqBK, int sqWP, int sqWK);
////////////////////////////////////////////////////////////////////////////
// Recursive search, Black to move
////////////////////////////////////////////////////////////////////////////
static int CanPawnRunBTM(int sqBK, int sqWP, int sqWK)
{
if (sqWP < sqWPG && sqWP >= 0x10)
return CanPawnRun(0, sqBK, sqWP, sqWK);
return CanPawnRunWTM(sqBK - 0x11, sqWP, sqWK) &&
CanPawnRunWTM(sqBK - 0x0f, sqWP, sqWK) &&
CanPawnRunWTM(sqBK - 0x10, sqWP, sqWK) &&
CanPawnRunWTM(sqBK - 0x01, sqWP, sqWK) &&
CanPawnRunWTM(sqBK + 0x01, sqWP, sqWK) &&
CanPawnRunWTM(sqBK + 0x0f, sqWP, sqWK) &&
CanPawnRunWTM(sqBK + 0x11, sqWP, sqWK) &&
CanPawnRunWTM(sqBK + 0x10, sqWP, sqWK) &&
CanPawnRunWTM(sqBK, sqWP, sqWK); // No zugzwang !
}
////////////////////////////////////////////////////////////////////////////
// Recursive search, White to move
////////////////////////////////////////////////////////////////////////////
static int CanPawnRunWTM(int sqBK, int sqWP, int sqWK)
{
if ((sqBK & 0x88) ||
(tAttacks[0][119 + sqWK - sqBK] & tcbPiece::King) ||
(tAttacks[0][119 + sqWP - sqBK] & tcbPiece::Pawn))
return 1; // Illegal move by the black King
if (sqBK == sqWP)
return 0; // Capture by the black King
if (sqWP <= 0x07)
return 1; // Pawn promotion
if (sqBK == sqWP - 0x10 || sqWK == sqWP - 0x10)
return 0; // Blocked pawn
if (sqBK > sqWP + 8 && (sqWK > sqWP - 8 || ((sqWK ^ sqWP) & 7)))
return 1; // Easy speed-up
if (sqWP <= 0x57)
return CanPawnRunBTM(sqBK, sqWP - 0x10, sqWK);
else
return sqBK != sqWP - 0x20 &&
sqWK != sqWP - 0x20 &&
CanPawnRunBTM(sqBK, sqWP - 0x20, sqWK);
}
////////////////////////////////////////////////////////////////////////////
// Probe the table
////////////////////////////////////////////////////////////////////////////
int CanPawnRun(int fWTM, int sqBK, int sqWP, int sqWK)
{
//
// Flip the board if necessary
//
if ((sqWK & 0x07) > 3)
{
sqBK ^= 0x07;
sqWP ^= 0x07;
sqWK ^= 0x07;
}
//
// Compute mask and index
//
int WKMask = 1 << ((sqWK & 0x03) | ((sqWK & 0x70) >> 2));
int PackedBK = ((sqBK & 0x07) | ((sqBK & 0x70) >> 1)) << 1;
int PackedWP = ((sqWP & 0x07) | ((sqWP & 0x70) >> 1) - 8) << 7;
//
// Return result from the table
//
return tCanRun[fWTM + PackedBK + PackedWP] & WKMask;
}
////////////////////////////////////////////////////////////////////////////
// Function to initialize tCanRun
////////////////////////////////////////////////////////////////////////////
void FillPawnRaceTable()
{
for (int i = sizeof(tCanRun) / sizeof(*tCanRun); --i >= 0;)
tCanRun[i] = 0;
for (sqWPG = 0x10; sqWPG <= 0x67; sqWPG++, sqWPG += sqWPG & 8)
for (int sqBK = 0; sqBK <= 0x77; sqBK++, sqBK += sqBK & 8)
for (int sqWK = 0; sqWK <= 0x77; sqWK++, sqWK += 3 * (sqWK & 4))
{
int WKMask = 1 << ((sqWK & 0x03) | ((sqWK & 0x70) >> 2));
int PackedBK = ((sqBK & 0x07) | ((sqBK & 0x70) >> 1)) << 1;
int PackedWP = ((sqWPG & 0x07) | ((sqWPG & 0x70) >> 1) - 8) << 7;
if (CanPawnRunWTM(sqBK, sqWPG, sqWK))
tCanRun[1 + PackedBK + PackedWP] |= WKMask;
if (CanPawnRunBTM(sqBK, sqWPG, sqWK))
tCanRun[0 + PackedBK + PackedWP] |= WKMask;
}
}
And now, some Crafty logs :
Crafty v15.17
Crafty 15.17 vs tcb
playing a computer!
pondering disabled.
choose from book moves randomly (using weights.)
choose from 5 best moves.
hash table memory = 6M bytes.
noise level set to 1000.
White(1): setboard 8/1p3p/p//7P/P3k/2R1b1K w - -
+---+---+---+---+---+---+---+---+
8 | | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | | *P| | | | *P| | |
+---+---+---+---+---+---+---+---+
6 | *P| | | | | | | |
+---+---+---+---+---+---+---+---+
5 | | | | | | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | | | | P |
+---+---+---+---+---+---+---+---+
3 | P | | | | *K| | | |
+---+---+---+---+---+---+---+---+
2 | | | R | | *B| | K | |
+---+---+---+---+---+---+---+---+
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
White(1): bd
Illegal move: bd
White(1): display
White(1): analyze
end-game phase
clearing hash tables
time surplus 0.00 time limit 30.00 (3:00)
depth time score variation (1)
5 0.10 5.28 1. Rxe2+ Kxe2 2. h5 f5 3. h6 f4 4.
a4
5-> 0.27 5.28 1. Rxe2+ Kxe2 2. h5 f5 3. h6 f4 4.
a4
6 0.45 4.96 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
a4
6-> 0.67 4.96 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
a4
7 1.06 4.59 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
a4 f4+ 5. Kg4
7-> 1.51 4.59 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
a4 f4+ 5. Kg4
8 2.20 4.56 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
Kh4 f4 5. Kg4
8-> 3.91 4.56 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
Kh4 f4 5. Kg4
9 5.23 4.63 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
h6 f4+ 5. Kg2 Ke2 6. Kh3 Ke3
9-> 7.88 4.63 1. Rxe2+ Kxe2 2. h5 f5 3. Kg3 Ke3 4.
h6 f4+ 5. Kg2 Ke2 6. Kh3 Ke3
10 8.93 -- 1. Rxe2+
10 11.93 3.57 1. Rxe2+ Kxe2 2. Kh3 f5 3. Kg3 Ke3
4. h5 f4+ 5. Kg2 b5 6. h6 f3+ 7. Kf1
a5
10-> 1:23 3.57 1. Rxe2+ Kxe2 2. Kh3 f5 3. Kg3 Ke3
4. h5 f4+ 5. Kg2 b5 6. h6 f3+ 7. Kf1
a5
11 1:25 -- 1. Rxe2+
11 1:36 1.86 1. Rxe2+ Kxe2 2. Kg3 Ke3 3. Kg4 Ke4
4. h5 f5+ 5. Kh4 Ke5 6. Kg5 Ke6 7.
h6 Kf7 8. Kxf5
11 3:04 ++ 1. Rc5!!
11 5:14 2.73 1. Rc5 Bf3+ 2. Kh2 Kf4 3. h5 b5 4.
h6 Be4 5. Rc7 Kg5 6. Rxf7 Kxh6 7. Rf6+
Kg5 8. Rxa6
11 5:55 ++ 1. Rc7!!
11 6:24 3.50 1. Rc7 Bh5 2. Kg3 b5 3. Rc6 f5 4. Re6+
Kd4 5. Rxa6 Ke5 6. Rb6 f4+ 7. Kf2 Be8
11 7:18 ++ 1. Kg3!!
11 7:35 3.91 1. Kg3 Bh5 2. Rc5 Bg6 3. h5 Bb1 4.
Rc7 f5 5. Re7+ Kd4 6. Rxb7 Be4 7. Re7
11-> 8:00 3.91 1. Kg3 Bh5 2. Rc5 Bg6 3. h5 Bb1 4.
Rc7 f5 5. Re7+ Kd4 6. Rxb7 Be4 7. Re7
Crafty v15.17
Crafty 15.17 vs tcb
playing a computer!
pondering disabled.
choose from book moves randomly (using weights.)
choose from 5 best moves.
hash table memory = 6M bytes.
noise level set to 1.
White(1): setboard 8/8/2p5/1pp5/p7/P1PPk2P/2R1b1K w - -
+---+---+---+---+---+---+---+---+
8 | | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | | | | |
+---+---+---+---+---+---+---+---+
6 | | | *P| | | | | |
+---+---+---+---+---+---+---+---+
5 | | *P| *P| | | | | |
+---+---+---+---+---+---+---+---+
4 | *P| | | | | | | |
+---+---+---+---+---+---+---+---+
3 | P | | P | P | *K| | | P |
+---+---+---+---+---+---+---+---+
2 | | | R | | *B| | K | |
+---+---+---+---+---+---+---+---+
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
White(1): analyze
end-game phase
clearing hash tables
time surplus 0.00 time limit 30.00 (3:00)
depth time score variation (1)
1 0.00 1.24 1. h4 Bxd3
1 0.09 ++ 1. d4!!
1 0.09 3.36 1. d4
1 0.15 ++ 1. Rxe2+!!
1 0.17 6.10 1. Rxe2+ Kxd3
1-> 0.20 6.10 1. Rxe2+ Kxd3
2 0.23 -- 1. Rxe2+
2 0.27 4.64 1. Rxe2+ Kxe2 2. h4 Kxd3
2-> 0.37 4.64 1. Rxe2+ Kxe2 2. h4 Kxd3
3 0.39 4.64 1. Rxe2+ Kxe2 2. h4 Kxd3
3-> 0.49 4.64 1. Rxe2+ Kxe2 2. h4 Kxd3
4 0.51 -- 1. Rxe2+
4 0.54 2.54 1. Rxe2+ Kxe2 2. h4 Kxd3 3. h5 Kxc3
4-> 0.68 2.54 1. Rxe2+ Kxe2 2. h4 Kxd3 3. h5 Kxc3
5 0.73 -- 1. Rxe2+
5 0.83 -1.66 1. Rxe2+ Kxe2 2. Kg3 Kxd3 3. h4 Ke4
5 0.87 ++ 1. d4!!
5 1.15 1.07 1. d4 cxd4 2. cxd4 Bc4 3. h4 Kxd4
5 1.37 1.34 1. Rb2 Bxd3 2. Kg3 Bf5 3. h4 Be4
5 1.49 1.48 1. h4 Bxd3 2. Rf2 Be4+ 3. Kg3 Kd3
5-> 1.57 1.48 1. h4 Bxd3 2. Rf2 Be4+ 3. Kg3 Kd3
6 1.72 1.65 1. h4 Bxd3 2. Rf2 Be4+ 3. Kg3 Kd3 4.
Kf4
6-> 1.94 1.65 1. h4 Bxd3 2. Rf2 Be4+ 3. Kg3 Kd3 4.
Kf4
7 2.27 1.62 1. h4 Bxd3 2. Rf2 Be4+ 3. Kg3 Kd3 4.
Kf4 c4
7-> 2.75 1.62 1. h4 Bxd3 2. Rf2 Be4+ 3. Kg3 Kd3 4.
Kf4 c4
8 3.06 -- 1. h4
White(1): setboard 2bk4/5p2/2R5/8/p1K1pP1P/8/8/8 w - -
+---+---+---+---+---+---+---+---+
8 | | | *B| *K| | | | |
+---+---+---+---+---+---+---+---+
7 | | | | | | *P| | |
+---+---+---+---+---+---+---+---+
6 | | | R | | | | | |
+---+---+---+---+---+---+---+---+
5 | | | | | | | | |
+---+---+---+---+---+---+---+---+
4 | *P| | K | | *P| P | | P |
+---+---+---+---+---+---+---+---+
3 | | | | | | | | |
+---+---+---+---+---+---+---+---+
2 | | | | | | | | |
+---+---+---+---+---+---+---+---+
1 | | | | | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
White(1): display
White(1): analyze
end-game phase
clearing hash tables
time surplus 0.00 time limit 30.00 (3:00)
depth time score variation (1)
1 0.09 ++ 1. Rxc8+!!
1 0.11 3.86 1. Rxc8+ Kd7
1-> 0.16 3.86 1. Rxc8+ Kd7
2 0.17 4.07 1. Rxc8+ Kd7 2. h5
2-> 0.29 4.07 1. Rxc8+ Kd7 2. h5
3 0.32 3.78 1. Rxc8+ Kxc8 2. h5 f5
3-> 0.43 3.78 1. Rxc8+ Kxc8 2. h5 f5
4 0.46 ++ 1. Rxc8+!!
4 0.49 4.21 1. Rxc8+ Kxc8 2. h5 a3 3. Kc3
4-> 0.62 4.21 1. Rxc8+ Kxc8 2. h5 a3 3. Kc3
5 0.64 -- 1. Rxc8+
5 0.69 3.29 1. Rxc8+ Kxc8 2. h5 a3 3. Kc3 f5
5-> 0.86 3.29 1. Rxc8+ Kxc8 2. h5 a3 3. Kc3 f5
6 0.93 -- 1. Rxc8+
6 1.04 -2.03 1. Rxc8+ Kxc8 2. h5 e3 3. h6 e2 4.
h7 e1=Q 5. h8=Q+ Kc7
6 1.16 ++ 1. h5!!
6 2.47 0.70 1. h5 e3 2. h6 Bf5 3. Rd6+ Ke7 4. Kd5
<HT>
6-> 3.50 0.70 1. h5 e3 2. h6 Bf5 3. Rd6+ Ke7 4. Kd5
<HT>
7 4.39 0.79 1. h5 e3 2. Kd3 e2 3. Kxe2 Bg4+ 4.
Ke3 Bxh5 5. Kd4
7-> 5.83 0.79 1. h5 e3 2. Kd3 e2 3. Kxe2 Bg4+ 4.
Ke3 Bxh5 5. Kd4
8 7.66 0.63 1. h5 e3 2. Kd3 Bg4 3. h6 Kd7 4. h7
Bf5+ 5. Kxe3 Bxh7
8-> 10.40 0.63 1. h5 e3 2. Kd3 Bg4 3. h6 Kd7 4. h7
Bf5+ 5. Kxe3 Bxh7
Crafty 16.6 vs tcb
pondering disabled.
choose from book moves randomly (using weights.)
choose from 5 best moves.
hash table memory = 6M bytes.
noise level set to 1.
Crafty v16.6
White(1): setboard 8/3ppp2/8/1p6/8/k2PPP2/b2R3P/3K4 w - -
+---+---+---+---+---+---+---+---+
8 | | | | | | | | |
+---+---+---+---+---+---+---+---+
7 | | | | *P| *P| *P| | |
+---+---+---+---+---+---+---+---+
6 | | | | | | | | |
+---+---+---+---+---+---+---+---+
5 | | *P| | | | | | |
+---+---+---+---+---+---+---+---+
4 | | | | | | | | |
+---+---+---+---+---+---+---+---+
3 | *K| | | P | P | P | | |
+---+---+---+---+---+---+---+---+
2 | *B| | | R | | | | P |
+---+---+---+---+---+---+---+---+
1 | | | | K | | | | |
+---+---+---+---+---+---+---+---+
a b c d e f g h
White(1): display
White(1): analyze
end-game phase
clearing hash tables
time surplus 0.00 time limit 30.00 (3:00)
depth time score variation (1)
1 0.01 5.75 1. Rxa2+ Kxa2
1-> 0.13 5.75 1. Rxa2+ Kxa2
2 0.15 ++ 1. Rxa2+!!
2 0.19 6.27 1. Rxa2+ Kxa2 2. h4
2-> 0.29 6.27 1. Rxa2+ Kxa2 2. h4
3 0.32 5.94 1. Rxa2+ Kxa2 2. h4 b4
3-> 0.43 5.94 1. Rxa2+ Kxa2 2. h4 b4
4 0.47 6.25 1. Rxa2+ Kxa2 2. h4 b4 3. h5
4-> 0.55 6.25 1. Rxa2+ Kxa2 2. h4 b4 3. h5
5 0.58 -- 1. Rxa2+
5 0.64 5.38 1. Rxa2+ Kxa2 2. h4 b4 3. h5 b3
5-> 0.77 5.38 1. Rxa2+ Kxa2 2. h4 b4 3. h5 b3
6 0.82 ++ 1. Rxa2+!!
6 0.89 5.87 1. Rxa2+ Kxa2 2. h4 b4 3. h5 b3 4.
h6
6-> 1.03 5.87 1. Rxa2+ Kxa2 2. h4 b4 3. h5 b3 4.
h6
7 1.14 -- 1. Rxa2+
7 1.58 -5.32 1. Rxa2+ Kxa2 2. f4 b4 3. f5 b3 4.
f6 b2 5. fxe7 b1=Q+ 6. Ke2
7 1.67 ++ 1. d4!!
7 2.01 1.52 1. d4 b4 2. h4 b3 3. Rd3 d5 4. Ke2
7 2.47 ++ 1. Rc2!!
7-> 2.80 1.91 1. Rc2
8 4.15 2.15 1. Rc2 b4 2. Rc7 Bb3+ 3. Ke2 Be6 4.
h4 b3 5. Ra7+ Kb4
8-> 4.58 2.15 1. Rc2 b4 2. Rc7 Bb3+ 3. Ke2 Be6 4.
h4 b3 5. Ra7+ Kb4
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.