Quick introduction to the Zobrist Hash with real examples
I'm covering this because I think .NET is a great programming language for games that might take advantage of the Zobrist Hash. Traditionally any move based game such as Tic-Tac-Toe, Checkers, or Chess can gain super performance increases by storing and retrieving information evaluation various board positions. A chess example is in order.
In chess, the first player has the opportunity to make how many different moves? The answer is 20 based on the rules.
Now, the second player, how many moves do they get? The answer is again 20 based on the rules.
This results in 20^2 possibly board positions for the first two moves of the game (or first move for each player).
Now, when a player is considering moves in chess, they consider many moves into the future or several levels. By the time the first player has made a move, they have already thought through the ramifications of say 10,000 board positions and have evaluated each in terms of risk. So when the second player makes a move, the first player isn't confused or caught unaware, since they most likely evaluated the resulting board position already, and possibly many beyond that. They can quickly look up their previous thought process and begin making decisions from that point on without having to re-do their intermediate decisions. Generally speaking, we store all of these intermediate calculations or future calculations into a hashtable, indexed by some unique hash of the boards position.
Computing the boards position can be a pain in the butt. Let's do something simple like compute the hash of a string really fast. Assume that each character in the string is a pieces color and location on the board, thus having a direct effect on the hash of the board layout. The string we'll use is just a bunch of garbage, and I'm ripping the hash function from the rotor source. We'll show that you can hash the string, decompose a character out, and then add it back in and get the original result of the full hash.
using System;
public class ComputeStringHash {
private static void Main() {
string hashable = "sjflasjflajslfjasdfjas";
ulong hash = 0;
ulong hash2 = 0;
hash = ComputeHash(hashable);
Console.WriteLine("{0:x}", hash);
hash = BackoutCharacter(hashable[hashable.Length - 1], hash);
Console.WriteLine("{0:x}", hash);
hash2 = ComputeHash(hashable.Substring(0, hashable.Length - 1));
Console.WriteLine("{0:x}", hash);
hash = AddCharacter(hashable[hashable.Length - 1], hash);
Console.WriteLine("{0:x}", hash);
}
private static ulong ComputeHash(string str) {
ulong hash = 5381; // Some signifiance to the hash
for(int i = 0; i < str.Length; i++) {
hash = ((hash << 5) + hash) ^ str[i];
}
return hash;
}
private static ulong BackoutCharacter(char c, ulong oldHash) {
return ((oldHash ^ c) / 33);
}
private static ulong AddCharacter(char c, ulong oldHash) {
return (((oldHash << 5) + oldHash) ^ c);
}
}
Note that the hash of any string, versus the substring from 0 to string.length - 1 are somehow dependent or linked. Because of this dependency, we can back characters out of the hash and get hashes for portions of the string assuming those portions being at offset 0. We can also add to the hash as more characters are added. This would be the same thing as if we had a board position 50 moves into the game, with one exception. The hash function we use can't be dependent on location. We need to be able to remove any arbitrary *character* and add in another arbitrary character to represent the new position.
To do this we need to take an XOR example. Assume there is a board out there where you remove a piece from the board, and then place a new piece on the board. The initial state of the game is a given number of pieces. Forget about winning, these are just the rules. The user should be able to remove any piece that is currently on the board (this'll need to be enforced by game rules, since the Zobrist hash is not safe against tampering), and then place that piece in any other location that isn't already taken. The following example shows how initializing the hash of the board state is independent of the order in which pieces are placed, then shows that the order in which pieces are removed and replaced is also unimportant. Thus is the power of XOR.
using System;
public class XorExample {
private static void Main() {
Random rand = new Random();
int[] randomValues = new int[10];
for(int i = 0; i < randomValues.Length; i++) {
randomValues[i] = rand.Next(0, Int32.MaxValue);
}
// A board state
int xOrTarget1 = randomValues[0] ^ randomValues[1] ^ randomValues[2];
Console.WriteLine("{0:x}", xOrTarget1);
// Order doesn't matter
int xOrTarget2 = randomValues[1] ^ randomValues[0] ^ randomValues[2];
Console.WriteLine("{0:x}", xOrTarget2);
// Move a couple of pieces around. Intrinsically we are removing
// two pieces 0 and 1 from the board, and adding two new pieces
// 4 and 8.
xOrTarget1 ^= randomValues[0]; // Move a piece
xOrTarget1 ^= randomValues[4]; // To here
xOrTarget1 ^= randomValues[1]; // Move another piece
xOrTarget1 ^= randomValues[8]; // To here
Console.WriteLine("{0:x}", xOrTarget1);
// We do the same transformation on 2, but we show that
// again, order doesn't matter. Simply adding pieces to
// the board shows the true state of the board at any time
xOrTarget2 ^= randomValues[0]; // Move a piece
xOrTarget2 ^= randomValues[8]; // To here
xOrTarget2 ^= randomValues[1]; // Move another piece
xOrTarget2 ^= randomValues[4]; // To here
Console.WriteLine("{0:x}", xOrTarget2);
}
}
The Zobrist hash as above, uses a collection of random numbers in order to represent the game state. For instance, in chess, each piece of each color for each location on the board would be granted a random number. Once the random numbers are assigned, the hash is simply built based on the initial state, and then torn down and rebuilt as pieces are moved, taken off the board, or otherwise changing the state of the game. The hash can be used to look into a history of pre-computed risk values for board positions, or, if the random numbers are always the same, you can look into a pre-built history of every board position ever encountered throughout the life-time of the game.
This isn't an attempt to be complete. When using this method you need to be aware of board states that might hash to the same value. For the chess example, most implementations also use an additional XOR to represent which player gets to place the next piece. This is really important since it has drastic consequences to the risk assessment of the state. While I used integers from the Random class, I'd recommend using something a bit better for random number generation as well. I guess any method that increases performance comes at a slight cost.
Uses for the Zobrist Hash
-
Keep a stack of prior game state hashes to look for repeats. Much smaller than saving the game states themselves.
-
Quickly evaluate new board positions in a recursive manner by *popping* pieces of the hash and *pushing* pieces back on.
-
Quickly look-up historical calculations for previously seen board states. Perhaps prevent a large cyclical repeating pattern?
Considerations for the Zobrist Hash
- Invest in a good set of random numbers or a really good random number generator.
- Test for arbitrary XOR collisions, and once you've found a good set use a static array of those numbers.
- 64 bits isn't enough to enumerate all chess positions. However, could it be enough for simpler games?