Author: Robert Hyatt
Date: 12:31:23 03/08/06
Go up one level in this thread
On March 08, 2006 at 13:38:57, Gerd Isenberg wrote: >On March 08, 2006 at 10:28:42, Robert Hyatt wrote: > >>On March 08, 2006 at 05:39:24, Tord Romstad wrote: >> >>>On March 07, 2006 at 21:42:15, Robert Hyatt wrote: >>> >>>>On March 07, 2006 at 16:01:57, Dann Corbit wrote: >>>> >>>>>Fruit uses late move reductions, and yet the search is perfectly symmetrical. >>>> >>>>Same number of nodes at same depth in all 4 positions? >>> >>>No, not even from the initial position, as you can see from my reply to Dann. >>> >>>>I don't see how he does it, but then again, bitboard programs have different >>>>issues. I have FirstOne() and LastOne(). But if you flip the board >>>>horizontally, I can't flip the way those two functions find the first 1 bit, >>>>so my moves are generated in a different order. >>> >>>Even if a program has perfectly symmetrical move ordering (which Fruit >>>does not have, by the way), the search will not be symmetrical, because of >>>the hash table. When sufficiently many of the lower order bits of the >>>Zobrist keys of two different positions match, they will be stored to the >>>same address in the transposition table. The lower order bits of the >>>two corresponding mirrored positions will of course generally not >>>resemble each other at all, and the positions will no longer be stored >>>to the same address. This means that the search can never be symmetrical, >>>as long as a transposition table is used. >>> >>>Tord >> >> >>First step would be to invert the random numbers so that you get the same hash >>signature for the starting position. But for me that would not be enough, >>still, because of the BSF/BSR problem I mentioned. For me, BSF starts at a1=0 >>and goes through h8=63. Flipping the board wrecks that. >> >>Suppose white has rooks at a1 and h1. For white, I use LastOne() to give me the >>most advanced rook to generate moves for first. That gives me the rook on h1. >>When I reflect the board (a1 -> a8, etc...) I now have rooks on a8 and h8 for >>black instead. I now use FirstOne() to generate black moves and now I get the >>rook on a8 first, rather than the equivalent rook on h8. So the moves come out >>in a different order, which means each branch is searched with different history >>counters to affect move ordering and reductions. >> >>I don't see how I could overcome that without a lot of slow-down work... >> >>reversing the a-h, b-g, etc files has the same exact problem. white rook on a1 >>and f1. I search moves for the white rook on f1 first. Then mirror the board >>left to right and LastOne() now returns the rook on h1 rather than the rook on >>c1, again changing the move order... >> >>symmetric search looks hopeless for bitboard programs. I haven't thought about >>the effect on mailbox approaches. > > >Still bitscanning? Thought you did a major rewrite ;-) Eval and search. Not basic data structures or move generation. :) > >What i have in mind with disjoint direction wise attack-sets is to traverse them >in point symmetric manner, depending the board quarter they reside. > >Problem is traversing pawns and pieces - specially after some pawn promotions >with more than one queen, one bishop per square color, two rooks or knights per >side. > >Bishops may be traversed with piece color equals square color first. For rooks >and knights i intend to use for two pieces (rooks, knights) first white : x&-x, >second white (if any) x&(x-1) but vice versa for black. > >For pawns - i still don't know exactly. >Maybe generating all pawn captures/moves at once and try to assign unique scores >so that they are picked in point symmetric manner as well. > >For the hashkey issue - one may try > > zobristKey[piece][sq] == zobristKey[piece^1][sq^56] > >where xor 1 toggles the piece color and xor 56 mirrors the rank? >Guess that gives some additional hits in symmetrical positions, specially with >nullmove ;-) > >For mirrored files, additionally applying the trick seems a bit dangerous. > > zobristKey[piece][sq] == zobristKey[piece][sq^7] > >but what about > > zobristKey[piece][sq] == -zobristKey[piece][sq^7] > >and to probe not only with zobristKey % tblsize but also with >((unsigned)-zobristKey) % tblsize > >;-?
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.