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.

The positions located above show the advantage of the Knight at d5 over the Rock at e8. The Knight has 7 legal moves and the location in the center of the chessboard gives him a lot of the board control. The Rook has 3 possible moves – that make it weaker and less useful in the game than the Knight, but the fixed value of each figure is still the same. Therefore, the machine cannot limit its analysis to calculating the values of the pieces on the chessboard. To make the machine more precise some more specific rules must be considered.

The data in the 8 by 8 tables above is equivalent to the value for the given square on the chessboard where the figure can be placed.

 

Each piece receives a value depending on what square the piece is in and each piece of each color has its own table. The value of a square for a certain piece can vary through the game and with this different goals can be achieved, like pawns advancing in the end-game or knights and bishop developing in the opening stages of the game. The actual value of the figure istherefore the result of the value shown for the field. This is enough material to create a basic chess engine however, specific pieces work better at different stages of the game, which makes the table not always reliable. Players don't learn such theoretical things by heart. Usually, when making difficult decisions, they are guided by intuition, which is something that the engine does not have.

The most crucial thing when playing a game is the position of the king. For the early game, the most valuable for the white king will be the coordinates: (7,1) (8,1) (2,1) (3,1), (reference Figure 12) and for black king: (7,8) (8,8) (2,8) (3,8), (reference Figure 12). These squares are the "safest" because then players prioritize piece mobility, attack, and strategy.On the other hand, during the endgames, the best position for a king is around the coordinates: (4,4) (4,5) (5,4) (5,5), (reference Figure 12.), which are the center of the chessboard. The king in the final position has the task of supporting the pieces, which he can do by being in the middle of the board, from where he can get to the desired place much faster than from "safe" squares. Table 4. and Table 5. Shows the differences in position values depending on King location in early game and in ending.

Game theory is simply a branch of mathematics dealing with behavior in strategic situations, where the outcome depends on the choices undertaken by players. Chess is a very interesting method to study this branch of mathematics, moreover it is a zero-sum game. In general, a zero-sum game represents a closed system: everything that someone wins must be lost by someone else.For example, if in a game of chess player A has an advantage of 1 queen is because player B has an advantage of -1 queen. Chess is a perfect information (both players – black and white has the same knowledge about the position), no chance game (outcome relies on the skill of players, there is no random external factor) and is called combinatorial game. Such features allow the use of various mathematical formulas in chess engines, with which algorithms that will analyze and play games can be created.

However, having only theoretical knowledge of the use of mathematics in a chess engine is not enough to create one. To make good use of this information, the engine needs an appropriate algorithm. Minimax algorithm assumes that players will decide to go for the best legal move, what at the same time means, that player A want to do a move that will interfere with the player’s B plans. In other words, players are minimizing the maximum loss

 

In order to find the most profitable move for each side, the engine has to calculate the actual values for each legal position that could happen. Graph 2. Shows sample game tree however, instead of moves (shown in graph 1.) on „branches” it has real values of the position after some move.

Let’s say that „max” player is playing with the white pieces and „min” player is playing black pieces. Min- max algorithm begin it’s work from the bottom of the game tree. At first, the bottom „max” has to choose between values: +0.3 and +0.8. Since, the „max” stands for white it is looking for the highest values, so value +0.8 is chosen. This process is successively repeated in the lowest part of the tree. When every value for „max” is assigned, then the engine search for „min”. At this point, the two previously selected values meet: +0.8 and +1.6. Because now the engine looks for the smallest value it picks +0.8. Again it’s time for engine to look for „max” values. It chooses between: +0.8, +0.5 and +0.4. After it choose value +0.8, a move that matches this value is called a proposed move.

 

The chess engine is a very objective position analysis tool as it always looks for the best moves for white and black regardless of position. In a position (Figure 15.) where black has a king and a queen, and white has only a king; even though the position is lost for white, the engine will look for moves for black "min" that will lead to checkmate as soon as possible and moves for white "max" will delay the loss as much as possible.

Alpha- Beta Pruning is a form of search technique used to expedite decision-making in computational game theory and artificial intelligence. It functions by restricting the options a player can consider while making a choice. In order to save time and resources, Alpha-Beta Pruning examines each branch of the game tree and prunes (eliminates) any branches that have little possibility of leading to a better result than another branch, so it’s therefore used to reduce the amount of time it takes to search the tree

 

Consider a node k which is possible for a player to choose. If a player has a better choice l at any parent node of k or any choice further up, then k will never be reached in actual play. Therefore – once a player found choice l ,the choice of node k and its continuation is not subject to further analysis.

 

Again - just like the prunes engine, unprofitable nodes, so a player, thanksto his intuition and imagination, is able to reject the least likely events.

For example, if white has a pawn on e4 and is considering moving it to e5, but black has a Knight on f6, then there is no need to evaluate the branch where white moves the pawn to e5, since Black will take it with their knight. By using alpha-beta pruning, this branch of the tree can be eliminated, saving time and allowing the algorithm to focus on other possible (better) moves.

The aspects presented above made it possible to answer the question asked : How game theory, the use of vectors and algorithms contribute to the effective operation of today’s chess engines?

 

The use of mathematical principles such as tree search, heuristic evaluation functions, and machine learning algorithms has allowed for the creation of chess engines that are now stronger than any human player. The work presents various mathematical applications in the development of chess engines, from the fundamental algorithms that allow for efficient evaluation of positions, to the more complex techniques used for search, which has enabled chess engines to become more sophisticated and accurate in their game predictions. Keep in mind that chess is a too complex game to be fully encapsulated in mathematical formulas. Research, however, proves that mathematical concepts are crucial to programming the basic information in the engine. However, while the use of mathematics in chess engines has had a significant impact on the game of chess, it is important to remember that chess is still a game of human skill and intuition.Human-machine inserts prove that math is only useful for engine design, not game strategy, so it can be said that the mathematical understanding of chess is not fully possible and not practical.

 

The main limitation of research is the aforementioned fact that the engine does not rely solely on mathematics. This greatly limited the study of mathematics. The work could include aspects of chess in mathematics (fe. Morphy number) rather than mathematics in chess, which could lead to more interesting results. An alternative to this study was to create a new basic chess engine, which would contain only mathematical elements. With the help of such an action, one could check how much actual mathematics is in the chess engine and more accurately answer the given research question. Nevertheless, the work inspires to explore the topic of mathematics in chess engines.

 

The beauty of mathematics can be shown through many mathematical concepts, but including it in entertainment and in such an art as chess shows the advantage of technology over human-being. Research shows how many areas of mathematics remain to be contained in theoretical formulas. The size of the numbers involved in chess is practically infinite, which means that chess players will never be able to solve the game.

Baum, Alicja, & Łukasiewicz-Wieleba, Joanna (2018). Korelaty uzdolnień szachowych. Środowiskowe badania nad młodymi adeptami królewskiej gry. [Correlates of chess skills. Environmental research on young adepts of the royal game] ACCESSED: February 23, 2023, from http://www.aps.edu.pl

 

Beal, Donald (1982). Benefits of using multivalued functions for minimaxing. ACCESSED: January 18, 2023, from: https://www.sciencedirect.com/science/article/pii/B978008026898950005X

 

Claude E. Shannon (1950) XXII. Programming a computer for playing chess, The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41:314, 256-275

 

Hartikka, Lauri. (2017, March 15). A step-by-step guide to building a simple chess AI. freeCodeCamp.org. ACCESSED: February 22, 2023, from: https://www.freecodecamp.org/news/simple-chess-ai-step-by-step- 1d55a9266977

 

Haworth, Guy & Hernandez, Nelson. (2019). The 16th Top Chess Engine Championship, TCEC16. ICGA Journal. 41. 1-12. 10.3233/ICG-190122. ACCESSED: February, 21.2023 from: https://www.researchgate.net/publication/337642377_The_16th_Top_Chess_Engine_Championship_TCE C16

 

Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002), Games solved: Now and in the future, Artificial Intelligence 134, 277–311

 

Knuth, Donald Ervin, & Moore, Ralph Westwood. (2002). An Analysis of Alpha-Beta Priming '. ACCESSED: February, 22 2023 from: https://www.semanticscholar.org/paper/An-Analysis-of-Alpha-Beta-Priming-%27- Knuth -Moore/dce26118156e5bc287bca2465a62e75af39c7e85

 

Owen, Guillermo (2013). Game Theory. Google Books. ACCESSED: January,18 2023, from: https://books.google.pl/books?hl=pl&lr=&id=yeVbAAAAQBAJ&oi=fnd&pg=PP2&dq=game+theory&ots=Yo 7ZWvVBlf&sig=UCXU89LZ5ESRZYuxndCwjD4kwkE&redir_esc=y#v=onepage&q=game%20theory&f=false

 

Point Value - Chessprogramming wiki. (n.d.). ACCESSED: February 19, 2023, from: https://www.chessprogramming.org/Point_Value#cite_note-2

 

Rodriguez, Marrero Roberto (2021, June 8). Theseus: Developing a chess engine. ACCESSED: December,12.2022 from: https://www.theseus.fi/handle/10024/502571

 

Scott P. Stevens (2008) Games People Play: Game Theory in Life, Business, and Beyond (The Great Courses). The Teaching Company; 2nd edition (2008-01-01). ACCESSED: December, 12.2022 from: https://dokumen.pub/games-people-play-game-theory-in-life-business-and-beyond.html

 

Silver, David. (2017, December 5). Mastering Chess and Shogi by Self-Play with a General. . . arXiv.org. ACCESSED: 29.12.2022 from: https://arxiv.org/abs/1712.01815

 

Stezano, Martin . (2021, November 18). Alan Turing Created a Chess Computer Program That Prefigured A.I. ACCESSED: February 23, 2023, from https://www.history.com/news/in-1950-alan-turing-created-a- chess-computer-program-that-prefigured-a-i