Chess program self-study
Hello, Habr!
In an article published last year , we solved the problem of determining the mathematically sound values of chess pieces. Using a regression analysis of the games played by computers and people, we were able to obtain a scale of the value of “units”, which largely coincides with the traditional values known from books and practical experience.
Unfortunately, the direct substitution of the corrected values for the figures did not strengthen the author's program - in any case, more than within the framework of the statistical error. Application of the original “head-on” method to other parameters of the evaluation function yielded somewhat absurd results, the optimization algorithm clearly needed some refinement. Meanwhile, the author decided that the next release of his engine will be the final in a long series of versions, originating in the code a decade ago. A version of GreKo 2015 was released and no further changes were planned in the near future.
Anyone interested in what happened next - after viewing the picture to attract attention, welcome to cat.
The motivation for the sudden continuation of the work and, ultimately, the appearance of this article, were two events. One of them thundered around the world through the media - this is a match in Go of Korean top player Lee Sedol with the Google AlphaGo program .
Developers from Google DeepMind were able to effectively combine two powerful techniques - a search in a tree using the Monte Carlo method and deep learning using neural networks. The resulting symbiosis led to phenomenal results in the form of a victory over two professional players in Go (Lee Sedolem and Fan Hui) with a total score of 9 - 1. Details of the implementation of AlphaGo were widely discussed, including on Habré, so now we will not dwell on them.
The second event, not so widely publicized, and noticed mainly by chess programming enthusiasts, is the appearance of the Giraffe program . Its author, Matthew Lai, actively used the ideas of machine learning, in particular, all the same deep neural networks. Unlike traditional engines, in which the evaluation function contains a number of predefined position attributes, Giraffe independently extracts these characteristics from the training material at the training stage. In fact, the goal was stated to automatically output “chess knowledge” in the form in which it is stated in textbooks.
In addition to the evaluation function, neural networks in Giraffe were also used to parameterize tree searches, which also suggests some parallels with AlphaGo.
The program demonstrated certain successes, having achieved from scratch in a few days the strength of an international master. But, unfortunately, an interesting research project was prematurely completed ... in connection with the transfer of Matthew Lai to work in the Google DeepMind team!
One way or another, the information wave that arose in connection with AlphaGo and Giraffe prompted the author of this article to once again return to the code of his engine and still try to strengthen his game using the methods of machine learning so popular nowadays.
Perhaps this will disappoint someone, but in the described project there will be neither multilayer neural networks, nor automatic detection of key features of the position, nor the Monte Carlo method. Random search of a tree in chess is practically not required due to the limitations of the task, and well-functioning factors for evaluating the chess position have been known since the time of Kaissa . In addition, the author was interested in how much you can strengthen the game program within the framework of a fairly minimalistic set of them, which is implemented in GreKo.
The basic method was chosen algorithm for setting the evaluation function, which was proposed by the Swedish researcher and developer Peter Österlund, the author of the powerful Texel program. The winning sides of this method, according to its creator, are:
Let θ = (θ 1 , ..., θ K ) be the vector of parameters of the evaluation function (material weight and positional signs).
For each position p i , i = 1 ... N from the test set, we calculate its static estimate E θ (p i ) , which is a certain scalar quantity. Traditionally, the rating is normalized so that it gives an idea of the superiority of one or the other side in units of chess material - for example, hundredths of a pawn. We will always consider the assessment in terms of whites.
We now turn from the material representation of the assessment to the probabilistic one. Using the logistic function, we make the following transformation:
The value of R pred has the meaning of the mathematical expectation of the result of the game for White in this position (0 - defeat, 0.5 - draw, 1 - victory). The normalization constant K can be defined as such a material advantage in which "everything becomes clear." In this study, the value K = 150 was used , i.e. one and a half pawns. Of course, "it becomes clear" only in a statistical sense, in real chess games you can find a huge number of counterexamples when a much greater material advantage does not lead to a win.
In the original algorithm, instead of a static estimation function for calculating R predthe result of the so-called PV search was used. The name is associated with the concept of a forced version, in the English version - quiescence search. This is an alpha-beta search from a given position, which considers only capturing, turning pawns, sometimes - checkers and avoiding them. Although the search trees are small, in comparison with a static estimate, the computation speed decreases by tens and hundreds of times. Therefore, it was decided to use a faster scheme, and to filter out dynamic positions at the stage of preparing the initial data.
Now, knowing for each position the predicted R pred and the actual R fact results of the batch in which it met, we can calculate the mean square error of the prediction:
In fact, the obtained rms estimate can already be considered as the objective functional to be minimized. This approach is described in the original description of the method.
Let's make one more small modification - we will introduce the account of the number of moves remaining until the end of the game. Obviously, the positional attribute that existed on the board at the very beginning of the game may not affect its outcome at all if the main events in the game occurred much later. For example, White in the opening may have a proud knight in the center of the board, but lose in the deep endgame when this knight has already been traded, due to the invasion of the enemy rook in his camp. In this case, the sign “horse in the center of the board” should not receive too much punishment compared to the sign “rook on the second horizontal” - the horse is not to blame for anything!
Accordingly, we add to our objective function a correction related to the number of moves n i remaining until the end of the game . For each position, it will be an exponential decay factor with parameter λ . The “physical meaning” of this parameter is the number of moves during which a particular positional attribute affects the game. Again, on average. In the experiments described below, λ takes values of several tens of half-passages.
In the original Texel's Tuning Method description, the first moves in batches were discarded from the training set. The introduction of " λ- forgetting" allows us not to introduce an explicit restriction on the moves from the opening book - their influence is somehow small.
The final form of our target functional:
The task of training an evaluation function now reduces to minimizing J in the space of values of the vector θ .
Why does this method work? In fact, most of the signs that arise in positions on large batches of parties, due to averaging, are mutually neutralized. Only those that really had an effect on the result retain their value and receive higher weights. The sooner the evaluation function begins to notice them during the game, the better the prediction and the more accurate the position assessment will be, the more powerful the program will demonstrate.
Positions from 20 thousand games played by the program with itself were used as an array of training data. Of these, positions that arose after taking a piece or declaring a check were excluded. This is necessary in order for the training set of examples to match the actual positions from the enumeration tree as best as possible, for which a static estimate is applied.
The result was about 2.27 million positions. Not all of them are unique, but for the method used this is not critical. Positions were randomly divided into training and test sets in the ratio of 80/20, respectively 1.81 million and 460 thousand positions.
Functionality was minimized on a training set using the coordinate descent method. It is known that for multidimensional optimization problems this method is usually not the best choice. However, simplicity of implementation as well as an acceptable runtime played in favor of this algorithm. On a typical modern PC, optimization for 20 thousand games takes from one to several hours, depending on the subset of 27 possible weights selected for configuration.
Below is a graph of the functional change versus time. The criterion for stopping training is the non-improvement of the result for the test subset after the next cycle of descents in all parameters.
The evolution of a group of parameters related to pawns is shown in the following graph. It can be seen that the process converges quite quickly - at least to a local minimum. The task of finding a global minimum has not yet been set, our goal now is to strengthen the program by at least some amount ...
Here is a complete list of evaluation parameters with initial and final values. The meaning of most is understandable without additional comments; those wishing to familiarize themselves with their exact purpose are invited to the source code of the program - the file eval.cpp, the Evaluate () function.
The table shows an example for one of the training sessions, in which only positional evaluation parameters were optimized, and the cost of the figures remained unchanged. This is not a critical requirement. In the tests described below, full training was used in all 27 parameters. But the best results in a practical game were shown by a version with an unchanged scale of material.
What conclusions can be drawn from the resulting weights? It can be seen that some of them remained almost unchanged compared to the original version of the program. It can be assumed that over the years of debugging the engine, they were selected intuitively quite correctly. However, at some points cold mathematics corrected human intuition. So, the harm of backward pawns was overrated by the author. But the following parameters seemed more important to the algorithm, their weights were almost doubled:
Separately, it is worth mentioning the sign of the passage, unattainable by the "rule of the square." Its optimized value has reached the limit of the admissible interval set in the algorithm. Obviously, it could be more. The reason, probably, is that in the training file, with such a passing pawn, the parties won 100% of the time. The value of 200 was left as the weight, as quite sufficient - its increase in the game practically does not affect the strength of the game.
So, we trained the evaluation function to predict the outcome of the game based on the position on the board. But the main check ahead is how this skill will be useful in a practical game. For this purpose, several versions of the engine with various settings were prepared, each of which was obtained in its own training mode.
20000.pgn - parts of the program with itself (super blitz)
gm2600.pgn - parts of grandmasters from the FTP site of the author of Crafty Robert Hyatt (classic control)
large.pgn - combination of these two files
Each version played 100 games with the original program GreKo 2015 , as well as with a set of other engines with time control “1 second + 0.1 seconds per stroke”. The results are shown in the table below. With the help of the bayeselo program, relative version ratings were calculated, the strength of GreKo 2015 was fixed as a reference point at 2600. The value of LOS (likelihood of superiority) was also determined - the probability that a particular version plays stronger than GreKo 2015 taking into account the confidence interval for rating calculation.
It can be seen that the improvement of the game occurred in all cases except one (version D). It is also interesting that training on the parties of grandmasters (version G) had little effect. But adding to the games of grandmasters our own games of the program plus modification of the figure values (version H2) turned out to be a rather successful combination.
The strongest in terms of the totality of the results turned out to be version C, with an increase in the ranking of about 70 points. For a given number of parties, this advantage is statistically significant, the error is plus or minus 30 points.
We trained and tested the program on ultra-short time control, when one batch lasts several seconds. We’ll check how our improvements work in a “serious” game, with longer controls.
So, despite a slight drop in efficiency with an increase in the duration of the games, the trained version definitely demonstrates a stronger game than the engine with the original version of the settings. She was released as another final release of the program.
Program GreKo 2015 ML can free download with source code in C ++. It is a console application for Windows or Linux. To play with a person, analyze or sparring with other engines, you may need a graphical interface - for example, Arena, Winboard, or some other. However, you can play directly from the command line, entering the moves in standard English notation.
The self-learning function in GreKo is implemented as a built-in command of the console mode (the author is not currently aware of other engines that support this functionality). A vector of 27 coefficients of the evaluation function is stored in the weights.txt file. To automatically adjust it based on a PGN file, type the learn command, for example:
The program will read all the batches from the specified file, create an intermediate file with positions for training and break it into training and test subsets:
Then it will save the initial values of the parameters to the weights.old file, and begin the optimization process. During operation, the intermediate values of the weights and the target functional are displayed on the screen and in the learning.log file.
Upon completion of training, the weights.txt file will contain already new values of weights, which will take effect the next time the program starts.
The learn command can contain two more arguments, the lower and upper bounds of the optimization interval. By default, they are 6 and 27 - i.e. all signs are optimized, except the cost of the figures. To enable full optimization, you must specify the boundaries explicitly:
The algorithm is randomized (in terms of partitioning into training and test samples), therefore, with different starts, different coefficient vectors can be obtained.
To configure the evaluation function, we used reinforcement learning. The best results were achieved when analyzing the games of the program against itself. In fact, the only external source of chess knowledge was the debut book of the shell, necessary for the randomization of playing games.
We managed to increase the predictive ability of the assessment, which led to a statistically significant increase in the power of the game on different time controls both with the previous version and with a set of independent opponents. The improvement was 50 ... 70 points Elo.
It is worth noting that the result was achieved on rather modest volumes: about 20 thousand games and 1 million positions (for comparison: AlphaGo studied at 30 million positions from parties of strong amateurs from the server, not counting further games with herself). The GreKo evaluation function is also very simple, and includes only 27 independent parameters. With the strongest chess engines, their score can go to hundreds and thousands. However, even under such conditions, machine learning methods have been successful.
Further improvement of the program could include adding new criteria to the evaluation function (in particular, taking into account the stage of the game for all the parameters considered) and the use of more advanced methods of multidimensional optimization (for example, searching for global extrema). At the moment, however, the author’s plans in this direction have not yet been determined.
In an article published last year , we solved the problem of determining the mathematically sound values of chess pieces. Using a regression analysis of the games played by computers and people, we were able to obtain a scale of the value of “units”, which largely coincides with the traditional values known from books and practical experience.
Unfortunately, the direct substitution of the corrected values for the figures did not strengthen the author's program - in any case, more than within the framework of the statistical error. Application of the original “head-on” method to other parameters of the evaluation function yielded somewhat absurd results, the optimization algorithm clearly needed some refinement. Meanwhile, the author decided that the next release of his engine will be the final in a long series of versions, originating in the code a decade ago. A version of GreKo 2015 was released and no further changes were planned in the near future.
Anyone interested in what happened next - after viewing the picture to attract attention, welcome to cat.
The motivation for the sudden continuation of the work and, ultimately, the appearance of this article, were two events. One of them thundered around the world through the media - this is a match in Go of Korean top player Lee Sedol with the Google AlphaGo program .
Developers from Google DeepMind were able to effectively combine two powerful techniques - a search in a tree using the Monte Carlo method and deep learning using neural networks. The resulting symbiosis led to phenomenal results in the form of a victory over two professional players in Go (Lee Sedolem and Fan Hui) with a total score of 9 - 1. Details of the implementation of AlphaGo were widely discussed, including on Habré, so now we will not dwell on them.
The second event, not so widely publicized, and noticed mainly by chess programming enthusiasts, is the appearance of the Giraffe program . Its author, Matthew Lai, actively used the ideas of machine learning, in particular, all the same deep neural networks. Unlike traditional engines, in which the evaluation function contains a number of predefined position attributes, Giraffe independently extracts these characteristics from the training material at the training stage. In fact, the goal was stated to automatically output “chess knowledge” in the form in which it is stated in textbooks. In addition to the evaluation function, neural networks in Giraffe were also used to parameterize tree searches, which also suggests some parallels with AlphaGo.
The program demonstrated certain successes, having achieved from scratch in a few days the strength of an international master. But, unfortunately, an interesting research project was prematurely completed ... in connection with the transfer of Matthew Lai to work in the Google DeepMind team!
One way or another, the information wave that arose in connection with AlphaGo and Giraffe prompted the author of this article to once again return to the code of his engine and still try to strengthen his game using the methods of machine learning so popular nowadays.
Algorithm
Perhaps this will disappoint someone, but in the described project there will be neither multilayer neural networks, nor automatic detection of key features of the position, nor the Monte Carlo method. Random search of a tree in chess is practically not required due to the limitations of the task, and well-functioning factors for evaluating the chess position have been known since the time of Kaissa . In addition, the author was interested in how much you can strengthen the game program within the framework of a fairly minimalistic set of them, which is implemented in GreKo.
The basic method was chosen algorithm for setting the evaluation function, which was proposed by the Swedish researcher and developer Peter Österlund, the author of the powerful Texel program. The winning sides of this method, according to its creator, are:
- The ability to simultaneously optimize up to several hundred parameters of the evaluation function.
- No need for a source of “external knowledge” in the form of expert assessments of positions - only texts and party results are needed.
- Correct work with strongly correlated signs - no preliminary preparation is required like their orthogonalization.
Let θ = (θ 1 , ..., θ K ) be the vector of parameters of the evaluation function (material weight and positional signs).
For each position p i , i = 1 ... N from the test set, we calculate its static estimate E θ (p i ) , which is a certain scalar quantity. Traditionally, the rating is normalized so that it gives an idea of the superiority of one or the other side in units of chess material - for example, hundredths of a pawn. We will always consider the assessment in terms of whites.
We now turn from the material representation of the assessment to the probabilistic one. Using the logistic function, we make the following transformation:
The value of R pred has the meaning of the mathematical expectation of the result of the game for White in this position (0 - defeat, 0.5 - draw, 1 - victory). The normalization constant K can be defined as such a material advantage in which "everything becomes clear." In this study, the value K = 150 was used , i.e. one and a half pawns. Of course, "it becomes clear" only in a statistical sense, in real chess games you can find a huge number of counterexamples when a much greater material advantage does not lead to a win.
In the original algorithm, instead of a static estimation function for calculating R predthe result of the so-called PV search was used. The name is associated with the concept of a forced version, in the English version - quiescence search. This is an alpha-beta search from a given position, which considers only capturing, turning pawns, sometimes - checkers and avoiding them. Although the search trees are small, in comparison with a static estimate, the computation speed decreases by tens and hundreds of times. Therefore, it was decided to use a faster scheme, and to filter out dynamic positions at the stage of preparing the initial data.
Now, knowing for each position the predicted R pred and the actual R fact results of the batch in which it met, we can calculate the mean square error of the prediction:
In fact, the obtained rms estimate can already be considered as the objective functional to be minimized. This approach is described in the original description of the method.
Let's make one more small modification - we will introduce the account of the number of moves remaining until the end of the game. Obviously, the positional attribute that existed on the board at the very beginning of the game may not affect its outcome at all if the main events in the game occurred much later. For example, White in the opening may have a proud knight in the center of the board, but lose in the deep endgame when this knight has already been traded, due to the invasion of the enemy rook in his camp. In this case, the sign “horse in the center of the board” should not receive too much punishment compared to the sign “rook on the second horizontal” - the horse is not to blame for anything!
Accordingly, we add to our objective function a correction related to the number of moves n i remaining until the end of the game . For each position, it will be an exponential decay factor with parameter λ . The “physical meaning” of this parameter is the number of moves during which a particular positional attribute affects the game. Again, on average. In the experiments described below, λ takes values of several tens of half-passages.
In the original Texel's Tuning Method description, the first moves in batches were discarded from the training set. The introduction of " λ- forgetting" allows us not to introduce an explicit restriction on the moves from the opening book - their influence is somehow small.
The final form of our target functional:
The task of training an evaluation function now reduces to minimizing J in the space of values of the vector θ .
Why does this method work? In fact, most of the signs that arise in positions on large batches of parties, due to averaging, are mutually neutralized. Only those that really had an effect on the result retain their value and receive higher weights. The sooner the evaluation function begins to notice them during the game, the better the prediction and the more accurate the position assessment will be, the more powerful the program will demonstrate.
Training and results
Positions from 20 thousand games played by the program with itself were used as an array of training data. Of these, positions that arose after taking a piece or declaring a check were excluded. This is necessary in order for the training set of examples to match the actual positions from the enumeration tree as best as possible, for which a static estimate is applied.
The result was about 2.27 million positions. Not all of them are unique, but for the method used this is not critical. Positions were randomly divided into training and test sets in the ratio of 80/20, respectively 1.81 million and 460 thousand positions.
Functionality was minimized on a training set using the coordinate descent method. It is known that for multidimensional optimization problems this method is usually not the best choice. However, simplicity of implementation as well as an acceptable runtime played in favor of this algorithm. On a typical modern PC, optimization for 20 thousand games takes from one to several hours, depending on the subset of 27 possible weights selected for configuration.
Below is a graph of the functional change versus time. The criterion for stopping training is the non-improvement of the result for the test subset after the next cycle of descents in all parameters.
The evolution of a group of parameters related to pawns is shown in the following graph. It can be seen that the process converges quite quickly - at least to a local minimum. The task of finding a global minimum has not yet been set, our goal now is to strengthen the program by at least some amount ...
Similar charts for other signs
The following graph presents data related to another training session, in which material weights were also adjusted. It can be seen that from the "computer" values used in GreKo, they gradually converge to more classical values.
The following graph presents data related to another training session, in which material weights were also adjusted. It can be seen that from the "computer" values used in GreKo, they gradually converge to more classical values.
Here is a complete list of evaluation parameters with initial and final values. The meaning of most is understandable without additional comments; those wishing to familiarize themselves with their exact purpose are invited to the source code of the program - the file eval.cpp, the Evaluate () function.
| room | Sign | Description | Before training | After training |
|---|---|---|---|---|
| 1. | VAL_P | pawn value | 100 | 100 |
| 2. | VAL_N | horse cost | 400 | 400 |
| 3. | VAL_B | elephant value | 400 | 400 |
| 4. | VAL_R | rook value | 600 | 600 |
| 5. | VAL_Q | queen value | 1200 | 1200 |
| 6. | Pawndoubled | double pawn | -10 | -10 |
| 7. | Pawnisolated | isolated pawn | -10 | -19 |
| 8. | Pawnbackswards | backward pawn | -10 | -5 |
| 9. | Pawncenter | pawn in the middle of the board | 10 | 9 |
| 10. | PawnPassedFreeMax | unlocked checkpoint | 120 | 128 |
| eleven. | PawnPassedBlockedMax | blocked checkpoint | 100 | 101 |
| 12. | PawnPassedKingDist | remoteness from the opponent’s king in the endgame | 5 | 9 |
| thirteen. | PawnPassedSquare | walk-through, unattainable by the "rule of the square" | fifty | 200 |
| 14. | Knightcenter | horse centralization | 10 | 27 |
| fifteen. | Knightoutpost | protected item for horse | 10 | 7 |
| 16. | Knight mobility | horse mobility | 20 | 19 |
| 17. | BishopPairMidgame | a pair of elephants in the middlegame | 20 | 20 |
| 18. | BishopPairEndgame | a pair of elephants in the endgame | 100 | 95 |
| 19. | Bishopcenter | elephant centralization | 10 | 9 |
| 20. | Bishop mobility | elephant mobility | 60 | 72 |
| 21. | Roook7th | rook on the 7th horizontal | 20 | 24 |
| 22. | Roookopen | rook on an open vertical | 10 | 17 |
| 23. | Hookmobility | rook mobility | 40 | 40 |
| 24. | QueenKingTropism | the queen's proximity to the enemy king | 40 | 99 |
| 25. | KingCenterMid | centralization of the king at middlegame | -40 | -41 |
| 26. | Kingcenterend | king centralization in the endgame | 40 | 33 |
| 27. | Kingpawnshield | king pawn shield | 120 | 120 |
The table shows an example for one of the training sessions, in which only positional evaluation parameters were optimized, and the cost of the figures remained unchanged. This is not a critical requirement. In the tests described below, full training was used in all 27 parameters. But the best results in a practical game were shown by a version with an unchanged scale of material.
What conclusions can be drawn from the resulting weights? It can be seen that some of them remained almost unchanged compared to the original version of the program. It can be assumed that over the years of debugging the engine, they were selected intuitively quite correctly. However, at some points cold mathematics corrected human intuition. So, the harm of backward pawns was overrated by the author. But the following parameters seemed more important to the algorithm, their weights were almost doubled:
- isolated pawn
- rook on an open vertical
- remoteness from the opponent’s king in the endgame
- horse centralization
- the queen's proximity to the enemy king
Separately, it is worth mentioning the sign of the passage, unattainable by the "rule of the square." Its optimized value has reached the limit of the admissible interval set in the algorithm. Obviously, it could be more. The reason, probably, is that in the training file, with such a passing pawn, the parties won 100% of the time. The value of 200 was left as the weight, as quite sufficient - its increase in the game practically does not affect the strength of the game.
Check behind a chessboard
So, we trained the evaluation function to predict the outcome of the game based on the position on the board. But the main check ahead is how this skill will be useful in a practical game. For this purpose, several versions of the engine with various settings were prepared, each of which was obtained in its own training mode.
| Version | Training file | Number of parties | Rating Coefficients | Scaling constant λ |
|---|---|---|---|---|
| A | 20000.pgn | 20000 | 6 ... 27 | 40 |
| B | 20000.pgn | 20000 | 1 ... 27 | 40 |
| C | 20000.pgn | 20000 | 6 ... 27 | 20 |
| D | 20000.pgn | 20000 | 1 ... 27 | 20 |
| E | 20000.pgn | 20000 | 6 ... 27 | 60 |
| F | 20000.pgn | 20000 | 1 ... 27 | 60 |
| G | gm2600.pgn | 27202 | 6 ... 27 | 20 |
| H1 | large.pgn | 47202 | 6 ... 27 | 20 |
| H2 | large.pgn | 47202 | 1 ... 27 | 20 |
20000.pgn - parts of the program with itself (super blitz)
gm2600.pgn - parts of grandmasters from the FTP site of the author of Crafty Robert Hyatt (classic control)
large.pgn - combination of these two files
Each version played 100 games with the original program GreKo 2015 , as well as with a set of other engines with time control “1 second + 0.1 seconds per stroke”. The results are shown in the table below. With the help of the bayeselo program, relative version ratings were calculated, the strength of GreKo 2015 was fixed as a reference point at 2600. The value of LOS (likelihood of superiority) was also determined - the probability that a particular version plays stronger than GreKo 2015 taking into account the confidence interval for rating calculation.
| Version | GreKo 2015 | Fruit 2.1 | Delfi 5.4 | Crafty 23.4 | Kiwi 0.6d | Rating | Los |
|---|---|---|---|---|---|---|---|
| GreKo 2015 | 33 | 40.5 | 39.5 | 73.5 | 2600 | ||
| A | 53.5 | 38 | 49.5 | 46.5 | 76 | 2637 | 97% |
| B | 55 | 43.5 | 71 | 36.5 | 78.5 | 2667 | 99% |
| C | 52.5 | 39.5 | 81 | 42.5 | 75 | 2672 | 99% |
| D | 42 | 23.5 | 58 | 33.5 | 68 | 2574 | 7% |
| E | 53.5 | 37 | 51.5 | 46 | 81.5 | 2646 | 99% |
| F | 59 | 36.5 | 63 | 31.5 | 79.5 | 2648 | 98% |
| G | 48 | 24.5 | 59 | 43.5 | 65.5 | 2602 | 54% |
| H1 | 45.5 | 40 | 51.5 | 40.5 | 75.5 | 2616 | 81% |
| H2 | 55 | 33.5 | 65 | 39 | 74 | 2646 | 99% |
It can be seen that the improvement of the game occurred in all cases except one (version D). It is also interesting that training on the parties of grandmasters (version G) had little effect. But adding to the games of grandmasters our own games of the program plus modification of the figure values (version H2) turned out to be a rather successful combination.
The strongest in terms of the totality of the results turned out to be version C, with an increase in the ranking of about 70 points. For a given number of parties, this advantage is statistically significant, the error is plus or minus 30 points.
We trained and tested the program on ultra-short time control, when one batch lasts several seconds. We’ll check how our improvements work in a “serious” game, with longer controls.
| Time control | Number of parties | Result | Rating | Los |
|---|---|---|---|---|
| 1 minute. + 1 sec / move | 200 | 116.5 - 83.5 | + 56 | 99% |
| 3 min. + 2 sec / move | 100 | 57.5 - 42.5 | + 45 | 94% |
| 5 minutes. for 40 moves | 100 | 53.5 - 46.5 | + 21 | 77% |
So, despite a slight drop in efficiency with an increase in the duration of the games, the trained version definitely demonstrates a stronger game than the engine with the original version of the settings. She was released as another final release of the program.
GreKo 2015 ML
Program GreKo 2015 ML can free download with source code in C ++. It is a console application for Windows or Linux. To play with a person, analyze or sparring with other engines, you may need a graphical interface - for example, Arena, Winboard, or some other. However, you can play directly from the command line, entering the moves in standard English notation. The self-learning function in GreKo is implemented as a built-in command of the console mode (the author is not currently aware of other engines that support this functionality). A vector of 27 coefficients of the evaluation function is stored in the weights.txt file. To automatically adjust it based on a PGN file, type the learn command, for example:
White(1): learn gm2600.pgn
The program will read all the batches from the specified file, create an intermediate file with positions for training and break it into training and test subsets:
Creating file 'gm2600.fen'
Games: 27202
Loading positions...
Training set: 1269145
Validation set: 317155
Then it will save the initial values of the parameters to the weights.old file, and begin the optimization process. During operation, the intermediate values of the weights and the target functional are displayed on the screen and in the learning.log file.
Old values saved in file 'weights.old'
Start optimization...
0 0.139618890118 0.140022159883 2016-07-21 17:01:16
Parameter 6 of 27: PawnDoubled = -10
Parameter 7 of 27: PawnIsolated = -19
1 0.139602240177 0.140008376153 2016-07-21 17:01:50 [1.7] -20
2 0.139585446564 0.139992945184 2016-07-21 17:01:58 [1.7] -21
3 0.139571113698 0.139980624436 2016-07-21 17:02:07 [1.7] -22
4 0.139559690029 0.139971803640 2016-07-21 17:02:15 [1.7] -23
5 0.139552067028 0.139965861844 2016-07-21 17:02:23 [1.7] -24
6 0.139547879916 0.139964477620 2016-07-21 17:02:32 [1.7] -25
7 0.139543242843 0.139961056939 2016-07-21 17:02:40 [1.7] -26
8 0.139542575174 0.139962314286 2016-07-21 17:02:48 [1.7] -27
Parameter 8 of 27: PawnBackwards = -5
9 0.139531995624 0.139953185941 2016-07-21 17:03:04 [1.8] -4
10 0.139523642489 0.139947035972 2016-07-21 17:03:12 [1.8] -3
11 0.139518695795 0.139943580937 2016-07-21 17:03:21 [1.8] -2
12 0.139517501456 0.139943802704 2016-07-21 17:03:29 [1.8] -1
Parameter 9 of 27: PawnCenter = 9
Parameter 10 of 27: PawnPassedFreeMax = 128
13 0.139515067927 0.139941456600 2016-07-21 17:04:00 [1.10] 129
14 0.139500815202 0.139927669884 2016-07-21 17:04:08 [1.10] 130
...
Upon completion of training, the weights.txt file will contain already new values of weights, which will take effect the next time the program starts.
The learn command can contain two more arguments, the lower and upper bounds of the optimization interval. By default, they are 6 and 27 - i.e. all signs are optimized, except the cost of the figures. To enable full optimization, you must specify the boundaries explicitly:
White(1): learn gm2600.pgn 1 27
The algorithm is randomized (in terms of partitioning into training and test samples), therefore, with different starts, different coefficient vectors can be obtained.
conclusions
To configure the evaluation function, we used reinforcement learning. The best results were achieved when analyzing the games of the program against itself. In fact, the only external source of chess knowledge was the debut book of the shell, necessary for the randomization of playing games.
We managed to increase the predictive ability of the assessment, which led to a statistically significant increase in the power of the game on different time controls both with the previous version and with a set of independent opponents. The improvement was 50 ... 70 points Elo.
It is worth noting that the result was achieved on rather modest volumes: about 20 thousand games and 1 million positions (for comparison: AlphaGo studied at 30 million positions from parties of strong amateurs from the server, not counting further games with herself). The GreKo evaluation function is also very simple, and includes only 27 independent parameters. With the strongest chess engines, their score can go to hundreds and thousands. However, even under such conditions, machine learning methods have been successful.
Further improvement of the program could include adding new criteria to the evaluation function (in particular, taking into account the stage of the game for all the parameters considered) and the use of more advanced methods of multidimensional optimization (for example, searching for global extrema). At the moment, however, the author’s plans in this direction have not yet been determined.
References
- We determine the weight of chess pieces by regression analysis - an introductory article on a model for evaluating material.
- GreKo is the GreKo chess program, the training of which we were engaged in in this article.
- Texel's Tuning Method - a description of the basic method for optimizing the evaluation function.
- Mastering the Game of Go with Deep Neural Networks and Tree Search (original) - Original article about AlphaGo in Nature.
- AlphaGo on the fingers - a summary of the basic principles of the AlphaGo device in Russian.
- Giraffe: Using Deep Reinforcement Learning to Play Chess - article about the Giraffe chess program.
- bayeselo - utility for calculating ratings based on PGN files.
