In 1996 IBM’s Deep Blue, a chess computer, beat the world champion, Garry Kasparov. This marked the first time a computer was capable of defeating an expert chess player under normal tournament rules. However, Kasparov beat Deep Blue three times after and tied the other two games resulting in a convincing victory (Kasparov 4 points total and Deep Blue 2 points total). The following year there was a rematch and Deep Blue beat Kasparov by a point (Deep Blue 3.5 points total and Kasparov 2.5 points total) with some amount of controversy (Kasparov claimed after the tournament that Deep Blue seemed to have had human assistance during one of the games). Since then chess engines have continued to improve significantly. One of the top current chess engines, Rybka, has an estimated elo rating of 3,200 when being run on a typical PC and would easily be able to beat Deep Blue (for reference Kasparov had the highest elo rating ever documented for humans at 2,851 elo in 1999).
What makes chess engines such strong players? Their ability to assign a value of how good any particular move is by comparison to every possible move that can be played. This way of conceptualizing chess is very similar to Game Theory as whatever move happens to have the highest value will be the move the computer chooses. It is also worth noting that chess engines that can see several moves deep have a slightly modified method of choosing how to play as a move that seems good to play immediately may cause problems several moves later.
Before considerations of how an AI will chose the best move it has available a chess environment has to be programmed. The environment will keep track of the positions of all the pieces, remove pieces that have been captured, alert in-game events (checks, checkmates, promotions, and draws), and most importantly find all the possible moves that can be played. The method of finding all the possible moves that can be played depends on how the other aspects of the environment are setup. Here is a method of setting up a minimal environment:
- Board Representation: Chess is played on an 8×8 grid and is normally marked by Algebraic Notation which is a combination of letters and numbers. Using letters is not an efficient method of communicating a square’s location to an AI and so a number only system is preferred. One method is to number the squares from 0 – 63 starting from the top left with 0. The top row would be numbered 0 – 7 (left to right), the second row would be numbered 8 – 15, the third row would be numbered 16 – 23, ect.
The numbering starts from 0 instead of 1 to be more efficiently stored in memory and also allows ‘x’ and ‘y’ values for squares to be found later if necessary. The ‘x’ coordinate of a square can be found by passing its number through a modulo of 8 (8 because the board is 8 squares wide). The ‘y’ coordinate of a square can be found by dividing its number by 8 (this is assuming the square’s number is stored as an integer). For example the square numbered ’25’ would have a ‘x’ coordinate of 1 (25%8 = 1) and a ‘y’ coordinate of 3 (25/8 = 3.125 however an integer is floored to 3).
- Piece Location: Using the above system for board representation, a piece’s location can be stored as the number of the square it is currently standing on (or the ‘x’ and ‘y’ coordinates of that square if it is preferable to think that way). For example, a piece on square 5 that moves down two spaces lands on square 21 would be the same as a piece at coordinates (5, 0) that is moved by (0, 2) lands on (5, 2).
- Piece Type: Once again a numbering system has to be setup however this time to allow an AI to know what kind of a piece is on any given square. An example could be 1 = Pawn, 2 = Rook, 3 = Knight, 4 = Bishop, 5 = Queen, 6 = King. If a piece is supposed to be removed from the board because another piece captured it then its number could be set to 0 and it would not be rendered to the screen. It is important that this list of piece type information matches the order of the piece location information.
- Additional Information: There are a special conditions in chess that have to be kept track to accurately produce a list of possible moves such as castling, en passant, and promotion. I am not going to go into detail about these conditions for this article but they can be verified as a valid possible move by storing a boolean regarding whether or not their condition has been broken (for example, if either of the rooks or the king has moved the appropriate castling boolean would be set to false).
After an environment like this has been setup a list of the possible moves can be generated. This is done by running a loop that uses the information of a piece’s location and type (this is why these lists needed to match). As an example pretend that there is only one piece on the board and it is a rook on square 0 (the top left of the board). The rook would have 14 possible moves available to it which would be moving to any of the 7 squares to its right or any of the 7 squares below it. If there was another piece on the board that blocked its movement to any of these squares then those squares would not be included in the possible moves list. In a more realistic use assume it is white’s turn and none of the pieces have been removed from the board. The loop would run for each piece, find the available moves it could take, and add these moves to the possible moves list.
Here is where the design of the AI comes into play. It is up to the programmer to determine how the AI will find the best move using a game theory kind of logic. For each possible move considerations as to whether an opponents piece could be taken, a piece under the AI’s control could be protected or retreated, the pawn structure could be strengthened, ect would be evaluated. The move that best fit these kinds of ideas the programmer gives the AI would be the move that is selected from all of the possible moves. In order to make an AI that plays well future moves should also be considered. This means that for every possible move lists of responses by the opponent would be generated and also given a value using the same game theory logic. This is enough information for analysis of the best move one move deep. The process can be continued indefinitely theoretically but in practice becomes very expensive in terms of processing time and becomes quite slow even after checking only a few moves into the future. For example, if there are 30 possible moves at any given position and 30 responses an opponent could make that means 900 positions would have to be calculated. This process of searching for the best move very quickly creates an overwhelmingly large branching structure of possible future moves. To solve this problem of over-calculation modern chess engines use various techniques of “pruning” branches that score too poorly so that lists of responses are not generated for them. Another technique to avoid over-calculation is to have the best move for important positions stored in the AI’s memory.
Amazingly this kind of information is sufficient to create an expert artificial chess player. Additional concepts can be given to the AI when it is evaluating the best possible set of future moves such as as whether it can force checkmate on an opponent or what measures to take to avoid being placed in checkmate.
To see an example of this kind of logic being put to use click here (note: this AI is only looking for a best move one move deep so it is not generating future plans).
Article Written by: Alex Simes