ENTUAL Chessbot Part 2
Chess, the royal game, is one of the oldest board games in the world. For centuries, chess enthusiasts have been testing their strategic thinking and moving the 32 pieces with intense concentration; the Entual team is, of course, no exception.
While in the pre-digital era players like Bobby Fischer and Boris Spassky dominated the action on the board, today it is AI-powered chess programs that are unbeatable. Even current grandmasters like Magnus Carlsen and Hikaru Nakamura have long since had to admit defeat in the face of modern technology.
The most prominent and currently strongest chess program is Stockfish, which uses neural networks, among other things, to find the best moves in every position.
But how does a chess computer actually work? What algorithms are used to defeat even the strongest human players? Is it possible to program a chess computer yourself without much trouble?
Entual explored these questions over the summer. The result is a prototype chess computer, powered by Ab Initio, that will give even fairly advanced players a run for their money.
In our previous blog post , we took an in-depth look at FEN notation and the basic functionality of a chess computer. Now we’ll turn our attention to identifying all possible moves in a given board position and explore how a rating function for those moves can be implemented.
https://www.pexels.com/photo/man-holding-chess-piece-277124/
Move determination
Before a chess computer can determine the best move for a given board position, it must first identify all possible moves. To do this, it iterates through all the pieces still on the board belonging to the player whose turn it is. Taking into account the position of each piece and applying the known rules governing how each piece can move, the computer then determines the player’s legal moves. Particular care must be taken to ensure that moves resulting in a check on one's own king are excluded. All moves identified in this way transform the FEN of the board position into a new FEN.
We will analyze the algorithm for determining a knight's moves using the following board position as an example:
There are eight squares on the board that the knight on e5 could currently move to. Legal moves are those that result in capturing an opponent’s piece (d7 and f7) or end by landing on an unoccupied square. Moving the knight to the d3 square, however, is not allowed, since a piece of the same color is already there.
None of the seven possible moves results in a check on the white king, which is why they are all valid.
For the knight, rook, and queen, the move-calculation algorithm works slightly differently, as it does not search a fixed number of target squares. Instead, moves are executed in each of the four directions until the edge of the board is reached, a capturing move is made, or a piece of the same color is in the way.
In pseudocode, it looks like this:
for each direction_of_movement:
while (ON_BOARD):
Move piece one space forward
if (SQUARE_FREE):
New move found
else if (OPPONENT'S_PIECE_ON_SQUARE):
New move found
exit while
else if (TEAM'S_PIECE_ON_SQUARE or OFF_BOARD):
exit whileThe following diagram, based on the pseudocode above, illustrates the moves of a rook in an endgame, with the arrowheads representing possible final positions:
Evaluation function
In the next step, the chess computer must evaluate which of the moves it has just identified are particularly advantageous, and which ones should be avoided. This requires a quantitative evaluation function that assigns a numerical value to each board position. A positive number indicates an advantage for White, while a negative number indicates an advantage for Black. The higher the absolute value of the number, the greater the advantage in the position being analyzed.
The challenge facing the development team is now to devise a particularly effective evaluation function that takes into account all relevant parameters of the board position. The remaining pieces on the board provide a good starting point for this. Starting from a neutral value of 0, the values of the white pieces are added, while those of the black pieces are subtracted. A generally accepted point value for the pieces is as follows: Queen: 9, Rook: 5, Knight: 3, Bishop: 3, Pawn: 1. Other factors, such as the degree of development of a player’s pieces or the safety of the king, should also be taken into account in the evaluation function. A central knight, for example, has a higher point value than a knight on the edge of the board. An advanced passed pawn in the endgame is also worth more than a pawn on its starting square.
The evaluation function is now evaluated for the following board position:
White: 2 rooks (10) + 1 knight (3) + 1 bishop (3) + 2 pawns (2) = 18
Black: 1 queen (9) + 1 bishop (3) + 3 pawns (3) = 15
This results in a total value of 18–15 = +3, which gives White an advantage.
For the sake of simplicity, we will assume a valuation function that takes into account only the pieces still on the board, but initially disregards all strategic principles.
Minimax algorithm
A rudimentary chess computer can be built using the following principle: For any given board position, all possible moves are identified, executed, and the resulting board position is evaluated. The move that leads to the highest evaluation for White (and the lowest for Black) is then executed.
Consider the following position on the board (White to move):
The move Sxe5 results in a +1 evaluation for White; all other moves result in no material gain and therefore a balanced evaluation of 0. The chess computer therefore suggests the check move for White.
Let’s now consider another position on the board (White to move):
Here, too, a simple chess computer will recommend the check move Sxe5, as it remains the only move that leads to a material gain.
Of course, any amateur player immediately realizes that the pawn on e5 is protected, so capturing it would not be a good move. The chess computer must therefore not only determine all possible moves for White, but also all of Black’s possible responses to each of those moves. If any of Black’s responses contains a move that is disadvantageous for White, the initial White move must be discarded and another move made. The algorithm must therefore maximize the evaluation function for the white player, subject to the constraint that the black player will attempt to minimize the evaluation function. This line of reasoning leads to the so-called minimax algorithm, which also forms the basis of the Entual Chessbot.
The minimax algorithm is an algorithm from the field of game theory that can be used to calculate optimal moves for two-player games with perfect information. A key component of the minimax algorithm is a value function for the game. It is assumed that both players play optimally. Player White attempts to maximize the value function, while Player Black attempts to minimize it.
In the first step, starting from a board position, the game tree of all possible moves is generated to a predefined depth. For simplicity, we consider a depth of 3 and assume that each player always has only two possible moves to choose from. The rows in the game tree alternate between the maximizing player and the minimizing player. At the bottom of the game tree, the static evaluation function is used to quantify the resulting board positions.
Now the game tree is backtracked. White goes first and therefore always chooses the move that maximizes the evaluation function. Next, it is Black’s turn, and Black therefore always chooses the move that minimizes the evaluation function.
Once you reach the top, applying the minimax algorithm provides a dynamic evaluation of the current board position as well as the best move.
One drawback of the minimax algorithm is the rapidly increasing number of board positions that must be analyzed. Assuming an average of 40 possible moves per player, a search depth of 4 would require analyzing 40^4 = 2,560,000 positions. Furthermore, in a naive application of the algorithm, the entire search tree must always be examined, even in cases where certain parts of it cannot affect the result.
However, such depth is essential for discovering powerful tactical techniques, such as temporarily sacrificing a piece to launch a successful attack.
Outlook
In the next blog post , we will explore the technical implementation aspects of the chessbot using Ab Initio and Continuous Graph, as well as the workflow logic employed.