Author: Roberto Waldteufel
Date: 19:54:49 10/09/98
Go up one level in this thread
On October 09, 1998 at 18:46:36, David Eppstein wrote: >On October 09, 1998 at 15:24:26, Robert Hyatt wrote: >>This doesn't matter however, because *every* possible position must be accounted >>for, with an exact distance to mate for the side on move with that specific >>piece configuration. So they *all* have to be computed to build the next one >>after them... > >You don't need distance to mate if you are searching from a non-tablebase >position trying to reach a tablebase position (and aren't worried about the 50 >move rule, but you must not be since you're using distance to mate). > >If the actual game reaches a won tablebase position, you need some way to force >progress, but it doesn't have to be distance to mate. If you can always search >deeply enough to find a conversion (capture or pawn move), you can use distance >to conversion, and only store win/loss/draw in the tablebase. In any KXP-KP or >KX-KPP endgame, searching deeply enough to find a conversion should be easy >(there are fewer than a million distinct positions in which at most one pawn has >moved, so you can load just that part of the tablebase into memory and use the >hashtable to do the search quickly no matter how deep it is). > >But I agree with your main point, that the heuristics suggested by the poster >you were responding to aren't good enough -- the information needs to be exact, >and you need to compute lots of other tablebases before you can think about >KPP-KP. Even if the search were too deep to be feasible, eg an ending like KBBKN, it is still possible to reduce memory access requirements during the search by storing only win/loss/draw information, if we maintain a separate tablebase (not used in the search) which simply contains the best move (regardless of win/loss/draw status) for each position. If the game reaches a tablebase position, we just look up the best move at the root, without even doing a 1 ply search. Some time back I implemented a KPK tablebase in this way, with 1 bit per position to store win/draw (the stronger side can never lose), and a separate table of moves which is only accessed at the root. I generated these myself, without knowing much about how it was done in other programs, not realising that the approach is a little unusual. I subsequently developed "best move tables" for the simple mates KQK and KRK, which do not need separate win/loss/draw information, since the stronger side to move always wins. The program could win these positions without tables, but was very inefficient in doing so. I find this method works very well, but I have not extended the idea to any of the 4 piece endings, since it is much more complicated to generate the data. I thought I might obtain the Stephen Edwards tablebases and use them to construct files of the type I have described, since this may be easier than generating everything from scratch. Best wishes, Roberto
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.