Computer Chess Club Archives




Subject: Re: not using nullmove?

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).


This page took 0.05 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.