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.

---

Table of Contents

• Features
• Requirements
• Quick start
• Interface
  • Starting application
  • Creating game process
  • Initializing new game
  • Making moves
    • API
    • Castling
    • Promotion
    • En passant
  • Getting FEN
  • PGN loading
  • Board visualization
  • Game status
  • List of legal moves
  • Setting a draw
  • Stopping game process
  • Stopping application
• Building and testing
  • Building
  • Dialyzer
  • Testing
  • Code coverage
  • Generating Edoc files
• Binbo and Magic Bitboards
• Changelog
• Contributing
• License

---

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:

  • En-passant move;

  • Castling;

  • Fifty-move rule;

  • Threefold repetition;

  • Draw by insufficient material:

    • King versus King,

    • King and Bishop versus King,

    • King and Knight versus King,

    • King and Bishop versus King and Bishop with the bishops on the same color;

• Unicode chess symbols support for the board visualization right in Erlang shell:
  ♙ ♘ ♗ ♖ ♕ ♔    ♟ ♞ ♝ ♜ ♛ ♚

• Passes all perft tests.

• Ready for use on game servers.

Requirements

• Erlang/OTP 20.0 or higher.

• rebar3

Quick start

Run make shell or rebar3 shell and then:

%% Start Binbo application first:
binbo:start().

%% Start new process for the game:
{ok, Pid} = binbo:new_server().

%% Start new game in the process:
binbo:new_game(Pid).

%% Or start new game with a given FEN:
binbo:new_game(Pid, <<"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1">>).

%% Look at the board with ascii or unicode pieces:
binbo:print_board(Pid).
binbo:print_board(Pid, [unicode]).

%% Make move for White and Black:
binbo:move(Pid, <<"e2e4">>).
binbo:move(Pid, <<"e7e5">>).

%% Have a look at the board again:
binbo:print_board(Pid).
binbo:print_board(Pid, [unicode]).

Interface

There are three steps to be done before making game moves:

1. Start Binbo application.

2. Create process for the game.

3. Initialize game state in the process.

Note: process creation and game initialization are separated for the following reason: since Binbo is aimed to handle a number of concurrent games, the game process should be started as quick as possible leaving the supervisor doing the same job for another game. It’s important for high-load systems where game creation is a very frequent event.

Starting application

To start Binbo, call:

binbo:start().

Creating game process

binbo:new_server() -> {ok, pid()}.

So, to start one or more game processes:

{ok, Pid1} = binbo:new_server(),
{ok, Pid2} = binbo:new_server(),
{ok, Pid3} = binbo:new_server().

Initializing new game

binbo:new_game(Pid) -> {ok, GameStatus} | {error, Reason}.

binbo:new_game(Pid, Fen) -> {ok, GameStatus} | {error, Reason}.

where:

• Pid is the pid of the process where the game is to be initialized;

• Fen (string() or binary()) is the Forsyth–Edwards Notation (FEN);

• GameStatus is the game status.

It is possible to reinitilize game in the same process. For example:

binbo:new_game(Pid),
binbo:new_game(Pid, Fen2),
binbo:new_game(Pid, Fen3).

Example:

%% In Erlang shell.

> {ok, Pid} = binbo:new_server().
{ok,<0.185.0>}

% New game from the starting position:
> binbo:new_game(Pid).
{ok,continue}

% New game with the given FEN:
> binbo:new_game(Pid, <<"rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1">>).
{ok,continue}

Making moves

API

binbo:move(Pid, Move) -> {ok, GameStatus} | {error, Reason}.

binbo:san_move(Pid, Move) -> {ok, GameStatus} | {error, Reason}.

where:

• Pid is the pid of the game process;

• Move is of binary() or string() type;

• GameStatus is the game status.

Function binbo:move/2 supports only strict square notation with respect to argument Move, for example: <<"e2e4">>, <<"e7e5">>, etc.

Function binbo:san_move/2 is intended to handle various formats of argument Move including standard algebraic notation (SAN), for example: <<"e4">>, <<"Nf3">>, <<"Qxd5">>, <<"a8=Q">>, <<"Rdf8">>, <<"R1a3">>, <<"O-O">>, <<"O-O-O">>, <<"e1e8">>, etc.

Examples for binbo:move/2:

%% In Erlang shell.

% New game from the starting position:
> {ok, Pid} = binbo:new_server().
{ok,<0.190.0>}
> binbo:new_game(Pid).
{ok,continue}

% Start making moves
> binbo:move(Pid, <<"e2e4">>). % e4
{ok,continue}

> binbo:move(Pid, <<"e7e5">>). % e5
{ok,continue}

> binbo:move(Pid, <<"f1c4">>). % Bc4
{ok,continue}

> binbo:move(Pid, <<"d7d6">>). % d6
{ok,continue}

> binbo:move(Pid, <<"d1f3">>). % Qf3
{ok,continue}

> binbo:move(Pid, <<"b8c6">>). % Nc6
{ok,continue}

% And here is checkmate!
> binbo:move(Pid, <<"f3f7">>). % Qf7#
{ok,checkmate}

Examples for binbo:san_move/2:

%% In Erlang shell.

% New game from the starting position:
> {ok, Pid} = binbo:new_server().
{ok,<0.190.0>}
> binbo:new_game(Pid).
{ok,continue}

% Start making moves
> binbo:san_move(Pid, <<"e4">>).
{ok,continue}

> binbo:san_move(Pid, <<"e5">>).
{ok,continue}

> binbo:san_move(Pid, <<"Bc4">>).
{ok,continue}

> binbo:san_move(Pid, <<"d6">>).
{ok,continue}

> binbo:san_move(Pid, <<"Qf3">>).
{ok,continue}

> binbo:san_move(Pid, <<"Nc6">>).
{ok,continue}

% Checkmate!
> binbo:san_move(Pid, <<"Qf7#">>).
{ok,checkmate}

Castling

Binbo recognizes castling when:

• White king moves from E1 to G1 (O-O);

• White king moves from E1 to C1 (O-O-O);

• Black king moves from E8 to G8 (O-O);

• Black king moves from E8 to C8 (O-O-O).

Binbo also checks whether castling allowed or not acording to the chess rules.

Castling examples:

% White castling kingside
binbo:move(Pid, <<"e1g1">>).
binbo:san_move(Pid, <<"O-O">>).

% White castling queenside
binbo:move(Pid, <<"e1c1">>).
binbo:san_move(Pid, <<"O-O-O">>).

% Black castling kingside
binbo:move(Pid, <<"e8g8">>).
binbo:san_move(Pid, <<"O-O">>).

% Black castling queenside
binbo:move(Pid, <<"e8c8">>).
binbo:san_move(Pid, <<"O-O-O">>).

Promotion

Binbo recognizes promotion when:

• White pawn moves from square of rank 7 to square of rank 8;

• Black pawn moves from square of rank 2 to square of rank 1.

Promotion examples:

% White pawn promoted to Queen:
binbo:move(Pid, <<"a7a8q">>).
binbo:san_move(Pid, <<"a8=Q">>).
% or just:
binbo:move(Pid, <<"a7a8">>).
binbo:san_move(Pid, <<"a8">>).

% White pawn promoted to Knight:
binbo:move(Pid, <<"a7a8n">>).
binbo:san_move(Pid, <<"a8=N">>).

% Black pawn promoted to Queen:
binbo:move(Pid, <<"a2a1q">>).
binbo:san_move(Pid, <<"a1=Q">>).
% or just:
binbo:move(Pid, <<"a2a1">>).
binbo:san_move(Pid, <<"a1">>).

% Black pawn promoted to Knight:
binbo:move(Pid, <<"a2a1n">>).
binbo:san_move(Pid, <<"a1=N">>).

En passant

Binbo also recognizes the en passant capture in strict accordance with the chess rules.

Getting FEN

binbo:get_fen(Pid) -> {ok, Fen}.

Example:

> binbo:get_fen(Pid).
{ok, <<"rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1">>}.

PGN loading

binbo:load_pgn(Pid, PGN) -> {ok, GameStatus} | {error, Reason}.

binbo:load_pgn_file(Pid, Filename) -> {ok, GameStatus} | {error, Reason}.

where:

• Pid is the pid of the game process;

• PGN is a Portable Game Notation, its type is binary();

• Filename is a path to the file from which PGN is to be loaded. Its type is binary() or string().

• GameStatus is the game status.

Function binbo:load_pgn/2 loads PGN itself.

If PGN is pretty large and you are able to load it from local file, to avoid sending large data between processes, use binbo:load_pgn_file/2 since it’s highly optimized for reading local files.

To extract move list, Binbo takes into account various cases specific to PGN such as comments in braces, recursive annotation variations (RAVs) and numeric annotation glyphs (NAGs).

Examples:

%% Binary PGN:
load_pgn() ->
  PGN = <<"1. e4 e5 2. Nf3 Nc6 3. Bb5 a6">>,
  {ok, Pid} = binbo:new_server(),
  binbo:load_pgn(Pid, PGN).

%% From file:
load_pgn_from_file() ->
  Filename = "/path/to/game.pgn",
  {ok, Pid} = binbo:new_server(),
  binbo:load_pgn_file(Pid, Filename).

Board visualization

binbo:print_board(Pid) -> ok.
binbo:print_board(Pid, [unicode|ascii|flip]) -> ok.

You may want to see the current position right in Elang shell. To do it, call:

% With ascii pieces:
binbo:print_board(Pid).

% With unicode pieces:
binbo:print_board(Pid, [unicode]).

% Flipped board:
binbo:print_board(Pid, [flip]).
binbo:print_board(Pid, [unicode, flip]).

Game status

binbo:game_status(Pid) -> {ok, GameStatus} | {error, Reason}.

where:

• Pid is the the pid of the game process;

• GameStatus is the game status itself;

• Reason is the reason why the game status cannot be obtained (usually due to the fact that the game is not initialized via binbo:new_game/1,2).

The value of GameStatus:

• continue - game in progress;

• checkmate - one of the sides (White or Black) checkmated;

• {draw, stalemate} - draw because of stalemate;

• {draw, rule50} - draw according to the fifty-move rule;

• {draw, insufficient_material} - draw because of insufficient material;

• {draw, threefold_repetition} - draw according to the threefold repetition rule;

• {draw, {manual, WhyDraw}} - draw was set manually for the reason of WhyDraw.

List of legal moves

binbo:all_legal_moves(Pid) -> {ok, Movelist} | {error, Reason}.

binbo:all_legal_moves(Pid, Movetype) -> {ok, Movelist} | {error, Reason}.

where:

• Pid is the pid of the game process;

• Movelist is a list of all legal moves for the current position. Each element of Movelist is a tuple {From, To} or {From, To, Promo}, where:

  • From and To are starting and target square respectively.

  • Promo is one of the atoms: q, r, b, n (i.e. queen, rook, bishop, and knight respectively). Three-element tuple {From, To, Promo} occurs in case of pawn promotion.

• Movetype can take on of the values: int, bin, or str.

The call binbo:all_legal_moves(Pid) is the same as binbo:all_legal_moves(Pid, int).

The values of From and To depend on Movetype as follows:

• int: the values of From and To are integers in range 0..63, namely, square indices. For example, the move from A1 to H8 corresponds to {0, 63}. Use int to get the fastest reply from the game process.

• bin: the values of From and To are binaries. For example: {<<"e2">>, <<"e4">>}.

• str: the values of From and To are strings. For example: {"e2", "e4"}.

Example:

> {ok, Pid} = binbo:new_server().
{ok,<0.212.0>}

%% Start new game from FEN that corresponds to Position 5
%% from Perft Results: https://www.chessprogramming.org/Perft_Results
> binbo:new_game(Pid, <<"rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8">>).
{ok,continue}

> {ok, Movelist} = binbo:all_legal_moves(Pid).
{ok,[{51,58,q},
     {51,58,r},
     {51,58,b},
     {51,58,n},
     {26,53},
     {26,44},
     {26,40},
     {26,35},
     {26,33},
     {26,19},
     {26,17},
     {15,31},
     {15,23},
     {14,30},
     {14,22},
     {12,29},
     {12,27},
     {12,22},
     {12,18},
     {12,6},
     {10,18},
     {9,25},
     {9,17},
     {8,24},
     {8,16},
     {7,...},
     {...}|...]}

%% Count moves:
> erlang:length(Movelist).
44

> binbo:all_legal_moves(Pid, bin).
{ok,[{<<"d7">>,<<"c8">>,q},
     {<<"d7">>,<<"c8">>,r},
     {<<"d7">>,<<"c8">>,b},
     {<<"d7">>,<<"c8">>,n},
     {<<"c4">>,<<"f7">>},
     {<<"c4">>,<<"e6">>},
     {<<"c4">>,<<"a6">>},
     {<<"c4">>,<<"d5">>},
     {<<"c4">>,<<"b5">>},
     {<<"c4">>,<<"d3">>},
     {<<"c4">>,<<"b3">>},
     {<<"h2">>,<<"h4">>},
     {<<"h2">>,<<"h3">>},
     {<<"g2">>,<<"g4">>},
     {<<"g2">>,<<"g3">>},
     {<<"e2">>,<<"f4">>},
     {<<"e2">>,<<"d4">>},
     {<<"e2">>,<<"g3">>},
     {<<"e2">>,<<"c3">>},
     {<<"e2">>,<<"g1">>},
     {<<"c2">>,<<"c3">>},
     {<<"b2">>,<<"b4">>},
     {<<"b2">>,<<"b3">>},
     {<<"a2">>,<<"a4">>},
     {<<"a2">>,<<...>>},
     {<<...>>,...},
     {...}|...]}

> binbo:all_legal_moves(Pid, str).
{ok,[{"d7","c8",q},
     {"d7","c8",r},
     {"d7","c8",b},
     {"d7","c8",n},
     {"c4","f7"},
     {"c4","e6"},
     {"c4","a6"},
     {"c4","d5"},
     {"c4","b5"},
     {"c4","d3"},
     {"c4","b3"},
     {"h2","h4"},
     {"h2","h3"},
     {"g2","g4"},
     {"g2","g3"},
     {"e2","f4"},
     {"e2","d4"},
     {"e2","g3"},
     {"e2","c3"},
     {"e2","g1"},
     {"c2","c3"},
     {"b2","b4"},
     {"b2","b3"},
     {"a2","a4"},
     {"a2",[...]},
     {[...],...},
     {...}|...]}

Setting a draw

It is possible to set a draw via API:

binbo:game_draw(Pid) -> ok | {error, Reason}.
binbo:game_draw(Pid, WhyDraw) -> ok | {error, Reason}.

where:

• Pid is the pid of the game process;

• WhyDraw is the reason why a draw is to be set.

Calling binbo:game_draw(Pid) is the same as: binbo:game_draw(Pid, undefined).

Example:

% Players agreed to a draw:
> binbo:game_draw(Pid, by_agreement).
ok

% Trying to set a draw for the other reason:
> binbo:game_draw(Pid, other_reason).
{error,{already_has_status,{draw,{manual,by_agreement}}}}

Stopping game process

If, for some reason, you want to stop the game process and free resources, use:

binbo:stop_server(Pid) -> ok | {error, {not_pid, Pid}}.

Function terminates the game process with pid Pid.

Stopping application

To stop Binbo, call:

binbo:stop().

Building and testing

Two possible ways are presented here for building and testing the application (with make and rebar3).

Building

$ make

$ rebar3 compile

Dialyzer

$ make dialyze

$ rebar3 dialyzer

Testing

$ make test

$ rebar3 ct --verbose

Code coverage

$ make cover

$ rebar3 cover

Generating Edoc files

$ make docs

$ rebar3 edoc

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 aproach 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 requred for the attack mask);

• for bishop on A1 it is 64 (2^6 = 64, 6 bits requred 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 atack 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.

Changelog

See CHANGELOG for details.

Contributing

Want to contribute? Really? Awesome!

Please refer to the CONTRIBUTING file for details.

License

This project is licensed under the terms of the Apache License, Version 2.0.

See the LICENSE file for details.