cracraft@wheaties.ai.mit.edu (Stuart Cracraft) (01/08/90)
A famous Reti endgame study is listed here with some machine analysis
and a question for the reader.
The Reti problem consists of the White king on h8, White pawn
on c6, Black king on a6, and the Black pawn on h5. It is White's
move.
Endgame Study
composed by Richard Reti
------------------------
-- ** -- ** -- ** -- WK
** -- ** -- ** -- ** --
BK ** WP ** -- ** -- **
** -- ** -- ** -- ** BP
-- ** -- ** -- ** -- **
** -- ** -- ** -- ** --
-- ** -- ** -- ** -- **
** -- ** -- ** -- ** --
White to draw
***** SPOILER HERE ! IF YOU WISH TO SOLVE YOURSELF, READ NO FURTHER ***
*
*
*
*
*
*
*
*
The winning strategy involves straddling the a1-h8 diagnoal with
White's king, permitting escort of the c-pawn to queening in those
variations in which black is also allowed to queen, and secondly to
allow entering the "square of the pawn" of the black h-pawn
threatening to queen thus preventing it.
>>> Machine analysis <<<
The Reti position was submitted to GNU Chess 1.55 on a one-user
Sparc-1, Fidelity Mach 3 (16mhz 68000), and AI Chess 1.46
(unreleased; 16mhz 80386).
Solution was taken to be the point at which the program saw an
approximate draw value in the material (e.g. neither side having
significant material advantage.) Since during most of the search for
all three programs, the material evaluation was heavily in Black's
favor by 3-7 pawns, this appeared reasonable. Also, examination of
the principal variation (AI and GNU show full variations while
Fidelity shows only four ply of the solution) was done in those
cases where it was available.
A summary:
Solution At what ply Seconds Speed Evaluation
AI Chess yes during 10th 168 1351 pos/sec 0.00
Fidelity yes after 11th 13 1500 pos/sec -.25
GNU Sparc yes after 11th 503 5100 pos/sec .06
Note that AI is the only program that saw the true flat draw.
AI also finds the solution at least one ply earlier due to its
search strategies.
The solution is Kg7 with either K-f6-e6-d7 or K-f6-e5-f4-g3-h2-etc.
Fidelity's speed on this problem is incredible. All three programs
use tranposition tables in the search -- so Fidelity must be using
some other trick.
Here is GNU's printout for statistics hounds...
Your move is? white
Move# 0 Target= 12000 Clock: 36000
1. 8 0 13 c6c7 a6b7
2. -76 0 51 h8g7 h5h4
3& -60 0 83 h8g7 h5h4 c6c7 a6b7
3. -60 0 118 h8g7 h5h4 c6c7 a6b7
4- -232 0 180 h8g7 h5h4 g7f6 h4h3
4& -226 0 397 h8g7 h5h4 g7f6 h4h3
4. -226 1 503 h8g7 h5h4 g7f6 h4h3
5& -210 1 902 h8g7 h5h4 g7f6 h4h3 c6c7 a6b7
5. -210 1 1089 h8g7 h5h4 g7f6 h4h3 c6c7 a6b7
6- -465 1 1549 h8g7 h5h4 g7f6 h4h3 f6e5 h3h2
6& -437 1 3085 h8g7 h5h4 g7f6 h4h3 f6e5 h3h2 c6c7 a6b7
6. -437 1 3352 h8g7 h5h4 g7f6 h4h3 f6e5 h3h2 c6c7 a6b7
7+ -226 2 5173 h8g7 h5h4 g7f6 h4h3 f6e6 a6b5 c6c7
7& -448 3 11858 h8g7 h5h4 g7f6 h4h3 f6e6 h3h2 c6c7 a6b7
e6d7
7. -448 6 27063 h8g7 h5h4 g7f6 h4h3 f6e6 h3h2 c6c7 a6b7
e6d7
8+ -242 7 30565 h8g7 h5h4 g7f6 h4h3 f6e6 a6b6 e6d7 b6c5
8& -251 13 57468 h8g7 h5h4 g7f6 a6b6 f6e5 h4h3 e5d6 b6b5
8. -251 47 246906 h8g7 h5h4 g7f6 a6b6 f6e5 h4h3 e5d6 b6b5
9- -474 50 259215 h8g7 h5h4 g7f6 a6b6 f6e5 h4h3 e5d6 h3h2
c6c7 b6b7 d6d7
9& -447 54 274343 h8g7 h5h4 g7f6 a6b6 f6e5 h4h3 e5d6 h3h2
c6c7 b6b7 d6d7
9. -447 54 275069 h8g7 h5h4 g7f6 a6b6 f6e5 h4h3 e5d6 h3h2
c6c7 b6b7 d6d7
10+ -192 59 295192 h8g7 a6b6 g7f6 h5h4 f6e5
10& -207 66 321423 h8g7 a6b6 g7f6 h5h4 f6e5 h4h3 e5d6 b6a6
c6c7 a6b7 d6d7
10. -207 96 481186 h8g7 a6b6 g7f6 h5h4 f6e5 h4h3 e5d6 b6a6
c6c7 a6b7 d6d7
11+ -39 104 510968 h8g7 a6b6 g7f6 b6c6 f6e5 c6b5 e5e4 b5c4
e4e5
11& 6 117 559208 h8g7 a6b6 g7f6 b6c6 f6e5 c6b5 e5f4 h5h4
f4g4 h4h3 g4h3
11. 6 503 2557132 h8g7 a6b6 g7f6 b6c6 f6e5 c6b5 e5f4 h5h4
f4g4 h4h3 g4h3
Nodes= 2557132 Eval= 23625 Hash= 23934 Rate= 5140 CPU= 08:17.45
My move is: h8g7
If anyone would care to speculate on Fidelity's programming tricks
for solving this problem, please do.
Stuartutility@quiche.cs.mcgill.ca (Ronald BODKIN) (01/10/90)
(I'd bet on this -- it has a fairly good idea that one should chase enemy pawns and/or protect your own in king-pawns endgames) 2) an outright lookup table at some point (very dubious, given the -0.25 evaluation, where a lookup table would give 0.00 -- I'm curioushow it could produce such an evaluation -- probably they don't have it instructed that king vs. king is a draw (so one king is considered "safer" or "more mobile" by the program). Note that people have constructed such tables for up to 6 pieces, and I'm sure KP vs. KP has been constructed. I've actually written a chess program, so I'll feed your problem to it and report the results. Ron
garth@nyx.UUCP (Garth E. Courtois Jr.) (01/12/90)
In Message-ID: <5785@rice-chex.ai.mit.edu>, Date: 8 Jan 90 00:47:29 GMT Stuart Craycraft writes: > A famous Reti endgame study is listed here with some machine > analysis and a question for the reader. > ... > Fidelity's speed on this problem is incredible. All three programs > use tranposition tables in the search -- so Fidelity must be using > some other trick. > ... > If anyone would care to speculate on Fidelity's programming tricks > for solving this problem, please do. Here are two possible approaches that Fidelity may be using. 1. pruning moves at even ply after only analyzing one move. Large fanouts at even ply can be pruned before they are analyzed with little risk. The root position, with the computer to play, is a ply 0 node. The computer also has node choices at ply 2, 4, 6, etc. If the analysis has found a acceptable node score after analyzing one or two moves, it is safe to stop and prune at this point. There is a good lower bound on the node value and if the position should occur on the board, there are good ways to proceed. The philosophy for this foreward pruning technique is that one has confidence in the move ordering algorithm, and it is more beneficial to examine the game at deeper ply that to expand an internal node's secondary options. In a selective search you have a choice of expanding internal nodes or leaf nodes, and we need a way to select which is more likely to force an improved result. I have never heard of this being programmed. 2. build a selective tree out of sub-trees. This is interesting because it uses the transposition table, and there has been some discussion here about how change of value of table entries can affect the analysis result. In Stuart's message, the Fidelity machine visited about 13 x 1500 = 19,500 nodes. I want to show that the sub-tree below has less than 24K nodes searched. That's dramatically less than Gnuchess' 11 ply 2200 K nodes for the same result! From the Reti position, the tree searched is (a) (b) (c) (d) (e) (f) (g) (h) 1.Kh8g7---h5h4---2.Kg7f6---Ka6b6---3.Kf6e5----h4h3---4.e5d6---h3h2 | | (j) (k) (l) --- h4h3---3.Kf6e6---Ka6a7 and all positions in this "base" tree are analyzed to depth=5 usimg Gnuchess. The tables below show low scores (under -200) until node (g), and node (h) affirms the result of (g). The new discovery is backed up to nodes (f) and (e). The attempt at (d) produces an alternate move for black, and we are led down to node (l). Here it is seen that white achieves equality and the result is backed up to (k) and (j). Black has no "under -200". Values continue to be backed up to (c), (b), and (a). I followed an algorithm, visiting these elven nodes by hand. The details are below and I believe that anyone who can compile gnuchess can get similar results if you make the routine which clears the transposition table a null routine, such that the table isn't cleared between moving and UNDOing. Gnuchess Gnuchess Node White's Node commands moves letter score Count ---------------- -------- ------- ------- ----- depth=5 white 1. Kh8g7 (a) -104 794 black 1... h5h4 (b) -227 795 white 2 . Kg7f6 (c) -424 1253 black 2...Ka6b6 (d) -429 1165 white 3. Kf6e5 (e) -449 1056 black 3... h4h3 (f) -222 1255 white 4. Ke5d6 (g) + 19 2170 black 4... h3h2 (h) + 8 3742 undo, undo, white 4. Ke5e6 (g) + 13 56 undo, undo, black 3...Kb6c6 (f) - 3 696 undo, undo, white 3. Kf6e5 (e) + 2 58 undo, undo, black 2....h4h3 (d/j) -209 699 white 3. Kf6e6 (k) + 1 3493 black 3....h3h2 (l) + 2 5030 undo, undo, white 3. Kf6e6 (k) + 7 54 undo, undo, black 2...Ka6a7 (j) - 53 673 undo, undo, white 2. Kg7f6 (c) - 48 50 undo, undo, black 1....h5h4 (b) - 53 282 undo, undo, white 1. Kh8g7 (a) - 48 25 ------- Total nodes 23346 Nodes (d) and (j) are critical to the Reti position. I went into the transposition table and forced the score of those two nodes to stay zero. These two nodes alone caused the ply 5 iteration to go to -47 and stay near that score for more iterations. My conclusion is that if the Fidelity model with transposition table learning were to play threough these lines as black, it would change its move preference on the second or third play. I am using a 1989 version of Gnu chess, with modifications made by David Furtney. The modifications are primarily an interface to permit interaction with the transposition table. garth@nyx.UUCP alternate: furtney@boulder.Colorado.EDU
cracraft@wheaties.ai.mit.edu (Stuart Cracraft) (01/14/90)
In article <253@nyx.UUCP> garth@nyx.UUCP (Garth E. Courtois Jr.) writes: >I am using a 1989 version of Gnu chess, with modifications >made by David Furtney. The modifications are primarily >an interface to permit interaction with the transposition >table. > > garth@nyx.UUCP > alternate: furtney@boulder.Colorado.EDU Indeed. Would you be willing to contact Furtney to see if he would contribute his transposition interface to GNU? Also, thanks for a very interesting article. Fascinating. Stuart