Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Pawn hashing without Zobrist keys

Author: Ricardo Gibert

Date: 21:41:34 09/12/03

Go up one level in this thread


On September 12, 2003 at 14:13:55, Gerd Isenberg wrote:

>Hi,
>
>i never used Zobrist keys for pawn hashing in IsiChess,
>but 64-bit difference of white and black pawn-bitboards
>modulus some odd tablesize.
>
>Not for speed reasons, but simply because i didn't knew
>it better a few years ago.
>
>Recently i played with some modulus by fixed point
>approximation methods to get rid of the slow 64-bit mod:
>
>http://www.azillionmonkeys.com/qed/adiv.html
>
>I figured out following routine for mod(49981),
>which is an appropriate size for a pawn hash table:
>
>unsigned int mod49981 (unsigned __int64 a)
>{
>  // (2**64 + 49981 - 1) / 49981
>  // is not exact divisible without remainder
>  // 369075130023601.0003001140433 ~ 0x14FAC00053EB1
>  unsigned __int64 m = (0x00014FAC00053EB1 * (a >> 32)
>                      + 0x00014FAC * (a & 0xffffffff));
>  int modulus = (int)(a - (__int64)(m>>32)* 49981);
>  if ( modulus < 0 )  // correct negative results
>    modulus += 49981; // due to the remainder of 0.0003
>  return (unsigned int) modulus;
>}
>
>With compiler's help - inspecting the assembler output,
>i fiddled out following assembler routine. It uses four
>32-bit multiplications, but outperforms the above C-routine
>as well as modulus 64-bit:
>
>unsigned int CPawnHashTable::GetIndex(const CNode &node)
>{
> __asm
> {
>    mov  ecx, [node]
>    mov  eax, 0x00014FAC
>    mov  esi, dword ptr [ecx.m_PawnBB +  0]  ; white pawns low
>    mov  ebx, dword ptr [ecx.m_PawnBB +  4]  ; white pawns high
>    sub  esi, dword ptr [ecx.m_PawnBB +  8]  ; black pawns low
>    sbb  ebx, dword ptr [ecx.m_PawnBB + 12]  ; black pawns high
>    // unsigned int mod49981 (dwordSwapped(whitepawns-blackpawns))
>    mul  esi        ; high dword of the swapped differece
>    mov  ecx, eax
>    mov  eax, 0x00053EB1
>    mul  esi
>    mov  esi, eax
>    mov  eax, 0x00014FAC
>    add  ecx, edx   ; ecx:esi
>    mul  ebx	    ; edx:eax
>    add  esi, eax
>    mov  esi, 49981
>    adc  ecx, edx
>    mov  eax, esi
>    mul  ecx        ; * 49981
>    sub  ebx, eax
>    mov  eax, ebx
>    sar  ebx, 31    ; extend sign bit to mask
>    and  ebx, esi   ; if ( modulus < 0 )
>    add  eax, ebx   ;    modulus += 49981;
>  }
>}
>
>I found mul by 49981 faster on my Athlon, than a lea,add,shift sequence,
>prefered by the MSC6-compiler:
>
>    ; eax = ebx * 49981
>    lea  eax,[ebx+ebx*2]
>    lea  eax,[ebx+eax*4]
>    shl  eax,6
>    add  eax,ebx
>    lea  eax,[eax+eax*2]
>    lea  edx,[eax+eax*4]
>    lea  eax,[ebx+edx*4]
>
>The hitrate with this method (and replace ever scheme)
>is > 85% with the initial position after a one minute search.
>In most testpositions > 95% and up to 99.9% (e.g. fine 70).
>
>If you do pawn hashing in a similar "modulus 64-bit" way,
>regardless whether using Zobrist keys or not, you may try
>this routine - feedback and suggestions welcome.
>
>Regards,
>Gerd


Just use zobrist hashing with a power of 2 table size? I don't understand the
motive to do otherwise.




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.