cdani wrote:One idea could be to share 7 of 8 bytes (or 4 of 8...) with the next key, thus saving roughly 7/8 of memory. If this works, should suffice for wildest chess variants.
Indeed, micro-Max and Shokidoki do this. Shokidoki because with an 81-square board and 2x14 piece types a full Zobrist table would provide a rather heavy cache load (28x81*8 = 18KB, while at the time the usual L1 size was still 16KB). In micro-Max mainly because the rand() function delivered only 16-bit values, so that it would be a lot of work to fill 8-byte variables.
Code: Select all
int BOARDSIZE=256;
char T[8200];
// during the engine initialization
N=32*BOARDSIZE+7;while(N-->BOARDSIZE+3)T[N]=rand()>>9;
// access
*(int*)(T + square + BOARDSIZE*pieceType)
Note this acces them as 32-bit integers, because micro-Max keeps the two halves of the hash key in separate variables (one used for indexing, the other stored in the entry as signature). The second key is then using square+4 instead of square for its update.
If you would want to do 64-bit acces, you would just have to write *(long long int*) in stead of *(int*). The unaligned accesses turned out to have no speed penalty as long as they do not straddle two 64-byte cache lines. If they do, it just requires an extra cycle. But with 0x88 square numbering there is no need to ever straddle a cache line.
However, with 2x100 piece types and 625 board squares it would still require 125KB, far exceding L1. So I did not consider it suitable for HaChu.