Author: Robert Hyatt
Date: 07:28:42 03/08/06
Go up one level in this thread
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.
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.