Author: Dieter Buerssner
Date: 15:21:24 08/30/05
Go up one level in this thread
On August 30, 2005 at 05:11:07, Joachim Rang wrote: > >>Or you can store 2 tables -- one with Win/No Win, and other with Lost/No Lost. >>Presumable they will compress even better, and in lot of cases during the search >>you will probe only one of them, because that is all you need to know. >> > >Just a crazy idea from a non-techie: Couldn't you store only win/draw in a table >and simply skip all lost positions and tell the chess program that in case there >is no entry for a position it is lost? Uri was pretty correct with his reply. A very simplified example how TBs are stored. Assume KQK. Enumerate squares (in any order you wish) from 0 to 63. For a concrete position, calculate index = square(wK)*64*64 + square(bK)*64 + square(Q). You can probably convince yourself easily, that each possible KQK position will yield in a different index. Use that index as an offset into the actual TB data (into the physical file on the disk, for example). The byte at that offset will have the game theoretical result of this position stored (value 0 of that byte may mean: mated, value 1 mated in one, ... value 128 draw, value 254 mate in 2, 255: mate in one). You would have a file size of 64*64*64 bytes for each side to move with this scheme. There is no way to not store lost positions (which will not happen in kqk - but you get the general idea) with such an index calculation. BTW. This could be considered a perfect hash function - each different position yields a different hash value (index above). The index space is extremely dense (contrary to typical perfect hash functions). In practice, more complicated index functions will be used, that will take symmetry into account and avoid allocating space for many illegal positions. Above simple formula would allocate space for positions, where all 3 men are on the same square, or positions, where both kings are on adjacent squares. Regards, Dieter
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.