The Chess Endgame Project
This project which started as part of the Media Specialist Practice module of my masters program, aims to improve the performance of a chess engine in the endgame stage using known Artificial Intelligence (AI) algorithms. I chose this particular project because as said in the 'Chess Endgame' section of this blog, the final stage of a chess game or the endgame is where many chess engines even powerful ones suffer a decline in their performance quality; in other words they tend to not make very 'smart' choices in this stage of the game despite an otherwise excellent performance up until then; this obviously can cost them the game.
In order to ensure 'smart' decision on move making by the program throughout all three stages of the game, we need to improve the endgame performance. Of course this is easier said than done. One needs to carefully study the differences between the middle game and endgame, the change in the roles and as a result values of the pieces, the strategies needed in the endgame, the goal and objectives in the endgame vs those of the middle game and other such factors before one can even have an attempt at tackling this issue.
I tried to do as much research as possible before starting on the project. It must be said that I had no experience in AI programming prior to this project which made it that much more challenging. I am happy, however, that I did take on this project as I learned a great deal working on it.
Below I will demonstrate all the steps taken through this project to turn it into what it is today.
Also note that this project has been written entirely c++ using Visual Studio 2013.
I tried to do as much research as possible before starting on the project. It must be said that I had no experience in AI programming prior to this project which made it that much more challenging. I am happy, however, that I did take on this project as I learned a great deal working on it.
Below I will demonstrate all the steps taken through this project to turn it into what it is today.
Also note that this project has been written entirely c++ using Visual Studio 2013.
Step 1: Creating the board and the pieces:
Before I could begin working on the chess AI and improving the endgame, I need to have a fully working chess game. The first and most fundamental step in writing a chess game is creating a chessboard complete with all the pieces. I used an 8x8 integer array to represent the board:
int board[8][8];
Now for the pieces. I used positive values for white pieces and negative values for black ones as is the common practice. Each piece needs to have a unique value so they can be represented on the board these values are especially important later on when writing the AI. I used the most commonly used relative pieces values for assigning values to the chess pieces: (Source: Wikipedia)
Pawn : 1
Knight:3
Bishop:3
Castle(Rook):5
Queen:9
The king is usually assigned a much larger value to emphasize its importance. In the code I multiplied the values by 100 to avoid fractions and make calculations easier. Also even though the values of bishop and knight are the same, I had to give one of them a slightly higher value so they can be distinguished from one another on the board.
Here is how the board looked at the end:
Note that the capital letters represent the white pieces and small letters the black pieces.
Step 2: The Rules:
After creating the board and the pieces, I needed to implement the rules of chess so neither the human player nor the program can make illegal moves. I decided to implement the rules using a function called Moves. Moves takes one argument named color which determines which side it should generate moves for. Color can only take 1 or -1 (1 for white and -1 for black). It should be mentioned that the more advanced rules like castling and en passant have not been implemented as of yet. However, promotions have been implemented as promoting pawns is an important strategy in the endgame but as of now only promotions to queen is possible. In other words underpromotions have not been implemented.
The Moves function calculates all the legal moves for the chosen side at the current position of the board and returns the result ( a list of all the legal moves) in form of a string. The function is then called when a player makes a move and the move list it generates is compared to the move made by the player to see if the moves is in the list, if so then the move is legal and is allowed to be played, otherwise the move is not made and the player is told that his or her move is illegal.
I forgot to mention that in the Moves function after the legal moves are calculated, they are checked to see if they leave the king in check and if so are discarded from the list. The function isCheck is used to investigate whether the king is in check or not; this function is called from within the Moves function.
The checkmate and stalemate conditions are checked after the players make their moves.
Step 3: The AI:
We need to have a working, efficient AI before attempting to improve its performance in the endgame stage. I researched different AI algorithms and compared their efficiency and speed before beginning the implementation. Finally I decided on a combination of negamax and alpha beta pruning.
Negamax is the negated and more efficient implementation of the minimax algorithm. Unlike minimax where positions are always evaluated from the white player's point of view, negamax evaluates from the point of view of the player whose turn it is currently to move.
Here's the pseudocode version of my implementation of the combination of these two algorithms:
int negamax (int board, int depth, int color, int alpha, int beta){
if (depth==0)
return evaluate(int color);
int max= -infinity;
for each legal moves {
make move
int x= -negamax(board, depth-1, -color, -beta, -alpha);
unmake move
if(x>max)
max=x;
if(x>alpha)
alpha=x;
if(alpha>beta)
return alpha;
}
return max;
}
The move making and unmaking is done via two separate functions in the actual code. The evaluation function takes into account the current position of the pieces on the board, the number of pieces left, and the value of each piece.
Unfortunately I didn't have enough time to implement a hash table for storing the moves and their score, instead the moves are stored in a file for now . I will add a hash table as soon as I can because it's far more efficient and time saving to work with. However in the context of MSP , the project delivered does not use a hash table.
Step 4: The Endgame:
As said before the main purpose of this project is to improve the endgame performance of the chess engine. I did a lot of research for this part of the project, I studied other open source chess engines to see the algorithms they had employed for the AI in general and endgame in particular and the strategies they had used. I also tried to learn as much as I could about the endgame and its differences from the other two stages of chess, especially the middle game. I frequented websites such as chessprogramming.wikispaces.com and http://en.wikipedia.org/wiki/Chess_endgame as well as www.thechesswebsite.com/chess-end-game/ and http://www.expert-chess-strategies.com/chess-endgame-strategy.html and others like these to familiarize myself with the concept as much as possible.
One of the things I learned was that the value of the pieces changes and it some cases drastically so in the endgame compared to the middle game. For instance, the pawn is one of the pieces that see a significant increase in importance and as a result value as the we enter the endgame. The reason for this is that much of the endgame is spent attempting to promote one's pawns to other pieces (usually the queen) in order to gain the upper hand in the game. The king also becomes much more active in the endgame and is valuable attacking piece in this stage so its attacking value increases.
The queen might see a slight decrease of its value even though it still will be a highly important piece. The castle also generally has an increase in value, the bishop's value as well increases albeit to a lesser degree while the knight might lose some power and value as a result.
This changes in the value of the pieces had to be taken into account when evaluating a position in the endgame, so as to make sure that the program makes the right 'decisions'.
Another change in the endgame is that of the objectives and as a result the strategies employed. As mentioned before, promotions play an important role in the endgame and so that's where the main focus of the player should be: getting your pawn to the 8th rank to promote it to a pieces that could be more valuable in deciding the game in your favor while preventing the opposing pawns to do the same
Also in this stage, caution has not much of a place. one must take one's pieces to the center of the board and attempt attacks on the opposing king. The castle and the queen specifically are decisive pieces in the endgame and should be in the center of every action and every attack.
I tried my best to implement this into my code.
This project has a long way to go before it can be considered as anything near completed. What I am delivering as my coursework for the MSP module is just a game demo, an indication of what this program will one day become. So please bear that in mind when judging the demo, it is not meant to be complete and it could not be in such short a time.
In the next section called 'Future Goals' I will talk about what has not been achieved so far and needs to be done in the future in order for this project to turn into a fully working chess game with a strong AI performance in all three stages of the game.
Thank You!
Sources:
1.http://en.wikipedia.org/wiki/Chess_endgame
2. https://chessprogramming.wikispaces.com/Negamax
3. https://chessprogramming.wikispaces.com/Minimax
4. http://www.expert-chess-strategies.com/chess-endgame-strategy.html
5. http://en.wikipedia.org/wiki/Computer_chess
6. https://chessprogramming.wikispaces.com/Alpha-Beta
7.http://en.wikipedia.org/wiki/Chess_piece_relative_value
8.https://chessprogramming.wikispaces.com/Point+Value
Before I could begin working on the chess AI and improving the endgame, I need to have a fully working chess game. The first and most fundamental step in writing a chess game is creating a chessboard complete with all the pieces. I used an 8x8 integer array to represent the board:
int board[8][8];
Now for the pieces. I used positive values for white pieces and negative values for black ones as is the common practice. Each piece needs to have a unique value so they can be represented on the board these values are especially important later on when writing the AI. I used the most commonly used relative pieces values for assigning values to the chess pieces: (Source: Wikipedia)
Pawn : 1
Knight:3
Bishop:3
Castle(Rook):5
Queen:9
The king is usually assigned a much larger value to emphasize its importance. In the code I multiplied the values by 100 to avoid fractions and make calculations easier. Also even though the values of bishop and knight are the same, I had to give one of them a slightly higher value so they can be distinguished from one another on the board.
Here is how the board looked at the end:
Note that the capital letters represent the white pieces and small letters the black pieces.
Step 2: The Rules:
After creating the board and the pieces, I needed to implement the rules of chess so neither the human player nor the program can make illegal moves. I decided to implement the rules using a function called Moves. Moves takes one argument named color which determines which side it should generate moves for. Color can only take 1 or -1 (1 for white and -1 for black). It should be mentioned that the more advanced rules like castling and en passant have not been implemented as of yet. However, promotions have been implemented as promoting pawns is an important strategy in the endgame but as of now only promotions to queen is possible. In other words underpromotions have not been implemented.
The Moves function calculates all the legal moves for the chosen side at the current position of the board and returns the result ( a list of all the legal moves) in form of a string. The function is then called when a player makes a move and the move list it generates is compared to the move made by the player to see if the moves is in the list, if so then the move is legal and is allowed to be played, otherwise the move is not made and the player is told that his or her move is illegal.
I forgot to mention that in the Moves function after the legal moves are calculated, they are checked to see if they leave the king in check and if so are discarded from the list. The function isCheck is used to investigate whether the king is in check or not; this function is called from within the Moves function.
The checkmate and stalemate conditions are checked after the players make their moves.
Step 3: The AI:
We need to have a working, efficient AI before attempting to improve its performance in the endgame stage. I researched different AI algorithms and compared their efficiency and speed before beginning the implementation. Finally I decided on a combination of negamax and alpha beta pruning.
Negamax is the negated and more efficient implementation of the minimax algorithm. Unlike minimax where positions are always evaluated from the white player's point of view, negamax evaluates from the point of view of the player whose turn it is currently to move.
Here's the pseudocode version of my implementation of the combination of these two algorithms:
int negamax (int board, int depth, int color, int alpha, int beta){
if (depth==0)
return evaluate(int color);
int max= -infinity;
for each legal moves {
make move
int x= -negamax(board, depth-1, -color, -beta, -alpha);
unmake move
if(x>max)
max=x;
if(x>alpha)
alpha=x;
if(alpha>beta)
return alpha;
}
return max;
}
The move making and unmaking is done via two separate functions in the actual code. The evaluation function takes into account the current position of the pieces on the board, the number of pieces left, and the value of each piece.
Unfortunately I didn't have enough time to implement a hash table for storing the moves and their score, instead the moves are stored in a file for now . I will add a hash table as soon as I can because it's far more efficient and time saving to work with. However in the context of MSP , the project delivered does not use a hash table.
Step 4: The Endgame:
As said before the main purpose of this project is to improve the endgame performance of the chess engine. I did a lot of research for this part of the project, I studied other open source chess engines to see the algorithms they had employed for the AI in general and endgame in particular and the strategies they had used. I also tried to learn as much as I could about the endgame and its differences from the other two stages of chess, especially the middle game. I frequented websites such as chessprogramming.wikispaces.com and http://en.wikipedia.org/wiki/Chess_endgame as well as www.thechesswebsite.com/chess-end-game/ and http://www.expert-chess-strategies.com/chess-endgame-strategy.html and others like these to familiarize myself with the concept as much as possible.
One of the things I learned was that the value of the pieces changes and it some cases drastically so in the endgame compared to the middle game. For instance, the pawn is one of the pieces that see a significant increase in importance and as a result value as the we enter the endgame. The reason for this is that much of the endgame is spent attempting to promote one's pawns to other pieces (usually the queen) in order to gain the upper hand in the game. The king also becomes much more active in the endgame and is valuable attacking piece in this stage so its attacking value increases.
The queen might see a slight decrease of its value even though it still will be a highly important piece. The castle also generally has an increase in value, the bishop's value as well increases albeit to a lesser degree while the knight might lose some power and value as a result.
This changes in the value of the pieces had to be taken into account when evaluating a position in the endgame, so as to make sure that the program makes the right 'decisions'.
Another change in the endgame is that of the objectives and as a result the strategies employed. As mentioned before, promotions play an important role in the endgame and so that's where the main focus of the player should be: getting your pawn to the 8th rank to promote it to a pieces that could be more valuable in deciding the game in your favor while preventing the opposing pawns to do the same
Also in this stage, caution has not much of a place. one must take one's pieces to the center of the board and attempt attacks on the opposing king. The castle and the queen specifically are decisive pieces in the endgame and should be in the center of every action and every attack.
I tried my best to implement this into my code.
This project has a long way to go before it can be considered as anything near completed. What I am delivering as my coursework for the MSP module is just a game demo, an indication of what this program will one day become. So please bear that in mind when judging the demo, it is not meant to be complete and it could not be in such short a time.
In the next section called 'Future Goals' I will talk about what has not been achieved so far and needs to be done in the future in order for this project to turn into a fully working chess game with a strong AI performance in all three stages of the game.
Thank You!
Sources:
1.http://en.wikipedia.org/wiki/Chess_endgame
2. https://chessprogramming.wikispaces.com/Negamax
3. https://chessprogramming.wikispaces.com/Minimax
4. http://www.expert-chess-strategies.com/chess-endgame-strategy.html
5. http://en.wikipedia.org/wiki/Computer_chess
6. https://chessprogramming.wikispaces.com/Alpha-Beta
7.http://en.wikipedia.org/wiki/Chess_piece_relative_value
8.https://chessprogramming.wikispaces.com/Point+Value
