Chess0 (Chess Engine for Educational Purposes) Claudio M. Camacho Last revised: 19.7.2009 Table of Contents ----------------- 1. Motivation 2. General Description 3. Architectural Design 4. Detailed Design 5. Implementation 6. Versioning 7. Testing 8. License 9. More Information 1. Motivation ------------- 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. 2. General Description ---------------------- 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. 3. Architectural Design ----------------------- 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. 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. 4. Detailed Design ------------------ TBD 5. Implementation ----------------- 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: * negamax(): a simplification of the minimax algorithm for finding the best possible moves at each board situation * alpha-beta pruning: an addition to the negamax() algorithm to speed up move searches * quiescence search: an extension to the move search that attempts to avoid the horizon effect found in classical AI approaches All the algorithms presented in the list above are related to the AI implementation. Out of that, there is no major implementation of anyalgorithm, since most of the things out of the AI are simple tasks that are usually accomplished by the C++ existing algorithms. 6. Versioning ------------- The release cycle of Chess0 is simple enough to be explained in a few lines. There are three different branches: - stable: vN.x.y (N is a non-zero natural number, and x/y are <= 9) - testing: vN.x.y (N = 0, or x or y equal 99) - head vN.x.y.z (N is any natural number including 0, and y equals 99) Examples: Chess0 v0.1.2 -> Testing version. 1 major, 2 patches. Chess0 v0.99.3 -> Testing version. Turning to branch 1, 3 patches. Chess0 v2.3.0 -> Stable version. Branch 2, version 3, 0 patches. Chess0 v2.99.3 -> Testing version. Turning to branch 3, 3 patches. Chess0 v2.2.99.1 -> Development version. Turning to 2.3, 1 patch. 7. Testing ---------- The main tester is Tito Houzy. For more information about how to test and bug-hunt in Chess0, please contact him directly. Furthermore, there is another contributor, mainly for ideas and optimizations, which is C2H5OH, whom you may contact if you want to cooperate with your own ideas and improvements to Chess0. For extended information and more technical details about the implementation, debugging or profiling, please contact the author of the program. 8. License ---------- This is free software. You may redistribute copies of it under the terms of the GNU General Public License There is NO WARRANTY, to the extent permitted by law. For more information, please read LICENSE. 9. More Information ------------------- For more information, please me directly by email or any other means.