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.