| Home | Projects | Photos | About |
The purpose of Chess0 is to create a well-design, modular chess engine capable of representing generic data structures present in chess games so that a middle-level student can understand how the information is organized and processed in this type of heuristics-driven applications.
As a Final Year Project application for the Helsinki Metropolia University of Applied Sciences, Chess0 intends to be non-complex and self-explaining in most of its built-in modules. Moreover, it is considered an enriching project from the point of view that several learning processes are put in common in order to deploy a functional version. For instance, abilities in software design, good level of understanding in both procedural and object-oriented programming, application development and deployment, technical documentation, etcetera.
Besides, writing a chess engine application ensures that its creator or creators put together algorithms and data structures, without leaving aside the heuristic part of the problem, for generating board moves.
As I mentioned in the introduction, Chess0 aims, ultimately, at providing a simple-enough chess engine, easy to understand and fulfilling basic requirements for computer-based two-players games. Besides, it is a primary target to create fully understandable source code, easy to follow and update, so that other students can learn from it and contribute at the same time, without having to behold much knowledge.
Chess0 is written in C++, which has advantages and disadvantages. The main disadvantage is the performance (both in processing and memory management). However, the main advantage is far more important for this project, which is the well structuring of the application modules, so that they can be easily understood by Bachelors-level students without knowing much about programming.
In spite the basic requirements, this project is guided on a clear purpose: compare classic (sometimes obsolete) techniques in computer chess with the incorporation of adaptive methods. A clear target here is the Turing test. Computers tend to play always the best move, with a tiny margin for randomization. In practice, Chess0 intends to demonstrate the main differences (mostly visual, on the board) between a classic engine using simple heuristics and an adaptive engine that is capable of modifying its strategy as the board changes during a chess match.
Behind all these ideas, there is an aim for the actual Bachelor's Thesis, which is to experiment and discuss about adaptive behavior in computational intelligent systems. Admittedly, Chess0 (and its whole idea) is far from being a real computational intelligent system, yet it aims for demonstrating classic versus adaptive behaviorism in intelligent systems in a highly simplified manner.
Chess0 provides a simple architectural design, where only a few components communicate with each other in order to offer the user the whole functionality of the program. The two core components of Chess0 are the Application Manager and the Game Manager.
The Application Manager is the component in charge of interfacing the end user and providing an architecture for entering information (commands or moves) into the application. Its tasks are, mainly, to start, carry out and finalize the application, as well as interfacing the Game Manager for managing any ongoing chess game.
On the other hand, the Game Manager is in charge of managing chess games. It keeps track of some information about the current game, who are the players, and how a game is being carried out. The Game Manager is transparent to the end user, and it also interfaces minor modules such as Move Parser and Game for administrating and carrying out a game.
Figure 1 depicts the general idea of the Chess0 design model. The first interface is the user interface, where the Application Manager interacts with the user. This interaction may occur in two different ways: either through the console (normal behavior) or through a graphical user interface (using an Xboard-compliant program), in which case the application functionality is delegated from the Application Manager to the XBoard component.
Then, it is the task of the Application Manager to read the input from the user and analyze it. If the input is a command, the application will execute that command (remember that a command may modify the course of the application, finalize the application, start a new game, modify the course of a game and finalize a game). Nevertheless, if the input is not a command, then the Application Manager communicates with the Game Manager in order to discover if the input is a valid move or not.
If the input is a valid move, then the Game Manager applies the move to the current game (if there is any), with the help of the Game class. The Game class updates certain details about the current game and then issues Board to physically perform the move. The function of the Move Parser is simply to see if an input is a valid move or not, due to the support for SAN (Standard Algebraic Notation).
Last, the Board class holds all the necessary data structures (squares, pieces, etcetera) and all the mandatory rules for playing chess. When a move is being performed, the Game module interacts with Board and hence the latter alters its data structures to reflect the last move issued by the former.
Chess0 has one clear goal: to be simple enough to be understood by BSc students. The intention is to create modular code, yet powerful enough to provide an effective chess engine. The language I chose is C++. The decision does not condition the simplicity and readability of the code, but it is a personal choice, as C++ was one of the programming languages I did not use before.
To keep data, Chess0 uses most of the facilities provided in the C++ STL library. This is a decision that implies both positive and negative consequences. The obvious result of using the C++ standard library is that the program is portable out of the box and the data structures are already defined, so the code is reduced and as simplified as possible.
On the negative side, the optimizations are few, and everything is left to the C++ implementation. This might not seem an issue at first, but it is indeed, since computer chess may suffer from heavy optimizations that are admittedly not present in a simple standard library.
The most heavily used data structures are STL::vector, in which Chess0 keeps most of the status variables for restoring board situations. Its use is straightforward, yet it produces a non-effective overall behavior, as mentioned above. Some of the non-standard optimizations include the basic use of Bitboards, which are 64-bit numbers holding a certain structure for a chess board. All the utilities to convert from STL-utilities to non-STL-utilities are mainly located in the files src/utils and src/utils.cpp.
Most of the algorithms used in Chess0 are a recreation of a common solution already known in Computer Science. However, the implementation is genuine in almost every case. Some basic algorithms, such as vector searches or vector sorting, are extracted from the C++ STL library. The most important algorithms and techniques used in Chess0 are:
All the algorithms presented in the list above are related to the AI implementation. Out of that, there is no major implementation of any algorithm, since most of the things out of the AI are simple tasks that are usually accomplished by the C++ existing algorithms.
Chess0's main purpose is to work on the command line. However, it does not provide any argument (as when you call the program), but the xboard argument, by which it understands that the program is interfacing an XBoard's protocol-compatible graphical chess board.
Definitely, you don't need a graphical board to play Chess0, as it has been designed for console use, and it can display an ASCII board representation for visualizing the ongoing match.
By default, you are greeted and white are set to move. You may introduce a move or a command. In order to obtain some help, you may type the command help. Furthermore, if you wish to obtain extra information (in detail) about one of the commands presented in the general help, you may type help COMMAND.
If you want to start playing, just type a move into the prompt. On the other hand, if you want Chess0 to go first, just type go, and Chess0 will take the control for the white. As soon as you want to take the whole control over the game, just type manual and you will be able to play both sides (manually). Last, if you wish to visualize the board at any time, just type display, and you will see an ASCII representation of it.
In order to use Chess0 with an XBoard-compatible graphical chess board (e.g. WinBoard, eboard, etcetera), you must run the graphical board an specify the path to Chess0 with the argument xboard. See the example below:
Obviously, you might have to change the path of ./chess0, depending on where you have the executable. Moreover, on Windows systems, probably you will use WinBoard, and so you must first run the program and then set the path for Chess0, in order to play with it.
Figure 1 shows a match between Chess0 and me. As you may appreciate, you can take advantage of the graphical board and flip sides, and you can do actually many more things. In figure 2, it is noticeable that Chess0 is able to play a good-enough opening using much less time, due to all the improvements brought to v0.3.1.
From v0.3.1 to v0.3.2
From v0.3 to v0.3.1
From v0.2 to v0.3
From v0.1 to v0.2
I have set up an online repository for Chess0, so that friends can browse the code and contribute, if they like. Honestly, I already got more patches and help than what I expected, so below I provide the URL for accessing the online repository, in case you may be interested:
TBD
