This is an introduction to creating a novice-level chess opponent on the computer. It is assumed that the reader is proficient with one or more high-level computer languages (I prefer C) and understands the rules of chess. Obviously, there are many ways one could go about doing this, and this is just one of them. It's no Deep Blue, but it might be able to beat a clever six year old from time to time. With some tweaking and optimization (which I won't cover here) it could be a much stronger program. Ever been beaten at chess by your own program? It's a satisfying experience.
Data Structures
A good first step with this (or any program) is to design the data structures needed. Because a chess board has 64 squares on it, and there are 12 different types of pieces, an array of 64 bytes is sufficient to represent any particular board. A different structure may be more advantageous in terms of size or operating efficiency, but the array of 64 is simply unbeatable in the ease-of-use department. I also elected to declare a global variable which equals 0 if it's White's move, and 1 if it is Black's.
The chess pieces themselves are each represented by a single byte. It is completely arbitrary which byte value is associated with which piece.
Scoring
It's essential for the program to be able to evaluate a given board configuration and calculate two scores: White's strength, and Black's strength. Without this, the program would have no way of choosing winning moves. This can be as complicated as one cares to make it, but really, only a few scoring criteria are needed for decent results.
Material Score
First, due to their unique talents, some chess pieces are more valuable than others based on type alone. A Knight is more valuable than a Pawn, for example. Of course, that can change depending on the position of the piece in a particular game, but for starters, rank the pieces based solely on their types. (I'm sure my rankings here are a little off, but they seem to do the job.)
Rankings of the pieces:
Pawn 1 point
Knight 3 points
Bishop 3 points
Rook 5 points
Queen 9 points
King 200 points
The King is ranked the highest not because of its strength, but simply because the fate of the game depends on it.
With this knowledge in hand, it is possible to calculate the first part of our board scores. Simply sum the rankings of all of White's pieces for the white score, and Black's for the black score. (i.e. White gets 3 points for each white Bishop on the board, etc.)
Mobility Score
Mobility is the essence of a strong game of chess; The more squares accessible by a player's pieces, the more unbeatable they are. It's a good idea to quantify this principle for use in the scoring. For each piece on the board, count the number of squares accessible to it, and add this number to either the White's or Black's score depending on the piece's color. The specifics of this deterministic algorithm are left as an exercise for the lucky reader. Don't forget about capturing en passant, castling, or pawn promotion, and consider ingesting some caffeinated beverage before starting. It is helpful to encapsulate part of this into a function that returns the moves available to a specified piece on a specified board. That routine will be useful for other aspects of the program.
Other Scoring Components
Those two criteria are enough to have a workable scoring system. It might be a good idea to also have an offensive component based on how many pieces are threatened and a defensive score based on how many pieces are defended, but I haven't tried that yet. Feedback is always welcome!
The First Move
Now that the scoring component is in place, we can start to get to the fun part. With a freshly initialized board array (starting game), a tie score, and a global variable equal to zero, we can consider White's opening move. For each white piece on the board, apply your available moves function. There will be 20 possible opening moves, each resulting in a different score. A sophomoric approach might be to immediately choose the move that results in the best score. While that might be a fun exercise to try, we're hoping for a program that can play at least as well as a drunken chimpanzee, and that approach just won't cut it.
White's move needs to be based on what Black might do in subsequent moves, which depends on what White might do after that, which depends on what Black might do after that, and so on, and so on, and so on, branching out into a tree of possibilities... Which brings us to the bane of Computer Science students everywhere...
Recursion
A recursive function is a function which calls itself. Lets consider a function called int PickBestMove. It might take three parameters: char * Board, char WhosMove, and char Depth, where Board points to an array of 64 bytes which represents a board under consideration, WhosMove indicates which player is to make the next move (0 for White, or 1 for Black), and Depth is the number of moves we are looking ahead. Initially, the function is called with a starting board, 0 for the player to move, and a depth of zero. These parameters are typically stored on a finite stack in the computer's memory whenever this function is called, so all of the possibilities under consideration will very quickly fill up the available storage space unless steps are taken to limit the depth of the recursion. That is where the depth parameter comes in. It ensures that we will only be looking three moves ahead.
The function must first identify all of the moves availiable to the player specified by WhosMove, generate a hypothetical board and scores for each of these, and, if Depth is less than three, call itself for each hypothetical board, with the opponent (NOT WhosMove) to move next, and Depth+1 for the depth.
If the depth is three, we are considering an end case. At this level, find the move which results in the worst possible score for the player specified by the global variable, and return that bad score as the return value of the function. It might seem odd that we are looking for bad scores here when we are trying to win the game, but the reason will hopefully become apparent shortly.
If the depth is greater than zero but less than three, we are in a middle case. Return the lowest returnvalue of the functions called from this function.
If the depth is zero, we are at the top case. The highest returnvalue returned from the functions called from this level is the best move to choose. It is the move that had the best worst-case scenario of all of the end cases.
Update 20-Dec-2004:
Well, well, well. I learn something new every day... Some fine fine noders pointed me to a very nice clarification of this technique under Minimax. I thought I was such a trail-blazer when I thunk up my chess program. Ah well. I enjoyed reading Improving your chess game, and Alpha-Beta pruning as well.