Skip to content
Advertisement

How to make custom hash function for hashing matrix (Othello board) to number

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.

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
```
User contributions licensed under: CC BY-SA
6 People found this is helpful
Advertisement