Author: Urban Koistinen
Date: 22:38:02 04/08/01
Go up one level in this thread
On April 08, 2001 at 09:49:13, Tony Werten wrote: >On April 07, 2001 at 11:18:34, Urban Koistinen wrote: > >>I have written down a algorithm for computing endgame tablebases that should be >>about 10 times quicker than the Nalimov algorithm and requires much less ram. >>It is similar to the Arlazarov&Futer algorithm of 1979 but is more general as it >>does not require a pawn. >>It might be too technical for most here, but if anyone has questions I will try >>to answer them. > >I don't claim I completely understand it, but here are some remarks. > >- It better be smaller than Nalimov tables. Nalimov uses 16 bits to give >distance to mate, you use 1 bit to show wether it's a win. 14 bits/position (regardless of side to move) of disk space is needed while computing. Once the computation is done 8 bits/position is needed to store the result. 1 bit for black to move and lose, 1 bit for white to move and win and 6 for distance to conversion with white to move. >- t100 black lose with g50=100 > t99 white win with g50=99 > >Where's t100 white win with g50=100 ? ie Why do you assume white has made the >last move that sets the counter back to 100; it could have been black. If black had made the last move and it would matter, there would have to be a forced black capture/pawn move with g50=0 in the critical path. As far as I know no one has managed to construct such a position, so it does not seem to matter. >- combining tables t0 to t98 with 6 bits/position is the real challenge I think. I only bother with t1, t3, ..., t99, as they can be examined more cheaply. (Examining t0, t2, ..., t100, would increase the i/o cost by about 1/6.) When t3 is computed, the difference between t1&t3 is stored with run length encoding. Same for t3&t5, t5&t7, etc. To combine, use (t99 or t1) with the difference files to find when each bit got set. >- Using the tables: How do you make sure you make any progress? ie From current >position I have 2 moves. One checkmate in 10, one in 20. How do you see the >difference ? Both moves will have counter g50-1, both will be a win. I don't see the difference. I think a slow but sure win is good enough. Progress is ensured by the 50 move rule. Urban Koistinen
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.