KKFChess creates opening books from PGN files. It is a statistical base process that is based on how often a position has appeared in a won, lost or drawn game. By using special postfixes, one can alter this statistic by faking that a position (after making the "marked" move) had appeared in a huge number of games hence raising it's statistical importance.
Opening book generation in KKFChess is in-memory so it can use a lot of memory. However, smaller books can be merged together so it is possible make a huge opening book with limited amount of memory.
The stages of opening book generations are:
PGN game parsing
Position sorting
Statistics merging
Book file creation
Index file creation
The PGN parser is responsible for reading moves, tags and comments within a PGN formatted game. It also handles any FEN string that is present is the "FEN" tag and sets up the position accordingly. If no "FEN" tag is present, it is assumed that the game starts at the initial position.
This parser is used extensively for loading PGN games and other PGN based commands.
Each position that arises after make a move is noted and it's hash key and game result stored as individual records. This is where most of the memory is used.
After all games have been read in, the stored positions are sorted according to their hash key values. A merging process now takes place and statistics of the same hash keys are merged (summed) into single records, each with a unique key.
The merged records are simply written to disk as an opening book file, together with version and checksum information.
This optional step scans the keys stored in the opening book and creates an index file for quicker reference. This index file also has a version and checksum but the checksum is the same as the book file it was created from to link the opening book file to its index file.
Opening book probing is simply looking up the correct record with a given key. It is done differently, depending on the presence or absence of an index file.
When an index file is present, a binary search is made to locate the key just before or equal to the desired one. The read is then directed to start at this location in the book file and records read until a matching one is found.
Without an index file, a similar binary search is performed but on the opening book file itself.
Book statistics can be displayed in two ways in KKFChess - by popularity of play or by win/lose ratios. The former is based on the number of games the position had appeared in and the latter is based on the number of won/lost games a position has appeared in. With the win/lose ratio display, a lower an upper limit can be used to indicate a very good or very bad move, e.g. >90% winning chance means the position is almost a certain win, hence the move that leads to this position is an excellent move.
V2.6.1 has an user settable option that allows the search routines to look into opening book statistics and decide if it is worth expanding the nodes or not. Currently implementation only recognizes postfixed moves (moves marked with "!" or "?") and returns a very high or very low score respectively. Later implementation will be more sophisticated.
KKFChess does not support book learning at present but it can be simulated by manual means by creating or merging games that the program played into the opening book. Future releases may incorporate book learning.