Author: Gerd Isenberg
Date: 14:20:39 11/17/04
Go up one level in this thread
On November 16, 2004 at 13:04:45, Dieter Buerssner wrote:
>Hi Gerd,
>
>I made a similar experience. Some while ago, I programmed the "pawn game" (it
>was discussed here, chess board, only pawns, no kings). When implementing
>hashing, I remembered your idea of some simple arithmetics on the pawn bitboards
>to get a hash key. I cannot remember all details, but I remember that it was
>significantly worse than others schemes I tried. Best really seems to be
>Zorbrist like hashing. I used a variant that is almost equivilant. Have a look
>up table of zob_key[12][156]. 12 for the 12 bytes in the two bitboards, and then
>I added (instead of xor) the values together. I doubt, that incremental hashkeys
>would be much faster. But certainly more work and more possibilities for errors.
>
>Still better than simple arithmetics was the following idea. I considered the 2
>bitboards as the state of a PRNG (a multiply with carry generator), and
>calculated a "random number" out of this state.
>
>INLINE HASH_ENTRY *calc_idx(int side, POSITION *pos)
>{
> unsigned long idx, l1, l2;
> /* The const slows down this code by a factor of 10 on some K6 */
> static /* const */unsigned long mul=2051013963UL; /* 999996864UL */
> unsigned long *lp = (unsigned long *)pos->pawns;
>
> l2 = lp[0];
> l1 = lp[1];
> idx = l2+l1*mul;
> l2 = lp[2];
> l1 = lp[3];
> idx += l2+l1*mul;
> idx = (idx%hentries)*3; /* cluster 3 entries per pos together *(
> // idx = ((unsigned long)((hentries * (unsigned long long)idx)>>32))*3;
> return htable[side]+idx;
>}
>
>Regards,
>Dieter
Hi Dieter,
after Richard's reply it seems my hit-rate is not that bad with
( 5* whitepawnBB - 3*blackpawnBB ) % 65077
The "pure" hit-rate is really based on the huge number of pawn positions with
"fast" saturation of a 64-K-entry pawn hash table (10 seconds).
The difference of odd (prime) multiplies seems more intuitive than the
commutative add to me, since no bit is set in both sets.
As Johan de Koning mentioned recently during Dutch Open,
( whitepawnBB - blackpawnBB ) % TBLSIZE
sucks a bit, due to this simple collision with only three changed pawns:
White 1000 or 0100
-Black -0100 -0000
= 0100 0100
Cheers,
Gerd
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.