Xref: utzoo rec.games.chess:3775 gnu.chess:89 comp.ai:5492 Path: utzoo!telly!philmtl!uunet!bu.edu!bu-cs!lll-winken!brutus.cs.uiuc.edu!uakari.primate.wisc.edu!pikes!udenva!isis!nyx!garth From: garth@nyx.UUCP (Garth E. Courtois Jr.) Newsgroups: rec.games.chess,gnu.chess,comp.ai Subject: Re: A Study by Reti Summary: Two methods for faster chess analysis Keywords: Fidelity speculation, computer chess, foreward pruning, Message-ID: <253@nyx.UUCP> Date: 11 Jan 90 20:30:32 GMT References: <5785@rice-chex.ai.mit.edu> Reply-To: garth@nyx.UUCP (Garth E. Courtois Jr.) Organization: Public Access Unix - University of Denver Lines: 115 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