Author: Dieter Buerssner
Date: 09:25:57 02/02/05
Go up one level in this thread
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). >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." 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. 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.
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.