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.