I have to do project for which I need custom function for hashing matrix. Project is about Othello (Reversi) game which means that I need to hash fixed 8×8 matrix.
This is how initializing matrix looks like:
board = [['.' for x in range(8)] for y in range(8)]
Here is one example of how board looks:
[ ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '2', '1', '.', '.', '.', '.', '.'], ['.', '.', '2', '.', '.', '.', '.', '.'], ['.', '.', '1', '2', '1', '.', '.', '.'], ['.', '.', '.', '1', '2', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'] ]
As you can see, one player is 1 (which is always me) and the second player is 2 (which is always computer) and .
are empty board places.
I made some kind of hashing function. It looks like this:
def hash(self, board): string = '' for y in range(8): for x in range(8): string += board[y][x] broj = 0 for index, znak in enumerate(string): broj += (index + 1) * ord(znak) return broj
Function accepts board (matrix) and first makes string that contains all board fields in exact order and state as it is in board. After that I hash that string using formula from for
loop. Function ord
returns ASCII value of character.
I am aware that this is not good hash function so I am interested to hear some ideas for improving this one or implementing some completely different. I saw idea which is based on representing board with two 64-bit binary numbers where first number contains ones on places where player 1 has pieces and zeros on all other places, and second number contains ones where player 2 has pieces and zeros on all other places. After that, as I remember, I have to do hashing for that two numbers using some kind of algorithm. Thing is, I don’t know if that is good hash function and if I can implement it whatsoever.
Important to note is that I can’t use built-in hash functions or any other function imported from some library. I have to make custom hash function with some kind of algorithm.
Thanks in advance.
Advertisement
Answer
As I indicated in a response to my original (bogus) comment, you could consider each board state to be a 64 digit base-3 number. This approach will result in a unique integer value for every possible configuration — which can be considered its “hash” value.
This is what I mean:
def hash_func(board): numstr = (''.join(''.join(row) for row in board)).replace('.', '0') return int(numstr, 3) # Convert to an integer. sample = [['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '2', '1', '.', '.', '.', '.', '.'], ['.', '.', '2', '.', '.', '.', '.', '.'], ['.', '.', '1', '2', '1', '.', '.', '.'], ['.', '.', '.', '1', '2', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.']] print(f'{hash_func(sample):,}') # -> 135,688,629,099,716,090,516,394,594