2.7 Population count
// we have 8*8 board and 12 pieces (6 for white side and 6 for black)
uint64_t table[12][8][8]; // filled with random values
int position[8][8]; // for each square on board. 0 - no piece. 1..12 - piece
uint64_t hash;
for (int row=0; row<8; row++)
for (int col=0; col<8; col++)
{
int piece=position[row][col];
if (piece!=0)
hash=hash^table[piece][row][col];
};return hash;
Now the most interesting part: if the next (modified) chess position differs only by one (moved) piece,
you don’t need to recalculate hash for the whole position, all you need is:
hash=...; // (already calculated)
// subtract information about the old piece:
hash=hash^table[old_piece][old_row][old_col];
// add information about the new piece:
hash=hash^table[new_piece][new_row][new_col];
2.6.7 By the way
The usualORalso sometimes calledinclusive OR(or evenIOR), as opposed toexclusive OR. One place is
operatorPython’s library: it’s calledoperator.iorhere.
2.6.8 AND/OR/XOR as MOV.
OR reg, 0xFFFFFFFFsets all bits to 1, hence, no matter what has been in register before, it will be set
to− 1 .OR reg, -1is shorter thanMOV reg, -1, so MSVC uses OR instead the latter, for example:3.15.1
on page 527.
Likewise,AND reg, 0always resets all bits, hence, it acts likeMOV reg, 0.
XOR reg, reg, no matter what has been in register beforehand, resets all bits, and also acts likeMOV reg,
0.
2.7 Population count
POPCNTinstruction is population count (AKAHamming weight). It just counts number of bits set in an input
value.
As a side effect,POPCNTinstruction (or operation) can be used to determine, if the value has 2 nform.
Since, 2 nnumber always has just one single bit,POPCNT’s result will always be just 1.
For example, I once wrote a base64 strings scanner for hunting something interesting in binary files^21.
And there is a lot of garbage and false positives, so I add an option to filter out data blocks which has size
of 2 nbytes (i.e., 256 bytes, 512, 1024, etc.). The size of block is checked just like this:
if (popcnt(size)==1)
// OK
...