Erlang, Chess and Bitboards. The application that was supposed to appear one day
Tags: erlang, functional, showdev, programming
Published: 2019-08-02 15:13:01

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

![Binbo in Erlang shell](https://thepracticaldev.s3.amazonaws.com/i/8ecq4mukdp61gs7vzd1w.png)

[Binbo](https://github.com/DOBRO/binbo) is a Chess representation written in pure Erlang using [Bitboards](https://www.chessprogramming.org/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 **bin**ary **bo**ard 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](https://www.chessprogramming.org/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](https://ru.wikipedia.org/wiki/Portable_Game_Notation) loading.
* All the chess rules are completely covered including:
  * [En-passant move](https://en.wikipedia.org/wiki/En_passant);
  * [Castling](https://en.wikipedia.org/wiki/Castling);
  * [Fifty-move rule](https://en.wikipedia.org/wiki/Fifty-move_rule);
  * [Threefold repetition](https://en.wikipedia.org/wiki/Threefold_repetition);
  * [Draw by insufficient material](http://www.e4ec.org/immr.html);
* Unicode chess symbols support for the board visualization right in Erlang shell:
&#9817; &#9816; &#9815; &#9814; &#9813; &#9812; &#9823; &#9822; &#9821; &#9820; &#9819; &#9818;
* 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]( https://www.chessprogramming.org/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](https://stackoverflow.com/questions/16925204/sliding-move-generation-using-magic-bitboard/30862064#30862064) and [here](http://vicki-chess.blogspot.com/2013/04/magics.html).

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++:_

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

_in Erlang:_

```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](https://www.chessprogramming.org/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](https://github.com/DOBRO/binbo/blob/master/include/binbo_magic.hrl).

To be accurate, Binbo uses [Fancy Magic Bitboards](https://www.chessprogramming.org/Magic_Bitboards#Fancy). 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:

```c
move = global_move_table[square][magic_index]
```

_If detailed:_

```c
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 :&#41;.

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:_

```erlang
GlobalMovesTable = { MoveMap1, ..., MoveMap64 }
```

_where:_

```erlang
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_):

```erlang
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:

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

where `Mask1`, `Mask2`, ..., `Mask64` are _bitboards_ (integers).

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

```erlang
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](http://erlang.org/doc/man/ets.html)? 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](https://github.com/mochi/mochiweb/blob/master/src/mochiglobal.erl).

Using [persistent_term](http://erlang.org/doc/man/persistent_term.html) (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.