Author: Robert Hyatt
Date: 07:56:13 08/21/99
Go up one level in this thread
On August 21, 1999 at 04:47:36, Rémi Coulom wrote:
>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
I don't follow. I don't do the pawn race if the opponent has a piece left
(pawns only to trigger the test.) In that case, how can a check win a tempo?
> 2. If the opponent has "hidden passed pawns", which are not taken into
>consideration
I eval these, but I depend on the search to 'expose' the passer which
happens. I haven't seen this as a problem in any game so far.
> 3. If the opponent has two passed pawns and the King is in both's square
I don't worry about this one. again I depend on the search. With nothing
but pawns, 20 plies is easy to reach, and that is usually enough to resolve
things.
> 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.
You have to make a conscious decision about what you are going to do in the
eval, and what you are going to do in the search.. If my eval says "white
wins" it is generally correct. If it says black wins, ditto. Yes, there are
cases where it says neither, and is wrong. But to resolve those, I depend on
the search to find positions where the eval will be right.
>
>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.