Zobrist hashing in Elixir

Photo by Hassan Pasha on Unsplash

Zobrist hashing is a hashing mechanism which is used in representing the state of board games (such as chess, go, etc…). It doesn’t have to be a known board game per-se, you could also use it to represent Advent Of Code 2021 Day 23 if you would want to do so.

It’s useful because it can represent a complex state, such as that of a chess game where there are many different types of pieces which all can be in one of the 64 squares, in just a single number. This can help speed up certain algorithms by allowing the developer to compare different states of the game with each other. It can also be helpful in easily transitioning pieces on the game board.

Let’s dive in!

In Zobrist hashing, the state itself is a number. So having nothing but the board (no pieces yet added to the game board) would be represented by the number 0.

The algorithm also requires us to have a mapping from the all combinations of the possible positions on the game board combined with all possible game pieces, to some randomly generated number where these numbers have to be unique.

In Elixir we could represent it with the following struct:

defmodule Zobrist do
  defstruct [:table, state: 0]
end

Let’s also add the new/2 function to it