Erlang, Chess and Bitboards. The application that was supposed to appear one day

Sergei Semichev — Fri, 02 Aug 2019 15:13:01 +0000

I found that there was no Chess representation written in Erlang. So, I wrote Binbo.

Binbo is a Chess representation written in pure Erlang using Bitboards. It is basically aimed to be used on game servers where people play chess online.

It's called Binbo because its ground is a binary board containing only zeros and ones (0 and 1) since this is the main meaning of Bitboards as an internal chessboard representation.

Binbo also uses the Magic Bitboards approach for a blazing fast move generation of sliding pieces (rook, bishop, and queen).

Note: it's not a chess engine but it could be a good starting point for it. It can play the role of a core (regarding move generation and validation) for multiple chess engines running on distributed Erlang nodes, since Binbo is an OTP application itself.

Features

Blazing fast move generation and validation.
No bottlenecks. Every game is an Erlang process (gen_server) with its own game state.
Ability to create as many concurrent games as many Erlang processes allowed in VM.
Support for PGN loading.
All the chess rules are completely covered including:
Unicode chess symbols support for the board visualization right in Erlang shell: ♙ ♘ ♗ ♖ ♕ ♔ ♟ ♞ ♝ ♜ ♛ ♚
UCI protocol support.
Cross-platform application. It runs on Linux, Unix, Windows, and macOS.
Ready for use on game servers.

Binbo and Magic Bitboards

As mentioned above, Binbo uses Magic Bitboards, the fastest solution for move generation of sliding pieces (rook, bishop, and queen). Good explanations of this approach can also be found here and here.

The main problem is to find the index which is then used to lookup legal moves of sliding pieces in a preinitialized move database. The formula for the index is:

in C/C++:

magic_index = ((occupied & mask) * magic_number) >> shift;

in Erlang:

MagicIndex = (((Occupied band Mask) * MagicNumber) bsr Shift).

where:

Occupied is the bitboard of all pieces.
Mask is the attack mask of a piece for a given square.
MagicNumber is the magic number, see "Looking for Magics".
Shift = (64 - Bits), where Bits is the number of bits corresponding to attack mask of a given square.

All values for magic numbers and shifts are precalculated before and stored in binbo_magic.hrl.

To be accurate, Binbo uses Fancy Magic Bitboards. It means that all moves are stored in a table of its own (individual) size for each square. In C/C++ such tables are actually two-dimensional arrays and any move can be accessed by a simple lookup:

move = global_move_table[square][magic_index]

If detailed:

moves_from = global_move_table[square];
move = moves_from[magic_index];

The size of moves_from table depends on piece and square where it is placed on. For example:

for rook on A1 the size of moves_from is 4096 (2^12 = 4096, 12 bits required for the attack mask);
for bishop on A1 it is 64 (2^6 = 64, 6 bits required for the attack mask).

There are no two-dimensional arrays in Erlang, and no global variables which could help us to get the fast access to the move tables from everywhere.

So, how does Binbo beat this? Well, it's simple :).

Erlang gives us the power of tuples and maps with their blazing fast lookup of elements/values by their index/key.

Since the number of squares on the chessboard is the constant value (it's always 64, right?), our global_move_table can be constructed as a tuple of 64 elements, and each element of this tuple is a map containing the key-value association as MagicIndex => Moves.

If detailed, for moves:

GlobalMovesTable = { MoveMap1, ..., MoveMap64 }

where:

MoveMap1  = #{
  MagicIndex_1_1 => Moves_1_1,
  ...
  MagicIndex_1_K => Moves_1_K
},
MoveMap64 = #{
  MagicIndex_64_1 => Moves_64_1, ...
  ...
  MagicIndex_64_N => Moves_64_N
},

and then we lookup legal moves from a square, say, E4 (29th element of the tuple):

E4 = 29,
MoveMapE4   = erlang:element(E4, GlobalMovesTable),
MovesFromE4 = maps:get(MagicIndex, MovesMapE4).

To calculate magic index we also need the attack mask for a given square. Every attack mask generated is stored in a tuple of 64 elements:

GlobalMaskTable = {Mask1, Mask2, ..., Mask64}

where Mask1, Mask2, ..., Mask64 are bitboards (integers).

Finally, if we need to get all moves from E4:

E4 = 29,
Mask = erlang:element(E4, GlobalMaskTable),
MagicIndex = ((Occupied band Mask) * MagicNumber) bsr Shift,
MoveMapE4   = erlang:element(E4, GlobalMovesTable),
MovesFromE4 = maps:get(MagicIndex, MovesMapE4).

Next, no global variables? We make them global!

How do we get the fastest access to the move tables and to the attack masks from everywhere?

ETS? No! Using ETS as a storage for static terms we get the overhead due to extra data copying during lookup.

And now we are coming to the fastest solution.

When Binbo starts up, all move tables are initialized. Once these tables (tuples, actually) initialized, they are "injected" into dynamically generated modules compiled at Binbo start. Then, to get the values, we just call a getter function (binbo_global:get/1) with the argument as the name of the corresponding dynamic module.

This awesome trick is used in MochiWeb library, see module mochiglobal.

Using persistent_term (since OTP 21.2) for storing static data is also a good idea. But it doesn't seem to be a better way for the following reason with respect to dynamic modules. When Binbo stops, it gets them unloaded as they are not necessary anymore. It should do the similar things for persistent_term data, say, delete all unused terms to free memory. In this case we run into the issue regarding scanning the heaps in all processes.

So, using global dynamic modules with large static data seems to be more reasonable in spite of that fact that it significantly slows down the application startup due to the run-time compilation of these modules.

DEV Community: Sergei Semichev

Erlang, Chess and Bitboards. The application that was supposed to appear one day

Features

Binbo and Magic Bitboards