Author: Marc Bourzutschky
Date: 11:45:57 02/01/05
Go up one level in this thread
On February 01, 2005 at 12:39:55, Dieter Buerssner wrote: >On January 31, 2005 at 08:11:18, Marc Bourzutschky wrote: > >>Unlike Thompson, I did not use a "fully-retro" algorithm, i.e., instead of >>obtaining lost in N by backing up (with reverse moves) from wins in N and then >>verifying that the backed up positions are indeed lost in N, I simply loop over >>the still unresolved positions and determine lost in N by checking whether all >>(forward) moves end on the other side winning in <= N. Unless there are a lot >>of draws there is probably not much benefit, if any, in doing a fully retro >>algorithm. > >I assume, your generator is rather general. How long does it take to generate >KBBKN or KQPKQ? (From memory those belong to the toughest ones of the 5-men). I >have a generator that is very similar to Wu Beal and fully retro. The mentioned >TBs take about 10 minutes on my P4 2.53; the old Nalimov generator, that was >available at Hyatt's ftp took over 8 hours on the same computor). > Actually, I only implemented KNNNNKQ as a one-off, so I have no general generator at all. I have done a number of changes to the Nalimov generator, mainly to look at different size chessboards, metrics, fairy pieces, etc. To do KQPKQ in 10 minutes on your hardware is awfully fast. You can do that using only 2 bits per position? >>For the 1 ply consistency check I actually transformed the four output files >>(KNNNNKQ and KQKNNNN with both white and black to move) to the Nalimov format, >>including the non-blocking check trick. I then added code to Eugene's program >>for KNNNNK and KNNNNKQ (pretty ugly) and ran his verification option. > >What exactly is the verifaction option doing? > Verification loops through all positions, does a 1-ply search through all relevant subtables (or opposites), applies minimax, and compares the result to the table entry for consistency. Since there is some code overlap between the generator and this verification it will not catch all bugs, but it does catch a good number. >And another question from your original post: >"Originally I had planned to implement a general 7-man tablebase generator using >Johan de Koning's clever algorithm which requires very little memory." > >Is the algorithm published? Or your private knowledge (that you want/have to >keep for yourself)? > There was a related post by Urban Koistinen a long time ago (1990s) on rec.games.chess, which I can't put my hands on at the moment. Then there is the FEG generator, downloadable from www.chessmaster.com (it seems you have to go to the old chessmaster 9000 section to find the download link.) There is no description of the algorithm, but I think I pieced most of it together from conversations with Johan, and by looking at what kind of files are created during generation. The basic idea is very simple. Suppose it is white to move, and lost positions for black are stored with the black pieces in the most significant bits, and the white pieces in the least significant bits. Since the position of the black pieces does not change when white moves, backing up wins from losses only requires random access to the white pieces. The complication is that switching the side to move flips the color of the most significant bits...
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.