www.fam-petzke.de

Chess Programming Tutorial...[]

Part 2: Fundamentals and Architural Overview

The main components of a chess engine

A chess engine consists basically out of 4 components

Board - This were the position of all pieces is stored, which side is on the move, casteling rights, en passant square, but also a history of previous positions

Move Generator - This is the part of the engine responsible for generating all moves or special moves (captures only, moves that give check only) for a certain board position

Evaluator - The evaluator calculates a static score for a given board position. A score of 0 means equal chances for both sides. A high negative or positive score indicates an good position for either white or black. The score involves basic stuff like material but also positional factors like double pawns, king safety and passed pawns. The evaluator is responsible for the personality of the engine and influences its strategic or positional play.

Positional Play, Steinitz

Search - This is the algorithm that decides which moves look promising and are to be searched first and more thoroughly than other not promising looking ones. Search is responsible for the tactical strength of the engine. It is usually implemented as a recursive algorithm that calls itself to traverse the game tree up to a certain depth where then the evaluator is used to estimate a score for that position.

If the student ... masters of tactics.

And of course a framework is needed that connects all of those parts together and handles user interface input and output.

Architectural Overview Diagram

Our first simple version of the AOD looks as follows.

AOD

So in this architecture the board and the evaluator are standalone components.

Search and the IO interface are implemented in the framework itself.

The move generator is implemented as part of the board component.

It is possible to make the move generator also a component that receives a board and outputs move lists (and in fact earlier version of my chess engines did that), but now I find it more naturally to see a list of possible moves for a certain board position as property of the board and let therefore the board generate move lists.

How to implement the framework structure

It all starts with a main function. The main function for a chess engine can actually be quiet simple. It just requires a few lines.

/***************************************************************  Create the Chess Engine Object and call its run method  run will loop forever until a "quit" command is received  ****************************************************************/ int main() { TChessEngine* engine; engine = new TChessEngine(); engine->run(); delete engine; return 0; }

The engine constructor will later create the board object, for now it does nothing. The call to run() will enter an infinite loop that polls for user in put and calls methods depending on the commands the user has entered. When the user enters a "quit" command run returns, the chess engine object is deleted and the program terminates.

That's it for the main() function. You will probably never have to modify it again. It will stay that way for the rest of your development work.

So lets have a look at the run() methode of the chess engine. Also fairly simple. It is looping as long as processGuiMessages returns true.

void TChessEngine::run() { for(; ;) // loop forever { if (!processGuiMessages(50)) break; } }

processGuiMessages is a method that looks for a new message or command from the user interface and if no new command is received sleeps for a few milliseconds. This is necessary to prevent an idle engine that has nothing to do to consume a whole processor just by polling for user input.

Note: inputThread is a special class that retrieves complete lines from standard input. Its implementation is very specific as Windows requires slightly different code than Linux (and as the name suggests in the final engine it might execute even as a separate execution thread, so that the engine is responsive even when calculating). For the start it is ok just to use standard libraries calls to read lines from standard in. You might want however wrap this library call into its own class so you can modify its implementation later without impact on your framework.

bool TChessEngine::processGuiMessages(int wait) { if (inputThread.isNewInputAvailable()) { string input = inputThread.getNewInput(); if (input.length() > 0) { return inputHandler(input); } } else if (wait>0) Sleep(wait); return true; }

And finally the call to input handler parses the received input and calls methods depending on the input it received. When it receives a quit command it returns false which will break the loop in the run() method and hands over control back to main(). Here the destructor is called and the program terminates.

bool TChessEngine::inputHandler(string input) { vector v; string string0; split( v, input, " " ); // split the line into a vector of words string0 = v[0];         // the 1st word is the command id if (string0=="quit") return false; if (string0=="uci") { sendUCIResponse(); return true; } // more commands }

So what have we accomplished so far

The skeleton of our engine is done. We have a program that after start executes a loop reading input from standard in and when this input is a "quit" command it terminates.

The important thing here is that we have now a flexible and maintainable framework we can build our chess engine functionality into.

Now let's move on to some more chess related stuff - the chess board!