25,161
edits
Changes
Created page with "'''Home * Automated Tuning * Point Value By Regression Analysis''' FILE:MedvedevArticlePieceEquations.jpg|border|right|thumb|link=http://habrahabr.ru/post..."
'''[[Main Page|Home]] * [[Automated Tuning]] * Point Value By Regression Analysis'''
[[FILE:MedvedevArticlePieceEquations.jpg|border|right|thumb|link=http://habrahabr.ru/post/254753/]]
'''Point Value by Regression Analysis''',<br/>
an article by [[Vladimir Medvedev]] on determining [[Point Value|point values]] by [[Automated Tuning#LogisticRegression|logistic regression]], posted as "Определяем веса шахматных фигур регрессионным анализом" on April 30, 2015 in [https://en.wikipedia.org/wiki/Habrahabr Habrahabr], a popular Russian IT portal <ref>[http://habrahabr.ru/post/254753/ Определяем веса шахматных фигур регрессионным анализом / Хабрахабр] by [[Vladimir Medvedev|WinPooh]], April 27, 2015 (Russian)</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=56168 Piece weights with regression analysis (in Russian)] by [[Vladimir Medvedev]], [[CCC]], April 30, 2015</ref>, translated with the help of [https://en.wikipedia.org/wiki/Google_Translate Google Translate], slightly edited, and published here with the permission of Vladimir Medvedev.
----
Hello Habr!<br/>
<span id="course"></span>
This article deals with a programmer's study on [[Learning|machine learning]], inspired by an online course ''Machine Learning'' by [[Andrew Ng]] at [[Stanford University]] and [https://en.wikipedia.org/wiki/Coursera Coursera] <ref>[https://www.coursera.org/learn/machine-learning Machine Learning - Stanford University | Coursera]</ref> <ref>[https://www.youtube.com/view_play_list?p=A89DCFA6ADACE599 Lecture Collection | Machine Learning - YouTube] by [[Andrew Ng]], [[Stanford University]]</ref> <ref>[http://cs229.stanford.edu/materials.html CS 229: Machine Learning (Course handouts)]</ref>. After becoming familar with some methods discussed in the lectures, such as [https://en.wikipedia.org/wiki/Regression_analysis regression analysis], the author was keen to apply them to real problems - in the domain of chess engine optimization.
=Introduction=
[[FILE:MedvedevArticleSearchTree.jpg|border|right|thumb|link=http://habrahabr.ru/post/254753/]]
The main components of virtually any chess program are [[Search|search]] and [[Evaluation|evaluation]]. The evaluation function maps a set of positional features to a numerical scale and serves as an objective function to find the best move. It is applied at the [[Leaf Node|leaves]] of the [[Search Tree|tree]], gradually backed up to the [[Root|root]] using [[Alpha-Beta|alpha-beta procedure]] or its variations along with [[Iterative Deepening|iterative deepening]].
Strictly speaking, this evaluation has only three values: win, loss or draw - 1, 0, or ½, as determined to any given position due to the [https://en.wikipedia.org/wiki/Zermelo%27s_theorem_%28game_theory%29 theorem] by [[Ernst Zermelo|Zermelo]]. In practice, due to the [https://en.wikipedia.org/wiki/Combinatorial_explosion combinatorial explosion], no computer will be able to calculate all variations through the complete game tree. Therefore, chess programs work in the model by [[Claude Shannon]] with truncated games trees and approximate estimate at the leaves based on various heuristics.
Search and evaluation are not independently from each other, and must be well balanced. Modern search algorithms no longer apply a pure [[Brute-Force|brute-force]] approach, but apply [[Selectivity|selectivity]] searching heterogeneous trees due to [[Quiescence Search|quiescence search]], [[Extensions|extensions]] specially along the [[Principal Variation|principal variation]], but also [[Pruning|prune]] and [[Reductions|reduce]] not so promising branches also based on static evaluation.
Search optimization by machine learning methods is another interesting topic, but for now we focus on evaluation.
=Evaluation=
Calculating the static evaluation [[Score|score]] is usually implemented by a [https://en.wikipedia.org/wiki/Linear_combination linear combination] of various position features scaled by some weights - most importantly the number of pieces and pawns of both sides, further the position of these pieces, [[Center Control|centralization]], and [[Mobility|mobility]]. Assuming a state of the art search, only considering [[Material|material]] and [[Piece-Square Tables|piece-square tables]] is already sufficient to build a 2000-2200 Elo engine nowadays.
Further refinements of the assessment may include more and more subtle terms of a chess position: the presence and advancement of [[Passed Pawn|passed pawns]], the [[Distance|proximity]] of the [[King Safety#KingTropism|king to attacking pieces]], its [[King Safety#PawnShield|pawn shield]] and more. The legendary chess program [[Kaissa]], first [[WCCC 1974|world champion among programs in 1974]], had several dozens of evaluation terms, as descibed in ''The machine plays chess'' by [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Alexander Bitman]] and [[Mikhail Donskoy]] in 1983 <ref>[[Georgy Adelson-Velsky|Г.М. Адельсон-Вельский]], [[Vladimir Arlazarov|В.Л. Арлазаров]], [[Alexander Bitman|А.Р. Битман]], [[Mikhail Donskoy|М.В. Донской]] ('''1983'''). ''Машина играет в шахматы''. [http://genes1s.net/files/kaissa.pdf pdf] (book with detailed explanations of Kaissa algorithms, Russian)</ref> .
Lacking such resources as the creators of [[Deep Blue]], the task here is limited, and considers only the most significant term - the [[Material#Balance|balance of material]] on the board.
=Point Values - Simple Model=
If one takes any chess book for beginners, just behind the explaining of moves, usually these relative [[Point Value|point values]] were given:
{| class="wikitable"
|-
! Piece
! Value
|-
| Pawn
| style="text-align:center;" | 1
|-
| Knight
| style="text-align:center;" | 3
|-
| Bishop
| style="text-align:center;" | 3
|-
| Rook
| style="text-align:center;" | 5
|-
| Queen
| style="text-align:center;" | 9
|-
| King
| style="text-align:center;" | ∞
|}
The King is sometimes attributed to a final score, certainly greater than the sum of all the material on the board - for example, 200 pawn units. In this study, we will leave His Majesty alone, and kings will not be considered at all. Why is that? The answer is simple, they are always present on the board, so they are mutually subtracted in the material evaluation, as the overall balance of the power is not affected.
[[FILE:MedvedevArticleCapa.jpg|border|right|thumb|link=http://habrahabr.ru/post/254753/]]
Here is how the third world champion, [https://en.wikipedia.org/wiki/Jos%C3%A9_Ra%C3%BAl_Capablanca José Raúl Capablanca], describes the evaluation of different material combinations in his classic textbook ''Chess fundamentals'' <ref>[https://en.wikipedia.org/wiki/Jos%C3%A9_Ra%C3%BAl_Capablanca José Raúl Capablanca] ('''1921'''). ''[https://openlibrary.org/books/OL23286033M/Chess_fundamentals Chess fundamentals]''. ''[https://archive.org/stream/cu31924014756724#page/n41/mode/2up 5. Relative Values of the Pieces, pp. 24-25]''.</ref>
For all general theoretical purposes the Bishop and the Knight have to be considered as of the same value, though it is my opinion that the Bishop will prove the more valuable piece in most cases; and it is well known that two Bishops are almost always better than two Knights.
The Bishop will be stronger against Pawns than the Knight, and in combination with Pawns will also be stronger against the Rook than the Knight will be. A Bishop and a Rook are also stronger than a Knight and a Rook, but a Queen and a Knight may be stronger than a Queen and a Bishop. A Bishop will often be worth more than three Pawns, but a Knight very seldom so, and may even not be worth so much.
A Rook will be worth a Knight and two Pawns, or a Bishop and two Pawns, but, as said before, the Bishop will be a better piece against the Rook. Two Rooks are slightly stronger than a Queen. They are slightly weaker than two Knights and a Bishop, and a little more so than two Bishops and a Knight. The power of the Knight decreases as the pieces are changed off. The power of the Rook, on the contrary, increases.
It turns out that most of these rules can be met, while remaining within the framework of a linear model, and just slightly shifting the scores of their "school" values. For example, in [[Simplified Evaluation Function|simplified evaluation function]], the following boundary conditions:
<pre>
B > N > 3P
B + N = R + 1.5P
Q + P = 2R
</pre>
which might be satisfied by (values in [[Centipawns|centipawns]]):
<pre>
P = 100
N = 320
B = 330
R = 500
Q = 900
K = 20000
</pre>
In fact, the resulted value set is not the only solution. Moreover, even the non-compliance with some of the "inequalities them. Capablanca "will not lead to a sharp drop in strength of the chess program, and only affect its stylistic features. As an experiment, the author spent a little match-tournament - four versions of his engine [[GreKo]] with different point values playing [[Fruit|Fruit 2.1]], [[Crafty|Crafty 23.4]] and [[Delfi|Delfi 5.4]] - 200 games each with ultra-low time control óf 1 sec per game + 0.1 increment per move. The results are shown in the table:
{| class="wikitable"
|-
! Version
! Pawn
! Knight
! Bishop
! Rook
! Queen
! Fruit 2.1
! Crafty 23.4
! Delfi 5.4
! Rating
|-
! Greko 12.5
| style="text-align:right;" | 100
| style="text-align:right;" | 400
| style="text-align:right;" | 400
| style="text-align:right;" | 600
| style="text-align:right;" | 1200
| style="text-align:right;" | 61.0
| style="text-align:right;" | 76.0
| style="text-align:right;" | 71.0
| style="text-align:right;" | 2567
|-
! Greko A
| style="text-align:right;" | 100
| style="text-align:right;" | 300
| style="text-align:right;" | 300
| style="text-align:right;" | 500
| style="text-align:right;" | 900
| style="text-align:right;" | 55.0
| style="text-align:right;" | 69.0
| style="text-align:right;" | 73.0
| style="text-align:right;" | 2552
|-
! Greko B
| style="text-align:right;" | 100
| style="text-align:right;" | 320
| style="text-align:right;" | 330
| style="text-align:right;" | 500
| style="text-align:right;" | 900
| style="text-align:right;" | 57.0
| style="text-align:right;" | 71.0
| style="text-align:right;" | 64.0
| style="text-align:right;" | 2548
|-
! Greko C
| style="text-align:right;" | 100
| style="text-align:right;" | 325
| style="text-align:right;" | 325
| style="text-align:right;" | 550
| style="text-align:right;" | 1100
| style="text-align:right;" | 72.5
| style="text-align:right;" | 74.5
| style="text-align:right;" | 69.0
| style="text-align:right;" | 2575
|}
We see that some of the variation in the weights of the pieces lead to the fluctuations of the ratings in the range of 20-30 Elo. Moreover, one of the test versions showed even better results than the basic version. However, such statements based on that small number of games is prematurely, since confidence interval calculation rating is comparable to the value of several tens of Elo.
"Classic" weights of chess material were obtained intuitively by chess experience. Attempts were also made to bring these values by some mathematical basis - for example, based on [[Mobility|mobility]] figures, the number of squares that they can keep under control. We try to approach the topic experimentally - based on the analysis of a large number of chess games. To calculate the point values we do not need the approximate assessment of the positions of the games - only the final results, as the most objective measure of success in chess.
=Material Advantage and Logistic Function=
[[Pawn Advantage, Win Percentage, and Elo|Statistical analysis]] was taken from [[Portable Game Notation|PGN-Files]] containing almost 3,000 blitz chess games between 32 different chess engines in the range from 1800 to 3000 Elo. Using a specially written utility for each batch of material has compiled a list of relations that have arisen on the board. Each material balance was included in the statistics after a [[Captures|capture]] or [[Promotions|pawn promotions]], not considering immediate exchanges. Then, the material balance of scale of "1-3-3-5-9" from -20 to 20 was used as index to accumulate the number of points scored by White. The statistics is presented by the following graph:
[[FILE:MedvedevArticleChart.png|none|border|text-bottom|link=http://habrahabr.ru/post/254753/]]
On the x-axis the material balance ΔM from white point of view. It is calculated as the difference between the total values of all the white pieces and pawns and the same value for Black. On the y-axis the expectation of the result of selective batches (0 - winning Black, 0.5 - a draw, 1 - winning White). We see that the experimental data are very well described by the [https://en.wikipedia.org/wiki/Logistic_function logistic function]:
[[FILE:PointValByRegressionFormula11.jpg|none|text-bottom]]
with a steepness α of 0.7. For comparison, the graph shows two more logistic curves with steepness α of 0.2 and 0.1.
What does this mean in practice? Suppose we see a randomly chosen position in which White has an pawn advantage of 2. With a probability of close to 80%, we can assert a White win. Similarly, if one lacks the bishop or a knight (ΔM = -3), the chances not to lose are only about 12%. As expected, material equality most often leads to a draw.
=Problem Statement=
Now we are ready to formulate the problem of optimizing the evaluation function in terms of [https://en.wikipedia.org/wiki/Logistic_regression logistic regression]. Suppose we are given a set of vectors of the form:
<span style="font-size:150%;">x<span style="vertical-align: sub;">j</span>=(Δ<span style="vertical-align: sub;">P</span>, Δ<span style="vertical-align: sub;">N</span>, Δ<span style="vertical-align: sub;">B</span>, Δ<span style="vertical-align: sub;">R</span>, Δ<span style="vertical-align: sub;">Q</span>)<span style="vertical-align: sub;">j</span></span>
where Δ<span style="vertical-align: sub;">i, j</span> = P ... Q - is the difference between the number of white and black pieces of type i from pawn to queen. These vectors are material relationships encountered in batches (one batch usually corresponds to several vectors).
Let there be a vector y<span style="vertical-align: sub;">j</span> of components of whith the values 0, 1 and 2, corresponding to the outcome of the game - 0 - Black wins, 1 - a draw, 2 - White wins.
Finding the optimal point values of the weight vector θ,
<span style="font-size:150%;">Θ =(Θ<span style="vertical-align: sub;">P</span>, Θ<span style="vertical-align: sub;">N</span>, Θ<span style="vertical-align: sub;">B</span>, Θ<span style="vertical-align: sub;">R</span>, Θ<span style="vertical-align: sub;">Q</span>)</span>
requires [https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_minimization minimizing] the [https://en.wikipedia.org/wiki/Cross_entropy cross-entropy] [https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_error_function_and_logistic_regression cost function] for the [https://en.wikipedia.org/wiki/Logistic_regression logistic regression] <ref>"Using [https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_error_function_and_logistic_regression cross-entropy error function] instead of [https://en.wikipedia.org/wiki/Mean_squared_error sum of squares] leads to faster training and improved generalization", from [https://en.wikipedia.org/wiki/Sargur_Srihari Sargur Srihari], [http://www.cedar.buffalo.edu/~srihari/CSE574/Chap5/Chap5.2-Training.pdf Neural Network Training] (pdf)</ref>:
[[FILE:PointValByRegressionFormula2.jpg|none|text-bottom]]
with the [https://en.wikipedia.org/wiki/Logistic_function logistic function] for the vector argument:
[[FILE:PointValByRegressionFormula3.jpg|none|text-bottom]]
The introduction of [https://en.wikipedia.org/wiki/Regularization_%28mathematics%29 regularization] prevents [https://en.wikipedia.org/wiki/Overfitting overfitting] and effects of instability in the solution found in the cost function:
[[FILE:PointValByRegressionFormula4.jpg|none|text-bottom]]
The coefficients of regularization is chosen small, in this case λ = 10<span style="font-size: 90%; vertical-align: super;">-6</span>.
To solve the problem of [https://en.wikipedia.org/wiki/Maxima_and_minima minimization], a simple [https://en.wikipedia.org/wiki/Gradient_descent gradient descent] with a constant slope is applied <ref>[https://en.wikipedia.org/wiki/Del Nabla operator or Del from Wikipedia]</ref>:
[[FILE:PointValByRegressionFormula5.jpg|none|text-bottom]]
where the components of the gradient of J reg have the form:
[[FILE:PointValByRegressionFormula6.jpg|none|text-bottom]]
[[FILE:PointValByRegressionFormula7.jpg|none|text-bottom]]
Since we are looking for a symmetric solution in material equality which gives the probability of the outcome of the game ½, coefficient vector θ is always zero, and we only need for the gradient of the second of these expressions. Anyone interested in the justification of the above formulas is recommend to study the [[#course|already mentioned]] machine learning course at [https://en.wikipedia.org/wiki/Coursera Coursera].
=Program and Results=
Since the first part of the problem, the analysis of [[Portable Game Notation|PGN-Files]] and the allocation for each item set of features, has practically been implemented in the chess engine [[GreKo]], it was decided to use [[Cpp|C++]] for the pgn learning stuff as well. Source code and PGN samples are available at [https://en.wikipedia.org/wiki/GitHub GitHub] <ref>[https://github.com/WinPooh/pgnlearn WinPooh/pgnlearn · GitHub]</ref> . The program can be compiled and run under [[Windows]] ( [https://en.wikipedia.org/wiki/Visual_C%2B%2B MSVC]) or [[Linux]] ([[Free Software Foundation#GCC|GCC]]).
The ability to use further [https://en.wikipedia.org/wiki/List_of_numerical_analysis_software specialized tools] like [https://en.wikipedia.org/wiki/GNU_Octave GNU Octave], [https://en.wikipedia.org/wiki/MATLAB MATLAB], [https://en.wikipedia.org/wiki/R_%28programming_language%29 R], etc. is also provided, the program generates an intermediate text file with a set of features and outcome of the game, which can easily be imported into these environments. The file contains the text representation of a set of vectors x j - matrix of dimension mx (n + 1) in the first 5 columns that contain components of the material balance (from the pawn to a queen), and in the 6th - the result of the game.
Consider a simple example. Below is a PGN-record of one of the test batches:
<pre>
[Event "OpenRating 31"]
[Site "BEAR-HOME"]
[Date "2013.05.09"]
[Round "1"]
[White "Simplex 0.9.7"]
[Black "IvanHoe 999946f"]
[Result "0-1"]
[TimeControl "60+1"]
[PlyCount "96"]
1.d4 d5 2.c4 e6 3.e3 c6 4.Nf3 Nd7 5.Nbd2 Nh6 6.e4 Bb4 7.a3 Ba5 8.cxd5 exd5
9.exd5 cxd5 10.Qe2+ Kf8 11.Qb5 Nf6 12.Bd3 Qe7+ 13.Kd1 Bb6 14.Re1 Bd7 15.Qb3
Be6 16.Re2 Qc7 17.Qb4+ Kg8 18.Nb3 Bf5 19.Bb1 Bxb1 20.Rxb1 Nf5 21.Bd2 a5 22.Qa4
h6 23.Rc1 Qb8 24.Bxa5 Qf4 25.Qb4 Bxa5 26.Nxa5 Kh7 27.Nxb7 Rab8 28.a4 Ne4 29.h3
Rhc8 30.Ra1 Rc7 31.Qa3 Rcxb7 32.g3 Qc7 33.Rc1 Qa5 34.Rxe4 dxe4 35.Rc5 Qa6
36.Nd2 Nxd4 37.Rc4 Nb3 38.Nxb3 Qxc4 39.Nd2 Rd8 40.Qc3 Qf1+ 41.Kc2 Qe2 42.f4 e3
43.b4 Rc7 44.Kb3 Qd1+ 45.Ka2 Rxc3 46.Nb1 Qxa4+ 47.Na3 Rc2+ 48.Ka1 Rd1# 0-1
</pre>
The corresponding fragment of intermediate file looks like:
<pre>
0 0 0 0 0 0
1 0 0 0 0 0
2 0 0 0 0 0
2 -1 0 0 0 0
2 0 0 -1 0 0
1 0 0 -1 0 0
1 1 0 -2 0 0
</pre>
The 6th column, 0 everywhere - is the result of the game, black won. The other columns - the balance of pieces on the board. The first line of complete equality of material, all of the components are 0. The second line - a pawn for white, is a position after the 24th move. Note that prior exchanges are not considered as they were too early. After the 27th move White has two extra pawns. Before the final attack of Black, White has only a pawn and a knight for two rooks.
[[FILE:MedvedevArticlegendiag.png|none|border|text-bottom|link=http://habrahabr.ru/post/254753/]]
Like the opening exchanges, the final moves in the game are not considered. They were screened out by "filter tactics" because they represent a series of captures, checks and evadings from check.
Similar records were created for all analyzed batches, the average obtained 5-10 lines per game. After analysis of the PGN-base, that file is further directed to the second part of the program dealing with the problem of minimizing their own decisions. A starting point for the [https://en.wikipedia.org/wiki/Gradient_descent gradient descent] is a vector with the values of the balances from the textfile. Starting from scratch, it turned out that the cost function is "good" enough to convert during several thousand steps to a global minimum, as shown in the following chart (at each step, the normalization of the weight of the pawn = 100):
[[FILE:MedvedevArticleChart2.png|none|border|text-bottom|link=http://habrahabr.ru/post/254753/]]
After normalization and rounding, the following values were determined:
{| class="wikitable"
|-
! Piece
! Value
|-
| Pawn
| style="text-align:right;" | 100
|-
| Knight
| style="text-align:right;" | 288
|-
| Bishop
| style="text-align:right;" | 345
|-
| Rook
| style="text-align:right;" | 480
|-
| Queen
| style="text-align:right;" | 1077
|-
| King
| style="text-align:right;" | ∞
|}
Compared with the rules of Capablanca:
{| class="wikitable"
|-
! Condition
! Numerical
! True?
|-
| <span style="color: #088a29;">B > N</span>
| style="text-align:center;" | <span style="color: #088a29;">345 > 288</span>
| <span style="color: #088a29;">yes</span>
|-
| <span style="color: #088a29;">B > 3P</span>
| style="text-align:center;" | <span style="color: #088a29;">345 > 300</span>
| <span style="color: #088a29;">yes</span>
|-
| <span style="color: #ff0000;">N > 3P</span>
| style="text-align:center;" | <span style="color: #ff0000;">288 < 300</span>
| <span style="color: #ff0000;">no</span>
|-
| <span style="color: #088a29;">B + N = R + 1.5P</span>
| style="text-align:center;" | <span style="color: #088a29;">345+288 = 480+150</span>
| <span style="color: #088a29;">yes (accuracy of < 0.5%)</span>
|-
| <span style="color: #ff0000;">Q + P = 2R</span>
| style="text-align:center;" | <span style="color: #ff0000;">1077 + 100 > 960</span>
| <span style="color: #ff0000;">no</span>
|}
The result is quite encouraging. Not knowing anything about the actual events taking place on the board, considering only the outcome of the game, the algorithm has managed to bring the point values close to their traditional values.
Is it possible to use the resulting values to enhance the chess program? Alas, at this point the answer is no. Test blitz matches showed that the strength of GreKo using the parameters found remained virtually unchanged, and in some cases even declined. Why did it happen? One of the obvious reasons - the already mentioned strong link between search and evaluation. The search incorporates a number of heuristics to cut off the dead-end branches and the criteria of pruning (thresholds) are closely tied to the static evaluation. By changing the value of the pieces, one shifts the scale of values - a form of search tree change requires new balancing of constants for all heuristics, which is a rather time consuming task.
=Human Players=
Let's try to expand the experiment, considering not only computers, but also human chess players. The data set to study the games were taken from two outstanding contemporary grandmasters - the [https://en.wikipedia.org/wiki/World_Chess_Championship world chess champion] [https://en.wikipedia.org/wiki/Magnus_Carlsen Magnus Carlsen] and former world chess champion [https://en.wikipedia.org/wiki/Viswanathan_Anand Viswanathan Anand], as well a representative of [https://en.wikipedia.org/wiki/Romantic_chess romantic chess] of the [https://en.wikipedia.org/wiki/19th_century 19th century], [https://en.wikipedia.org/wiki/Adolf_Anderssen Adolf Andersen].
{| class="wikitable"
|-
|
| style="text-align:center;" | [[FILE:VishyAnand09.jpg|none|border|text-bottom|x200px]]
| style="text-align:center;" | [[FILE:Carlsen Magnus (30238051906).jpg|none|border|text-bottom|x200px]]
| style="text-align:center;" | [[FILE:And00278.png|none|border|text-bottom|x200px]]
|-
!
! Anand <ref>[https://en.wikipedia.org/wiki/Viswanathan_Anand Viswanathan Anand], world chess champion, Photo by Stefan64, January 2013, [https://en.wikipedia.org/wiki/World_Chess_Championship_2014 World Chess Championship 2014 from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>
! Carlsen <ref>[https://en.wikipedia.org/wiki/Magnus_Carlsen Magnus Carlsen], chess grandmaster from Norway, Photo by Stefan64, January 2013, [https://en.wikipedia.org/wiki/World_Chess_Championship_2014 World Chess Championship 2014 from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>
! Andersen <ref>[https://en.wikipedia.org/wiki/Adolf_Anderssen Adolf Andersen from Wikipedia]</ref>
|-
| Pawn
| style="text-align:center;" | 100
| style="text-align:center;" | 100
| style="text-align:center;" | 100
|-
| Knight
| style="text-align:center;" | 216
| style="text-align:center;" | 213
| style="text-align:center;" | 286
|-
| Bishop
| style="text-align:center;" | 230
| style="text-align:center;" | 243
| style="text-align:center;" | 289
|-
| Rook
| style="text-align:center;" | 355
| style="text-align:center;" | 352
| style="text-align:center;" | 531
|-
| Queen
| style="text-align:center;" | 762
| style="text-align:center;" | 786
| style="text-align:center;" | 1013
|-
| King
| style="text-align:center;" | ∞
| style="text-align:center;" | ∞
| style="text-align:center;" | ∞
|}
It is easy to notice that the "human" point values appear different of how beginners are taught in textbooks. In the case of Carlsen and Anand strikes a smaller scale - the queen is a little more than 7.5 pawns, respectively, reduced for all other pieces. Bishop is still a little more worth than knight, but they don't even reach the traditional three pawns. Two rooks are weaker than the queen, etc.
I must say that a similar situation is observed not only from Vishy and Magnus, but for most GMs, whose games failed the test. The values are shrinked from classic in the same way for masters like [[Mikhail Botvinnik]] and [https://en.wikipedia.org/wiki/Anatoly_Karpov Anatoly Karpov], and the attacking players [https://en.wikipedia.org/wiki/Mikhail_Tal Mikhail Tal], and [https://en.wikipedia.org/wiki/Judit_Polg%C3%A1r Judit Polgár] ...
One of the few exceptions was Adolf Andersen, one of the best European players in the middle of the 19th century, famous for the [https://en.wikipedia.org/wiki/Immortal_Game Immortal Game]. His point values are very similar to those from chess programs.
Why is there such an effect with compressing the range of point values? Of course, don't forget about the very limited model - considering additional positional features could make a significant difference. But perhaps it is a case of a "weak implementation" of human players concerning material advantage - compared to modern chess programs. Simply put - a person has a hard time to correctly play with the queen due to its opportunities. I remember an anecdote from a textbook by [[Mathematician#EmanuelLasker|Emanuel Lasker]] (in other versions from Capablanca, [https://en.wikipedia.org/wiki/Alexander_Alekhine Alekhine] or Tal), ostensibly to play with handicap with a random fellow traveler in the train. The culmination was the phrase: "The queen only hinders!"
=Conclusion=
We examined one aspect of the evaluation function of chess programs - the material balance. We made sure that this part of the static evaluation model is smooth through the logistic function and associated with the probability of the outcome of the game. Then we looked at several weight combinations to estimate their influence on the strength of the chess program.
With the help of lots of different regression players, both humans and chess programs, we have determined the optimum value of the piece values under the assumption of a purely "financial" evaluation function. We found an interesting effect in humans versus machines. We tried to use the values found in a real engine, and ... had not achieved much success.
Where to go from here? For a more accurate estimate of the position a new model of chess knowledge may be established - that is, to increase the dimension of x and θ. Even staying in the material only world (excluding the squares occupied by the pieces on the board), one can add a number of relevant features: bishop pair, a couple of queen and knight, the last pawn in the endgame ... Chess players do well know as the value of the pieces may depend on the combination or the stage of the game. In chess programs, corresponding weights (bonuses or penalties) may reach tenths of a pawn and more.
One way (along with an increase in sample size) used for training games, is playing the previous version of the same program. In this case, there is hope for some signs of greater coherence with other assessments. Also, a cost function may be used which is not predicting the outcome of the game (which could end in a few tens of moves behind the position under consideration), but the correlation of static with dynamic assessment, ie. with the result of the alpha-beta search of a certain depth.
However, as noted above, to directly enhance the chess program's results may not be suitable. It often happens that after a series of tests, the trained program begins to better address the tests (in our case - to predict the result of the game), but did not play better! At present, the mainstream chess programs were extensively tested exclusively in practical play. New versions of the top engines are tested before release with tens and hundreds of thousands of games with ultrashort time control ...
In any case, I plan to spend another series of experiments on the statistical analysis of chess games. If this topic is of interest to the audience Habra, upon receipt of any non-trivial result of the article can be continued.
No chess pieces were harmed during investigation.
[[FILE:MedvedevArticlePieces2.jpg|none|border|text-bottom]]
----
=See also=
* [[Komodo#PointValues|Centered Point Values in Komodo]]
* [[Eval Tuning in Deep Thought]]
* [[Learning]]
* [[Neural Networks]]
* [[Pawn Advantage, Win Percentage, and Elo]]
* [[Point Value]]
* [[Texel's Tuning Method]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=56168 Piece weights with regression analysis (in Russian)] by [[Vladimir Medvedev]], [[CCC]], April 30, 2015
: [http://www.talkchess.com/forum/viewtopic.php?t=56168&start=22 Results of 234 players] by [[Jesús Muñoz]], [[CCC]], May 02, 2015
: [http://www.talkchess.com/forum/viewtopic.php?t=56168&start=36 Re: Piece weights with regression analysis (in Russian)] by [[Fabien Letouzey]], [[CCC]], May 04, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56232&start=24 Re: Pawn value estimation] by [[Larry Kaufman]], [[CCC]], May 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=64972 Approximating Stockfish's Evaluation by PSQTs] by [[Thomas Dybdahl Ahle]], [[CCC]], August 23, 2017 » [[Automated Tuning#Regression|Regression]], [[Piece-Square Tables]], [[Stockfish]]
=External Links=
* [http://habrahabr.ru/post/254753/ Определяем веса шахматных фигур регрессионным анализом / Хабрахабр] by [[Vladimir Medvedev|WinPooh]], April 27, 2015 (Russian)
* [https://github.com/WinPooh/pgnlearn WinPooh/pgnlearn · GitHub]
* [https://en.wikipedia.org/wiki/Regression_analysis Regression analysis from Wikipedia]
* [https://en.wikipedia.org/wiki/Logistic_function Logistic function from Wikipedia]
* [https://en.wikipedia.org/wiki/Logistic_regression Logistic regression from Wikipedia]
* [https://en.wikipedia.org/wiki/Maximum_likelihood Maximum likelihood from Wikipedia]
* [https://en.wikipedia.org/wiki/Cross_entropy Cross-entropy from Wikipedia]
* [https://www.coursera.org/learn/machine-learning Machine Learning - Stanford University | Coursera]
=References=
<references />
'''[[Automated Tuning|Up one Level]]'''
[[FILE:MedvedevArticlePieceEquations.jpg|border|right|thumb|link=http://habrahabr.ru/post/254753/]]
'''Point Value by Regression Analysis''',<br/>
an article by [[Vladimir Medvedev]] on determining [[Point Value|point values]] by [[Automated Tuning#LogisticRegression|logistic regression]], posted as "Определяем веса шахматных фигур регрессионным анализом" on April 30, 2015 in [https://en.wikipedia.org/wiki/Habrahabr Habrahabr], a popular Russian IT portal <ref>[http://habrahabr.ru/post/254753/ Определяем веса шахматных фигур регрессионным анализом / Хабрахабр] by [[Vladimir Medvedev|WinPooh]], April 27, 2015 (Russian)</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=56168 Piece weights with regression analysis (in Russian)] by [[Vladimir Medvedev]], [[CCC]], April 30, 2015</ref>, translated with the help of [https://en.wikipedia.org/wiki/Google_Translate Google Translate], slightly edited, and published here with the permission of Vladimir Medvedev.
----
Hello Habr!<br/>
<span id="course"></span>
This article deals with a programmer's study on [[Learning|machine learning]], inspired by an online course ''Machine Learning'' by [[Andrew Ng]] at [[Stanford University]] and [https://en.wikipedia.org/wiki/Coursera Coursera] <ref>[https://www.coursera.org/learn/machine-learning Machine Learning - Stanford University | Coursera]</ref> <ref>[https://www.youtube.com/view_play_list?p=A89DCFA6ADACE599 Lecture Collection | Machine Learning - YouTube] by [[Andrew Ng]], [[Stanford University]]</ref> <ref>[http://cs229.stanford.edu/materials.html CS 229: Machine Learning (Course handouts)]</ref>. After becoming familar with some methods discussed in the lectures, such as [https://en.wikipedia.org/wiki/Regression_analysis regression analysis], the author was keen to apply them to real problems - in the domain of chess engine optimization.
=Introduction=
[[FILE:MedvedevArticleSearchTree.jpg|border|right|thumb|link=http://habrahabr.ru/post/254753/]]
The main components of virtually any chess program are [[Search|search]] and [[Evaluation|evaluation]]. The evaluation function maps a set of positional features to a numerical scale and serves as an objective function to find the best move. It is applied at the [[Leaf Node|leaves]] of the [[Search Tree|tree]], gradually backed up to the [[Root|root]] using [[Alpha-Beta|alpha-beta procedure]] or its variations along with [[Iterative Deepening|iterative deepening]].
Strictly speaking, this evaluation has only three values: win, loss or draw - 1, 0, or ½, as determined to any given position due to the [https://en.wikipedia.org/wiki/Zermelo%27s_theorem_%28game_theory%29 theorem] by [[Ernst Zermelo|Zermelo]]. In practice, due to the [https://en.wikipedia.org/wiki/Combinatorial_explosion combinatorial explosion], no computer will be able to calculate all variations through the complete game tree. Therefore, chess programs work in the model by [[Claude Shannon]] with truncated games trees and approximate estimate at the leaves based on various heuristics.
Search and evaluation are not independently from each other, and must be well balanced. Modern search algorithms no longer apply a pure [[Brute-Force|brute-force]] approach, but apply [[Selectivity|selectivity]] searching heterogeneous trees due to [[Quiescence Search|quiescence search]], [[Extensions|extensions]] specially along the [[Principal Variation|principal variation]], but also [[Pruning|prune]] and [[Reductions|reduce]] not so promising branches also based on static evaluation.
Search optimization by machine learning methods is another interesting topic, but for now we focus on evaluation.
=Evaluation=
Calculating the static evaluation [[Score|score]] is usually implemented by a [https://en.wikipedia.org/wiki/Linear_combination linear combination] of various position features scaled by some weights - most importantly the number of pieces and pawns of both sides, further the position of these pieces, [[Center Control|centralization]], and [[Mobility|mobility]]. Assuming a state of the art search, only considering [[Material|material]] and [[Piece-Square Tables|piece-square tables]] is already sufficient to build a 2000-2200 Elo engine nowadays.
Further refinements of the assessment may include more and more subtle terms of a chess position: the presence and advancement of [[Passed Pawn|passed pawns]], the [[Distance|proximity]] of the [[King Safety#KingTropism|king to attacking pieces]], its [[King Safety#PawnShield|pawn shield]] and more. The legendary chess program [[Kaissa]], first [[WCCC 1974|world champion among programs in 1974]], had several dozens of evaluation terms, as descibed in ''The machine plays chess'' by [[Georgy Adelson-Velsky]], [[Vladimir Arlazarov]], [[Alexander Bitman]] and [[Mikhail Donskoy]] in 1983 <ref>[[Georgy Adelson-Velsky|Г.М. Адельсон-Вельский]], [[Vladimir Arlazarov|В.Л. Арлазаров]], [[Alexander Bitman|А.Р. Битман]], [[Mikhail Donskoy|М.В. Донской]] ('''1983'''). ''Машина играет в шахматы''. [http://genes1s.net/files/kaissa.pdf pdf] (book with detailed explanations of Kaissa algorithms, Russian)</ref> .
Lacking such resources as the creators of [[Deep Blue]], the task here is limited, and considers only the most significant term - the [[Material#Balance|balance of material]] on the board.
=Point Values - Simple Model=
If one takes any chess book for beginners, just behind the explaining of moves, usually these relative [[Point Value|point values]] were given:
{| class="wikitable"
|-
! Piece
! Value
|-
| Pawn
| style="text-align:center;" | 1
|-
| Knight
| style="text-align:center;" | 3
|-
| Bishop
| style="text-align:center;" | 3
|-
| Rook
| style="text-align:center;" | 5
|-
| Queen
| style="text-align:center;" | 9
|-
| King
| style="text-align:center;" | ∞
|}
The King is sometimes attributed to a final score, certainly greater than the sum of all the material on the board - for example, 200 pawn units. In this study, we will leave His Majesty alone, and kings will not be considered at all. Why is that? The answer is simple, they are always present on the board, so they are mutually subtracted in the material evaluation, as the overall balance of the power is not affected.
[[FILE:MedvedevArticleCapa.jpg|border|right|thumb|link=http://habrahabr.ru/post/254753/]]
Here is how the third world champion, [https://en.wikipedia.org/wiki/Jos%C3%A9_Ra%C3%BAl_Capablanca José Raúl Capablanca], describes the evaluation of different material combinations in his classic textbook ''Chess fundamentals'' <ref>[https://en.wikipedia.org/wiki/Jos%C3%A9_Ra%C3%BAl_Capablanca José Raúl Capablanca] ('''1921'''). ''[https://openlibrary.org/books/OL23286033M/Chess_fundamentals Chess fundamentals]''. ''[https://archive.org/stream/cu31924014756724#page/n41/mode/2up 5. Relative Values of the Pieces, pp. 24-25]''.</ref>
For all general theoretical purposes the Bishop and the Knight have to be considered as of the same value, though it is my opinion that the Bishop will prove the more valuable piece in most cases; and it is well known that two Bishops are almost always better than two Knights.
The Bishop will be stronger against Pawns than the Knight, and in combination with Pawns will also be stronger against the Rook than the Knight will be. A Bishop and a Rook are also stronger than a Knight and a Rook, but a Queen and a Knight may be stronger than a Queen and a Bishop. A Bishop will often be worth more than three Pawns, but a Knight very seldom so, and may even not be worth so much.
A Rook will be worth a Knight and two Pawns, or a Bishop and two Pawns, but, as said before, the Bishop will be a better piece against the Rook. Two Rooks are slightly stronger than a Queen. They are slightly weaker than two Knights and a Bishop, and a little more so than two Bishops and a Knight. The power of the Knight decreases as the pieces are changed off. The power of the Rook, on the contrary, increases.
It turns out that most of these rules can be met, while remaining within the framework of a linear model, and just slightly shifting the scores of their "school" values. For example, in [[Simplified Evaluation Function|simplified evaluation function]], the following boundary conditions:
<pre>
B > N > 3P
B + N = R + 1.5P
Q + P = 2R
</pre>
which might be satisfied by (values in [[Centipawns|centipawns]]):
<pre>
P = 100
N = 320
B = 330
R = 500
Q = 900
K = 20000
</pre>
In fact, the resulted value set is not the only solution. Moreover, even the non-compliance with some of the "inequalities them. Capablanca "will not lead to a sharp drop in strength of the chess program, and only affect its stylistic features. As an experiment, the author spent a little match-tournament - four versions of his engine [[GreKo]] with different point values playing [[Fruit|Fruit 2.1]], [[Crafty|Crafty 23.4]] and [[Delfi|Delfi 5.4]] - 200 games each with ultra-low time control óf 1 sec per game + 0.1 increment per move. The results are shown in the table:
{| class="wikitable"
|-
! Version
! Pawn
! Knight
! Bishop
! Rook
! Queen
! Fruit 2.1
! Crafty 23.4
! Delfi 5.4
! Rating
|-
! Greko 12.5
| style="text-align:right;" | 100
| style="text-align:right;" | 400
| style="text-align:right;" | 400
| style="text-align:right;" | 600
| style="text-align:right;" | 1200
| style="text-align:right;" | 61.0
| style="text-align:right;" | 76.0
| style="text-align:right;" | 71.0
| style="text-align:right;" | 2567
|-
! Greko A
| style="text-align:right;" | 100
| style="text-align:right;" | 300
| style="text-align:right;" | 300
| style="text-align:right;" | 500
| style="text-align:right;" | 900
| style="text-align:right;" | 55.0
| style="text-align:right;" | 69.0
| style="text-align:right;" | 73.0
| style="text-align:right;" | 2552
|-
! Greko B
| style="text-align:right;" | 100
| style="text-align:right;" | 320
| style="text-align:right;" | 330
| style="text-align:right;" | 500
| style="text-align:right;" | 900
| style="text-align:right;" | 57.0
| style="text-align:right;" | 71.0
| style="text-align:right;" | 64.0
| style="text-align:right;" | 2548
|-
! Greko C
| style="text-align:right;" | 100
| style="text-align:right;" | 325
| style="text-align:right;" | 325
| style="text-align:right;" | 550
| style="text-align:right;" | 1100
| style="text-align:right;" | 72.5
| style="text-align:right;" | 74.5
| style="text-align:right;" | 69.0
| style="text-align:right;" | 2575
|}
We see that some of the variation in the weights of the pieces lead to the fluctuations of the ratings in the range of 20-30 Elo. Moreover, one of the test versions showed even better results than the basic version. However, such statements based on that small number of games is prematurely, since confidence interval calculation rating is comparable to the value of several tens of Elo.
"Classic" weights of chess material were obtained intuitively by chess experience. Attempts were also made to bring these values by some mathematical basis - for example, based on [[Mobility|mobility]] figures, the number of squares that they can keep under control. We try to approach the topic experimentally - based on the analysis of a large number of chess games. To calculate the point values we do not need the approximate assessment of the positions of the games - only the final results, as the most objective measure of success in chess.
=Material Advantage and Logistic Function=
[[Pawn Advantage, Win Percentage, and Elo|Statistical analysis]] was taken from [[Portable Game Notation|PGN-Files]] containing almost 3,000 blitz chess games between 32 different chess engines in the range from 1800 to 3000 Elo. Using a specially written utility for each batch of material has compiled a list of relations that have arisen on the board. Each material balance was included in the statistics after a [[Captures|capture]] or [[Promotions|pawn promotions]], not considering immediate exchanges. Then, the material balance of scale of "1-3-3-5-9" from -20 to 20 was used as index to accumulate the number of points scored by White. The statistics is presented by the following graph:
[[FILE:MedvedevArticleChart.png|none|border|text-bottom|link=http://habrahabr.ru/post/254753/]]
On the x-axis the material balance ΔM from white point of view. It is calculated as the difference between the total values of all the white pieces and pawns and the same value for Black. On the y-axis the expectation of the result of selective batches (0 - winning Black, 0.5 - a draw, 1 - winning White). We see that the experimental data are very well described by the [https://en.wikipedia.org/wiki/Logistic_function logistic function]:
[[FILE:PointValByRegressionFormula11.jpg|none|text-bottom]]
with a steepness α of 0.7. For comparison, the graph shows two more logistic curves with steepness α of 0.2 and 0.1.
What does this mean in practice? Suppose we see a randomly chosen position in which White has an pawn advantage of 2. With a probability of close to 80%, we can assert a White win. Similarly, if one lacks the bishop or a knight (ΔM = -3), the chances not to lose are only about 12%. As expected, material equality most often leads to a draw.
=Problem Statement=
Now we are ready to formulate the problem of optimizing the evaluation function in terms of [https://en.wikipedia.org/wiki/Logistic_regression logistic regression]. Suppose we are given a set of vectors of the form:
<span style="font-size:150%;">x<span style="vertical-align: sub;">j</span>=(Δ<span style="vertical-align: sub;">P</span>, Δ<span style="vertical-align: sub;">N</span>, Δ<span style="vertical-align: sub;">B</span>, Δ<span style="vertical-align: sub;">R</span>, Δ<span style="vertical-align: sub;">Q</span>)<span style="vertical-align: sub;">j</span></span>
where Δ<span style="vertical-align: sub;">i, j</span> = P ... Q - is the difference between the number of white and black pieces of type i from pawn to queen. These vectors are material relationships encountered in batches (one batch usually corresponds to several vectors).
Let there be a vector y<span style="vertical-align: sub;">j</span> of components of whith the values 0, 1 and 2, corresponding to the outcome of the game - 0 - Black wins, 1 - a draw, 2 - White wins.
Finding the optimal point values of the weight vector θ,
<span style="font-size:150%;">Θ =(Θ<span style="vertical-align: sub;">P</span>, Θ<span style="vertical-align: sub;">N</span>, Θ<span style="vertical-align: sub;">B</span>, Θ<span style="vertical-align: sub;">R</span>, Θ<span style="vertical-align: sub;">Q</span>)</span>
requires [https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_minimization minimizing] the [https://en.wikipedia.org/wiki/Cross_entropy cross-entropy] [https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_error_function_and_logistic_regression cost function] for the [https://en.wikipedia.org/wiki/Logistic_regression logistic regression] <ref>"Using [https://en.wikipedia.org/wiki/Cross_entropy#Cross-entropy_error_function_and_logistic_regression cross-entropy error function] instead of [https://en.wikipedia.org/wiki/Mean_squared_error sum of squares] leads to faster training and improved generalization", from [https://en.wikipedia.org/wiki/Sargur_Srihari Sargur Srihari], [http://www.cedar.buffalo.edu/~srihari/CSE574/Chap5/Chap5.2-Training.pdf Neural Network Training] (pdf)</ref>:
[[FILE:PointValByRegressionFormula2.jpg|none|text-bottom]]
with the [https://en.wikipedia.org/wiki/Logistic_function logistic function] for the vector argument:
[[FILE:PointValByRegressionFormula3.jpg|none|text-bottom]]
The introduction of [https://en.wikipedia.org/wiki/Regularization_%28mathematics%29 regularization] prevents [https://en.wikipedia.org/wiki/Overfitting overfitting] and effects of instability in the solution found in the cost function:
[[FILE:PointValByRegressionFormula4.jpg|none|text-bottom]]
The coefficients of regularization is chosen small, in this case λ = 10<span style="font-size: 90%; vertical-align: super;">-6</span>.
To solve the problem of [https://en.wikipedia.org/wiki/Maxima_and_minima minimization], a simple [https://en.wikipedia.org/wiki/Gradient_descent gradient descent] with a constant slope is applied <ref>[https://en.wikipedia.org/wiki/Del Nabla operator or Del from Wikipedia]</ref>:
[[FILE:PointValByRegressionFormula5.jpg|none|text-bottom]]
where the components of the gradient of J reg have the form:
[[FILE:PointValByRegressionFormula6.jpg|none|text-bottom]]
[[FILE:PointValByRegressionFormula7.jpg|none|text-bottom]]
Since we are looking for a symmetric solution in material equality which gives the probability of the outcome of the game ½, coefficient vector θ is always zero, and we only need for the gradient of the second of these expressions. Anyone interested in the justification of the above formulas is recommend to study the [[#course|already mentioned]] machine learning course at [https://en.wikipedia.org/wiki/Coursera Coursera].
=Program and Results=
Since the first part of the problem, the analysis of [[Portable Game Notation|PGN-Files]] and the allocation for each item set of features, has practically been implemented in the chess engine [[GreKo]], it was decided to use [[Cpp|C++]] for the pgn learning stuff as well. Source code and PGN samples are available at [https://en.wikipedia.org/wiki/GitHub GitHub] <ref>[https://github.com/WinPooh/pgnlearn WinPooh/pgnlearn · GitHub]</ref> . The program can be compiled and run under [[Windows]] ( [https://en.wikipedia.org/wiki/Visual_C%2B%2B MSVC]) or [[Linux]] ([[Free Software Foundation#GCC|GCC]]).
The ability to use further [https://en.wikipedia.org/wiki/List_of_numerical_analysis_software specialized tools] like [https://en.wikipedia.org/wiki/GNU_Octave GNU Octave], [https://en.wikipedia.org/wiki/MATLAB MATLAB], [https://en.wikipedia.org/wiki/R_%28programming_language%29 R], etc. is also provided, the program generates an intermediate text file with a set of features and outcome of the game, which can easily be imported into these environments. The file contains the text representation of a set of vectors x j - matrix of dimension mx (n + 1) in the first 5 columns that contain components of the material balance (from the pawn to a queen), and in the 6th - the result of the game.
Consider a simple example. Below is a PGN-record of one of the test batches:
<pre>
[Event "OpenRating 31"]
[Site "BEAR-HOME"]
[Date "2013.05.09"]
[Round "1"]
[White "Simplex 0.9.7"]
[Black "IvanHoe 999946f"]
[Result "0-1"]
[TimeControl "60+1"]
[PlyCount "96"]
1.d4 d5 2.c4 e6 3.e3 c6 4.Nf3 Nd7 5.Nbd2 Nh6 6.e4 Bb4 7.a3 Ba5 8.cxd5 exd5
9.exd5 cxd5 10.Qe2+ Kf8 11.Qb5 Nf6 12.Bd3 Qe7+ 13.Kd1 Bb6 14.Re1 Bd7 15.Qb3
Be6 16.Re2 Qc7 17.Qb4+ Kg8 18.Nb3 Bf5 19.Bb1 Bxb1 20.Rxb1 Nf5 21.Bd2 a5 22.Qa4
h6 23.Rc1 Qb8 24.Bxa5 Qf4 25.Qb4 Bxa5 26.Nxa5 Kh7 27.Nxb7 Rab8 28.a4 Ne4 29.h3
Rhc8 30.Ra1 Rc7 31.Qa3 Rcxb7 32.g3 Qc7 33.Rc1 Qa5 34.Rxe4 dxe4 35.Rc5 Qa6
36.Nd2 Nxd4 37.Rc4 Nb3 38.Nxb3 Qxc4 39.Nd2 Rd8 40.Qc3 Qf1+ 41.Kc2 Qe2 42.f4 e3
43.b4 Rc7 44.Kb3 Qd1+ 45.Ka2 Rxc3 46.Nb1 Qxa4+ 47.Na3 Rc2+ 48.Ka1 Rd1# 0-1
</pre>
The corresponding fragment of intermediate file looks like:
<pre>
0 0 0 0 0 0
1 0 0 0 0 0
2 0 0 0 0 0
2 -1 0 0 0 0
2 0 0 -1 0 0
1 0 0 -1 0 0
1 1 0 -2 0 0
</pre>
The 6th column, 0 everywhere - is the result of the game, black won. The other columns - the balance of pieces on the board. The first line of complete equality of material, all of the components are 0. The second line - a pawn for white, is a position after the 24th move. Note that prior exchanges are not considered as they were too early. After the 27th move White has two extra pawns. Before the final attack of Black, White has only a pawn and a knight for two rooks.
[[FILE:MedvedevArticlegendiag.png|none|border|text-bottom|link=http://habrahabr.ru/post/254753/]]
Like the opening exchanges, the final moves in the game are not considered. They were screened out by "filter tactics" because they represent a series of captures, checks and evadings from check.
Similar records were created for all analyzed batches, the average obtained 5-10 lines per game. After analysis of the PGN-base, that file is further directed to the second part of the program dealing with the problem of minimizing their own decisions. A starting point for the [https://en.wikipedia.org/wiki/Gradient_descent gradient descent] is a vector with the values of the balances from the textfile. Starting from scratch, it turned out that the cost function is "good" enough to convert during several thousand steps to a global minimum, as shown in the following chart (at each step, the normalization of the weight of the pawn = 100):
[[FILE:MedvedevArticleChart2.png|none|border|text-bottom|link=http://habrahabr.ru/post/254753/]]
After normalization and rounding, the following values were determined:
{| class="wikitable"
|-
! Piece
! Value
|-
| Pawn
| style="text-align:right;" | 100
|-
| Knight
| style="text-align:right;" | 288
|-
| Bishop
| style="text-align:right;" | 345
|-
| Rook
| style="text-align:right;" | 480
|-
| Queen
| style="text-align:right;" | 1077
|-
| King
| style="text-align:right;" | ∞
|}
Compared with the rules of Capablanca:
{| class="wikitable"
|-
! Condition
! Numerical
! True?
|-
| <span style="color: #088a29;">B > N</span>
| style="text-align:center;" | <span style="color: #088a29;">345 > 288</span>
| <span style="color: #088a29;">yes</span>
|-
| <span style="color: #088a29;">B > 3P</span>
| style="text-align:center;" | <span style="color: #088a29;">345 > 300</span>
| <span style="color: #088a29;">yes</span>
|-
| <span style="color: #ff0000;">N > 3P</span>
| style="text-align:center;" | <span style="color: #ff0000;">288 < 300</span>
| <span style="color: #ff0000;">no</span>
|-
| <span style="color: #088a29;">B + N = R + 1.5P</span>
| style="text-align:center;" | <span style="color: #088a29;">345+288 = 480+150</span>
| <span style="color: #088a29;">yes (accuracy of < 0.5%)</span>
|-
| <span style="color: #ff0000;">Q + P = 2R</span>
| style="text-align:center;" | <span style="color: #ff0000;">1077 + 100 > 960</span>
| <span style="color: #ff0000;">no</span>
|}
The result is quite encouraging. Not knowing anything about the actual events taking place on the board, considering only the outcome of the game, the algorithm has managed to bring the point values close to their traditional values.
Is it possible to use the resulting values to enhance the chess program? Alas, at this point the answer is no. Test blitz matches showed that the strength of GreKo using the parameters found remained virtually unchanged, and in some cases even declined. Why did it happen? One of the obvious reasons - the already mentioned strong link between search and evaluation. The search incorporates a number of heuristics to cut off the dead-end branches and the criteria of pruning (thresholds) are closely tied to the static evaluation. By changing the value of the pieces, one shifts the scale of values - a form of search tree change requires new balancing of constants for all heuristics, which is a rather time consuming task.
=Human Players=
Let's try to expand the experiment, considering not only computers, but also human chess players. The data set to study the games were taken from two outstanding contemporary grandmasters - the [https://en.wikipedia.org/wiki/World_Chess_Championship world chess champion] [https://en.wikipedia.org/wiki/Magnus_Carlsen Magnus Carlsen] and former world chess champion [https://en.wikipedia.org/wiki/Viswanathan_Anand Viswanathan Anand], as well a representative of [https://en.wikipedia.org/wiki/Romantic_chess romantic chess] of the [https://en.wikipedia.org/wiki/19th_century 19th century], [https://en.wikipedia.org/wiki/Adolf_Anderssen Adolf Andersen].
{| class="wikitable"
|-
|
| style="text-align:center;" | [[FILE:VishyAnand09.jpg|none|border|text-bottom|x200px]]
| style="text-align:center;" | [[FILE:Carlsen Magnus (30238051906).jpg|none|border|text-bottom|x200px]]
| style="text-align:center;" | [[FILE:And00278.png|none|border|text-bottom|x200px]]
|-
!
! Anand <ref>[https://en.wikipedia.org/wiki/Viswanathan_Anand Viswanathan Anand], world chess champion, Photo by Stefan64, January 2013, [https://en.wikipedia.org/wiki/World_Chess_Championship_2014 World Chess Championship 2014 from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>
! Carlsen <ref>[https://en.wikipedia.org/wiki/Magnus_Carlsen Magnus Carlsen], chess grandmaster from Norway, Photo by Stefan64, January 2013, [https://en.wikipedia.org/wiki/World_Chess_Championship_2014 World Chess Championship 2014 from Wikipedia], [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons]</ref>
! Andersen <ref>[https://en.wikipedia.org/wiki/Adolf_Anderssen Adolf Andersen from Wikipedia]</ref>
|-
| Pawn
| style="text-align:center;" | 100
| style="text-align:center;" | 100
| style="text-align:center;" | 100
|-
| Knight
| style="text-align:center;" | 216
| style="text-align:center;" | 213
| style="text-align:center;" | 286
|-
| Bishop
| style="text-align:center;" | 230
| style="text-align:center;" | 243
| style="text-align:center;" | 289
|-
| Rook
| style="text-align:center;" | 355
| style="text-align:center;" | 352
| style="text-align:center;" | 531
|-
| Queen
| style="text-align:center;" | 762
| style="text-align:center;" | 786
| style="text-align:center;" | 1013
|-
| King
| style="text-align:center;" | ∞
| style="text-align:center;" | ∞
| style="text-align:center;" | ∞
|}
It is easy to notice that the "human" point values appear different of how beginners are taught in textbooks. In the case of Carlsen and Anand strikes a smaller scale - the queen is a little more than 7.5 pawns, respectively, reduced for all other pieces. Bishop is still a little more worth than knight, but they don't even reach the traditional three pawns. Two rooks are weaker than the queen, etc.
I must say that a similar situation is observed not only from Vishy and Magnus, but for most GMs, whose games failed the test. The values are shrinked from classic in the same way for masters like [[Mikhail Botvinnik]] and [https://en.wikipedia.org/wiki/Anatoly_Karpov Anatoly Karpov], and the attacking players [https://en.wikipedia.org/wiki/Mikhail_Tal Mikhail Tal], and [https://en.wikipedia.org/wiki/Judit_Polg%C3%A1r Judit Polgár] ...
One of the few exceptions was Adolf Andersen, one of the best European players in the middle of the 19th century, famous for the [https://en.wikipedia.org/wiki/Immortal_Game Immortal Game]. His point values are very similar to those from chess programs.
Why is there such an effect with compressing the range of point values? Of course, don't forget about the very limited model - considering additional positional features could make a significant difference. But perhaps it is a case of a "weak implementation" of human players concerning material advantage - compared to modern chess programs. Simply put - a person has a hard time to correctly play with the queen due to its opportunities. I remember an anecdote from a textbook by [[Mathematician#EmanuelLasker|Emanuel Lasker]] (in other versions from Capablanca, [https://en.wikipedia.org/wiki/Alexander_Alekhine Alekhine] or Tal), ostensibly to play with handicap with a random fellow traveler in the train. The culmination was the phrase: "The queen only hinders!"
=Conclusion=
We examined one aspect of the evaluation function of chess programs - the material balance. We made sure that this part of the static evaluation model is smooth through the logistic function and associated with the probability of the outcome of the game. Then we looked at several weight combinations to estimate their influence on the strength of the chess program.
With the help of lots of different regression players, both humans and chess programs, we have determined the optimum value of the piece values under the assumption of a purely "financial" evaluation function. We found an interesting effect in humans versus machines. We tried to use the values found in a real engine, and ... had not achieved much success.
Where to go from here? For a more accurate estimate of the position a new model of chess knowledge may be established - that is, to increase the dimension of x and θ. Even staying in the material only world (excluding the squares occupied by the pieces on the board), one can add a number of relevant features: bishop pair, a couple of queen and knight, the last pawn in the endgame ... Chess players do well know as the value of the pieces may depend on the combination or the stage of the game. In chess programs, corresponding weights (bonuses or penalties) may reach tenths of a pawn and more.
One way (along with an increase in sample size) used for training games, is playing the previous version of the same program. In this case, there is hope for some signs of greater coherence with other assessments. Also, a cost function may be used which is not predicting the outcome of the game (which could end in a few tens of moves behind the position under consideration), but the correlation of static with dynamic assessment, ie. with the result of the alpha-beta search of a certain depth.
However, as noted above, to directly enhance the chess program's results may not be suitable. It often happens that after a series of tests, the trained program begins to better address the tests (in our case - to predict the result of the game), but did not play better! At present, the mainstream chess programs were extensively tested exclusively in practical play. New versions of the top engines are tested before release with tens and hundreds of thousands of games with ultrashort time control ...
In any case, I plan to spend another series of experiments on the statistical analysis of chess games. If this topic is of interest to the audience Habra, upon receipt of any non-trivial result of the article can be continued.
No chess pieces were harmed during investigation.
[[FILE:MedvedevArticlePieces2.jpg|none|border|text-bottom]]
----
=See also=
* [[Komodo#PointValues|Centered Point Values in Komodo]]
* [[Eval Tuning in Deep Thought]]
* [[Learning]]
* [[Neural Networks]]
* [[Pawn Advantage, Win Percentage, and Elo]]
* [[Point Value]]
* [[Texel's Tuning Method]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=56168 Piece weights with regression analysis (in Russian)] by [[Vladimir Medvedev]], [[CCC]], April 30, 2015
: [http://www.talkchess.com/forum/viewtopic.php?t=56168&start=22 Results of 234 players] by [[Jesús Muñoz]], [[CCC]], May 02, 2015
: [http://www.talkchess.com/forum/viewtopic.php?t=56168&start=36 Re: Piece weights with regression analysis (in Russian)] by [[Fabien Letouzey]], [[CCC]], May 04, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=56232&start=24 Re: Pawn value estimation] by [[Larry Kaufman]], [[CCC]], May 09, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=64972 Approximating Stockfish's Evaluation by PSQTs] by [[Thomas Dybdahl Ahle]], [[CCC]], August 23, 2017 » [[Automated Tuning#Regression|Regression]], [[Piece-Square Tables]], [[Stockfish]]
=External Links=
* [http://habrahabr.ru/post/254753/ Определяем веса шахматных фигур регрессионным анализом / Хабрахабр] by [[Vladimir Medvedev|WinPooh]], April 27, 2015 (Russian)
* [https://github.com/WinPooh/pgnlearn WinPooh/pgnlearn · GitHub]
* [https://en.wikipedia.org/wiki/Regression_analysis Regression analysis from Wikipedia]
* [https://en.wikipedia.org/wiki/Logistic_function Logistic function from Wikipedia]
* [https://en.wikipedia.org/wiki/Logistic_regression Logistic regression from Wikipedia]
* [https://en.wikipedia.org/wiki/Maximum_likelihood Maximum likelihood from Wikipedia]
* [https://en.wikipedia.org/wiki/Cross_entropy Cross-entropy from Wikipedia]
* [https://www.coursera.org/learn/machine-learning Machine Learning - Stanford University | Coursera]
=References=
<references />
'''[[Automated Tuning|Up one Level]]'''
