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 0xffff000000000000 bb 0x2cff00000000ff2c bb 0x7600000000000076 bb 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 0xbdef241000000000 bb 0x2cef00101000ef2c bb 0x3400240000240034 bb 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