Author: Gerd Isenberg
Date: 05:37:45 08/04/03
Go up one level in this thread
On August 04, 2003 at 07:31:16, Tim Foden wrote: >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 :) > Thanks Tim, on x86-32 i stay with my current code, and live with some slight "mirror" differences. But with x86-64 i will try it in this manner (at least with some conditional compiles for mirrored test reasons): ; BitBoard in rcx, color2move in rdx xor rbx,rbx test rdx,rdx ; color2move jnz white black: xor rbx,38H ; mov rbx, 38H bswap rcx white: bsf rax,rcx xor rax,rbx Gerd
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.