How game theory, the use of vectors & algorithms contribute to the effective operation of today’s chess engines?

Chess is a strategic 64-patch board game, that was invented in the VI century and its charm has reached our times. Erenow the greatest players were spending a lot of time analyzing their games, but in 1951 two scientists – Claude Shannon and Alan Turing, started creating the machine that would analyze the position instead of them . This led to the crucial moment in the game’s history when almost every player used the chess engine to improve their skills. They came to the conclusion that the correlation between moves relies on specific sequences and mathematical concepts, such as vectors, that play a big role in the movement of figures. However, how does math apply to today's chess engines, which are far more advanced and accurate than the one invented in 1951? While discovering this topic tables, chess problems diagrams, and tree problems diagrams are used to fully feel my exploration.

The aim of this exploration isto discover how chess engines work. As a half-professional chess player, the chess engine Stockfish 14+ will be used and all my research will be supported by this engine system. Choosing this system allows to calculate the data as accurately as possible, because Stockfish software is one of the best chess software . The sources used are mainly taken from electronic libraries since the research of chess engines is not finished, and work on it continues. This made it possible to provide the latest information about chess engines. Another aim is to show how powerful are chess engines and compare human and computer capabilities to find the perfect variant, which will lead the player to victory; however, it will appear selectively, when possible.

American mathematician Claude Shannon discovered that in chess there are about 10 legal moves, which makes chess matches unique . For comparison - in the observable universe there are only about 10 atoms. These numbers aren’t fully reliable, because even the best scientists are not able to calculate them, but the difference is still huge. Claude Shannon, stated that it would take 10 years to compute every possible sequence of moves in a game of chess and create a complete, solved game tree.

The undeniable fact is that we as the human species will never be able to count and work with these numbers, so the game will stay too complicated, that’s why players are using the machine to check whether their way of thinking was good during the game. However, the number of possible moves rises after each move very rapidly and they are too big to count even for the machine, so what is the pattern? To think about how huge numbers are included in one chess game shown below values in the Table 1. must be considered. Table 1. represents the changes in possible positions after a few moves.

Players are often trying to learn as many as possible openings, they think that if they learn a few positions it will make them a winning site. Remembering the positions would guarantee a win if the game was strongly solved. The term strongly solved is being used for a game forwhich such a strategy has been determined for all legal positions . Someone who would recognize all of the setups would be winning every time. However, the number of positions istoo big, and that makes it impossible. The fact that neither man nor machine (calculation time is too long) is able to always win the game changes the way players look at chess, after all, is it possible to win something virtually infinite?

Chess engines show the best way of winning the game. At first, the computer creates a list of every legal move that might occur, and then it looks for the responses to listed moves. This is how the thousands of sequences create a game tree, which is a graph that represents every position on the board, that might occur after the next moves. As was said before the number of positions increase rapidly. For instance it took 32 minutes to calculate possibilities after the 4^th move of black (shown in Table 1.) , so the computer had to consider every legal position

For some state s, let’s assume that there are n possible choices: a₁, a₂, . . . , a_n, resulting in new states of the game from state s, respectively: b₁, b₂, . . . , b_n. Further, for each of these states we have again a set of possible choices. Continuing this procedure we naturally get a tree structure.

Move „e4” isthe starting position. A node has one branch for each decision the player can make there . The moves of both players follow each other respectively and the game tree is getting more expanded. Considering that chess has a lot of possible moves it is impossible to create a full game tree. The game tree that is shown above is just theoretical because black has much more responses for white’s move (while the game tree shown in Graph 2. has only three black answers). Many players, who already have great imagination create that kind of game tree (obviously not as extensive as a computer), and at the end of each branch, there is a final position. It should be remembered - technological development is so advanced that already at this stage it can be assumed that a man will never be better than a machine.

The machine istaught basic information. The machine knows how the figures move by using vectors and is aware of the length and width of the board, however by using only those information engines can analyze the movement of the figures on the board however, it still can’t work properly. The main basic rules are considered by the machine to let the engine play a real chess game. The basic game rules such as keeping or moving the king from the check are not enough for the chess engine to work precisely, because the machine does not have a brain and it processes the given by human information and formulas. The machine has a stored program that registers the position of the pieces on the chessboard using coordinates, and thus the possible moves of the pieces on the chessboard described by vectors.

To describe it better - the machine can be compared to human. Beginners have to learn the rules and characteristics of each figure. The same thing is with the chess engine – before it can choose the best move, the programmer have to describe the pattern of movement. Being good at chess is a process that has to be made step by step and even a machine can’t skip any of the steps – otherwise, there will be some gaps in calculations and analysis.

The movement of pieces might be expressed by vectors. In this way, the machine knows what movements a given figure can perform. Although in the chess language each coordinate of the chessboard is described by a letter (A-H) and a number (1-8), inserting the chessboard into the coordinates chart will allow to determine the shifts of the pieces by a given vector. It can be assumed that this isthe most important thing when creating a machine as well as learning how to play chess. Without knowing the movements of the figures, it is not possible to carry out further calculations.

Table 4. Shows how specific figures move using vectors. Each of the example positions shown in the table has a figure stacked on the center d4 (4,4) square to show sample moves for each figure.

The first thing that is calculated by a chess engine is the evaluation of the position by counting the value of the setup which isthe sum of the figures with the values of both players. Each figure has one average value that represents its strength. The values were contractually established by Hans Jack Berliner10 –and are still used to this day. Based on these calculations, the computer can decide which move contributes the most to winning.

Table 3. shows the values of each piece.

To calculate the value of the position, the computer sums up the product of the number of figures and their values. This step is done for both the white and black sides, however, black will be counted identically but with a "minus" sign. This means that if the position is rated positive, the engine sees an advantage for white and in the opposite situation, when the result is negative, the advantage of black is visible. This evaluation is then output in pawn-equivalents. +2.00 for example means that the player with the white pieces has an advantage that is evaluated equivalently to having two extra pawn11 . Figure 6. and Figure 6. represents examples for positive and negative score.

Considering this position the value is -

VP = (6 × 1 + 2 × 3 + 1 × 3 + 2 × 5 + 1 × 9) - (8 × 1 + 1 × 3 + 1 × 3 + 2 × 5 + 1 × 9)

VP = 34 − 33

VP = 1

So it can be assumed that white has an advantage equivalent to one extra pawn. Calculating the value of the position is extremely important to create the game tree, and after that, and based on this calculation it’s possible to choose the best move (for white the score with the highest value, for black - the lowest).

Despite the fact that material value is what influences most of the evaluation for humans, the complexity of chess is that in some cases actual values of figures can change. Figures 10. and 8. represents the position where the knight is better than a rock (even if its fixed value13 is lower). Every figure has its own role in the game and depending on the position it’s stronger or weaker. One of the most common ways for humans to measure the strength of the piece on the board is to count how many paths it covers/where it can move in the next move – this is how we (moreless) measure the usefullness of each figure. This kind of evaluation is called mobility. When it comes to engines, it can be assumed that the more information (such as mobility) is entered into the system, the greater the chance that the computer will calculate a better move. The advantage of a machine over a human can best be seen on the example of position evaluation. The human factor is very important in the game - the computer analyzes all possible data programmed by the programmer.