4 ms·

This trick is called zobrist hashing in chess/go programming. It allows for incremental calculation of the board hash, which is particularly useful because all

by brilee 4y ago

This trick is called zobrist hashing in chess/go programming. It allows for incremental calculation of the board hash, which is particularly useful because all of the game variations you're exploring are all nearly identical to one another, saving a lot of compute.

FartyMcFarter 4y ago
It's reminiscent of Zobrist hashing in that it's an incremental hash calculated with xor. But Zobrist hashing has the crucial difference of using a random k-bit number to be xor'ed into the hash (k is a constant, typically 64 these days) for each member of the set that is present, instead of an N-bit string where N is the number of possible elements in the set. For example, in a chess engine: if the hash value for "white knight on f3 square" is 0x8BADF00D and the hash value for "white king on e4 square" is 0x1BADB002, then a chess board containing only "white knight on f3 and white king on e4" would be hashed as (0x8BADF00D xor 0x1BADB002) = 0x9000400F. The upside of this trick is that if your set can contain N different objects (e.g. 768 combinations of 12 different chess pieces on each of 64 squares), you don't need to use an N-bit hash value, which would be pretty big. In the particular problem described in this blog, this isn't an advantage as it's using a set containing only up to 26 letters, which neatly fits in a u32 even if you dedicate a bit to each letter. However there are downsides to Zobrist hashing - it's very hard to guarantee that you don't get hash collisions in this manner, as AFAIK you'd have to try all combinations of valid sets, which is prohibitively expensive. So every algorithm relying on this hash value either has to be robust to hash collisions, or it accepts a small probability of failure. Most importantly in this case, Zobrist hashing doesn't let you test whether a particular element is present in the set, nor does it let you count the number of elements in a set. So it wouldn't work as a solution to the problem in this blog, which requires counting how many unique letters are present in the hash value.
thomasahle 4y ago
Zobrist hashing is different. With Zobrist you have a table pd random numbers. You look each key up in the table and xor the values.

by brilee 4y ago

FartyMcFarter 4y ago

It's reminiscent of Zobrist hashing in that it's an incremental hash calculated with xor. But Zobrist hashing has the crucial difference of using a random k-bit number to be xor'ed into the hash (k is a constant, typically 64 these days) for each member of the set that is present, instead of an N-bit string where N is the number of possible elements in the set. For example, in a chess engine: if the hash value for "white knight on f3 square" is 0x8BADF00D and the hash value for "white king on e4 square" is 0x1BADB002, then a chess board containing only "white knight on f3 and white king on e4" would be hashed as (0x8BADF00D xor 0x1BADB002) = 0x9000400F. The upside of this trick is that if your set can contain N different objects (e.g. 768 combinations of 12 different chess pieces on each of 64 squares), you don't need to use an N-bit hash value, which would be pretty big. In the particular problem described in this blog, this isn't an advantage as it's using a set containing only up to 26 letters, which neatly fits in a u32 even if you dedicate a bit to each letter. However there are downsides to Zobrist hashing - it's very hard to guarantee that you don't get hash collisions in this manner, as AFAIK you'd have to try all combinations of valid sets, which is prohibitively expensive. So every algorithm relying on this hash value either has to be robust to hash collisions, or it accepts a small probability of failure. Most importantly in this case, Zobrist hashing doesn't let you test whether a particular element is present in the set, nor does it let you count the number of elements in a set. So it wouldn't work as a solution to the problem in this blog, which requires counting how many unique letters are present in the hash value.

thomasahle 4y ago

Zobrist hashing is different. With Zobrist you have a table pd random numbers. You look each key up in the table and xor the values.