Search-based opening book

[hgm]

I am running an interesting experiment, using an engine with a modified search to generate an opening book. "What is the point of that?", you might ask. Well, the point is that this is that I have no set of games available by players stronger than the engine (and in fact no games at all), because this is a mini-Shogi engine.

So the only games available are games generated by the engine itself. There are two ways to make a useful book out of that: either play a staggering number of fast games (like a million), and draw conclusions from the statistics to effectively boost the search depth compared to what the engine was doing, or only use games where the engine was searching on each move significantly longer than what it would do at the TC where you want to use the book. Neither of that seems very efficient. Fast games might contain poor moves, and a lot of CPU time would be spent on finishing games startig with such moves, which eventually do not go into the book by their poor statistics. As the TC I am aiming for is 20-min sudden death, playing much slower games makes it very hard to generate enough games, so you might miss good moves. And also there the early moves will overlap, so that significant time is spent on thinking up the same move in the same position.

So I figured that if I want to have the engine search for a long time on each position in the book, to determine the best move (so that it could then instantly play this move in the game with a quality like it would have searched longer than it would actually be able to do), I'd better do it systematically: run a sort of perft to a given depth, and let the engine do a normal search in each to the desired depth (determining the book quality) leaf node of the perft. The perft part would actually be a normal search where beta-cutoffs are suppressed, (so all moves are searched), but where move sorting and minimaxing of scores would take place in the normal way. So it would also be aware of best move and score in the non-leaf positions of the perft (so these could go into the book as well).

Now a full perft would search all moves, no matter how obviously stupid they are. This would waste of course a lot of time, as most moves in most positions are incredibly stupid. So I prune moves of the tree for which a limited-depth search shows their score is too far from equality (which presumably is the root score for the opening position). E.g. if I want each node in the book to be searched to (say) 12 ply, when that 12-ply search would give me a score outside the acceptable score range (e.g. outside {-1.00, +1.00}), I would never expand that node, no matter how large the requested search depth was in the perft. With truly unbalanced positions, I make the pruning requirement even less. (e.g. if an 8-ply search produces a score > +8, I won't even attempt the 12-ply score).

Now this process is still a bit slow (meaning I won't get a very deep book if I want acceptable quality of the leaf-node searches). This is because what I described would be really an attempt to generate all possible theory in the world. Normally you would be happy to have just a single move in each position. (This would make an 'exploitable book', where you would repeat the same opening if the opponent does, but that is OK if the book is secret.)

So what I do is only expand the best move of the side I am building the book for, and prune the moves for which the target search depth sows they are worse than the best. (The opponent will of course always search all moves, to make sure the move is safe to play.) This does not mean they are permanently pruned: the search of the best move continues to deepen as the requested depth grows, and if despite its superficially good prospects it runs into trouble, so that its score drops below that of one of the pruned moves, the latter would become the new 'PV move''in a sort of PVS-like way, and be deepened to the requested depth. If this happens during the final iteraton of the book building, it would also mean that you have multiple moves available in that position (if their scores did not differ that much).

[syzygy]

Are you aware of this thesis: Exploring the Computational Limits of Large Exhaustive Search Problems.

The tricky part is how to deal with cycles.

[hgm]

No, I wasn't. Thank you for the link!

[mvk]

No, I wasn't. Thank you for the link!

I'm using a derivative of the drop-out expansion scheme for my book (plus several other forms of expansion).

[Rein Halbersma]

No, I wasn't. Thank you for the link!

I'm using a derivative of the drop-out expansion scheme for my book (plus several other forms of expansion).

It's standard practice in checkers to use drop-out expansion (DOE) for opening book preparation. Apart from the much smaller branching factor for checkers, it should also work for chess although you would get a much shallower book probably.

I never quite understood why it didn't catch on for chess (or at least I haven't heard about it for any of the top engines).

[hgm]

I think for Chess the opening is mostly strategic, rather than tactical, and this is exactly the part where even the top engines are lacking. In mini-Shogi, where the pieces are not locked in by a Pawn wall, the game is very tactical from the beginning. So producing a book with an engine makes much more sense.

Currently the whole operation just places the following code at the top of my Search(origAlpha, beta, depth, PV) routine of my normal engine (for making a white book):

Code: Select all

#ifdef BOOK
  if&#40;depth >= BOOK && depth < 1000&#41; &#123;
    if&#40;depth > BOOK&#41; &#123;
      bestScore = Search&#40;origAlpha, beta, lastPly, PV, BOOK-4&#41;; // first try at minimum depth
      retDep = depth; if&#40;abs&#40;bestScore&#41; >= 200&#41; return bestScore; // totally decided, very shallow suffices
      bestScore = Search&#40;origAlpha, beta, lastPly, PV, BOOK-2&#41;; // first try at minimum depth
      retDep = depth; if&#40;abs&#40;bestScore&#41; >= 100&#41; return bestScore; // nearly decided, no need for full depth
      bestScore = Search&#40;origAlpha, beta, lastPly, PV, BOOK&#41;; // first try at minimum depth
      retDep = depth; if&#40;abs&#40;bestScore&#41; >= RANGE&#41; return bestScore; // don't waste time on bad lines
      if&#40;PV <= 0 && stm == WHITE&#41; return bestScore; // reduce non-first-choice white moves
    &#125;
    if&#40;origAlpha > -RANGE&#41; origAlpha = -RANGE;
    if&#40;beta < RANGE&#41; beta = RANGE;
    PV = 1; // make this node a PV node so its first daughter will also be one
  &#125;
#endif

and then some code at the end of Search to print the path to the node to a file if depth == BOOK, (followed by score/ply as PGN comment). BOOK is the desired search depth for determining the leaf-node scores.

That means I expand all wtm nodes, but a btm node is only expanded if it is the PV daughter of a wtm node (normally the first daughter, but the propagated score of that gets lower than the 'heuristic' score of the non-expanded daughters, it starts to expand other daughters until an expanded (recursively to full depth) one scores better than the remaining non-expanded ones). This aims at just getting one playable move per position for white (deterministic book), although sometimes you might get more (if it switches PV move in the final iteration). For any possible counter play such a book would either reach the maximum depth, or you would get out of book with a guaranteed advantage RANGE.

[bob]

No, I wasn't. Thank you for the link!

I'm using a derivative of the drop-out expansion scheme for my book (plus several other forms of expansion).

It's standard practice in checkers to use drop-out expansion (DOE) for opening book preparation. Apart from the much smaller branching factor for checkers, it should also work for chess although you would get a much shallower book probably.

I never quite understood why it didn't catch on for chess (or at least I haven't heard about it for any of the top engines).

Several of us have tried this in the past. The problem is deep tactics and strategy. If you let the search guide building the book, you won't see the deep tactics, which is the same as overlooking them if you trust the book line.

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. If someone knows you use that approach, constructing a hand-optimized book to bust your chops is not very hard for the good book people. Nothing quite like playing down a book line your opponent knows is a dead loss from your side...

This book stuff has actually been one of the hardest problems I have tackled, given the approach of "hands off automatic creation and move selection."

Note that strategic planning is really nothing more than deep tactics. "Damn, I wish I didn't have that piece blocking that pawn, if I could move it right now I would have an advantage, but as it is, I am getting badly cramped..."

Hard to cope with that automatically...

[Dan Andersson]

Two other papers:

http://computer-super-go-acm08.googleco ... 0Books.pdf

http://www.personeel.unimaas.nl/M-Winan ... res9x9.pdf

[mvk]

No, I wasn't. Thank you for the link!

I'm using a derivative of the drop-out expansion scheme for my book (plus several other forms of expansion).

It's standard practice in checkers to use drop-out expansion (DOE) for opening book preparation. Apart from the much smaller branching factor for checkers, it should also work for chess although you would get a much shallower book probably.

I never quite understood why it didn't catch on for chess (or at least I haven't heard about it for any of the top engines).

All I can say it works fine for me, but it is not the most important form of expansion.

For the drop-out expansion scheme, I expand one move per iteration in a node (being the best move not yet leading to a book position), instead of all moves at once. That is a big difference. And I restrict it to nodes/moves within a certain asymmetrical path error window, which is tracked for White and Black separately (so my path error definition is a tuple, not a scalar). There is a need for path error normalisation when the position can be reached through multiple ways from the root, but that is not hard to figure out and kind of elegant.

[hgm]

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.

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.

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,:

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

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.

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.