A Perfect Hashing Function for an 8 by 8 board?

I'm implementing a board with only 2 types of pieces, and开发者_开发问答 was looking for a function to map from that board to a Long Integer (64 bits). I was thinking this should not be so hard, since a long integer contains more available information than an 8 by 8 array (call it grid[x][y]) with only 3 possible elements in each spot including the empty element. I tried the following:

(1) Zobrist hashing with Longs rather than ints (Just to test - I didn't actually expect that to work perfectly)

(2) Translated the grid into a 64 character string of a base 3 number, and then took that number and parsed it into a long. I think this should work, but it took a very very long time.

Is there some simpler solution to (2) involving bit operations of shifting or something like that?

Edit: Please don't give me actual code, as this is for a class project, and that would probably be considered unethical in our department (or at least not in Java).

Edit2: Basically, there are only 10 whites and 10 blacks on the board at any given time, of which no two pieces of the same color can be neighbors, either in the horizontal, vertical, or diagonal direction. Also, there are 12 spaces for each color where only that color may place pieces.

---

If each tile in the game can be 1 of any 3 states at any point in the game, then the minimum amount of storage required for a "perfect hash" when hashing every possible state of the game board, at any given moment will
= power(3,8*8) individual hashes
= log2(3^64) bits
= approx. 101.4 bits, so you will need at least 102 bits to store this info

At this point, you may as well just say there are 4 states for each tile, which will bring you to needing 128 bits.

Once you do this, its rather easy to make a fast hashing algorithm for the board.

E.g. (writtin as c++, may need to alter code if the platform doesn't support 128 bit numbers)

uint_128 CreateGameBoardHash(int (&game_board)[8][8])
{
    uint_128  board_hash = 0;
    for(int i = 0; i < 8; ++i)
    {
        for(int j = 0; j < 8; ++j)
        {
            board_hash |= game_board[i][j] << ((i * 8 + j) *2);
        }
    }
    return board_hash;
}

This method will only waste 26 bits (little more than 3 bytes) over the optimal solution of 102 bits, but you will save a LOT of processing time that would be otherwise spent doing base 3 math.

---

Edit Here's a version that doesn't require 128 bits and should work on any 16-bit (or better) processor

struct GameBoardHash
{
    uint16 row[8];
};


GameBoardHash CreateGameBoardHash(int (&game_board)[8][8])
{
    GameBoardHash board_hash;
    for(int i = 0; i < 8; ++i)
    {
        board_hash.row[i] = 0;
        for(int j = 0; j < 8; ++j)
        {
            board_hash.row[i] |= game_board[j] << (j*2);
        }
    }
    return board_hash;
}

---

It won't fit into a 64 bit integer. You have 64 squares and you need more than 1 bit to record each square. Why do you need it to fit into a 64 bit int? Are you targetting the ZX81?

---

How about a 16 byte array containing the bits? Each 2-bits, represent a position's value, so that given a position in the 8x8 board (pos=0-63), you can figure out the index by dividing pos by 4 and you can get the value by doing bit manipulation to get two bits (bit0=pos mod 4 and bit1=bit0 + 1). The two bits can be either 00, 01, or 10.

---

Reading your comments to David, it doesn't seem like you really need a perfect hash value. You just need a hashable object.

Make it simple for yourself... Make some hash for you position in the overwrite to GetHashCode(), and then do the rest of the work in the Equals function.

If you REALLY need it to be perfect, then you have to use a GUID to encode your data in and make your own hash that can use 128bit keys. But that is just a huge investment of time for little benifit.