Author: Anthony Cozzie
Date: 12:28:55 11/17/02
Go up one level in this thread
On November 17, 2002 at 12:01:02, Gerd Isenberg wrote:
>On November 17, 2002 at 10:53:05, Joel wrote:
>
>>Hey All,
>>
>>I am a 2nd year Uni student from Australia who has recently gotten into chess
>>programming. My first attempt was a simple array-based alpha-beta variant which
>>struggled to search more than 6 levels deep in most positions! I think that
>>might have something to do with the fact that there was no move ordering,
>>transposition table, an expensive evaluation function, no killer moves and weak
>>coding :)
>>
>>I have been working on my second attempt for some time now. It uses Bitboards. I
>>have a few questions regarding move generation.
>>
>>It seems to me that the performance of the Bitboard approach relies somewhat
>>heavily on how fast you can retrieve the position of a 1 bit within a 64-bit
>>unsigned integer. I looked for sometime on the Internet for some kind of
>>magical, hacky solution to this dilemna, and the best I could find was this (b &
>>-b) trick which I used in a debatedly clever way. I was just wondering if there
>>is any approach significantly better than the one which I will outline below:
>>
>>1. (b & -b) to clear all 1 bit's except for one.
>>2. get this value, mod it by 67 (which has the property that every possible
>> value returned is unique, thus i can hash to the position of the bit in the
>> 64 bit integer.)
>>
>>I am no expert, but it doesn't seem too ineffecient to me. Any problems?
>>
>>Also, if there are any improvements, I would prefer to find out about the ones
>>which do not involve assembly coding - I do not want to make my program too
>>dependant on any one CPU architecture at this stage.
>>
>>Thanks for your time,
>>Joel
>
>Hi Joel,
>
>nice idea with the mod 67 to get unique bitvalues. But i fear a 64 bit div/mod
>operation is too slow, even with 64bit-processors. If you don't want to use
>assembler eg. intels x86 bsf (bit scan foreward), i think using a lookup table
>indexed by the byte or 16-bit word is most common.
>
>I use this approach:
>
>#define LOWBOARD(bb) (*((UINT32*)&(bb)))
>#define HIGHBOARD(bb) (*(((UINT32*)&(bb))+1))
>
>// precondition: bb not null
>__forceinline UINT BitSearch(BitBoard bb)
>{
> ASSERT(bb != 0);
>#ifdef _M_IX86
> __asm
> {
> bsf eax,[bb+4]
> xor eax, 32
> bsf eax,[bb]
> }
>#else
> BitBoard lsbb = bb & (-(__int64)bb);
> UINT32 lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
> return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
> +((lsb & 0xffff0000)!=0))<<1)
> +((lsb & 0xff00ff00)!=0))<<1)
> +((lsb & 0xf0f0f0f0)!=0))<<1)
> +((lsb & 0xcccccccc)!=0))<<1)
> +((lsb & 0xaaaaaaaa)!=0);
>#endif
>}
>
>Regards,
>Gerd
Could you compare (or have you already tried) the following with BSF? I tried
using BSF in zappa with terrible results. I thought this was because BSF
actually scans the entire integer using uops, but maybe I just implemented it
incorrectly (your assembly is about 1/2 the size of mine).
c code:
a = r.l[0]; //lowboard
c = r.l[1]; //highboard
b = 0;
d = 32;
b = (a == 0) ? d : b;
a = (a == 0) ? c : a;
c = a >> 16;
a &= 65535;
d = b + 16;
b = (a == 0) ? d : b;
a = (a == 0) ? c : a;
c = a >> 8;
a &= 255;
d = b + 8;
b = (a == 0) ? d : b;
a = (a == 0) ? c : a;
return b + lead_one_lut[a & 255];
which compiles to (gcc 3.2):
subl $8, %esp
movl 12(%esp), %eax
movl 16(%esp), %edx
movl %ebx, (%esp)
movl $32, %ebx
movl %esi, 4(%esp)
movl %eax, %ecx
xorl %eax, %eax
testl %ecx, %ecx
cmovne %ecx, %edx
cmove %ebx, %eax
movl %edx, %ecx
movl %edx, %ebx
leal 16(%eax), %esi
sarl $16, %ecx
andl $65535, %ebx
cmovne %ebx, %ecx
cmove %esi, %eax
movl %ecx, %edx
movl %ecx, %ebx
leal 8(%eax), %esi
sarl $8, %edx
andl $255, %ebx
cmovne %ebx, %edx
cmove %esi, %eax
movl (%esp), %ebx
andl $255, %edx
movl 4(%esp), %esi
movsbl lead_one_lut(%edx),%ecx
addl $8, %esp
addl %ecx, %eax
ret
anthony
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.