Chess Engine, Part 1

Introduction

A number of years ago, I decided to combine my software development enthusiasm with my interest in chess. It would be interesting to write a chess-playing engine! And I’ll learn a lot! In my spare time, I started to research the topic. The following rules were decided upon, after careful thought.

1. I’ll have to write everything from scratch. Do not use any existing chess programming-related libraries.
2. Write the program in Java.

And with that, I started my journey down this complex journey!

Note: It’s assumed that the reader has an understanding of chess. Also, the colors White and Black (when capitalized) refer to the two sides of the two-player adversarial game. Furthermore, the term “chess state” (or just “state”) simply refers to the game at any given point in time, e.g. which pieces are occupying which squares, and whose turn it is to move. This article describes my software design approaches. However, I have not released any source code at this time.

Design Paradigms

The first major design decision was whether to represent the chess state in a board-centric way or a piece-centric way.

1. The board-centric approach puts emphasis on what’s on the board. Specifically, this approach answers the question of which pieces are currently occupying which squares.
2. The piece-centric approach can be thought of as a master piece table, with a map of which square each piece is occupying (if anywhere).

I learned about this key design tradeoff from Chess Programming Wiki. I made the decision to go with the board-centric approach because it was more intuitive to me. As a human, I see the physical chess board first, then I see the pieces on the board.

The next major design decision was regarding how to represent the state transitions over the course of a chess game. The classical computer science concept of a state machine made perfect sense. Given a current state, plus a move, the next state is arrived at.

Next is the representation of the board-centric state from a data structure perspective. I created a State class, and chose to use a simple 8x8 array. Then, a Piece class was created, which is a generic superclass representing a concrete chess piece (subclass) at runtime. A State object can have up to 64 Piece objects, although in practice, at most 32 of the 64 squares are occupied. Exactly 32 squares are occupied at the starting position of the game. I also wrote translation functions to convert chess ranks (1..8) and chess files (a..h) to their respective array indices. Shown below is the Java class inheritance diagram:

class inheritance diagram

Using the aforementioned design constructs, the appropriate chess pieces are instantiated to represent their occupancy in a given square. After consideration of alternatives, I decided to use the Java “null” object to represent unoccupied squares. Thus, it’s imperative that “null” checks are performed before any attempts to operate on a Piece are made!

Engine V1

The first major version of the chess engine is algorithmic in nature, meaning, the logic is programmed in. It does not utilize any machine learning (a modern form of artificial intelligence). The algorithmic approach is what Stockfish uses. Stockfish is arguably the world’s most powerful chess engine, although it lost to the AI/ML-based AlphaZero in 2017 under certain conditions. Stockfish is also open source. As stated above, my approach was not to use any portion of an existing chess engine’s code, but instead to write my own.

In order to understand how “good” a chess state is for a given player, which translates to probability of win, the concept of a score is defined based upon the three principles of chess:

1. Material (Pieces)
2. Position (how the good pieces are at controlling squares)
3. Time (Tempo)

Material is relatively easy to understand. For the purposes of my simple chess engine V1, I took the standard points for each piece, which all beginners learn early on. Positional strength is much more difficult, but as a simplifying design point, the more squares a piece can control, the greater its positional “points”. Also, more points are given for the center squares (vs flank squares). The concept of time is given “for free”, since the engine is always trying to maximize its chances of winning as quickly as possible. So the score of a given chess state is the sum of the material and positional points.

The engine utilizes a minimax approach. The algorithm seeks to maximize its chances of winning, while minimizing the chances that the opponent will win. Recursion is used explore all possible moves relative to the current state, and answer the following questions:

1. What’s the score of a given state?
2. What’s the best score that can be achieved if a given move was made?

As any computer science-minded reader may interpret, the above two questions align directly with a base (terminal) case and a recursive case of the algorithm. The algorithm will recursively explore all possible moves until a preset game tree depth is reached. Then, the score is determined for the terminal state. The recursive stack begins to “pop”. Using the rule of zero-sum game, which exists in all two-player adversarial games such as chess, the score is inversed with every state transition (“pop”). That is to say, the better my opponent’s move is, the worse it is for me, and vice versa.

A simple illustration-based example is the best way to communicate the best-move algorithm. Note that this is a fictitious game tree used solely for the mathematical verification of the algorithm.

In this example, there are a maximum of two depth levels being considered for the game tree, and each state has two possible move options. Each box represents a state on the game tree. The root of the tree is always at depth level zero (the leftmost box). In this example, it is White to move. With each successive depth, the color to move alternates, for example, it’s Black to move at depth level one. There are four terminal states at depth level two. The arrows show the possible progression of moves that White can move, followed by what Black can move. Notice that ideally, although improbably, White would like to attain the best score of 7/4 (1.75), or the second best score of 16/11 (1.45). The third score is 7/8 (0.875), and the worst score is 5/11 (0.45). As we’ll see, the best move results in the third score, 7/8. Why is that? The key principle is that in the game of chess, the best move is not just the immediate outcome of the move you make, but the net result of what your opponent may respond with! For chess engine development, the key assumption is that the opponent always responds with the best move. This principle, in conjunction with the concept of zero-sum game, is why the score is inversed as the state is popped from the recursion stack.

For this particular example, the upper right state (the best state) has a score of 7/8 for White, which is returned to the preceding state as a score of 8/7 for Black. That 8/7 is considered alongside the other move option, which has a score of 4/7. Since 8/7 is the better score, Black picks that move, and that score is returned to the preceding state as a score of 7/8. The 7/8 is compared with 5/11, and 7/8 is better score for White. At this point, because the evaluation process is at the root of the game tree, the best-move evaluation is complete. The move will be made by the chess engine.

Notice how the evaluation of the “goodness” of a state occurs at the terminal depth, also known as the base case. The non-terminal or recursive case is simply a combiner of the results returned to it as a result of the “pop”. This is a fundamental characteristic of recursion. Thus, the deeper the evaluation depth, the further into the future the engine can see, and the smarter the engine. But this comes at a great cost, that is, CPU cycles!

Although I was able to confirm empirical correctness through multiple test cases, including the reference example illustrated above, a formal mathematical proof was desired. So I used computer science induction to formally prove that the algorithm works to find the best move. Induction is the mathematical equivalent of a recursive algorithm. The details of the inductive proof are not shown here due to brevity, but there are references available on the Internet that show how induction is applied to prove recursive algorithms. On a side note, I was happy to annotate the end of my proof with “Q.E.D.” (Latin phrase for “what was to be shown”).

User Interface

Because the purpose of the chess engine is to explore the algorithmic aspects of a chess “brain”, no emphasis was placed on the user interface. In fact, it uses a very terminal-like ASCII text “roll and scroll” format. The following is the opening position from White’s viewpoint:

Inputs are accepted on the console to determine the from-to squares of a chess move (e.g. “e2 e4”), and other commands such as “quit” for exiting the application. The chess engine is executed as a console application, and can be deployed to any operating system with a Java Runtime.

Castling

Castling broke every rule of my original “state machine” design! I admit that I should have taken this special chess move into account before designing the “state machine”. Luckily, the end result was not too bad; additional processing was performed to artificially add the second half of the move (the Rook portion), when the first half of the move (the King portion) was specified as a move. Because the King moving two squares is always illegal except in the case of Castling, that was the special-case trigger to determine if Castling is legal, and if so, to complete the Castling by applying the aforementioned Rook portion of the move. In order to determine legality, the following checks were performed:

1. The King and the participating Rook have not moved yet,
2. The squares between the King and the participating Rook are unoccupied,
3. The King is not currently in check (‘e’ file),
4. The King does not traverse through check (‘f’ or ‘d’ file), and
5. The King does not end up in check at its destination (‘g’ or ‘c’ file).

The same “state machine” design was used to perform these checks. The King is “duplicated” onto the additional squares noted in #4 and #5. With the “ghost” Kings in place, additional determinations of whether the King is in check are performed. Then, the future states are simply thrown away.

First Real Game

My long-term colleague and friend, Ben (whose last name will remain strictly unnamed), kindly agreed to play my chess engine. He’s a beginner player that knows the rules of chess, but does not play competitively or frequently. This was the first real test of my Engine V1! Playing as Black, my engine won! Surprisingly, according to a game analysis by lichess, my favorite online chess website, my engine did well and did not commit any mistakes! There were a few inaccuracies due to the lack of depth, e.g. lack of seeing checkmate in N, where N is greater than two. That’s interesting, because I’ve always thought that my engine is weak, and plays oddly. The following diagram shows the game evaluation, where the midpoint represents equal possibility of win or loss (e.g. at the beginning of the game). The lower the red line, the higher probability of win for Black. As can be seen, after a number of moves, the line dropped very low, so my chess engine was well on its way to a victory.

Lessons Learned

There were many lessons learned during my adventure into chess programming, including:

1. Testability: Due to the massive number of possible moves available at a given game state, and multiplied by the number of possible moves thereafter, it was very difficult to test a “good enough” range of possibilities. Custom-state injection, a feature that I added a bit afterwards, helped with the ability to test specific test cases without having to start a new chess game every time. Automated testing may help too, but I did not try that.
2. Debugging: Recursion is challenging to debug, especially with the expansive nature of chess (see point #1 above). It can be hard to see the recursive depth, when deep in a debugging mindset.
3. Open vs closed interfaces: Because I jumped into my own design with few references to existing approaches, I neglected to consider more open designs from a data interface perspective, such as the way to represent the board and its pieces.
4. Performance: The intensive computing requirements of chess engine is always a design consideration, even though computing power has come such a long way since the 1990s. There are optimization methods available relative to minimax, but I’ve not tried them.

Credits and Acknowledgments

I would like to humbly acknowledge the (Sun) Oracle Java programming language creators for a modest memory-safe language of choice. True to its original vision, Java apps are written once and run everywhere (with certain limitations).

I also acknowledge the chess programming resources on the Internet. Chess Programming Wiki is just one of many amazing resources.

I’m very grateful to lichess as an outstanding open-source chess platform. To me, as a developer, lichess is the gold standard.

Last but not least, I’ve very appreciative of Ben’s time and willingness to participate in an experiment with my chess engine project. It was not easy at all to find someone to take on my chess engine!

I’ll appreciate any questions and comments that you may have. Thank you for reading. Be on the lookout for Part 2, which adds AI/ML as an engine approach! (last updated on Sun 3/5/23 at 1902)