Author: Eugene Nalimov
Date: 10:30:22 11/17/02
Go up one level in this thread
On November 17, 2002 at 13:25:55, Vincent Diepeveen wrote:
>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
>
>Isn't shifting on the P4 *WAY* slower than his mod 67 idea is?
No.
Thanks,
Eugene
This page took 0.01 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.