Opening Books
Whether you like it or not, opening books are very important in many games. Some games already have a large body of theory produced by humans (e.g. chess, checkers), for other games, particularly for relatively new or less popular games, there is nothing to go on. For those games where humans are competitive (like in chess), there is a simple approach to generating an opening book: produce it manually, selecting moves played by strong players. This type of approach is obivously not very interesting for our purposes, and for games where there is no theory or where computers are already superior to humans (like checkers), it is impossible or pointless. I will only look at approaches to generating books without manual intervention.Automated generation from a database
A simple way to generate an opening book is to take a database of games, and select promising moves based on the results of games in that database. The opening book of my chess program was generated like this, and many chess programmers use this technique. For chess, high-quality databases are available, with ratings of the players included, so you can decide to emulate the high-rated players only. For every position, statistics for all moves can be generated, such as the score it made, the average rating of the players playing this move, the average performance rating resulting from this move, or the difference between the performance rating and the player rating which might be the best measure for the quality of the move. Often, games are commented with symbols like ! (for good move) or !! (for excellent move), and it might be worth parsing such comments too. I don't know whether anybody is actually doing this. The book of my chess program was based on statistics only, playing the move with the highest player rating.Automated computation by drop-out expansion
If there is no human theory available, then you will have to compute an opening book with your program itself. Any method of computing an opening book automatically needs a graph representation of the game tree, with each node of the graph being a position. For each position, you need to compute the value of all possible moves, so that you know which moves are candidates for expansion. Along with this graph representation you need a method to select which node you will expand next - i.e. which final position in your graph will be added as a new full node. The method of choice here is called drop-out expansion (DOE), an invention of Thomas Lincke. The basic idea of DOE is that you want to build a book where you drop out of book as late as possible. A simple scheme of building an opening book would select the some of the best moves for each position to expand, and continue from there - always selecting a few moves (e.g. a fixed number, or all moves within a certain evaluation difference to the best move) to expand from the currently expanded moves. However, this scheme is no good as it will generate irrelevant positions: The book player will always only play the best move in the book, while the opponent might make mistakes (Note that of course the mistakes might be good moves, they just appear to be mistakes to the book generator). Therefore, the book generator should only generate lines where one side makes best moves, while the other side can play best or inferior moves. A DOE generator needs a graph representation of the book, the evaluation of all successor moves of every node in the book. Then, it needs a priority function, which gets called for all possible paths (under the DOE restriction, i.e. one player is playing best moves only) in the book tree and gives this path an expansion priority. The final node in the path with the highest priority will get expanded next. This scheme lends itself to massive parallel computation, if you have a cluster of machines available, you can have the DOE generator run on a master machine, and have multiple slaves do the actual computation of the values of the positions. The priority computation of a path is rather arbitrary, you will probably want to use something basic like
delta = sum_of_errors(path);
depth = length(path);
priority = - delta - CONST*depth;
This priority function will search lines with optimal play more deeply than lines where the opponent makes errors. You can also include other terms in the priority calculation - for example, you might include some measure of criticality of a node, Thomas Lincke used the conspiracy number in his priority function, I use a measure of singularity of a node, i.e. the difference between best and second best move to expand forced lines more deeply.
DOE in the real world
DOE is a relatively new technique and has been applied successfully to checkers (by Ed Gilbert and me) and Awari (by Thomas Lincke). My DOE generator for checkers has been running for nearly 2 years now on a single machine, and the result is extremely good - in checkers, there is human theory to compare with, and the book generated automatically has virtually no errors at all any more (after computing for about 1.5 years on a fast PC), and probably corrects human theory in all places where it is at fault. I'm writing virtually because there are no errors left that I currently know of, but of course there might be some bad moves hidden in the millions of moves that are in that book by now. Half a year ago, Ed Gilbert and I had our checkers engines play a match over 624 games, my program Cake won with 3 wins vs 1, the remaining 620 games were drawn - the highest-ever drawing percentage in such a match! This match uncovered a single problem in my opening book, which is fixed by now.Comments and questions are welcome!
Last update: 5th May 2005, using 