Author: David Eppstein
Date: 22:52:51 05/30/99
Go up one level in this thread
On May 30, 1999 at 08:29:56, Robert Hyatt wrote: >On May 29, 1999 at 23:31:38, Jeremiah Penery wrote: >>Someone wrote a fix for this and it was posted in the Crafty mailing list...I >>haven't payed much attention to whether it works always/sometimes/never, or >>whether it works very well, but it *seemed* to solve the problem. >>It'll make Crafty drop out of TBs if there is a good promotion move, but there >>is no TB for the promotion. > >It isn't simple, because I do things like stop the extra parallel threads when >in a tablebase position, etc. Searching the odd promotions would take a little >thought as we would want those threads back.. > >And the main point is, _why_? Because it will screw up the normal search >since a P on the board says mate in N, but a Q on the board doesn't say mate. >This means a search from a position where the promotion can be forced many >plies into the tree looks like a bad move to the search. > >Again, get 'em all, or don't get the P database in question... As Jeremiah wrote, it should no longer be necessary to get all the tablebases for all the easy promotion cases, since it is possible to use code similar to your "swindle mode" to make a good move from a tablebase to a non-tablebase position. Tim Hollebeek posted code for this to the Crafty mailing list on February 27, with a correction March 10. I'm enclosing a portion of his message below since the technique may be of interest for other programs: From: Tim Hollebeek <tim@wagner.princeton.edu> To: David Eppstein <eppstein@ics.uci.edu> Cc: crafty@jpunix.com Subject: Re: [crafty] TB Question Date: Sat, 27 Feb 1999 11:19:16 -0500 (EST) David Eppstein writes ... > > This does sound like a better idea. So the algorithm would be: > > if (you're currently in a tablebase position where you can promote && > the tablebase for the position after the promotion is missing && > your current score is mate-in-n && > none of the non-promotion moves lead to mate-in-(n-1)) > then do a search restricted to the promoting moves. > > Crafty's swindle mode already does a similar constrained search, how much > more work could another one be? Thanks for the idea. I looked at the swindle code, and found it is very easy to do "the right thing" in RootMoveList(), instead of fiddling with SearchRoot() like my previous hack. This one is much more elegant and, more importantly, has no obvious holes. It turns out that RootMoveList() already does the necessary EGTB checks due to the swindle code. My patch looks at the score of the current position, and if it is a EGTB mate, figures out what the score of the "correct" next move is. From the way the EGTBs are generated, we know a move exists that has that score. Now, when generating the move list, we discard all moves that (1) are in the EGTB, but (2) have a score worse than the expected score. The EGTB is telling us this is *not* the right move, despite the fact it is a mate. Now there are two cases: #1: we do have the TB that contains the continuation of the mate. In this case the correct move is in the root move list, and it is impossible for any other move to have a better score. So discarding "worse" moves has no effect on which move is played. #2 (the important case): the "correct" move is a capture or promotion moves us to a TB we don't have. In this case, our root move list consists only of moves that leave the TB. This is very likely to find the "correct" move, since the only way it can fail is positions which have more than one move that leaves the TB, one which wins, the other(s) which draw or lose, and it isn't obvious to a search which is best. Such positions would be rather fascinating, but probably exceedingly rare. Attached is a diff, and an example of crafty playing a position (with KNKP) it often screws up if it doesn't have the KNKQ TB. Note that crafty plays the obvious move "b1=Q" at the correct point, instead of moving its king around aimlessly. [ diff deleted - DE 5/30/99 ] --- EPD Kit revision date: 1996.04.21 unable to open book file [./book.bin]. book is disabled unable to open book file [./books.bin]. Crafty v16.5 White(1): egtb 4 EGTB access enabled using tbpath=./TB 4 piece tablebase files found 54kb of RAM used for TB indices and decompression tables White(1): ponder off pondering disabled. White(1): level 0 1 1 game/1 minutes primary time control increment 1 seconds. White(1): setboard KN/////kp b Black(1): go end-game phase clearing hash tables time limit 2.71 (16.26) [easy move] depth time score variation (1) 4 0.05 Mat15 1. ... b2 2. Kb7 Kb4 <EGTB> 4-> 0.05 Mat15 1. ... b2 2. Kb7 Kb4 <EGTB> time=0.18 cpu=16% mat=-2 n=494 fh=77% nps=2744 ext-> checks=43 recaps=0 pawns=5 1rep=0 predicted=0 nodes=494 evals=24 endgame tablebase-> probes done=46 successful=16 plimit=6 hashing-> trans/ref=34% pawn=96% used=0% mate in 15 moves. Black(1): b2 time used: 0.18 White(2): go clearing hash tables time limit 2.73 (16.38) depth time score variation (1) 10 0.67 -Mat14 2. Nc6 Ka4 3. Kb7 <EGTB> 10-> 0.67 -Mat14 2. Nc6 Ka4 3. Kb7 <EGTB> 11 2.59 -Mat14 2. Nc6 Ka4 3. Kb7 <EGTB> 11-> 2.59 -Mat14 2. Nc6 Ka4 3. Kb7 <EGTB> time=2.95 cpu=91% mat=2 n=77662 fh=98% nps=26326 ext-> checks=11587 recaps=3 pawns=0 1rep=231 predicted=0 nodes=77662 evals=63 endgame tablebase-> probes done=10035 successful=337 plimit=16 hashing-> trans/ref=67% pawn=98% used=4% mated in 14 moves. White(2): Nc6 Black(2): go clearing hash tables time limit 2.68 (16.08) depth time score variation (1) time=0.30 cpu=56% mat=-2 n=4510 fh=95% nps=15033 ext-> checks=480 recaps=0 pawns=20 1rep=32 predicted=0 nodes=4510 evals=1 endgame tablebase-> probes done=486 successful=0 plimit=8 hashing-> trans/ref=96% pawn=0% used=0% Black(2): b1=Q White(3): go clearing hash tables time limit 2.70 (16.20) depth time score variation (1) 6 0.58 -7.00 3. Nb8 Ka4 4. Ka7 Qb2 5. Ka8 Ka5 6-> 0.62 -7.00 3. Nb8 Ka4 4. Ka7 Qb2 5. Ka8 Ka5 7 0.92 -7.11 3. Nb8 Ka4 4. Ka7 Ka5 5. Nc6+ Kb5 6. Nd8 Kc5 7-> 1.74 -7.11 3. Nb8 Ka4 4. Ka7 Ka5 5. Nc6+ Kb5 6. Nd8 Kc5 8 2.18 -7.11 3. Nb8 Ka4 4. Ka7 Ka5 5. Nc6+ Kb5 6. Nd8 Qh7+ 7. Kb8 Ka6 8-> 2.36 -7.11 3. Nb8 Ka4 4. Ka7 Ka5 5. Nc6+ Kb5 6. Nd8 Qh7+ 7. Kb8 Ka6 time=2.87 cpu=90% mat=-6 n=68235 fh=88% nps=23775 ext-> checks=9689 recaps=0 pawns=0 1rep=276 predicted=0 nodes=68235 evals=1 endgame tablebase-> probes done=12120 successful=0 plimit=13 hashing-> trans/ref=79% pawn=0% used=4% White(3): Nb8 Black(3): go clearing hash tables time limit 2.64 (15.84) depth time score variation (1) 6-> 0.47 7.11 3. ... Ka4 4. Ka7 Qb5 5. Ka8 Ka5 6. Ka7 7 0.63 7.11 3. ... Ka4 4. Ka7 Qb5 5. Ka8 Ka5 6. Ka7 Qb1 7-> 0.96 7.11 3. ... Ka4 4. Ka7 Qb5 5. Ka8 Ka5 6. Ka7 Qb1 8 1.32 7.11 3. ... Ka4 4. Ka7 Qb5 5. Ka8 Ka5 6. Ka7 Qd5 7. Na6 8 2.68 ++ 3. ... Qb6!! time=2.81 cpu=91% mat=6 n=70507 fh=94% nps=25091 ext-> checks=11343 recaps=0 pawns=0 1rep=240 predicted=0 nodes=70507 evals=1 endgame tablebase-> probes done=10235 successful=0 plimit=12 hashing-> trans/ref=91% pawn=0% used=3% Black(3): Qb6 White(4): go clearing hash tables time limit 2.59 (15.54) [easy move] depth time score variation (1) 6 0.70 -9.85 4. Nd7 Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 6-> 0.73 -9.85 4. Nd7 Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 7 1.33 -10.08 4. Nd7 Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 7-> 1.36 -10.08 4. Nd7 Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 8 2.62 -10.11 4. Nd7 Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 time=2.75 cpu=91% mat=-6 n=70063 fh=99% nps=25477 ext-> checks=13617 recaps=0 pawns=0 1rep=344 predicted=0 nodes=70063 evals=1 endgame tablebase-> probes done=4335 successful=0 plimit=10 hashing-> trans/ref=94% pawn=0% used=3% White(4): Nd7 Black(4): go clearing hash tables time limit 2.54 (15.24) depth time score variation (1) 5 0.56 9.85 4. ... Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 5-> 0.71 9.85 4. ... Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 6 1.04 10.08 4. ... Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 6-> 1.35 10.08 4. ... Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 7 2.25 10.11 4. ... Qc6+ 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 time=2.70 cpu=88% mat=6 n=65868 fh=99% nps=24395 ext-> checks=12969 recaps=0 pawns=0 1rep=302 predicted=0 nodes=65868 evals=1 endgame tablebase-> probes done=4576 successful=0 plimit=11 hashing-> trans/ref=109% pawn=0% used=91% Black(4): Qc6+ White(5): go clearing hash tables time limit 2.49 (14.94) depth time score variation (1) 5 0.52 -9.85 5. Ka7 Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 5-> 0.52 -9.85 5. Ka7 Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 6 0.87 -10.08 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 6-> 0.89 -10.08 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 7 1.80 -10.11 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 7-> 1.81 -10.11 5. Ka7 Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 time=2.67 cpu=91% mat=-6 n=67947 fh=99% nps=25448 ext-> checks=13939 recaps=0 pawns=0 1rep=281 predicted=0 nodes=67947 evals=1 endgame tablebase-> probes done=2006 successful=0 plimit=9 hashing-> trans/ref=104% pawn=0% used=3% White(5): Ka7 Black(5): go clearing hash tables time limit 2.45 (14.70) depth time score variation (1) 4 0.45 9.85 5. ... Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 4-> 0.52 9.85 5. ... Qxd7+ 6. Ka6 Kb4 7. Kb6 Qc8 5 0.80 10.08 5. ... Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 5-> 0.90 10.08 5. ... Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 6 1.70 10.11 5. ... Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 6-> 1.88 10.11 5. ... Qxd7+ 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 time=2.57 cpu=89% mat=6 n=61042 fh=99% nps=23751 ext-> checks=12546 recaps=0 pawns=0 1rep=257 predicted=0 nodes=61042 evals=1 endgame tablebase-> probes done=6607 successful=0 plimit=11 hashing-> trans/ref=114% pawn=0% used=5% Black(5): Qxd7+ White(6): go clearing hash tables time limit 2.40 (14.40) depth time score variation (1) 4 0.43 -9.85 6. Ka6 Kb4 7. Kb6 Qc8 4-> 0.43 -9.85 6. Ka6 Kb4 7. Kb6 Qc8 5 0.69 -10.08 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 5-> 0.73 -10.08 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 6 1.51 -10.11 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 6-> 1.52 -10.11 6. Ka6 Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 time=2.51 cpu=90% mat=-9 n=63254 fh=99% nps=25200 ext-> checks=13409 recaps=0 pawns=0 1rep=217 predicted=0 nodes=63254 evals=1 endgame tablebase-> probes done=5455 successful=0 plimit=9 hashing-> trans/ref=112% pawn=0% used=2% White(6): Ka6 Black(6): go clearing hash tables time limit 2.36 (14.16) depth time score variation (1) 5 0.46 10.11 6. ... Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 5-> 1.35 10.11 6. ... Ka4 7. Kb6 Kb4 8. Ka6 Qb5+ 9. Ka7 Ka5 6 1.67 10.08 6. ... Ka4 7. Kb6 Kb4 8. Ka6 Qc6+ 9. Ka7 Qc7+ 10. Ka6 Kc4 time=2.66 cpu=91% mat=9 n=67550 fh=99% nps=25394 ext-> checks=14374 recaps=0 pawns=0 1rep=204 predicted=0 nodes=67550 evals=1 endgame tablebase-> probes done=6947 successful=0 plimit=9 hashing-> trans/ref=111% pawn=0% used=5% Black(6): Ka4 White(7): go clearing hash tables time limit 2.31 (13.81) [easy move] depth time score variation (1) time=0.21 cpu=38% mat=-9 n=1760 fh=99% nps=8380 ext-> checks=378 recaps=0 pawns=0 1rep=10 predicted=0 nodes=1760 evals=1 endgame tablebase-> probes done=258 successful=0 plimit=7 hashing-> trans/ref=117% pawn=0% used=2% White(7): Kb6 Black(7): go clearing hash tables time limit 2.33 (13.98) depth time score variation (1) 5 0.55 ++ 7. ... Kb4!! 5 0.55 Mat03 7. ... Kb4 8. Ka6 Kc5 9. Ka5 Qb5# 5-> 1.31 Mat03 7. ... Kb4 8. Ka6 Kc5 9. Ka5 Qb5# time=1.44 cpu=86% mat=9 n=34779 fh=99% nps=24152 ext-> checks=7547 recaps=0 pawns=0 1rep=170 predicted=0 nodes=34779 evals=1 endgame tablebase-> probes done=2819 successful=0 plimit=9 hashing-> trans/ref=104% pawn=0% used=1% mate in 3 moves. Black(7): Kb4 White(8): go clearing hash tables time limit 2.32 (13.91) [easy move] depth time score variation (1) time=0.31 cpu=51% mat=-9 n=4614 fh=99% nps=14883 ext-> checks=853 recaps=0 pawns=0 1rep=67 predicted=0 nodes=4614 evals=1 endgame tablebase-> probes done=268 successful=0 plimit=6 hashing-> trans/ref=126% pawn=0% used=87% mated in 2 moves. White(8): Ka6 Black(8): go clearing hash tables time limit 2.34 (14.04) depth time score variation (1) 3 0.05 Mat02 8. ... Kc5 9. Ka5 Qb5# 3-> 0.20 Mat02 8. ... Kc5 9. Ka5 Qb5# 4 0.21 Mat02 8. ... Kc5 9. Ka5 Qb5# 4-> 0.75 Mat02 8. ... Kc5 9. Ka5 Qb5# time=0.88 cpu=78% mat=9 n=19571 fh=100% nps=22239 ext-> checks=3936 recaps=0 pawns=0 1rep=178 predicted=0 nodes=19571 evals=1 endgame tablebase-> probes done=449 successful=0 plimit=5 hashing-> trans/ref=114% pawn=0% used=0% mate in 2 moves. Black(8): Kc5 White(9): go clearing hash tables time limit 2.34 (14.04) [easy move] depth time score variation (1) time=0.21 cpu=38% mat=-9 n=2132 fh=100% nps=10152 ext-> checks=404 recaps=0 pawns=0 1rep=33 predicted=0 nodes=2132 evals=1 endgame tablebase-> probes done=127 successful=0 plimit=6 hashing-> trans/ref=58% pawn=0% used=3% mated in 1 moves. White(9): Ka5 Black(9): go clearing hash tables time limit 2.37 (14.22) depth time score variation (1) 1 0.00 ++ 9. ... Qb5#!! 1 0.00 Mate 9. ... Qb5# 1-> 0.01 Mate 9. ... Qb5# 2 0.01 Mate 9. ... Qb5# 2-> 0.03 Mate 9. ... Qb5# 3 0.03 Mate 9. ... Qb5# 3-> 0.11 Mate 9. ... Qb5# 4 0.11 Mate 9. ... Qb5# 4-> 0.35 Mate 9. ... Qb5# time=0.48 cpu=60% mat=9 n=8453 fh=99% nps=17610 ext-> checks=1629 recaps=0 pawns=0 1rep=94 predicted=0 nodes=8453 evals=1 endgame tablebase-> probes done=396 successful=0 plimit=6 hashing-> trans/ref=74% pawn=0% used=0% Black(9): Qb5# 0-1 {Black mates}
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.