Author: Vincent Diepeveen
Date: 08:32:43 02/03/05
Go up one level in this thread
On February 02, 2005 at 12:25:57, Dieter Buerssner wrote: >On February 01, 2005 at 14:45:57, Marc Bourzutschky wrote: > >>On February 01, 2005 at 12:39:55, Dieter Buerssner wrote: >> > >>>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. > >It must have taken quite some time, to understand Eugene's code that far, that >you can do such changes. I wonder one thing: Could you code a reverse index >function (that runs efficiently)? The non blockable checks trick should make >this rather difficult!? > >>To do KQPKQ in 10 minutes on your hardware is awfully fast. You can do that >>using only 2 bits per position? > >The algorithm in theory only needs 1 bit random access memory per position (or >if you want, per 1/half position, if you count wtm/btm seperately). I also >implemented it like this, but can use the other stuff from RAM, too, instead of >from disk. So for those runs, I used 2 bits + 2 bytes RAM. But the number of >positions is small, because I consider different pawn positions as different >TBs. So for KQPKQ I need 3612 * 62 * 61. I cannot use the symmetry on the king >part of the position (I use it on the pawn part), so I cannot use the "normal" >1806 multiplier. > > >>>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. > >I remember it, I think. Much later, Urban posted again about it, perhaps even >here on CCC. Or perhaps Vincent cited some post of him? I was not that >interested in a generator at the time, so I did not try hard to understand the >posts (fast reading was not enough). I'm not using Urbans original idea. In diep's generator a modification of it inspired by Urban which i already formulated years ago somewhere. Practical it is very hard to implement it in such a way that you both reduce i/o and memory usage to levels that my hardware supports. Also i just am busy purchasing a raid5 array and writing is a lot slower than reading. Writing is simply harddisk speed (50MB/s) versus reading a lot more than that. The problem is with certain 7-men that can do en passant, which obviously are the most interesting to generate. KRPP KRP is the goal. That requires an EGTB or 35 to be generated first. Quite some work. >>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... > >Thanks, I think I got the idea. But I will need a bit of time. > >Regarding Thompson's algorithm - yes you are right, that he used only bits of >memory per positon. From the Wu Beal paper: "The retrograde algorithm used to >construct the databases demand large computing resources. Thompson's 1986 >algorithm (Thompson, 1986) needs two bits of RAM for every board configuration, >or random access to disc files, and it only gives one side's result." The entire 'unmakemove' idea of Thompson is just nuts if you ask me. >I fear not many are reading here anymore, but I can try to ask a favor anyway. >Would anybody be so kind, and send me a scanned in copy of this article? > >Thompson, K. (1986). Retrograde Analysis of Certain Endgames. ICCA Journal, >Vol. 9, No. 3. 131-139. there is article in advances in icca volume 8 too about this (if i remember the number from head correct). >From the Wu Beal article again: > >"His second paper (Thompson, 1996) gives details of an improved algorithm he >used to solve 6-piece chess endgames." > >But this article is only given as: > >Thompson, K. (1996). 6-Piece Endgames. > >No journal is given. If you know what exactly is meant and have it, I'd be >interested in it, too. > >Regards, >Dieter > >Antwort auf die mail folgt demnächst. CC me please.
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.