Fast hashing of 2-dimensional array

I'm building a Reversi player using the standard alpha beta pruning search algorithm. I'm trying to add a translation table to store previously calculated nodes in the search tree. So I need to ha开发者_开发知识库sh a 2 dimensional array representing the game board (the state) and store a value for that.

I can't come up with anything better than a double for loop iterating over my arrays and adding all values together multiplying them with the offsets to get unique hash values.

@Override
public int hashCode() {
    if (dirtyHash) {
        int hash = 0;
        for (int i = 0; i < Board.SIZEX; i++)
            for (int j = 0; j < Board.SIZEY; j++)
                hash += board[i][j] * (i + Board.SIZEY * j);

        hashValue = hash;
        dirtyHash = false;
    }

    return hashValue;
}

I suspect there must be a much smarter way to do this? Anyone got any ideas?

I would use java standard library as a first try:

int hash = java.util.Arrays.deepHashCode( board );

Once everything works well, profile your whole app, to check if the hashcode computation is really a performance bottleneck.

If you want to handle this yourself here is one way you could do it.

There are three values for each cell on the board: empty, black, white. That means you can use two bits per cell on the board. And since the board is 8x8 or 64 cells, you can encode the board in two long primitives. Maybe one of them tells you whether a particular cell is empty, and if it's not, the other tells you its color.

You do not even need to convert this representation into a 2D array. You can use bitwise operators on the longs directly in your methods to work with the board.

The hash value could then be the XOR of the two longs, or something like that.

You should be using a Zobrist hash for this. It is perfect for board games. It can also be updated incrementally as the board changes, instead of being recalculated from scratch every time. This makes it very efficient.

http://en.wikipedia.org/wiki/Zobrist_hashing

I'd suggest to following:

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < Board.SIZEX; i++)
        for (int j = 0; j < Board.SIZEY; j++)
            hash = (hash) ^ ( (Math.pow(p,i)+Math.pow(p,j))* board[i][j]
    return hashValue;
}

for p and q large 32-primes.

Why is that fast? Calculatoin for a board is quite easy: the new can be calculated from the old with hash = (hash) ^ ( (Math.pow(p,i)+Math.pow(p,j))* board[i][j], iterating not over the whole board, but only the Changed stones. (if you add a black once with the hash for the black stone, if you change from black to white once with the black stone to remove it from the hash und once again with the white to add it)