Connect Four Hash Function: Map close elements to close hash keys

I'm writing a Connect Four game engine. Currently I'm using Zobrist hashing to generate hash keys for different Connect Four board positions (In order not to do the same thing twice, evaluated board positions are stored in a hash table). The board positions evaluated (nodes in a minimax tree), are always close to each other. Unfortunately close board positions are mapped to uniformly distributed hash-keys leading to a lot of cpu cache misses.

Is it possible to build a hash function which maps close board positions to close hash keys?

A board position for one player is represented by a bitboard of following开发者_高级运维 structure:

.  .  .  .  .  .  .  TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2  9 16 23 30 37 44
1  8 15 22 29 36 43
0  7 14 21 28 35 42

I don't know if it is even possible. Thanks for your help!

I don't think this is possible. A good hash key (like zobrist hashing is for board games) will most likely have pseudo random properties to achieve a uniform distribution of keys in the transposition table. Having the keys of "close" positions close to each other in table contradicts this.

Consider this: Even if you map your board positions one to one to a table with (2^7-1)^7 positions, you will not be able to map "close" board positions to close memory locations: If a piece at a low index changes, positions will be near, but the higher the piece index gets the position differences double each time, and the high ones will be many terabyte apart ;-)

As an author of a chess engine I know this problem. AFAIK nobody solved this problem yet, and everybody uses zobrist hashing, maybe with some minor modifications.

Anyway, good luck solving Connect-4... I know it has been done before, but it is more satisfactory to do it self ;-)

Here is how to modify your presumably nearly uniformly random hash function to bias it in a way that similiar board positions are somewhat likely to occur at nearby hashes.

Let hash(gamestate) be your existing function. We'll create a newhash(gamestate) that uses hash for the random behavior, but has a reasonably high probability of generating hashes that are near each other for closely related game states.

Let the 'color' of a board state be the next player to move. If want to find the hash key for the white player, use newhash(board) = hash(board). If you want to find the hash for a black position, find the black piece with maximal number according to your order, say, at position i. Remove piece i from the game state and call the modified state probableparent Then use newhash(board) = hash(probableparent) + i. If you order the positions by likely order of placement (higher things come later as a first order criteria, maybe the middle locations come earlier as a second criteria? I don't really know good strategy for connect4), then it's somewhat likely that on the white turn before the black turn was at probableparent, and hence nicely in your cache and hence i is near by. Also, the 8 possible black moves will likely share the same prev_board state and hence have near by hash locations.

You can extend this idea to roll back more than one ply at a time. Say if current turn % 3 == 2, removing the maximal two moves at board positions i and j , and then use newhash(board) = hash(board-two-removals-ago) + i*48 + j.