This is a chess project I created for my artificial intelligence class. The program is capable of playing through a full game of chess. The human player takes the side of white, and the computer will respond with black's moves. The game can look an arbitrary number of moves (plies) into the future to select the best move. It uses four plies by default and takes between 10 and 90 seconds to make a move depending on the complexity of the current position. The game is written in C++ using SDL for graphics, and there are versions available for Windows and Linux.
Each state represents a single position of the board. Each state is linked to two other states: the next possible move on the current ply, and a state that represents the beginning of a list of all the possible moves the other player can make in response to that position. Together, these states form a game tree that can be searched to find the best state within a certain number of plies and determine which move is necessary to get to that state.
A rating system is used to compare states. It is based off of the generally accepted relative values of the pieces: pawn=100, bishop=300, knight=300, rook=500, and queen=900. The king has a value of 400 for its attack and defense capabilities, but cannot be captured. As moves are generated, an array is created that keeps track of which spaces are threatened by each piece. This array is used to determine whether each piece is threatened, defended, or neutral.
To determine how to modify each piece's value I began with a few guesses, and then played over and over, tweaking the system to make it select better moves. I eventually settled on the following system. A threatened piece is only worth 20% of its value, while a defended piece is worth 30% more. A piece in the center is worth 20% more. A pawn gets 50 points for each row it advances, and pawns are only reduced to 40% if they are threatened. Black's pieces are valued positively and white's are valued negatively. A state's final score is the sum of all of the values of the pieces of both players. If a state represents checkmate, it is given an arbitrarily high or low value, depending on the player.
To select a move, the computer player begins with the current state of the board, where it is assumed that white has made the last move. It generates all of the possible moves for that position. The function runs again on each of those states, generating the possible moves for white. This continues until it reaches the designated ply, where the states are rated. After ratings have been generated, they are passed back up the tree. On each level, the highest or lowest ranked state is selected, depending on which side's turn it is. Black wants higher ratings and white favors lower ratings. Eventually this process reaches the current state, and a move has been selected.
Looking ahead n plies requires searching approximately 35^n states. To prevent the program from running out of memory, one branch of the game tree is searched all the way to the bottom and then deleted before moving on to the next. On the second to last ply, a pruning system prevents any move that is not better than the current best move from being added to the game tree. This does not degrade move selection because only the best move matters on the final ply, and it significantly increases the speed.
The game performs fairly well. It tends to be better at defensive than offensive moves, but it will usually take an opportunity to attack when one exists. As it turned out, the rating and selection system was more powerful than I originally expected. In my original proposal I thought I would need to encourage the use of chess tactics such as forks and pins. I was pleased to discover that, because these positions either lead to less available moves or to more valuable moves, the selection algorithm already favors them as long as the benefits are within the number of plies it is searching.
Download with source for Linux or Windows.
|