Author: Tim Foden
Date: 04:31:16 08/04/03
Go up one level in this thread
On August 04, 2003 at 07:00:22, Gerd Isenberg wrote:
>On August 04, 2003 at 06:46:31, Tim Foden wrote:
>
>>On August 04, 2003 at 06:26:08, Zach Wegner wrote:
>>
>>>On August 04, 2003 at 06:11:20, Gerd Isenberg wrote:
>>>
>>>>Hi all,
>>>>
>>>>One common search/evaluation test is to compare the search of a position with
>>>>it's mirrored position.
>>>>
>>>>There is one principle problem related to bitboard traversal in move-generation.
>>>>
>>>>Black pieces and targets are traversed in an other order than the "mirrored"
>>>>pieces and targets, regardless if one uses bsf or bsr and the square-bitindex
>>>>mapping.
>>>>
>>>>Lets take some white pawns with following bit indicies: b2(9),d2(11) and c3(18).
>>>>With bsf you'll find them in ascending order: b2,d2,c3. Now with "mirrored"
>>>>black pawns on b7(49),d7(51),c6(42) we will foreward scan the ascending c6,b7,d7
>>>>squares.
>>>>
>>>>Even if there is further move sorting, the different initial order of generated
>>>>moves in mirrored positions implies different search trees - and therefore
>>>>slightly different search results.
>>>>
>>>>How do you deal with this behaviour in your bitboard based program?
>>>>I ignore it so far.
>>>>
>>>>One possible solution with x86-64 is to use the fast "bswap reg64" instruction
>>>>(direct path,1 cycle) before scanning black pieces or targets for movegen.
>>>>"bswap" mirrors the bits rankwise (8 becomes 1, 7 become 2...) and a remirror of
>>>>the scanned bit index is a simple xor with 0x38.
>>>>
>>>>According to the sample above we mirror the black b7,d7,c6 pawns to b2',d2',c3'
>>>>and we get the same order as with original white pawns: b7,d7,c6.
>>>>
>>>>One drawback is of course the need of a color2move paramter for bitScan - or
>>>>separate black/white traversal.
>>>>
>>>>Any remarks or implementaion hints?
>>>>
>>>>Regards,
>>>>Gerd
>>>
>>>What I have always done, which avoids this problem, is to use either MSB or LSB
>>>for removing a piece depending on which side of the board it is most likely to
>>>be on. e.g. for white pawns, use LSB; for black pawns, use MSB. I dont know if
>>>this helps, but it couldn't hurt.
>>
>>Yes, I basically do the same, for the same reason... it is a very simple
>>optimisation. For the white pieces I always use bsf, and for the black pieces I
>>always use bsr. This also has the added advantage of solving the problem that
>>Gerd is talking about.
>>
>>Cheers, Tim.
>
>Sorry Tim,
>
>i meant exclusive rank-symmetry, but no file-symmetry. In a (rank) mirrored
>position queen wing and king wing are still on the same side of the board.
<sound of hand slapping head>
Cough... Of course... I should have paid more attention. :)
I'm afraid I don't have any help for you.... well I'l try anyway :)
I guess one fast way to do the equivalent of the AMD64 bswap on i86 would be a
parallel shift thing...??
inline UINT64 bswap( UINT64 a )
{
a = (a << 32) | (a >> 32);
a = ((a & 0x0000FFFF0000FFFF) << 16) | (a & 0xFFFF0000FFFF0000) >> 16);
a = ((a & 0x00FF00FF00FF00FF) << 8) | (a & 0xFF00FF00FF00FF00) >> 8);
return a;
}
Or maybe there's a 32 bit equivalent to bswap? so...
inline UINT64 bswap( UINT64 a )
{
__asm
{
mov edx, dword ptr a
mov eax, dword ptr a + 4
bswap edx
bswap eax
}
}
Cheers, Tim.
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.