Hikaru Nakamura, who recently challenged a computer

The computer has long won a man of chess, now the strongest chess players are not able to win even an old laptop. Now, chess engines are used to analyze the games, search for new variants and play correspondence.

If it is interesting to you how chess engines are arranged - welcome under kat.

Introduction

Once I was sure that chess programs (they are the engines, however, about this a bit later) simply hold in mind a huge number of games played and find their current position in them and make the right move. In my opinion, I read about it in some book.
')
This is undoubtedly a very naive opinion. A new position in chess can be obtained by the tenth move. Although there are fewer positions in chess than in go , nevertheless, already after 3 moves (a move is one move of white and black, a half-move is a move of only one side) the move tree consists of almost 120 million knots. Moreover, the size of the tree after 14 half-moves from the initial position has been considered by enthusiasts for more than a year, having advanced by about a third.

I also thought that chess programs, despite the long-standing victory over the world champion, are still within the reach of the best people. This is also not true.

In a recent man-machine mini-match , Hikaru Nakamura , one of the strongest chess players in the world, played with Komodo , one of the (two) strongest chess programs in the world. The program was launched on 24-core Xeon. Since people can no longer compete with the computer on equal terms, the grandmaster got a head start in each of the 4 games:

• In the first game - a pawn and a move: the computer was playing black and without the f7 pawn
• In the second - only a pawn: the computer played white without the f2 pawn
• In the third, the quality (the difference between the rook and the light piece, is estimated at about 2 pawns): the computer is white without the rook a1, the man without the b8 knight and with the rook a8 in his place.
• In the fourth, there are four moves: the person plays white and instead of the first move he makes 4 any moves, without crossing the middle of the board.

There were some disputes about the odds - for example, the absence of the f pawn weakens the king somewhat, but after castling gives an open line to the rook. The absence of a central pawn, perhaps, gives a greater advantage. 4 moves give a good positional advantage, but if you play a closed debut like the King's Indian defense, then this advantage is not so difficult to negate.

In addition, the games were played with a control of 45 +15 ', that is, 45 minutes per game and 15 seconds of addition each turn. Usually, shorter controls give an additional advantage to the computer, while longer ones - somewhat increase the person’s chances. The computer even in a fraction of a second will have time to brush off the frankly losing moves, while due to the exponential growth of the options tree, each subsequent improvement of the analysis takes more and more time.

Nevertheless, the head start was and the person lost in the match 2.5–1.5, having tied the first 3 games and lost the fourth. At the same time, a weak grandmaster quite confidently won with a handicap of 2 pawns. Therefore, the advantage of the best programs over the best people at the moment is somewhere between 1 and 2 pawns of the handicap. Of course, this assessment is very rough, but for an accurate assessment we need to play several thousand games between people and programs, and this is unlikely that anyone will be involved. Please note that the ELO rating, which is often indicated for programs, has nothing to do with people rating.

What is a chess engine?

In order for a person to play chess with a computer, besides actually searching for a better move, you need a GUI. Fortunately, a universal interface was invented (even two, Winboard and UCI , but most engines use UCI) for communication between the GUI and the actual chess program (engine). Thus, programmers can concentrate on the very algorithm of the game of chess, without thinking about the interface. The reverse side of the coin - since the creation of a GUI is much more boring than writing the engine, the free GUIs noticeably lose out to the paid ones. Unlike engines, where free Stockfish confidently fights for the first line of the rating with paid Komodo.

How do they still play?

So, how does the modern chess engine work?

Board presentation

The basis of any engine is a representation of a chessboard. First of all, it is necessary to “explain” to the computer all the rules of chess and enable it to keep a chess position. Without this, it is impossible to evaluate the position and make moves.

There are two basic ways to store a board view — by shape or by cell . In the first case, we store for each piece its place on the board, in the second - on the contrary, for each cell we store what is there. Each method has its advantages and disadvantages, but at the moment all top engines use the same board representation - bitboards.

Bitboards

By happy coincidence, there are 64 squares on a chessboard. So, if for each cell to use one bit, we can store the entire board in a 64-bit integer.
In one variable we will store all white pieces, in the other - all black, and in another 6 - each type of figures separately (another option - 12 bitboards for each color and type of figures separately).

What is the advantage of this option?
First, the memory. As we will learn later, when analyzing the presentation of the board is copied many times, and, accordingly, eats off the RAM. Bitboards are one of the most compact representations of a chessboard.
Secondly, speed. Many calculations, for example, the calculation of possible moves, are reduced to several bit operations. Due to this, for example, using the POPCNT instruction gives ~ 15% acceleration to modern engines. In addition, during the existence of bitboards, many algorithms and optimizations have been invented, such as, for example, “magic” beatboards .

Search

Minimax

Most of the chess engines are based on the minimax search algorithm or its modification negamex. In short, we go down the tree, evaluate the leaves, and then go up, each time choosing the optimal move for the current player, minimizing the estimate for one (black) and maximizing for the second (white). Hence the name. Once at the root, we get a sequence of moves that is optimal for both players. The difference between minimax and non-maxama is that in the first case we choose turns with maximal and minimal marks, and in the second we change the sign for all marks instead and always choose maximal (we understood the name from where). Read more here and here .

Alpha beta

The first optimization is alpha beta . The idea of ​​alpha-beta is simple - if I already have a good move, then I can cut off moves that are obviously worse. Consider the example on the creepy picture on the left. Suppose player A has 2 possible moves - a3 and b3. After analyzing move a3, the program received a score of +1.75. Starting to evaluate the move b3, the program saw that player B has two moves - a6 and a5. Assessment of a6 +0.5. Since player B chooses a move with a minimum mark, he will not choose a move with a mark higher than 0.5, which means the mark of move b3 is less than 0.5, and it makes no sense to consider it. Thus, all remaining subtree b3 is cut off.

For clipping, we store the upper and lower bounds - alpha and beta. If, when analyzing a move, it receives an estimate higher than beta, then the current node is cut off. If the score is higher than the alpha, then the alpha is updated.

The nodes in alpha-beta are divided into 3 categories:

1. PV-Nodes are nodes whose score fell into the window (between alpha and beta). The root and the leftmost node are always nodes of this type.
2. Cut-Nodes (or fail-high nodes ) - the nodes in which cut-off has occurred.
3. All-Nodes (or fail-low nodes ) are nodes in which no move exceeded alpha by evaluation.

Sort moves

When using alpha-beta, the order of moves becomes important. If we can put the best move first, then the remaining moves will be analyzed much faster due to the cutoffs on the beta.

In addition to using the hash and the best move from the previous iteration, there are several techniques for sorting moves.

For taking, for example, a simple heuristic of MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) can be used. We sort all the takeovers by descending value of the “victim”, and inside we revisit the ascending value of the “aggressor”. Obviously, it is usually more profitable to take a queen pawn than vice versa.

For "quiet" moves, the "killer" method is used - the moves that caused clipping on the beta. These moves are usually checked immediately after hashes and takes.

Hash table or permutation table

Despite the huge size of the tree, many nodes in it are identical. In order not to analyze the same position twice, the computer stores the analysis results in a table and each time checks whether there is already a ready analysis of this position. Usually, such a table stores the actual hash of the position, score, best move, and age of the score. Age is required to replace old positions when filling out the table.

Iterative search

As you know, if we cannot analyze the entire tree completely, the minimax needs an evaluation function. Then, having reached a certain depth, we stop the search, evaluate the position and begin climbing the tree. But such a method requires a predetermined depth and does not provide qualitative intermediate results.

These problems are solved by iterative search. To begin with, we carry out the analysis to a depth of 1, then to a depth of 2, etc. Thus, each time we descend a little deeper than the last time, until the analysis is stopped. To reduce the size of the search tree, the results of the previous iteration are usually used to cut off obviously bad moves on the current one. This method is called aspiration window (aspiration window) and is used everywhere.

Quiet Search (Quiescence Search)

This method is designed to combat the “horizon effect”. Simply stopping the search at the right depth can be very dangerous. Imagine that we stopped in the midst of the exchange of queens - the white took the black queen, and the next move Black should pick up the white. But at the moment on the board - White has an extra queen and the static estimate will be fundamentally wrong.

To do this, before doing a static assessment, we check all captures (sometimes even shahs) and descend the tree to a position in which there are no possible captures and checks. Naturally, if all takes worsen the assessment, then we return the assessment of the current position.

Selective search

The idea of ​​a selective search is to consider “interesting” moves longer and less - uninteresting. To do this, use extensions that increase the depth of search in certain positions, and abbreviations that reduce the depth of search.

The depth is increased in the case of captures, shahs, if the only move is much better than alternatives or if there is a passed pawn.

Clipping and shortening

With clippings and contractions, everything is much more interesting. They can significantly reduce the size of the tree.

Briefly about clipping:

• Delta cutoff - check if taking can improve the current alpha. To do this, add the value of the taken shape to the node's estimate and a little more and see if the resulting value is greater than the alpha. For example, if White lacks a rook, then taking a pawn is unlikely to help them, on the other hand, taking an bishop can help.
• Cutting off uselessness is the same, only for non-taking. If the current estimate is so much lower than the alpha that no positional advantage can compensate for this, then such nodes are cut off. Usually applied at low depths (1-2).
• Historical clipping - for each move we store the number of times this move provoked the clipping, regardless of position. Movements with a high value of this heuristics are cut off. It is usually applied starting from a certain depth and will not be applied on PV nodes. Sometimes combined with the previous method.
• Multi-Cut - if from the first M (for example, 6) nodes at least C (for example, 3) are Cut-node, then we cut all the nodes.
• Clipping on a null-move - if after a null-move (a simple transfer of the queue to an opponent), the score is still higher than beta, then we cut the node. Simply put, if the position is so bad that even after making two moves in a row, the player still cannot improve it, then there is no point in considering this position.

Abbreviations are used when we are not so sure that the move is bad, and therefore we do not cut it, but simply reduce the depth. For example, razoring is an abbreviation, provided that the static estimate of the current position is less than alpha.

Due to the high-quality sorting of moves and clipping, modern engines manage to achieve a branching factor below 2 . Due to this, unfortunately, they sometimes overlook non-standard sacrifices and combinations.

NegaScout and PVS

Two very similar techniques that use the fact that after we found the PV-node (provided that our moves are well sorted), it most likely will not change, that is, all the remaining nodes will return a lower grade than alpha. Therefore, instead of searching with a window from alpha to beta, we are looking for a window from alpha to alpha + 1, which allows us to speed up the search. Of course, if in some node we get clipping by beta, then it should be re-evaluated, already by normal search.

The difference between the two methods is only in the formulation - they were developed at about the same time, but independently, and therefore are known by different names.

Parallel Search

Alpha-beta paralleling is a separate big topic. I will briefly go through it, and who is interested - read Parallel Alpha-Beta Search on Shared Memory Multiprocessors . The difficulty is that with parallel search, many Cut-nodes are analyzed before another thread finds a refutation (sets beta), while in a sequential search, with good sorting, many of these nodes would be cut off.

Lazy smp

Very simple algorithm. We just run all the threads at the same time with the same search. Communication flows at the expense of the hash table. Lazy SMP was surprisingly effective, so much so that the top Stockfish switched to it from YBW. However, some believe that the improvement was due to poor implementation of YBWC and too aggressive cuts, and not because of the advantage of Lazy SMP.

Young Brothers Wait Concept (YBWC)

The first node (older brother) should be fully analyzed, after which a parallel analysis of the remaining nodes (younger brothers) is launched. The idea is the same, the first move will either noticeably improve the alpha, or even allow you to cut off all the other nodes.

Dynamic Tree Splitting (DTS)

Fast and complicated algorithm. About speed: the search speed is measured in ttd (time to depth), that is, the time it takes for the search to reach a certain depth. This indicator can usually be used to compare the work of different versions of the engine or engine running on different number of cores (although Komodo, for example, increases the width of the tree with more available cores). In addition, during operation, the engine displays the search speed in nps (nodes per second). This metric is much more popular, but it does not allow comparing even the engine with itself. Lazy SMP, in which there is no synchronization, increases nps almost linearly, but due to the large amount of unnecessary work, its ttd is not so impressive. While for DTS, nps and ttd vary almost equally .

To be honest, I could not fully understand this algorithm, which, despite its high efficiency, is used literally in a pair of engines. Who is very interesting, follow the link above.

Evaluation

So, we have reached the necessary depth, made a search for peace, and finally we need to evaluate the static position.

The computer evaluates the position in pawns: +1.0 means that White has an advantage equivalent to 1 pawn, -0.5 means that Black has half a pawn advantage. A mate is estimated at 300 pawns, and the position in which the number of moves to mate x is known is at (300-0.01x) pawns. +299.85 means that whites checkmate in 15 moves. At the same time, the program itself usually operates with whole evaluations in centi-peshes (1/100 of a pawn).

What parameters does the computer take into account when evaluating the position?

Material and Mobility

The easiest. Queen 9-12 pawns, rook 5-6, knight and bishop 2.5-4 and pawn, respectively, one pawn. In general, the material is a worthy heuristic for evaluating a position, and any positional advantage is usually transformed eventually into a material one.

Mobility is considered simple - the number of possible moves in the current position. The more of them, the more mobile the player's army.

Figure Position Tables

The knight in the corner of the board is usually bad, pawns closer to the enemy rear are becoming more valuable, and so on. For each piece, a table of bonuses and penalties is compiled depending on its position on the board.

Pawn structure

• Double pawns - two pawns on the same vertical. Often they are difficult to defend with other pawns, considered weakness.
• Lagging pawns are pawns whose neighbors are in front of them. Such pawns cannot be defended by other pawns, and therefore they are considered weakness.
• Passing pawns are pawns that can reach the last rank without interference from enemy pawns. Strong threat to the opponent, especially in the endgame
• Isolated pawns are pawns that have no neighbors. Such pawns in general cannot be defended by other pawns, and therefore they are considered a serious weakness.

Stages of the game

All of the above parameters affect the assessment of the game in different ways, depending on the stage of the game. In the opening there is no sense in passing a pawn, but in the endgame you need to bring the king to the center of the board, and not hide behind the pawns.

Therefore, many engines have a separate estimate for the endgame and for the debut. They evaluate the stage of the game depending on the material remaining on the board and, in accordance with this, consider the assessment - the closer to the end of the game, the less impact the opening assessment and the more - the endgame.

Other

In addition to these main factors, the engines can add some other factors to the assessment - for example, the king’s security, locked pieces, pawn islands, center control, etc.

Accurate assessment or quick search?

Traditional dispute: what is more effective, accurately assess the position or achieve greater depth of search. Experience shows that too “heavy” evaluation functions are ineffective. On the other hand, a more detailed assessment that takes into account more factors usually leads to a more “beautiful” and “aggressive” game.

Debut books and endgame tables

Debut books

At the dawn of computer chess, the program played a very weak debut. Debut often requires strategic decisions that will affect the whole game. On the other hand, people had a well developed theory of debut, debuts were repeatedly analyzed and played from memory. So for computers such a “memory” was created. Starting from the initial position, a tree of moves was built and each move was evaluated. During the game, the engine simply chose one of the “good” moves with a certain probability.

Since then, debut books have grown, many debuts have been analyzed with the help of computers up to the endgame. There is no need for them, the strong engines have learned to play the debut, but they leave the main lines rather quickly.

Endgame tables

Let's return to the introduction. Remember the idea of ​​storing many positions in memory and choosing the right one. Here she is. For a small (up to 7) number of figures, all existing positions have been calculated. That is, in these positions, the computer starts to play perfectly, winning in the minimum number of moves. Minus - the size and time of generation. The creation of these tables helped in the study of endgroups.

Table generation

We will generate all possible (with symmetry) positions with a certain set of shapes. Among them we will find and designate all positions where there is a mat. By the next pass we will designate all positions in which you can get into positions with a mat - in these positions a checkmate is put in 1 move. Thus, we find all positions with a checkmate of 2,3,4, 549 moves. In all unmarked positions - a draw.

Nalimov tables

The first endgame tables published back in 1998. For each position is stored the result of the game and the number of moves to the mat in the ideal game. The size of all six-figure terminations is 1.2 terabytes.

Lomonosov tables

In 2012, all seven-figure endings were counted on the Lomonosov supercomputer at Moscow State University (except 6 vs. 1). These bases are available only for money and these are the only existing complete seven-figure endgame tables.

Syzygy

Standard de facto. These bases are much more compact than the bases of Nalimov. They consist of two parts - WDL (Win Draw Lose) and DTZ (Distance to zeroing). WDL databases are designed for use during a search. Once the tree node is found in the table, we have the exact result of the game in this position. DTZ are intended for use in the root - they store the number of moves until the move moves to zero, a move (a pawn or a take). thus, WDL bases are enough for analysis, and DTZ bases can be useful when analyzing endgames. Syzygy size is much smaller - 68 gigabytes for six-figured WDL and 83 for DTZ. Seven-figure bases do not exist, since their generation requires approximately a terabyte of RAM.

Using

Endgame tables are used mainly for analysis, the increase in the strength of the game engines is small - 20-30 points of ELO . However, since the depth of search for modern engines can be very large, requests for endgame bases from the search tree occur even in the opening.

Other interesting things

Giraffe or neural networks play chess

Some of you may have heard about the chess engine on neural networks that have reached the IM level (which, as we understood in the introduction, is not so cool for the engine). He wrote and posted on Bitbucket Matthew Lai, who unfortunately stopped working on him because he started working in Google DeepMind .

Tuning parameters

It is easy to add a new function to the engine, but how to check that it gave the gain? The simplest option is to play several games between the old and the new version and see who wins. But if the improvement is small, and it usually happens after all the main features are added, there should be several thousand games, otherwise there will be no certainty.

Stockfish

There are a lot of people working on this engine, and their every idea needs to be checked. With the current strength of the engine, each improvement gives an increase in a couple of points in the rating, but the result is a steady increase of several dozen points annually.

Their solution is typical for open source - volunteers provide their power to drive hundreds of thousands of games to them.

CLOP

A program that optimizes parameters through linear regression, using the results of the engine games with itself with different parameters. Of the minuses, the size of the task is very limited: it cannot optimize a hundred parameters (quite an adequate number for the engine), at least in an adequate time.

Texel's tuning

Solves the problem of the previous method. We take a large number of positions (the author offered 9 million positions from 64,000 games, I took 8 million from almost 200,000), for each we save the result of the game (White’s victory 1, draw 0.5, loss 0). Now we minimize the error, which is the sum of the squares of the difference between the result and the sigmoid estimate. The method is effective and popular, but does not work on all engines.

Stockfish tuning

Another technique from the leader. We take the parameter equal to x, and compare (in several tens of thousands of batches) the engine with the parameter equal to x-sigma and x + sigma. If the engine won with a large parameter, move it up a little, otherwise, move it down a little and repeat.

Engine contests

Of all the competitions being held, I would like to separately highlight TCEC . It differs from all the others with a powerful iron, careful selection of debuts and long control. In the last final, 100 games were played for 2 x Intel Xeon E5-2690v3 with 256 gigabytes of RAM with 180 '+ 30 "control. In such conditions, the number is huge, and only 11 games were productive.

Conclusion

So in brief in this long article I talked about the structure of chess engines. Many details were not disclosed, I simply did not know about something or forgot to say. If you have any questions, write them in the comments. In addition, I would advise you two resources that you probably noticed if you carefully opened all the links scattered on the article:

• Chess programming wiki
• Talkchess Forum
• And one more, not mentioned earlier - programmer corner