Zobrist Hashing

Reading time: 15 minutes | Coding time: 5 minutes

Algorithm

Note :

• We don't really need Zobrist hashing in the game of tic-tac toe , alpha beta pruning does optimisation fine for that game.
• You won't be encountering this algorithm until and unless you are facing a really large board. Some thing like 8x8 (chess) or 16x16 (ultimate tic-tac-toe)

A matrix intialised with random numbers in the beginning
Table[number_of_board_cells][number_of_pieces]

def zobristHash(board):
    ''' returns hash according to current board config'''
    hash = 0
    for each cell on board : 
        if cell is not empty:
            piece = board[cell]
            hash ^= table[cell][piece]
    return hash

Complexity

• Worst case Performance : O(N)
• Worst case space complexity : O(|V|) = O(b * d)

Implementations

Hash Mapping in chess-Python

Hash Mapping in tic tac toe-Python

import random
zobTable = [[[random.randint(1,2**64 - 1) for i in range(12)]for j in range(8)]for k in range(8)]


'''for i in zobTable:
    for j in i:
        for k in j:
            print k,
        print 

'''

def indexing(piece):
    ''' mapping each piece to a particular number'''
    if (piece=='P'):
        return 0
    if (piece=='N'):
        return 1
    if (piece=='B'):
        return 2
    if (piece=='R'):
        return 3
    if (piece=='Q'):
        return 4
    if (piece=='K'):
        return 5
    if (piece=='p'):
        return 6
    if (piece=='n'):
        return 7
    if (piece=='b'):
        return 8
    if (piece=='r'):
        return 9
    if (piece=='q'):
        return 10
    if (piece=='k'):
        return 11
    else:
        return -1

def computeHash(board):
    h = 0
    for i in range(8):
        for j in range(8):
           # print board[i][j]
            if board[i][j] != '-':
                piece = indexing(board[i][j])
                h ^= zobTable[i][j][piece]
    return h
def main():
    # Upper Case are white pieces
    # Lower Case are black pieces

    # a [8][8] format board
    board = [
        ['-', '-', '-', 'K', '-', '-', '-', '-'],
        ['-', 'R', '-', '-', '-', '-', 'Q', '-'],
        ['-', '-', '-', '-', '-', '-', '-', '-'],
        ['-', 'P', '-', '-', '-', '-', 'p', '-'],
        ['-', '-', '-', '-', '-', 'p', '-', '-'],
        ['-', '-', '-', '-', '-', '-', '-', '-'],
        ['p', '-', '-', '-', 'b', '-', '-', 'q'],
        ['-', '-', '-', '-', 'n', '-', '-', 'k']
    ]

    hashValue = computeHash(board)
    print "Current Board is :"
    for i in board:
        for j in i:
            print j,
        print

    print "\nThe Current hash is : ",hashValue,"\n"

    # an exaple of channge in game state and how it affects the hashes

    # move white Rook to at a new postion in right
    piece = board[1][1]

    board[1][1] = '-'
    hashValue ^= zobTable[1][1][indexing(piece)]

    board[3][1] = piece
    hashValue ^= zobTable[3][1][indexing(piece)]
    print "The new board is :"
    for i in board:
        for j in i:
            print j,
        print

    print "\nHash after the move is : ",hashValue,"\n"

if __name__ == "__main__":
    main()

Python

import random
zobTable = [[[random.randint(1,2**10 - 1) for i in range(2)]for j in range(3)]for k in range(3)]

def indexing(piece):
    ''' mapping X and O to a particular number'''
    if (piece=='X'):
        return 0
    if (piece=='O'):
        return 1
    else:
        return -1
def computeHash(board):
    h = 0
    for i in range(3):
        for j in range(3):
            if board[i][j] != '-':
                piece = indexing(board[i][j])
                h ^= zobTable[i][j][piece]
    return h

def main():
    # X is player one and O is player 2
    # a [3][3] format board
    board = [
        ['-', 'O', 'X'],
        ['-', 'X', '-'],
        ['O', '-', 'O'],
    ]

    hashValue = computeHash(board)
    print "Current Board is :"
    for i in board:
        for j in i:
            print j,
        print

    print "\nThe Current hash is : ",hashValue,"\n"

    # an exaple of channge in game state and how it affects the hashes

    # Add X at [2][1] to disrupt the O's winning strategy

    piece = 'X'

    board[2][1] = piece
    hashValue ^= zobTable[2][1][indexing(piece)]
    print "The new board is :"
    for i in board:
        for j in i:
            print j,
        print

    print "\nHash after the move is : ",hashValue,"\n"

if __name__ == "__main__":
    main()

Applications

As it is evident, it is a major feature used in two player games like chess and go. Just like standard hashes , it can be a great tool for graph traversals along with insertion and deletion.

The same method has been used to recognize substitutional alloy configurations during Monte Carlo simulations in order to prevent wasting computational effort on states that have already been calculated !

Further Reading

• Zobrist Hashing for parallel-first best searches by AAAI Publications