Author: Dieter Buerssner
Date: 10:47:11 02/18/04
Go up one level in this thread
On February 17, 2004 at 21:02:38, Dann Corbit wrote: >>One step further: >>For the list of possible board positions for a given class (e.g. KRK) create a >>list of them. Then create a perfect hash for these positions. Actually, I think the index functions used for adressing TBs (or W/D/L "bitbases") is a perfect hash function (I however do not know the exact definition of it). Note, that for KRK, one bit per position is enough: there are no losses for the R-side. Also, there is no need to give a broken position a special value - it can be detected by other means. >>Then, in your program, the table holds: >>HASHVAL, won/lost/drawn/brokenbits >> >>If (for instance) there were 65,000 possible postions after all reflections and >>rotations, then you would only need 18 bits per position to store the hash and >>the answer. > >The position could be implicit [based on the hash value], requiring only 2 bits >per position. If it were that compact, you would need a bitset/bitget operation >to pull the bits, since you can't address something smaller than one character. I use 1.6 bits per position for W/D/L bases. You may think, that in TBs typically positions are saved until now. They are implicit as you suggested. For example, I use 3612*61*24/5 bytes for KRKP. There are 3612 legal K-K positions, 61 squares left for the R, and 48 for the P. But we can force the P always onto one side of the board by mirroring. The devisor of 5 is, because there can be stored 5 W/D/L results in one byte (3^^5 < 2^^8). One could also save a bit by indexing the pawn higher, which would give 3612*24*60/5 bytes. Nalimov has few more trick: he can get rid of some broken positions with his indexing formulas: namely some unblockable checks. With white to move, for example there can never be a wR on a2 or b1, when the black K is on a1 (and similar for all other bK squares). This saves a bit more space (especially with a Q or a N). Regards, Dieter
This page took 0.04 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.