Development of a chess program
Have you ever been interested in writing your own chess program? Adjust and develop it, check it on familiar chess lovers and enjoy its victories. But how to write such a program? About this I will tell in this article.
At first, I wanted to give a complete description of my implementation of the chess engine (I called it Centurion). But then I suddenly realized that they were writing books on this topic, not articles. In the format of the article it is simply impossible to describe in detail all the components of the chess program with the details of the implementations. Therefore, I decided to limit myself to a general description of my chess engine and give a link to its source code and the program itself. Windows program looks like this:
Program for Windows.
You can walk either by entering a move in the field (E2-E4), or by a mouse - the left button from where, the right button - where.
So, let's begin.
To begin with, it is worth looking for special literature on how to write chess programs. Of these, I used the Kornilov book “Programming Chess and Other Logic Tasks” 2005. This book alone was not enough - the author did not focus on something important, but simply did not say something. And this is something, by the way, greatly reduces the brute force tree. Immediately I warn you that my engine does not use a move generator based on bit arrays. This level is not available to me yet. However, I did not really try to deal with them, preferring to write as transparent as possible (for me) the mechanism for working with the moves of the figures, even to the detriment of speed (the engine was not very fast, but quite efficient).
')
The first thing we need to think about is how we will represent the playing field. It turns out that it is very convenient to represent each cell as an integer, the individual bits of which are responsible for the parameters of this cell. I set a macro for the cells
And my cell itself is represented by bits as AHIIIIEWB0MFFF , where:
W-figure is white
B-figure black
F-type shape (no 0-shape)
M-Did the figure go
E-board edge
I-index of a figure in an array for searching for figures (0-15)
H-was short castling (flag is put only at the king and the rook)
A-was long castling (flag is put only at the king and the rook)
How convenient is the presentation using bits? Mask overlay allows you to quickly determine what kind of cell it is. Especially for this, I have been given masks:
Then you should decide what size the board will be. 8x8 is inconvenient for analyzing going beyond the board. It is much more convenient to set an array of 16x16 with a board in the middle, setting the border flag for all those cells that are not a board. In this case, the change of the X coordinate occurs by changing the X coordinate by the desired step, and by Y by the step * 16. The board is given as
In the future, it will be convenient to set some parameters for the 8x8 field, for this purpose it is worthwhile to get an array of coordinate conversion from the 16x16 field into the 8x8 field.
By the way, in order not to have to scan the entire board, it’s worth remembering where the pieces are on the board. For example:
Now we will define how we will set the moves. It is very convenient to do so:
Here in the arrays are given the changes of coordinates in the space of our 16x16 board for one step of the figure. It is convenient to consider pawn moves separately, since her moves are simple, but there is a specific take on the aisle.
How to use such an array? Well, for example, drawing up all the queen's moves:
As you can see, everything is simple. To store the moves, I created a structure.
Although the array of moves is given as
where MAX_PLY is the maximum depth of analysis (and 200 is the maximum number of moves of any piece (with a margin)), but the pointer to the next element sMove_NextPtr allows you to sort the moves conveniently (and you have to sort them). std :: list (or something else from stl) I didn’t use it here - speed is extremely critical here (and I won’t say that the master is in stl and modern C ++, rather the opposite). However, you can do it with stl and compare the speed of the program - I did not check it.
Well, in general, with the moves finished, let's move on to the algorithms.
First, we need a position evaluation function. Here the possibilities are just the sea. In my engine, in engine_score.cpp, everything that I use to assess my position is quite readable. There are presented arrays of points for finding a figure in a given cell of the field (for an 8x8 field, it is so easy to set).
Secondly, we need alpha-beta with depreciation of failures. I think it makes no sense to consider the alpha-beta algorithm itself - many articles and books have been written on this topic. And in general, he (or his modifications) is at the heart of a variety of chess programs. The most interesting thing in chess programs is how to reduce the number of moves for this algorithm.
Third, we need a hash table. The fact is that in chess the position is often repeated when sorting - why do we need to re-analyze what we have already watched? Identify such a position and allows the hash table. It stores “unique” values ​​that distinguish one position from another. These “unique” values ​​are constructed simply by performing the xor operation for the keys of the elements describing the position. Therefore, we will need arrays of unique 64-bit numbers (you can take any other dimension, the only question is how often different positions correspond to the same position values ​​- hash errors). My table is described as:
You will also need keys to change the course (since the positions can be the same, but the color of the pieces, which should be different). And the special key of the so-called zero move (I will tell about the zero move itself below). As far as I remember, Kornilov kept silent about these last two keys in his book.
I set all these keys hard in the program so as not to generate each time with a unique check.
Now, see what kind of thing comes out: if we initially get a position by executing xor of all the keys of the pieces on the board
, then when performing the move, as you can see, it is enough for us to do with the current hash value the position of the key xor of the figure in the old place, and then the key xor of the figure in the new place. So it is with taking. This makes it possible to calculate the hash value very quickly in the process of sorting positions.
Fourth, we need such a thing as history statistics. What it is? During the game you can see that some moves improve the assessment of the position. It is worth noting this fact, remembering and subsequently used when sorting moves. How to do it? Just start the array [64] [64] ([the starting position of the figure on the 8x8 field] [the final position of the figure on the 8x8 field]), zero at the beginning of the evaluation of the choice of the best move and then simply increase the counter by 1 in the case of a move that improves for us position evaluation.
Fifth, we need to sort the moves. The very first moves should be with the maximum benefit in assessing the position. It is clear that taking moves is more important than ordinary "quiet" moves. The moves are sorted according to the MVV / LVA principle (the most valuable victim is the least valuable attacker). In this case, it is worth advancing all unusual moves with a take (any move that does not have the MOVE_TYPE_SIMPLY type). It is also worth advancing the taking of the last walking figure of the enemy (if the take will be). Normal moves are sorted by ascending position, taking into account the history heuristics. All this sorting is very important! It per se allows reducing the tree walk of the game, but moreover, almost all “quiet” moves (and if the king is not under check) can be thrown out of consideration at the lower levels of the tree, without prejudice to the quality of the game! I saw this in the Ifrit program code and, of course, applied it. This is called Late Move Reduction, as I understand it.
To do this, use the following array:
Here the numbers mean how many “quiet” moves are analyzed depending on the level of the tree (the array is given in the reverse order). That is, at the last for analysis, 9 levels of the tree in consideration will be first 259 moves, then 131, then 67 and so on up to 19. This greatly speeds up the work of the program (and Kornilov also did not seem to tell about this in his book). Of course, such a cut will not work without sorting the moves.
Sixth, we need to definitely extend the analysis of the take and the check. This will increase the accuracy of the position estimate.
Seventh, we will need a killer heuristic. It consists in the fact that when analyzing tree branches, try the first move that caused clipping on the previous branch. This technique also reduces brute force. It should be remembered that such a move can only be “quiet”: taking and unusual moves cannot be used for such checks.
Eighth, there is such a thing as a zero move. The point is that you can make a pass and see how bad everything becomes. At the same time, it is possible to reduce the depth of analysis of a tree (to make a reduction) - anyway, a preliminary estimate. The main thing is not to forget to mark the hash position with the key of this very zero move
Ninth, there is Futility Prunning. What it is? On the last two half-moves of the tree, the position estimate is not accurate and in some cases (if we are not in the zero move, if the move is not a check, a take and a move is not the extension of the branch analysis), and also if the difference in the position estimate was greater than some small value, then just return this estimate and do not analyze further. This technique also speeds up the work of the program.
Tenth, Razoring was also invented to shorten the options. This is almost the same as Futility Prunning, but refers to the last four half-moves and the bound of the estimate is set at some value of the allowable loss of the pieces.
Eleventh, some moves should be extended in the analysis. These include the moves of the capture, the shahs, the approach of the opponent's pieces to the king. It is better to extend a separate analysis function, in which only checks should run a full brute force. For the remaining moves, it suffices to analyze only the capture moves. This is called static search.
Twelfth, there is still such a thing as Principal Variation (the main change). This is the line of the game that the program considers the best at the moment. This line is constantly updated during the search positions. The move from the main line when sorting is worth advancing.
Well, it seems to be all of the set that uses my chess engine. I hope I haven’t confused anything anywhere, since the engine has been around for two years and I haven’t touched it as much and could have completely forgotten something.
The archive contains the engine itself (it supports UCI, so you can connect it to Arena), a Windows program for playing with it (in haste), chess for QNX 6.3. I can’t accurately estimate the level of the game (I’m not a chess player, oddly enough), but it seems to be playing quite well.
Added a link to github:
Chess
At first, I wanted to give a complete description of my implementation of the chess engine (I called it Centurion). But then I suddenly realized that they were writing books on this topic, not articles. In the format of the article it is simply impossible to describe in detail all the components of the chess program with the details of the implementations. Therefore, I decided to limit myself to a general description of my chess engine and give a link to its source code and the program itself. Windows program looks like this:
Program for Windows.
You can walk either by entering a move in the field (E2-E4), or by a mouse - the left button from where, the right button - where.
So, let's begin.
To begin with, it is worth looking for special literature on how to write chess programs. Of these, I used the Kornilov book “Programming Chess and Other Logic Tasks” 2005. This book alone was not enough - the author did not focus on something important, but simply did not say something. And this is something, by the way, greatly reduces the brute force tree. Immediately I warn you that my engine does not use a move generator based on bit arrays. This level is not available to me yet. However, I did not really try to deal with them, preferring to write as transparent as possible (for me) the mechanism for working with the moves of the figures, even to the detriment of speed (the engine was not very fast, but quite efficient).
')
The first thing we need to think about is how we will represent the playing field. It turns out that it is very convenient to represent each cell as an integer, the individual bits of which are responsible for the parameters of this cell. I set a macro for the cells
#define CELL long And my cell itself is represented by bits as AHIIIIEWB0MFFF , where:
W-figure is white
B-figure black
F-type shape (no 0-shape)
M-Did the figure go
E-board edge
I-index of a figure in an array for searching for figures (0-15)
H-was short castling (flag is put only at the king and the rook)
A-was long castling (flag is put only at the king and the rook)
How convenient is the presentation using bits? Mask overlay allows you to quickly determine what kind of cell it is. Especially for this, I have been given masks:
#define BYTE8(b7,b6,b5,b4,b3,b2,b1,b0) ((CELL)((b7<<7)|(b6<<6)|(b5<<5)|(b4<<4)|(b3<<3)|(b2<<2)|(b1<<1)|(b0<<0))) //---------------------------------------------------------------------------------------------------- // //---------------------------------------------------------------------------------------------------- // #define FIGURE_TYPE_KING 1 // #define FIGURE_TYPE_QUEEN 2 // #define FIGURE_TYPE_ROOK 3 // #define FIGURE_TYPE_BISHOP 4 // #define FIGURE_TYPE_KNIGHT 5 // #define FIGURE_TYPE_PAWN 6 // #define BLACK BYTE8(0,0,1,0,0,0,0,0) #define WHITE BYTE8(0,1,0,0,0,0,0,0) // #define CASTLING_O_O (BYTE8(0,0,0,1,0,0,0,0)<<8) // #define CASTLING_O_O_O (BYTE8(0,1,0,0,0,0,0,0)<<8) // #define INDEX_SHIFT 8 // #define MASK_WHITE WHITE // #define MASK_BLACK BLACK // #define MASK_COLOR (MASK_WHITE|MASK_BLACK) // #define MASK_TYPE BYTE8(0,0,0,0,0,1,1,1) // #define MASK_BORDER BYTE8(1,0,0,0,0,0,0,0) //, #define MASK_IS_MOVED BYTE8(0,0,0,0,1,0,0,0) // #define MASK_INDEX ((BYTE8(0,0,0,0,1,1,1,1))<<INDEX_SHIFT) // #define MASK_CASTLING (BYTE8(0,0,1,1,0,0,0,0)<<8) // #define CELL_EMPTY 0 Then you should decide what size the board will be. 8x8 is inconvenient for analyzing going beyond the board. It is much more convenient to set an array of 16x16 with a board in the middle, setting the border flag for all those cells that are not a board. In this case, the change of the X coordinate occurs by changing the X coordinate by the desired step, and by Y by the step * 16. The board is given as
CELL Board[256];// (16x16). In the future, it will be convenient to set some parameters for the 8x8 field, for this purpose it is worthwhile to get an array of coordinate conversion from the 16x16 field into the 8x8 field.
By the way, in order not to have to scan the entire board, it’s worth remembering where the pieces are on the board. For example:
#define COORD long COORD FigureWhiteCoord256[16];// ( . 0- ) COORD FigureBlackCoord256[16];// ( . 0- ) COORD *KingWhitePointer;// COORD *KingBlackPointer;// Now we will define how we will set the moves. It is very convenient to do so:
long KingMove[9]={16,-16,1,-1,17,-17,15,-15,0};// long QueenMove[9]={16,-16,1,-1,17,-17,15,-15,0};// long RookMove[5]={16,-16,1,-1,0};// long BishopMove[5]={17,-17,15,-15,0};// long KnightMove[9]={32+1,32-1,16+2,16-2,-(32+1),-(32-1),-(16+2),-(16-2),0};// Here in the arrays are given the changes of coordinates in the space of our 16x16 board for one step of the figure. It is convenient to consider pawn moves separately, since her moves are simple, but there is a specific take on the aisle.
How to use such an array? Well, for example, drawing up all the queen's moves:
long n; CELL cell=Board[coord256]; FIGURE_COLOR color=cell&MASK_COLOR; FIGURE_COLOR opponent_color=color^(WHITE|BLACK); FIGURE_TYPE type=cell&MASK_TYPE; //-------------------------------------------------- // //-------------------------------------------------- if (type==FIGURE_TYPE_QUEEN) { n=0; while(QueenMove[n]!=0) { COORD c256=coord256+QueenMove[n]; while(Board[c256]==CELL_EMPTY)// { Move_AddMove(coord256,c256,FIGURE_TYPE_QUEEN,MOVE_TYPE_SIMPLY,sMove_Ptr,move,sMove_FirstPtr,sMoveKitPtr);// , c256+=QueenMove[n]; } cell=Board[c256]; if ((cell&MASK_COLOR)==opponent_color)// { Move_AddEatMove(coord256,c256,FIGURE_TYPE_QUEEN,MOVE_TYPE_SIMPLY,sMove_EatPtr,move_eat,sMove_FirstEatPtr,sMoveKitPtr);// } n++; } return; } As you can see, everything is simple. To store the moves, I created a structure.
// enum MOVE_TYPE { MOVE_TYPE_EMPTY=-1,// MOVE_TYPE_SIMPLY=0,// MOVE_TYPE_CASTLING=1,// MOVE_TYPE_WHITE_PASSED_PAWN_EAT=2,// MOVE_TYPE_BLACK_PASSED_PAWN_EAT=3,// MOVE_TYPE_CONVERSION=4,// }; // struct SMove { // COORD Coord256_1; // COORD Coord256_2; MOVE_TYPE MoveType;// FIGURE_TYPE NewFigureType;// , COORD Coord256_PassedPawn;// ( . 0- ) ENGINE_BOOL IsEat;//- // ( ) long Score; // SMove *sMove_NextPtr; }; Although the array of moves is given as
SMove sMove_Level[MAX_PLY+5][200];// SMove sMove_EatLevel[MAX_PLY+5][200];// where MAX_PLY is the maximum depth of analysis (and 200 is the maximum number of moves of any piece (with a margin)), but the pointer to the next element sMove_NextPtr allows you to sort the moves conveniently (and you have to sort them). std :: list (or something else from stl) I didn’t use it here - speed is extremely critical here (and I won’t say that the master is in stl and modern C ++, rather the opposite). However, you can do it with stl and compare the speed of the program - I did not check it.
Well, in general, with the moves finished, let's move on to the algorithms.
First, we need a position evaluation function. Here the possibilities are just the sea. In my engine, in engine_score.cpp, everything that I use to assess my position is quite readable. There are presented arrays of points for finding a figure in a given cell of the field (for an 8x8 field, it is so easy to set).
Secondly, we need alpha-beta with depreciation of failures. I think it makes no sense to consider the alpha-beta algorithm itself - many articles and books have been written on this topic. And in general, he (or his modifications) is at the heart of a variety of chess programs. The most interesting thing in chess programs is how to reduce the number of moves for this algorithm.
Third, we need a hash table. The fact is that in chess the position is often repeated when sorting - why do we need to re-analyze what we have already watched? Identify such a position and allows the hash table. It stores “unique” values ​​that distinguish one position from another. These “unique” values ​​are constructed simply by performing the xor operation for the keys of the elements describing the position. Therefore, we will need arrays of unique 64-bit numbers (you can take any other dimension, the only question is how often different positions correspond to the same position values ​​- hash errors). My table is described as:
//---------------------------------------------------------------------------------------------------- //- //---------------------------------------------------------------------------------------------------- //- [ ][ ][ 16x16] unsigned __int64 ZobristKey[FIGURE_TYPE_PAWN+1][2][256]= You will also need keys to change the course (since the positions can be the same, but the color of the pieces, which should be different). And the special key of the so-called zero move (I will tell about the zero move itself below). As far as I remember, Kornilov kept silent about these last two keys in his book.
unsigned __int64 ZobristKeyMove=0x54ca3eb5b5f3cb5b;// unsigned __int64 ZobristKeyNullMove=0x08d9bc25bebf91b1;// I set all these keys hard in the program so as not to generate each time with a unique check.
Now, see what kind of thing comes out: if we initially get a position by executing xor of all the keys of the pieces on the board
//---------------------------------------------------------------------------------------------------- // - //---------------------------------------------------------------------------------------------------- unsigned __int64 Hash_GetHKey(void) { unsigned __int64 key=0; COORD coord256=4*16+4; for(long y=0;y<8;y++,coord256+=16) { COORD coord256_local=coord256; for(long x=0;x<8;x++,coord256_local++) { CELL cell=Board[coord256_local]; FIGURE_COLOR color=cell&MASK_COLOR; FIGURE_TYPE type=cell&MASK_TYPE; if (type==0) continue; if (color==WHITE) key^=ZobristKey[type][ZOBRIST_WHITE][coord256_local]; if (color==BLACK) key^=ZobristKey[type][ZOBRIST_BLACK][coord256_local]; } } return(key); } , then when performing the move, as you can see, it is enough for us to do with the current hash value the position of the key xor of the figure in the old place, and then the key xor of the figure in the new place. So it is with taking. This makes it possible to calculate the hash value very quickly in the process of sorting positions.
Fourth, we need such a thing as history statistics. What it is? During the game you can see that some moves improve the assessment of the position. It is worth noting this fact, remembering and subsequently used when sorting moves. How to do it? Just start the array [64] [64] ([the starting position of the figure on the 8x8 field] [the final position of the figure on the 8x8 field]), zero at the beginning of the evaluation of the choice of the best move and then simply increase the counter by 1 in the case of a move that improves for us position evaluation.
Fifth, we need to sort the moves. The very first moves should be with the maximum benefit in assessing the position. It is clear that taking moves is more important than ordinary "quiet" moves. The moves are sorted according to the MVV / LVA principle (the most valuable victim is the least valuable attacker). In this case, it is worth advancing all unusual moves with a take (any move that does not have the MOVE_TYPE_SIMPLY type). It is also worth advancing the taking of the last walking figure of the enemy (if the take will be). Normal moves are sorted by ascending position, taking into account the history heuristics. All this sorting is very important! It per se allows reducing the tree walk of the game, but moreover, almost all “quiet” moves (and if the king is not under check) can be thrown out of consideration at the lower levels of the tree, without prejudice to the quality of the game! I saw this in the Ifrit program code and, of course, applied it. This is called Late Move Reduction, as I understand it.
To do this, use the following array:
static const long FutilityMoveCount[9]={19,19,19,19,19,35,67,131,259}; Here the numbers mean how many “quiet” moves are analyzed depending on the level of the tree (the array is given in the reverse order). That is, at the last for analysis, 9 levels of the tree in consideration will be first 259 moves, then 131, then 67 and so on up to 19. This greatly speeds up the work of the program (and Kornilov also did not seem to tell about this in his book). Of course, such a cut will not work without sorting the moves.
Sixth, we need to definitely extend the analysis of the take and the check. This will increase the accuracy of the position estimate.
Seventh, we will need a killer heuristic. It consists in the fact that when analyzing tree branches, try the first move that caused clipping on the previous branch. This technique also reduces brute force. It should be remembered that such a move can only be “quiet”: taking and unusual moves cannot be used for such checks.
Eighth, there is such a thing as a zero move. The point is that you can make a pass and see how bad everything becomes. At the same time, it is possible to reduce the depth of analysis of a tree (to make a reduction) - anyway, a preliminary estimate. The main thing is not to forget to mark the hash position with the key of this very zero move
Ninth, there is Futility Prunning. What it is? On the last two half-moves of the tree, the position estimate is not accurate and in some cases (if we are not in the zero move, if the move is not a check, a take and a move is not the extension of the branch analysis), and also if the difference in the position estimate was greater than some small value, then just return this estimate and do not analyze further. This technique also speeds up the work of the program.
Tenth, Razoring was also invented to shorten the options. This is almost the same as Futility Prunning, but refers to the last four half-moves and the bound of the estimate is set at some value of the allowable loss of the pieces.
Eleventh, some moves should be extended in the analysis. These include the moves of the capture, the shahs, the approach of the opponent's pieces to the king. It is better to extend a separate analysis function, in which only checks should run a full brute force. For the remaining moves, it suffices to analyze only the capture moves. This is called static search.
Twelfth, there is still such a thing as Principal Variation (the main change). This is the line of the game that the program considers the best at the moment. This line is constantly updated during the search positions. The move from the main line when sorting is worth advancing.
Well, it seems to be all of the set that uses my chess engine. I hope I haven’t confused anything anywhere, since the engine has been around for two years and I haven’t touched it as much and could have completely forgotten something.
The archive contains the engine itself (it supports UCI, so you can connect it to Arena), a Windows program for playing with it (in haste), chess for QNX 6.3. I can’t accurately estimate the level of the game (I’m not a chess player, oddly enough), but it seems to be playing quite well.
Added a link to github:
Chess
Source: https://habr.com/ru/post/329528/
All Articles