Fuzzy books - Approximate opening knowledge:
Author: Jeff Rollason



AI Factory has its own developed Shogi (Japanese Chess) program "Shotest" that regularly competes in the World Championship that is held in Japan every year. This article discusses the unusual book system that this program employs to choose opening moves in the game.

Opening Books

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.

Drawbacks

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.

Another Approach

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

Move
1. P7g-7f 154: 982: 645; SWX#01B For Shotest
2. P2g-2f 153: 446: 0; YV9#39W
3. S3i-4h 132: 8: 0; IQ4#37W
4. P5g-5f 108: 252: 0; IQ4#450W
5. R2h-6h 80: 28: 0; YQB#241B
6. P1g-1f 72: 6: 0; IQ4#34W

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 6 matches

1. P 2g-2f -10 1 (value –10, and 1 second)

The values below now consider Bonanza's replies. After randomisation, Shotest expects P8c-8d.

* 1. P8c-8d 255: 816: 125; SWX#01W For Bonanza
* 2. P5c-5d 125: 19: 2; SVW#24W
3. P3c-3d 84: 745: 0; YV9#26W
4. P7c-7d 72: 1: 0; YQB#217B
5. P1c-1d 60: 57: 0; YQ4#531B
6. G4a-3b 36: 6: 0; YTY#73B
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.

1. P5g-5f 98: 25: 0; IQ4#450W For Shotest
2. S7i-6h 90: 357: 0; YV7#07B
3. P2f-2e 88: 32: 0; YV9#39W
4. P1g-1f 84: 6: 0; IQ4#34W
5. P6g-6f 60: 6: 0; YTW#82B
6. R2h-6h 48: 28: 0; YQB#241B
3. P 2f-2e 20 1


1. P5c-5d 126: 19: 0; SVW#24W For Bonanza
2. P8c-8d 102: 804: 0; YV9#39W
3. P4c-4d 48: 134: 0; YUR#909B
4. S7a-6b 42: 9: 0; SXB#705B
5. B2b-3c 40: 21: 0; YTQ#11B
6. P3d-3e 32: 11: 0; SQJ#50B
4. B 2b-3c 0 1

Shotest here plays the 2nd choice move from the book

1. S7i-6h 60: 340: 0; YV7#07B For Shotest
2. S3i-4h 56: 8: 0; IQ4#37W
3. P1g-1f 48: 4: 0; IQ4#34W
4. P6g-6f 48: 4: 0; YTW#82B
5. R2h-6h 36: 12: 0; YQB#241B
6. R2h-7h 24: 2: 0; SQB#708W
5. S 3i-4h 13 1


1. P5c-5d 46: 11: 0; SVW#24W For Bonanza
2. P8c-8d 44: 712: 0; YV9#39W
3. P7c-7d 32: 1: 0; YQB#217B
4. R8b-2b 24: 8: 0; SQJ#51B
5. S3a-2b 18: 1: 0; YTQ#11B
6. G4a-3b 8: 4: 0; YTW#82B
6. R 8b-2b 0 1

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.

1. P1g-1f 56: 4: 0; IQ4#34W For Shotest
2. R2h-6h 56: 8: 0; YQB#241B
3. P7g-7f 40: 806: 0; YV9#26W
4. S7i-6h 40: 316: 0; YV7#07B
5. P6g-6f 40: 4: 0; YTW#82B
6. P5g-5f 32: 6: 0; IQ4#450W
7. P 1g-1f 34 1

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 out-of-book.

1. P8c-8d 108: 590: 0; YV9#39W For Bonanza
2. K5a-4b 42: 6: 0; IQ4#450W
3. P7c-7d 30: 1: 0; YQB#217B
4. P1c-1d 18: 1: 0; YQ4#531B
8. K 5a-6b 0 1

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.

1. P7g-7f 80: 746: 0; YV7#07B For Shotest
2. P6g-6f 56: 4: 0; YTW#82B
3. S7i-6h 48: 316: 0; YV7#07B
4. R2h-6h 24: 8: 0; YQB#241B
5. P5g-5f 6: 6: 0; IQ4#450W
9. P 9g-9f 100 1


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.

1. P8c-8d 98: 555: 0; YV9#39W For Bonanza
2. P5c-5d 42: 11: 0; SVW#24W
3. G4a-3b 18: 4: 0; YTW#82B
4. P7c-7d 12: 1: 0; YQB#217B
5. P1c-1d 6: 1: 0; YQ4#531B
10. S 3a-4b 0 4 Bonanza takes 4 seconds

Shotest continues with advice from the book, choosing a suggested book move.

1. R2h-6h 48: 8: 0; YQB#241B For Shotest
2. P5g-5f 36: 6: 0; IQ4#450W
3. S7i-6h 32: 283: 0; YV7#07B
4. P7g-7f 24: 746: 0; YV7#07B
5. K51-6h 16: 4: 0; YTW#82B
11. K 5i-6h 143 1

1. P5c-5d 60: 11: 0; SVW#24W For Bonanza
2. P1c-1d 12: 1: 0; YQ4#531B
12. K 6b-7b 0 5

1. P7g-7f 84: 746: 0; YV7#07B For Shotest
2. P6g-6f 56: 2: 0; YTW#82B
3. P5g-5 36: 6: 0; IQ4#450W
13. K 6h-7h 95 3

1. P5c-5d 42: 9: 0; YQB#241B For Bonanza
2. P7c-7d 36: 2: 0; YQB#217B
3. G4a-3b 36: 2: 0; YTW#82B
4. P8c-8d 30: 469: 0; YV9#39W
5. P1c-1d 30: 1: 0; YQ4#531B
14. K 7b-8b 0 5

1. P7g-7f 48: 6695: 0; YV7#07B For Shotest
2. P5g-5f 36: 1: 0; IQ4#450W
3. S7i-6h 24: 22: 0; SXB#924B
4. G4i-5h 24: 22: 0; YTW#104B
15. G 4i-5h 98 3

1. P8c-8d 50: 252: 0; YV9#39W For Bonanza
2. P5c-5d 30: 8: 0; SVW#24W
16. L 9a-9b 0 6

Shotest continues to take book suggestions.

1. P7g-7f 32: 613: 0; YV7#07B For Shotest
2. S7i-6h 24: 18: 0; SWX#01B
17. P 7g-7f 100 3


1. P8c-8d 36: 96: 0; YV9#39W For Bonanza
18. P 4c-4d 0 4

1. P6g-6f 42: 1: 0; INJ#04B For Shotest
2. P4g-4f 36: 9: 0; SQJ#50B
3. S7i-6h 30: 18: 0; SWX#01B
4. B8h-3c+ 30: 8: 0; SQJ#51B
5. P5g-5f 24: 48: 0; YUA#99B
19. S 7i-6h 197 4

1. P8c-8d 30: 95: 0; YV9#39W For Bonanza
20. S 4b-4c 0 4

Note the illegal move B8h-3c+, which would be possible without P4c-4d.

1. B8h-3c+f 36: 7: 0; SQJ#51B For Shotest
2. P5g-5f 30: 2: 0; IQ4#73B
21. P 5g-5f 195 7

1. P8c-8d 18: 955: 0; YV9#39W For Bonanza
2. P5c-5d 6: 2: 0; SVW#24W
22. K 8b-9a 0 6

1. S4h-5g 30: 3: 0; YTY#25B For Bonanza
23. S 4h-5g 169 3

1. P5c-5d 42: 2: 0; SVW#24W For Bonanza
2. P8c-8d 18: 95: 0; YV9#39W
24. S 7a-8b 0 6

1. P3g-3f 18: 2: 0; IPJ#112B For Shotest
25. P 3g-3f 146 5

1. P8c-8d 24: 95: 0; YV9#39W For Bonanza
26. G 6a-7a 0 4

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)

27. P 4g-4f 138 4

1. P5c-5d 36: 2: 0; SVW#24W For Bonanza
28. G 4a-5a 0 6

29. P 1f-1e 154 6
30. P 9c-9d 0 6
31. N 2i-3g 149 4
32. G 5a-6b 0 5
33. R 2h-2f 121 6
34. G 6b-7b 0 6
35. P 5f-5e 94 6
36. R 2b-5b 0 6
37. B 8h-7g 88 6
38. P 5c-5d 0 5
39. P 5ex5d 13 7
40. S 4cx5d 0 6
41. B 7g-8f 68 6
42. P 4d-4e 0 6
43. N 8i-7g 92 12
44. S 5d-5e 0 6

This move seems suspect, allowing Shotest to promote the bishop on 3a.

45. B 8f-3a+ 85 10
46. P * 5f 0 6
47. S 5gx5f 88 11
48. S 5ex5f 0 5
49. B+3ax2a 183 9
50. B 3c-5e 0 6
51. B+2a-4c 96 10
52. R 5b-5a 0 6
53. B+4c-4b 59 13
54. R 5a-5d 0 6
55. B+4b-3b 61 14
56. R 5d-8d 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.

58. B 5ex4f 0 5
59. N * 4i -262 13

Shotest switches to N*4i and believes it is ahead. From now on Shotest’s position continuously improves.

60. P 9d-9e 0 4
61. P 9fx9e 323 17
62. P * 9h 0 6
63. L 9ix9h 404 13
64. S 5fx5g+ 0 5
65. S 6hx5g 382 15
66. B 4f-5e 0 6
67. S 5g-6f 396 13
68. B 5e-4d 0 6
69. R 2f-2h 448 11
70. P 4e-4f 0 5
71. S * 7e 740 10
72. B 4dx6f 0 6
73. P 6gx6f 801 8
74. P 4f-4g+ 0 6
75. G 5hx4g 949 16
76. P * 4f 0 4
77. G 4g-5g 1198 17
78. S * 8i 0 4
79. K 7hx8i 1230 5
80. R 8dx8g+ 0 5
81. S * 8h 1199 6
82. S * 8f 0 6
83. G 6i-7h 1335 13
84. R+8gx7g 0 6
85. S 8hx7g 1391 8
86. S 8fx7g+ 0 4
87. G 7hx7g 1293 17
88. N * 8e 0 6
89. G 7g-8g 1360 9
90. P 3d-3e 0 4
91. P 3fx3e 1393 26
92. P * 3f 0 6
93. N 3g-4e 1561 15
94. P 3f-3g+ 0 5
95. N 4ix3g 1473 14
96. S * 3f 0 5
97. S * 4h 1482 11
98. S 3fx4e 0 5
99. N 3gx4e 1662 12
100. N * 3f 0 5
101. R 2h-3h 1747 11
102. N 3fx4h+ 0 6
103. R 3hx4h 1665 12
104. P 1c-1d 0 6
105. P * 8f -1713 31
106. P 1dx1e 0 6
107. P 8fx8e 1716 25
108. P * 5f 0 6
109. G 5g-6g 1735 9
110. P 4f-4g+ 0 4
111. R 4hx4g 1728 10
112. S * 5h 0 6
113. R 4g-3g 1784 15
114. S 5hx6g 0 6
115. R 3gx6g 1740 9
116. G * 4f 0 6
117. P * 5h 1896 11
118. P 7c-7d 0 4
119. S 7ex7d 1958 15
120. G 4fx4e 0 6
121. B+3bx2c 1896 21
122. G 4ex3e 0 4
123. B * 5e 1974 24
124. P * 7c 0 6
125. S 7d-6e 1961 23
126. P 5f-5g+ 0 6
127. R 6gx5g 2143 8
128. N * 4e 0 6
129. R 5g-4g 2314 9
130. N 8a-9c 0 6
131. B+2c-2d 2355 33
132. G 3e-3f 0 6
133. R 4gx4e 2307 11
134. N 9cx8e 0 4
135. B+2d-6h 2311 28
136. P * 9g 0 4
137. L 9hx9g 2341 11
138. N 8ex9g 0 6
139. G 8gx9g 2319 7
140. L 9bx9e 0 6
141. B+6hx9e 2363 17
142. L * 9b 0 6
143. P * 9d 2377 24
144. P * 9f 0 6
145. G 9gx9f 2739 15
146. L 9bx9d 0 6
147. B+9ex9d 2771 21
148. P * 9c 0 6
149. B+9d-9e 2736 16
150. P 1e-1f 0 4
151. N * 8e 3092 25
152. P 6c-6d 0 6
153. S 6ex6d 3455 52
154. G 7a-8a 0 6
155. R 4e-4a+ 4002 41
156. G 7b-7a 0 4

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.

157. S 6dx7c+ 9984 9
158. S 8bx7c 0 1
159. B+9ex7c 9988 1
160. S * 8b 0 1
161. B+7cx8b 9990 1
162. G 7ax8b 0 1
163. B 5ex8b+ 9992 1
164. K 9ax8b 0 1
165. S * 9a 9990 1
166. K 8bx9a 0 1
167. R+4ax8a 9992 1
168. K 9ax8a 0 1
169. G * 8b 9994 1
170. K 8ax8b 0 1
171. G * 7c 9986 4
172. K 8b-9b 0 1
173. G 7c-8b 9988 1
174. K 9bx8b 0 1
175. S * 7c 9990 1
176. K 8b-9b 0 1
177. S 7c-8b+ 9992 1
178. K 9bx8b 0 1
179. S * 7c 9994 1
180. K 8b-9b 0 1
181. R * 8b 9996 1
182. K 9b-9a 0 1
183. L * 9b 9998 1

Shotest wins.

Conclusion

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