Author: Gerd Isenberg
Date: 10:38:57 03/08/06
Go up one level in this thread
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 ;-) 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.