TU Delft Algorithmics
Jan Renze Steenhuisen
Delft University of Technology Computer Chess ALG Group
EWI ALG Renze SteenhuisenComputer Chess
eng
 
 
 
 
 
 
 
 
 
 
Computer Chess
A Brief Survey

There are many resources on the internet and in the literature that address many aspects of computer chess. In order to provide a clear and (relative) short overview, this page intends to give a survey the domain.

In terms of game theory, chess is a two-player zero-sum perfect-information game. This makes it possible to perfectly define the state a certain game of chess is currently in. Additionally, the rules of chess unambiguously define the legal state transitions (moves, or actually half moves) from each legal state. The rules also clearly define when a game is won, lost, or drawn.

Provided with the rules of this game, we are now able to build a program to play chess. First, a datastructure is needed to fully represent each possible state that is at least legally reachable. Although a straightforward representation of an 8x8 board would suffice, using another representation may boost performance. Many different representations have been suggested over the years, of which we give an overview with directions for further reading (survey on board representations). Second, move generation is a topic very much related to the choice of datastructure for representing the board. Multiple issues are related to generating moves: board representation, generation speed, specialised generators, and pseudo-legal or legal moves.

Assuming we also have a function that checks whether a position is terminated (win, draw, or loss), we can now support random counterplay. However, we want to achieve stronger play than that of random play. The most natural way to achieve better performance is to look what happens when a certain sequence of moves is played. We can, for instance, select the best option after having fully considered all legal moves. This can be done recursively, because we assume that both players try to play optimal (survey on search functions). Although it would be nice to search untill decidable positions, this is often not possible within reasonable time limits. Therefore, we need to stop the search preemptively and use some heuristic value that estimates the game-theoretic value. It is difficult to evaluate a position's value correctly, but the chess literature provides descriptions of important features (survey on evaluation patterns).

Although we now have described a complete chess-playing program, we still want to let it perform better. First, an opening book can be used for the first number of moves. Such an opening book can prevent the program from making tactical mistakes in the early part of the game. Additionally, it saves much time when the program does not need to redo all calculations for positions it has already seen in the past, and which were good choices. However, the construction of an opening book is a time-consuming excercise if done by hand, but letting the construction go automatically may lead to a poor opening book (survey on opening books). Second, perfect evaluation can be in reach when the game has come close to the end. Although chess has not been solved, some relatively-small subgames have. Because these subgames have been solved, the perfect knowledge can be used by the program. However, the complete solution is very large and must remain on the harddisk and can therefore only be consulted a limited number of times per second. Using these large amounts of perfect information to apply datamining techniques, it might be possible to distill rules that form a compact representation in code. This code can now be used as a specialised evaluation function, without any loss of performance (survey on perfect evaluation).

All basics are in place, but might not be used optimal. Therefore, we would like to optimise, or tune, the multiple modules of the program for better performance. Search - pruning - extensions - reductions Move ordering (survey on heuristics). Although the chess literature provides directions on which features to reward or to penalise, often no exact numbers are provided. Moreover, many heuristics are triggered when surpassing a certain threshold. These thresholds are commonly estimated in the literature, but empirical evidence has shown that optimal values are strongly program depend. For these reasons, parameters should be learned by experience of the program itself (survey on machine learning).

Finally, we want to stress that many has already been done in the field of computer chess. As a result, many standards (many already overlapping) exist, of which some are broadly supported. We advice to provide build-in support for the most important ones, because it is easier for you and others equally (survey on standards).

Board representations'); item('Search functions'); item('Evaluation patterns'); item('Opening books'); item('Perfect evaluation'); item('Heuristics'); item('Machine learning'); item('Standards'); # item('Perft results'); #item(''); end_data(); end_rhs(); page_footer(); ?>