Author: Gerd Isenberg
Date: 11:13:55 09/12/03
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
This page took 0.02 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.