Author: Marc Bourzutschky
Date: 05:11:18 01/31/05
Go up one level in this thread
On January 31, 2005 at 06:47:17, Dieter Buerssner wrote: >On January 30, 2005 at 02:51:33, Marc Bourzutschky wrote: > >Thanks for the nice and interesting article. > >>However, >>I got lazy and used the same basic scheme as Ken Thompson in his pioneering >>work. This is rather memory hungry, but even using 1 bit of RAM for every >>position in the state space requires less than 2G for KNNNNKQ, and so can be >>done even within the 2G virtual memory restriction on Windows XP. > >I calculate > 462*62*61*60*59*58/(4!*8) = ~1.9e9 bytes for one bit vector (without the non >blocking check trick of Eugene). Is one bit vector enough? Did you use the Wu >Beal method? Did Thompson already use bit vectors? (It is not totally clear from >the above, whether you fully followed Thompson, or perhaps just used his >indexing). > Yes, I did exactly your calculation and because the result magically turns out to be just under 2G I knew I could do it on XP. As far as I know, using more than 2G of memory is not possible under XP, unless booting with special switches and/or using special software, which I'm not familiar with. My method is probably closest to Wu Beal, which in itself is only a small variation on Thompson's algorithm. I'm pretty sure Thompson used bit vectors (with 2 bits per position) in his 6-man work. Like Thompson, I only resolve win vs non-win, so KNNNNKQ and KQKNNNN need to be run separately to distinguish the knights drawing from the knights losing. 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. 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. The fact that it passed makes me pretty confident that there are no bugs, but of course you never know... -Marc
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.