dchoman wrote:tpetzke wrote:I don't have hash signatures for moves (and I thought I don't have to start building them). So I would xor two positions, the current and a former one.
In principle you are right that an exchanged move order results in the same (difference) signature. But I can store two refutation moves (a white and a black one) and pick the one for the side to move.
Thomas...
You can also add an xor of the hash signature for the side-to-move at the end of the combination.
- Dan
If he is hashing 2 move sequences or more it is hardly a problem but you are right, it could be done this way.
To have a proper zobrist hash you need a separate random key table for each "element" of the thing you are hashing. In the simple case with just "from" and "to" hashing that would be 4 tables for a 2 move sequence.
A full move however really only needs 64 random numbers - you can construct offsets that do not represent legal moves. For example NO piece can move from a1 to g2 so you might be able to find a magic constant offset that would work with any valid move to avoid the from/to independence as long as one never mapped to the other. Presumably you would mask off the lower 6 bits to make sure your offset stayed on the board.
So you would want an offset that made ANY legal move by any piece come out as unique. Let's say the offset was 13 for example. Your key for a single move might be:
key = zobrist[f] ^ zobrist[ (t + 13) & 63 ];
where f is the from square and t is the to square.
to hash a 2 move sequence you need to multiply a well selected constant to the first move before xoring the second move:
seq2 = (key1 * K) ^ key2;
K could probably be any large random number but there are some hashing functions with multipliers such as Murmur Hash and you could steal constants known to work well for those - although I don't think it really would matter that much.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.