Board structure is a quad-bitboard with "vertical" nibbles as piece codes.
Branchless Make/Unmake is almost xor/bswap of the quad-bitboard and hashkeys by two pre-calculated tables with all from-to aspects of all moves, as well as and/add of ep, castle-rights, material-signature and move50 counter.
Motivation of flipping sides after each make/unmake was to have always white to move, with makes move-generation black/white-symmetric and other stuff like egtb simpler. As a side effect I also get some additional hash-hits in symmetric positions.
So far I made all zobrist keys of black pieces depending on white pieces:
Code: Select all
zobrist[piece][sq] == bswap(zobrist[piece^color][sq^56])
Of course I am concerned about collisions due to this dependeny of zobrist keys.
That is why i tried hashing of move-counts in perft - to compare perft results with/without hashing.
I use four 128-bit slots per index to eventually replace the entry with lowest perft-count. I store the upper 48-bit of the hashkey for verification, depth, ply&1 and perft-count. I only replace other entries, if the new perft-count to store is at least 16 times bigger than the already stored one - which somehow seems to result in best performance so far.
The reason I store odd-even ply is to determine whether a hash-hit with same depth and key is from a flipped position. That is why I do some kind of "iterative" perft-deepening e.g. perft(1..8) without clearing the hashtable inbetween. So doing e3-e5-e4 from the initial position transposes to the flipped position e4-e5 from perft(n-1) which is probably still available in the hash with same depth. So far I tried a lot of positions, specially all kind of symmetrical positions without any difference with/without hashing.
The perft is not the fastest one with pure legal movegen and popcounting 16 disjoint directionwise movetarget-sets at the leaves. sse2 is still quite slow on K8 and I already do a lot of stuff needed for eval and plausible move-gen aka sorting.
Some sample output of initial and four-knights symmetrical position:
Code: Select all
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
bb[0] 0xffff000000000000
bb[1] 0x2cff00000000ff2c
bb[2] 0x7600000000000076
bb[3] 0x9900000000000099
occup 0xffff00000000ffff
castleRights: 0x0f00000f
hashkey: 0xdcd7fa0d0dfad7dc
matSignature: 0x2822012323012228
perft( 1) 20 0.000 sec
perft( 2) 400 0.000 sec
perft( 3) 8902 0.000 sec
perft( 4) 197281 0.000 sec
perft( 5) 4865609 0.078 sec
perft( 6) 119060324 1.219 sec
perft( 7) 3195901860 15.203 sec
perft( 8) 84998978956 222.890 sec
HashStats: 33554432 entries (512MB)
Stored 201075730 100% 599% of entries
NewEntries 33554210 17% of Stored
ReplOthers 159837973 79% of Stored
ReplSames 7683547 4% of Stored
Hits 218870782 109% of Stored
RevHits 8477931 4% of Hits
Code: Select all
r1bqkb1r/pppp1ppp/2n2n2/4p3/4P3/2N2N2/PPPP1PPP/R1BQKB1R w KQkq - 0 1
bb[0] 0xbdef241000000000
bb[1] 0x2cef00101000ef2c
bb[2] 0x3400240000240034
bb[3] 0x9900000000000099
occup 0xbdef24101024efbd
castleRights: 0x0f00000f
hashkey: 0x2972061212067229
matSignature: 0x2822013030012228
perft( 1) 29 0.000 sec
perft( 2) 837 0.000 sec
perft( 3) 25563 0.000 sec
perft( 4) 773691 0.016 sec
perft( 5) 24503979 0.266 sec
perft( 6) 770077186 5.047 sec
perft( 7) 25206631197 84.734 sec
perft( 8) 818977102124 1745.953 sec
HashStats: 33554432 entries (512MB)
Stored 1586142876 100% 4727% of entries
NewEntries 33554432 2% of Stored
ReplOthers 1542572118 97% of Stored
ReplSames 10016326 1% of Stored
Hits 1324309226 83% of Stored
RevHits 4669107 0% of Hits
Thanks,
Gerd