Creating Book Knowledge:
Author: Jeff Rollason

Copyright Notice: This article is Copyright AI Factory Ltd. Ideas and code belonging to AI Factory may only be used with the direct written permission of AI Factory Ltd.

Games-playing programs are commonly designed to have a library of knowledge that can be referenced for making moves during opening and endgame play. This allows programs to take advantage of known standard theory, rather than having to re-calculate this. In a previous article a type of opening book was described in "Fuzzy books - Approximate opening knowledge". That dealt with book knowledge that provided some explicit exact moves, but also provided approximate advice. A further previous article "Playing Stronger by Learning" used a self-created book where the game program learned moves and performed a minimax on the "book" knowledge created. This article deals with taking a resource of book knowledge and converting it to a program-accessible book. This process also allows such a book to be used for learning.

Building Book Knowledge

In times gone past in computer games, opening books were created by hand, but nowadays this is usually automated. A problem is not just having a wide range of book moves available to play, but being able select which lines are best . A book creation program needs to not just record a move, but also provide a means of weighting its value.

Using Hash Table for Books

This is pretty well inevitable: The best way to store book knowledge is to use a hash table. Trying instead to simply store lines of moves is inflexible, as moves might crossover with other book lines, or moves might be played out of order. A book that stores lines of moves cannot easily accommodate this. A hash book however can allow lines of play to overlap so that a program can transpose into another line.

Hash works by creating a signature for a position using exclusive-or (XOR) of moves. If you play a move, then the signature is XORed with a unique bitmap for that piece moving from that square and again XORed with another unique bitmap for the square played to. If a piece is captured then the bitmap for that piece on that square is again XORed into the signature. This scheme is attractive as the signature can be restored by simply repeating the same bitmap operations. Therefore a whole sequence of moves can be played, but the position restored by simply repeating the entire move sequence.

To support this the program must have a table for each piece for every square on the board. For example in chess this would need a table of bitmaps, as follows:

( 12 different piece types ) x ( 64 different squares )

Each of these bitmaps would have to be unique (not hard to do).

Added to this is a special bitmap called "side to move", which must be XORed when a move is played. If this is not done then a board configuration might be reached with all the pieces in the same position, but a different side to move. This definitely needs to be counted as a different position!

Basic Hash Mechanics

There are some basic mechanisms intrinsic to hash tables. The general principle is that part of the hash signature is used to create an index into the hash table, while the remainder of the signature is stored in the table. Since this index is generally much smaller than the value of the signature, this results in likely clashes when storing in the table, as multiple signatures share the same index. The practical way of dealing with this is to scan from that index looking for an empty table entry. For example the current and following 7 indexed entries. These 8 entries can be scanned for a free slot.

To use the hash table, the program generates a list of legal moves and then tries each move and checks if the resulting signature is in the book hash table. If it is, then that move was a book move.

A key point here is that the book does not actually contain any moves, but just positions! The right "book move" is the move that reaches a position recorded in the book.

Choosing a Source of Data

From the earlier comments, crafting a large book entirely by hand is not practical. Long hours spent hand-coding from some game text is not productive. The obvious choice it to take electronic records of game played by strong players. As it happens these are increasingly easy to come by. For our Chess program we purchased a commercial archive of professional games, using the common PGN book format.

Choosing information to Store

The purpose of having a book is for the program to choose a known move to play. However a particular position may have several known "good" moves. When the moves list is scanned, then the user may find that several booked positions can be reached. Some of these may be positions where the next side to play will win. Clearly these need to be identified. There are various options:

1. Simply store TRUE or FALSE for side to move won or lost the game
2. Count the number of times than position lead to a win and to a loss

Solution (1) will let you distinguish between won and lost games, but still does not let you know which move you might play. Also one player might have won from that position whereas another player lost. You also need to distinguish between positions which might have been reached in thousands of won games whereas another might be a single win.

Clearly you need to store the number of wins and losses associated with that position. You can then choose moves that have a larger proportion of wins to losses is the total volume: 700 wins and 300 losses would probably be a better choice than 8 wins and 2 losses, simply because the result is more proven and that position would lead on to more follow-on moves.

For practical terms the program may need to add a random element to provide some variety of play, and allow uncommon lines to be occasionally played.

Using this for Tuning

A point made in an earlier article is that a library of perfect games may suit the program very badly. A common problem is that the book may be left and the program does not like the position. The program then spends its time re-arranging the pieces and losing the advantage in doing so. Playing book lines to positions the program does not like is pointless. However it may not be easy to know which lines are good and which are bad.

The easy solution is to let the program play many games using the book. When it loses, then the book can be adjusted to reduce the chance of that same line being played. This can be by scaling the win and loss counts. E.g. the win count can be multiplied by 80% and losses by 120%. This will gradually skew the book to provide positions the program can deal with. This needs to be depth sensitive. A move deep into the game needs to be heavily adjusted, whereas moves at the start should be marginally adjusted.

Note that the program might like to play moves that are actually not considered good book moves. While learning, the program should be allowed to sometimes reject all moves and simply try something different. In doing so it might find a line that is outside human knowledge that it does very well with.

After a long series of games the book will gradually turn into one that the program works well with, but can still have some option to play lines it likes less well.

Conclusion

This is an attractive procedure as it is easy to do and allows the program to do all the hard work of managing. The book database can be created and the program left to tune it. This might take weeks, but the end product is a book that it would be very hard to create by other means.

Jeff Rollason: December 2007