There's two schools of thought.hgm wrote:If you just use the book to instantly get a move that was obtained from a search much longer than the current TC could afford, I don't see how it could not work. It should always work in the sense that it makes the engine play better opening moves than what it could have done thinking them up OTB, and leave more time for the moves it does have to play once out of book.bob wrote:I tried several approaches to using search, but never really found anything that works, including the obvious idea of searching down the book lines, searching at each node, and minimaxing the resulting scores back up the book tree.
That it does not solve other problems, in particular that even at this longer TC that you emulate the engine is still deterministic, and could be 'booked-up' by an opponent that is allowed to analyze the book, is another matter. There are other solutions to that. That problem already gets enormously reduced if your opponents do not have advance access to the book, and no direct access, so they can only RE it by playing you. That they could repeat a won game once they win one is also not really helpful if the engine is lightly non-deterministic once out of book, and the book is such that you never come out of it in an inferior position.
But I agree that a robust book does need more than one move per position for the side playing from it, so that it can reach a large number of different positions even against a deterministic opponent by randomly choosing between them. That would make it virtually impossible for an opponent to 'book you up' even if he is allowed to play dozens of games against the same book.
But the algorithm I use now effectively does provide some move choice. It only expands the best move for the side that plays from the book, searching all non-best moves only upto the 'verification depth'. But the best move at one depth iteration needs not stay the best move at the next depth, and sometimes the score from the 'book move' searched at high depth will fall below that of one of the previously non-best moves). In that case PVS will promote that move to the PV move, and now that will be expanded to full depth. In cases where that happens you will then have multiple moves, and if their scores are not such that one is wildly inferior to the other, you can keep them both in the book. So I will get books with some move choice.
Btw, after fixing a bug (Calling Search() did not restore the hash key and incremental evaluation, so I could not do several calls of Search in a row without explicitly restoring those ), I get results that seem reasonable,:
This is for building a white book with a verification depth of 10 ply, which as to be subtracted from the reported depth to get the book depth. So the output shown will have created a book of 15 ply, where each end-leaf has received a score from a 10-ply search. Especially encouraging is that the EBF seems typically to be slightly below 2.Code: Select all
1 92 0 39 d1c2 eval = 0.64 (dif = 0 cor=6) 2 40 0 150 d1c2 b5c4 3 8 0 691 d1b3 b5c4 c1c2 4 40 0 1549 d1c2 b5c4 c1b2 c5d4 5 12 0 3335 d1c2 b5c4 c1b2 c5b4 e1d1 6 40 0 10315 d1c2 c5d4 c1b2 b5d3 c2d3 d4d3 7 8 1 20994 d1c2 b5c4 c1b2 c5b4 e1d1 c4e2 d1c1 8 40 3 38608 d1c2 b5c4 c1b2 c5b4 e1d1 c4e2 d1d2 e2c4 9 12 39 756393 d1c2 b5c4 c1b2 c5b4 e1c1 c4e2 b2b3 b4b3 c2b3 10 48 59 1228682 d1c2 b5c4 c1b2 c5b4 e1d1 c4e2 d1c1 a5c5 c1e1 e4e3 11 4 218 4633479 d1c2 c5d4 c1b2 b5c4 e1c1 a5c5 c2a4 c4d3 b1c2 d3c2 c1c2 12 4 360 7703348 d1b3 b5c4 13 0 1012 21910275 d1c2 c5d4 14 4 1797 39037723 d1c2 b5c4 c1b2 c5d4 e1c1 a5c5 a2a3 15 -4 3366 73353813 d1c2 b5c4 c1b2 c5d4 e1c1 a5c5 a2a3 c4e2 c2b3 e2c4 b1c2 c4b3 c2b3 c5c1+ b2c1 d5c5 16 -4 5921 129690430 d1c2 b5c4 c1b2 c5d4 e1d1 c4e2 d1c1 d5c4 c1e1 e2d3 c2d3 c4d3 e1c1 a5b5 c1c4 17 -4 9143 200390595 d1b3 d5d4 18 -4 18153 400044858 d1b3 d5d4 b1b2 c5b4 19 -8 29992 662086397 d1c2 b5c4 20 -8 42758 942551069 c1d2 d5d4 21 -12 69247 1508444823 d1b3 b5c4 22 -12 246125 1114104482 d1b3 b5c4 b3c4 c5c4 B@b2 B@d4 b2d4 d5d4 c1c2 a5b5 23 -16 361796 -625539100 c1b2 b5d3 24 -16 551713 -712772845 b1b2 b5c4 25 -20 1291574 -1602468001 d1c2 c5d4
What still worries me is that the PV seems to be cut. This suggests I still must have some bug, as I cannot understand how that could happen. I suppressed hash cutoffs at all requested depths larger than the verification depth. (Also to make sure it will properly recognize repeats in the book lines.)
That the root score slowly decreases with depth is also something that looks good, as the rules favor black, who wins in case of repetition.
(1) play a move that is better than what you would find after a normal search. IE your first point.
(2) play a move that you might not find even after a very deep search, because there is some strategic or tactical reason the move will turn out to be good, but the reason is beyond any practically reachable search depth...
In chess, the latter is almost a necessity, because book authors have worked out very deep lines where the "logical" moves end up losing...