A chess program consists of 3 parts:
a.) Move generator: Generates all possible moves in a given position
b.) Search function: Looks at all possible moves and replies and try to find the best continuation.
c.) Position evaluator. Gives a score to a position. It consists of a material score (pawn=100; knight=300 etc.) and a positional score (safe king=20; pawn in center=10; etc.) If the king is in checkmate, the score is very high, say 100000.
When the computer has to make a move, it does the following:
a.) Generate all possible moves.
b.) Make one of the moves (a root move)
c.) Generate all the replies of the opponent
d.) Make one of the moves of the opponent (the computer is now “thinking” 2 plies deep)
e.) Evaluate the resulting position and remember the score
f.) Unmake the move of the opponent and try another move
g.) Evaluate the position and if the score is better for the opponent (worse for us), remember the new score
h.) Repeat (f) and (g) until all replies have been looked at
i.) Now unmake the root move and give that move the best score for the opponent (worst for computer.)
j.) Make another root move and repeat (d) to (i)
k.) If the computer has looked at all root moves, it will play the root move with the best score for him (worst for opponent)
What I have just described is a simple 2 ply minimax search. The same process can be used to search deeper (make move [root move], make opponent move [ply 2], make move [ply 3], make opponent move [ply 4] etc.)
There are a lot of techniques that programmers use to make programs play better; I will briefly describe some of them.
Quiescent search
A program must always aim to end its search in quiet positions (e.g. positions with no captures) If a program doesn’t use quiescent search and the last move of its search is a queen capturing a knight, the program will think it is a good line (it wins a knight) and try to play it. It doesn’t take into account that the knight may be defended and thus his queen could also be captured! The same program with quiescent search would search all captures exhaustively and would then see that the queen could be recaptured and that it is actually a bad move!
Iterative deepening
When a program using iterative deepening is thinking, it doesn’t start its search with the maximum search depth. Instead it first searches only 2-ply deep. When the 2-ply search is finished, it increases the depth to 3-ply then 4-ply etc. This process will go on until either the time it allocated for that move is up or until it found a sufficiently good move (like checkmate.) The main reason programs use iterative deepening is because they don’t know how long a search with a fixed depth will take. If they start with say a 10-ply search and their time is finished before all the moves are looked at, they could easily miss the best move (it might even be a mate in 1!) With iterative deepening however, you always have the results of the previous search depth. If the program is forced to make a move and it hasn’t finished the current search, it just uses the results of the previous search depth – in which all the moves were tried.
Opening Books
You might have noticed that almost all chess programs make the first few moves instantaneous. The reason is that it uses an opening book with a lot of moves preprogrammed into it. Because all games begin the same way, the computer doesn’t have to think about the first few moves – it can just look it up in its opening book. As long as the opponent makes a move that is programmed in the book, the program can look up the best reply and make it instantaneously. Sometimes chess players use strange openings against computers to keep them from using their huge opening books and thus have an unfair advantage (chess players can also use strange openings against other players, but then it is more for psychological reasons – a tactic that is similar to a poker bluff.). Luckily an opening book is not all bad for us humans; it also helps the computer to play more variations and thus not always the same boring opening!
Endgame databases
Endgame databases work a lot like opening books. Some simple endgames (e.g. Pawn and King against King) have been exhaustively analysed by computers and the results (best moves) stored in a database. When a program reaches one of the endings in its database, it can just look up the best move and play such endings perfectly.
Hash Tables (Transposition tables)
Hash tables are used to store positions that you have searched earlier so that you don’t have to look at them again. A typical hash table will contain the following:
A Key: this is unique to each entry and is related to the position (Zobrist keys work well in chess – look it up!)
Score: The score for the position
Depth:The depth searched
Now, the bigger the hash table of your program, the more information will be reused and thus the better your program will be. You might think that with a big hash table it takes longer to retrieve the information than with a small hash table, but that is not so. The information is not stored chronologically, but is indexed by means of the key. Say your hash size is 1000 entries and your Key=11245. An easy way would be to store the key in the following memory position: 11245 modulo 1000 = 245. So if you have a position with a key of 11245, you know the hash entry would be stored in memory position: 11245 modulo 1000 = 245. Of course if your key is 1245, it would also be stored in memory position 245 (1245 modulo 1000 = 245) and we say a collision occurred. To make sure that you are looking at the correct data, you always have to compare the key’s. If they are not the same you cannot use the data, because it is for another position.