Evaluation

Both Shannon Type A and Type B programs rely heavily on an evaluation function. In Type B programs, the evaluation function has to encode sufficient "knowledge" about the game to make good move decisions without performing extensive search. In complex games like chess, the required volume of knowledge and exceptions to general principles have historically limited the performance of Type B programs.

In Type A programs, the search explores many lines of play and assigns values to them based on the evaluation function. The tree search algorithm uses these scores to estimate how good or bad individual moves are, and the program then makes the best available move. As with move generation, it is important that evaluation be accurate; however, there is usually some compromise to be made between accuracy of the evaluation (heuristics) and performance.

Evaluation functions assess the score of a position in terms of material (the number and value of pieces on the board) and positional considerations (the structure of the position). As such, the evaluation is a weighted sum of terms, each term corresponding to some aspect of the game. In chess, for instance, terms would include material (with pawn=1, knight=bishop=3, rook=5, queen=9), centre control, doubled pawns, rooks on open files, castle/uncastled and so forth. Determining which terms to include in your evaluation, and how to weight them, will have tremendous impact on the performance of your game. There are many thousands of books and Internet sites which you can consult to get an idea of possible terms, but you will have to limit the amount of knowledge you encode in order to retain reasonable speed.

Some work has been done toward automatically improving evaluation functions. Some of the approaches have included neural networks "learning" evaluations, genetic algorithms adjusting the weight of various terms, manual massaging of terms, and automatically adjusting the terms by least-squares regression analysis to try and get the evaluation to follow grandmaster games.