Chess Engine

Some design notes on how to develop a chess engine.

A chess engine is an application which is capable of playing chess and uses a standard protocol to communicate with an external Graphical User Interface (GUI).

Here are a couple of chess GUIs which are freely available:

And a couple of communication protocols:

In both protocols the chess engine is an executable which is started by the GUI and which exchanges plain text commands with the GUI through its standard input and output.

As an example, here is the C++ source code for the Hello World chess engine, which starts responding to a GUI using the UCI protocol and is only capable of playing (as black) the move e7-e5 in response to e2-e4:

#include <iostream> // for cin, cout
#include <string>
 
//=============================================================================
    int main ()
//=============================================================================
{
    using namespace std;
 
    string Line;
 
    // Make sure that the outputs are sent straight away to the GUI
    cout.setf (ios::unitbuf);
 
    while (getline (cin, Line))
    {
        if (Line == "uci")
        {
            cout << "id name Hello World" << endl;
            cout << "id author Silvestro Fantacci" << endl;
            cout << "uciok" << endl;
        }
        else if (Line == "isready")
 
            cout << "readyok" << endl;
 
        else if (Line == "ucinewgame")
 
            ; // nothing to do
 
        else if (Line == "position startpos moves e2e4")
 
            ; // nothing to do
 
        else if (Line.substr (0, 3) == "go ")
 
            // Received a command like:
            // "go wtime 300000 btime 300000 winc 0 binc 0"
            cout << "bestmove e7e5" << endl;
        else
            // Command not handled
            cout << "what?" << endl;
    }
 
    return 0;
}

… and here is a screenshot of Arena showing Hello World's move:

Arena-Hello-World-Screenshot.jpg

This diagram is a first stab at what could be the main software components of a Chess Engine and their "use" relations:

Chess-Engine-Design.jpg

This type of design is aimed at decoupling as far as possible from each other all the issues that need to be tackled in order to develop a chess engine. E.g.:

  • How will the chess engine deal with different GUI protocols or different versions of the same GUI protocol? —> Protocol Interpreter
  • How will positions on a chessboard be represented? —> Chessboard Position
  • How can it be estimated how good/bad a chessboard position is, without looking at the moves ahead? —> Evaluate
  • Which type of forward search algorithm will the chess engine employ? —> Search
  • How can the operating system multi-tasking capabilities be used to start an independent chess engine task? —> Tasking
  • How will the chess engine track the players' time? —> Clock
  • How will the chess engine synchronise with the GUI? —> Commands/Responses

Here is a tentative example of a possible sequence of events, which may clarify what the Chess Engine components might do and how they could interact with each other:

  • The Chess GUI runs the Chess Engine executable.
  • The Chess Engine main function - which is located in the Protocol Interpreter - is called.
  • The Protocol Interpreter calls the Setup-Engine method in the General Interface
  • The General Interface calls the Start method in Main Task.
  • The Main Task uses the Tasking functions to create and launch its Task (thread).
  • The Task starts its first cycle, suspending on Commands/Responses.
  • The Chess GUI sends the "uci" string to the Chess Engine.
  • The Protocol Interpreter sets itself up to support the Universal Chess Interface.
  • The Protocol Interpreter has a function UCI-Send-Move (Move) which sends the "bestmove <Notation>" string to the Chess GUI, where <Notation> is the algebraic notation returned by the specified object of class Move.
  • The Protocol Interpreter requests the General Interface to use the UCI-Send-Move (Move) function.
  • The General Interface forwards the request to Commands/Responses.
  • The Protocol Interpreter gets the <Engine Name> and <Engine Version> information from the General Interface, constructs the string "id name <Engine Name> <Engine Version>" and sends it to the Chess GUI.
  • The Protocol Interpreter gets the <Author’s Name> information from the General Interface, constructs the string "id author <Author’s Name>" and sends it to the Chess GUI.
  • The Protocol Interpreter sends the "uciok" string to the Chess GUI.
  • The Chess GUI sends the "isready" string to the Chess Engine.
  • The Protocol Interpreter calls the Wait-Until-Ready method in the General Interface.
  • The General Interface checks the Main Task status in the Commands/Responses module.
  • The status is ready, hence the General Interface returns from the call.
  • The Protocol Interpreter sends the "readyok" string to the Chess GUI.
  • The Chess GUI sends the "ucinewgame" string to the Chess Engine.
  • (Chess Engine actions to be defined)
  • The Chess GUI sends the "position startpos moves e2e4" string to the Chess Engine.
  • The Protocol Interpreter parses "position startpos".
  • The Protocol Interpreter calls the Set-Initial-Position method in the General Interface.
  • The General Interface calls the Reset method in Chessboard Position.
  • The Protocol Interpreter parses "moves".
  • The Protocol Interpreter parses "e2e4" and converts it to an object of class Move.
  • The Protocol Interpreter calls the Apply-Move (Move) method in the General Interface.
  • The General Interface calls the Apply-Move (Move) method in Chessboard Position.
  • The Chess GUI sends the "go wtime 300000 btime 300000 winc 0 binc 0" string to the Chess Engine.
  • The Protocol Interpreter parses "go".
  • The Protocol Interpreter parses "wtime 300000" and converts "300000" to an object of class Time representing 5 minutes.
  • The Protocol Interpreter calls the Set-Total-Time (White-Player, Time) in the General Interface.
  • The General Interface calls the Set-Total-Time (White-Player, Time) in Clock.
  • The Protocol Interpreter parses "btime 300000" and does likewise with Black-Player.
  • The Protocol Interpreter parses "winc 0" and calls the Set-No-Intermediate-Time-Control (White-Player) in the General Interface.
  • The General Interface calls the Set-No-Intermediate-Time-Control (White-Player) in Clock.
  • The Protocol Interpreter parses "binc 0" and does likewise with Black-Player.
  • The Protocol Interpreter calls the Start-Engine method in the General Interface.
  • The General Interface releases the Task suspended on Commands/Responses.
  • The Protocol Interpreter suspends on the standard input, waiting for the next command from the Chess GUI.
  • Task reads from Chessboard Position whether it is requested to play a White or a Black player’s move.
  • Task reads from Clock how much time is left and decides how much time to spend searching for the best move.
  • Task initialises Search using Chessboard Position.
  • Task starts cycling, at each cycle progressing Search a little bit further and then checking whether the time to spend on it is over.
  • Search constructs a forward search tree whose nodes represent chess positions and whose links represent chess moves, expanding the most promising branches according to Evaluate.
  • The Search class is actually a generic class with parameters Nodes, Links, Figure-of-Merit (Node), etc… that Task instantiates appropriately.
  • Evaluate statically examines a chess position and returns a real number indicating how good the position appears to be.
  • When the search time is over, Task reads from Search the most promising move and calls Send-Move (Move) in the Commands/Responses.
  • This triggers a call to UCI-Send-Move (Move) and the "bestmove <Notation>" string to be sent to the Chess GUI.
  • Task suspends on Commands/Responses.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License