Game playing programs commonly include libraries for opening and endgame play. The latter has the advantage of precision, as endgame knowledge is often exact, providing moves that are classified as win, loss or draw. Opening knowledge is usually less clear and more heuristic in nature. However opening books are generally necessary as, unlike in middlegame positions, the start of many games is typically very open and unstructured. This makes it hard for an evaluation to select suitable moves, as many moves will be plausible. Absence of an opening book also fails to exploit the existing knowledge base already established for that game.
There are many approaches to this problem, but here are a few common techniques:
(1) Expert game libraries
Here the programmer creates a library from thousands of games from expert play. Of course different experts play different lines, so you need a means of distinguishing which line to play. This can be achieved by counting which lines win more often and choosing these. This can be modified by automated learning (see Playing Stronger by Learning), to update the opening knowledge in response to actual games played.
(2) Hand crafted opening lines
An expert with a good understanding of the program can hand-craft special opening lines to best use the skills of the program. This is an uncertain science, relying on a keen insight into the program’s capabilities.
(3) Let the program write its own book
This technique was championed by Ken Thompson with the chess program “Belle”. Belle played thousands of games with large time limits to create its own opening book. This was started with a basic book and the program allowed to develop its own opening library.
All the methods above provide a book that will deliver a move in the opening. However you are generally either “in the book” or “out of the book”. As soon as the opening book has no move, the program has to fend for itself.
In practice this highlights many potential problems. A book constructed using method (1) above, with no other tuning, can show undesirable side-effects. A common scenario is that a book takes the program down a carefully crafted path to a well-balanced position. However when the book is left, the program does not understand the position and spends the next few moves re-arranging the pieces to one it does like. The advantage is lost and, as a consequence the position may now be inferior, and even losing.
This can be alleviated by (2) above, choosing lines that the program understands, but this is still a bit hit-and-miss. It is hard to arrange it for the program to be comfortable with the position regardless of the moment that the book is left.
A further amendment to the strategy above is to combine a well-prepared book with added variations to cover deviations from the lines in the book. This can be achieved by analysing the book and anticipating alternative moves outside the book and analysing these for replies. The analysed new moves added to the book can be generated after extended long think times, to take advantage of this once-only advance move choice. This, of course, could very substantially increase the book size and take a long time to create. However large book sizes are not a significant problem, given the storage capacity of modern machines, and this analysis can also be automated and left running continuously, including overnight, so requires limited human intervention.
No matter what you do to process the book above, using the techniques described, the program is still faced with the problem that it will have to switch from the book making a 100% contribution to move selection, down to 0%, as play deviates from the book.
This is where Shotest has taken another approach to using book knowledge. Shotest normally employs a conventional book, but also uses another approximate opening component (the "Fuzzy Book"), to help move selection. This Fuzzy Book was designed originally to compensate for a properly crafted book and later on as a means of assisting in the creation of a conventional book. At this year's World Championship Shotest was experimentally entered with no conventional book at all, but just its Fuzzy Book.
The Operation of the Fuzzy Book
Shotest has a series of limited game scores from professional games, which is combined with its own successfully won games, to create a Fuzzy Book. This works by comparing the moves played so far with the moves in the game stored in the book to measure how similar the game is to each book game. If the game is similar, then the next two unplayed moves from the recorded score are candidates for selection, with the first move with higher priority. The score attached to the move depends on the degree of similarity of the game score, in terms of the number of matching moves. Many game scores may match to predict the same move to play, in which case the move gets added credit.
To use this, a variation analysed that starts with one of these credited moves has the evaluation modified to reflect this added value. Therefore the program is encouraged to choose moves from the book in similar positions. This provides a combined value derived from the book and the evaluation. When both the evaluation and book like a move, it is much more likely to be selected. A move the evaluation does not like, but that the book recommends, may still get played.
The consequence of this is that the book is not suddenly exited, if play deviates from a known exact position in the book. An unexpected move will not stop the normal follow-on moves from such a variation from being made available to contribute to evaluation. All that happens is that the matches gradually weaken. The book spots and predicts likely follow-on moves in the current position from examining what was played in similar games.
This assessment also can match moves with varying move ordering. This acts as a kind of transposition assessment, so that the program can later transpose back into a variation that it initially had given a poor match to.
The Fuzzy Book in play
The following game score is a demonstration of the Fuzzy book in operation. This is a game between Shotest and the current 2006 World champion “Bonanza”. It was played on two similar PCs, with Bonanza running on slightly slower hardware than it was using in the 2006 World Championship.
Bonanza was using a 2500k book, compared to the 120k Fuzzy book used by Shotest. However Bonanza runs out of book knowledge more quickly, and eventually loses. Although Shotest wins this game, head to head. Shotest generally only scores about 20% against Bonanza, without any tuning against Bonanza.
The game score below shows the top 6 suggested moves that the Fuzzy book recommendations, after randomisation, and for both sides. In the tabulated results below each book entry the table lists:
1. The move (preceded by "*" if an exact variation match)
2. Value of move (this is also randomised)
3. Number of lines matched
4. Number of lines exactly matched
5. Variation game name/number with closest match
The actual move played is shown in bold, with the Shotest evaluation and the time for the move in seconds (rounded up to a minimum of one second). Bonanza moves are shown with value zero, as the value is not known.
The Game - Shotest vs Bonanza
From the opening position we can see the following matched moves from the Fuzzy book
From this you can see that the Fuzzy Book has many lines starting with p7g-7f
and P2g-2f, with 982 and 446 matching lines, and in this case P2g-2f is chosen.
Note that S3i-4h is rated above P5g-5f, although it has less matches. This
is because of the added random component. Note this list only shows the top
|1.||P 2g-2f||-10||1||(value –10, and 1 second)|
The values below now consider Bonanza's replies. After randomisation, Shotest
|2.||P 3c-3d||0||1||- - - - - - - - - -: K 5a-4b ?|
For this following move by Shotest, the top move is P5g-5f, although S7i-6h has many more matches, but actually the 3rd choice P2f-2e is chosen, as the Shotest evaluation favours this move.
Shotest here plays the 2nd choice move from the book
Again the most popular lines are further down the list due to randomisation. Note that this list includes the illegal move R2h-6h, which is only made illegal by the blocking Silver. However there is no need to weed this move out, as it cannot anyway be matched.
The number of matching options for Bonanza is now reduced to just 4 moves,
and Bonanza's choice is not on the list. However this does not take Shotest
In this move Shotest chooses a move that is not on the list of book moves,
as the evaluation for P9g-9f exceeds the book move values added to the evaluation.
However this too does not take Shotest out-of-book.
Again no match for the Bonanza move, but this is a critical move, as Bonanza
is now out-of-book, and no longer is able to make use of its own book (although
this is theoretically possible, through transposition). Bonanza will now have
to rely on evaluation.
|10.||S 3a-4b||0||4||Bonanza takes 4 seconds|
Shotest continues with advice from the book, choosing a suggested book move.
Shotest continues to take book suggestions.
Note the illegal move B8h-3c+, which would be possible without P4c-4d.
At last Shotest runs out of book moves, at move 27, whereas Bonanza ran out of book at move 10. Shotest chose 11 moves from the book and 2 where it overrode the book choice. Shotest likes this position, although it may not actually be better.
(no matching moves from Fuzzy book for Shotest)
This move seems suspect, allowing Shotest to promote the bishop on 3a.
|46.||P * 5f||0||6|
|57.||P * 5g||-105||17|
Shotest is not happy after playing P*5g, as Bonanza has some pressure here. Shotest expects B 5ex4f followed by G 5h-4h.
|59.||N * 4i||-262||13|
Shotest switches to N*4i and believes it is ahead. From now on Shotest’s position continuously improves.
|62.||P * 9h||0||6|
|71.||S * 7e||740||10|
|76.||P * 4f||0||4|
|78.||S * 8i||0||4|
|81.||S * 8h||1199||6|
|82.||S * 8f||0||6|
|88.||N * 8e||0||6|
|92.||P * 3f||0||6|
|96.||S * 3f||0||5|
|97.||S * 4h||1482||11|
|100.||N * 3f||0||5|
|105.||P * 8f||-1713||31|
|108.||P * 5f||0||6|
|112.||S * 5h||0||6|
|116.||G * 4f||0||6|
|117.||P * 5h||1896||11|
|123.||B * 5e||1974||24|
|124.||P * 7c||0||6|
|128.||N * 4e||0||6|
|136.||P * 9g||0||4|
|142.||L * 9b||0||6|
|143.||P * 9d||2377||24|
|144.||P * 9f||0||6|
|148.||P * 9c||0||6|
|151.||N * 8e||3092||25|
Shotest finds that the following move S 6dx7c+ gives a forced mate in 15 moves. However Shotest chooses some non-optimum path to mate, and takes 27 moves. This is a spurious fault in Shotest, but does not avoid the inevitable win.
|160.||S * 8b||0||1|
|165.||S * 9a||9990||1|
|169.||G * 8b||9994||1|
|171.||G * 7c||9986||4|
|175.||S * 7c||9990||1|
|179.||S * 7c||9994||1|
|181.||R * 8b||9996||1|
|183.||L * 9b||9998||1|
This mechanism showed that it could perform quite well against the worlds’s strongest Shogi program. However it may not be an optimum choice on its own. The highest level of play will expect to play many exact variations, which this type of book will not guarantee to follow.
However such a book is probably invaluable to take over once the exact book has been left. The program will then provide approximate suggestions that match similar games.
This also has implication for book creation. This Fuzzy Book was used to create Shotest’s own main book, when the program was short of any opening know-how. It allows the program to generate its own opening variations that were similar to known theory and these were tested in block runs against known strong programs. This allowed Shotest to win its first 3 encounters with the World Champion YSS, an unprecedented run against such a strong program. Shotest had used its fuzzy book to learn how to beat YSS.
The next generation of Shotest, to enter the World Championship in 2007, will use such techniques to prepare against the new generation of very strong Shogi programs.
Jeff Rollason: June 2006