Search-based opening book

[bob]

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.

There's two schools of thought.

(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...

[hgm]

Indeed, in Chess the opening is mostly strategic, and engines suck at that. In addition, there is a large body of information generated by strategically strong GMs.

In mini-Shogi, the game is tactical from the very beginning, though. And there are no GM games available.

[Don]

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).

I am very interested in this type of approach. I helped MIT build a program for a laser and mirror style of game similar to khet and I provided them with an automated tester. The tester had to provide variety and I was able to produce thousands of openings this way. As the program got stronger I updated the opening book in an attempt to keep the quality of the book reasonably high. But the truth of the matter is that it probably doesn't matter too much - espeically if you always play both sides of each opening. If there are errors in moves (which is quite surely the case) they should average out - so the hope is that there are not too many final positions that are ridiculously in favor of one side or the other. Obviously you want the highest quality you can reasonably get but I don't think it's a dominant factor for an automated test book.

Here is a chess book question. I thought at one point the answer was obvious, but I am not so sure now. Suppose you had 2 opening books for automated testing where each program plays both side of each opening. Do you want a book that tries to end with perfectly equal positions or would it be better to have one that had a lot of positions where one side had a significant (but perhaps not winning) advantage? What would be consequences in terms of ELO ratings?

My initial thinking on this is that if 2 program are perhaps 50-100 ELO apart in strength, the unbalanced book would tend to make the program look more equal and minimize the ELO difference. The thought experiment here is to imagine that all the openings ended with an easy win for one side - then any 2 programs that were not ridiculously weak would be winning when the position was a win and losing otherwise and thus even the weak programs would score 50% or close to it.

However, the draw rate of the top program at longer time controls is quite high these days - and you can many consecutive draws before one program wins a game. We saw some of that in the TCEC tournament with Stockfish and Houdini. I'm wonder if an unbalanced book would turn a lot of those draws into wins. The stronger program may survive the bad position while being much more likely to win the positions that were favorable. As it was, in that tournament, some of the openings would end in a position that was not very favorable for one side, even though you would later get an opportunity to play the other side. In a sense it put more pressure on you to win when you had the "good" side of the opening and that could make for more exciting chess.

So what do you think?

[hgm]

Starting from an unbalanced position basically shifts the score-vs-Elo curve horizontally. When you average this over many shifts, the effect is that the slope goes down, but the range of Elo difference over which you can do meaningful testing increases. And the decreased sensitivity is partly made up for by a decrease in variance as well, as those positions that are so unbalanced that they are a certain 1-0 between equal opponents not only fail to contribute to the score, but also do not contribute to the noise.

When you model a game as a random walk over the score axis, the higher the level of play, the more slowly the score will difuse away from its start value (and drift in the direction of advantage for the stronger player). In a game with a draw margin, such as Chess, you run the risk that at very high level, you will hardly ever diffuse into the win or loss zone. You could prevent that by starting from positions that are at the very boundary between win/draw and draw/loss. Then any small amount of drift will immediately result in a score change, without any need for the score distribution to broaden during the games to reach the p[oint where the score flips.

I think this is the most reliable way. Starting from equal positions would result in a very large number of draws. Trying to draw a conclusion from the difference between the number of rare wins and losses would be very sensitive to how exactly the tails of the score distribution evolve during the game. This need not be Gaussian at all; the random walk could be dominated by just a few steps. In Chess this is actually likely; there is not really a limit to the damage you can incur when you overlook something. So it is much more reliable to draw conclusions from near the peak of the distribution than from the tails.

[jack512]

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...

Has anyone ever investigated playouts for a chess engine, as an alternative to minimax? Playouts used in Monte Carlo Tree Search have shown promise in other games.

Ramanujan et al. (https://arxiv.org/pdf/1203.4011.pdf, section 5 ENHANCING RANDOM PLAYOUTS) did a few experiments in which playouts, with both players using shallow minimax searches, were able to find moves that a single shallow search by itself could not see, but that a deeper search could.

Playouts might give hope of seeing beyond the horizon of a minimax search.

[jdart]

I have been thinking about something similar.

Ideally you want full game results, and a lot of them. But a search score is a well-known proxy for game results. A reasonably deep search can be a pretty good predictor of win percentage.

If you have any book constructed already, you could start by searching the terminal nodes and then you can use dropout expansion to find which nodes are most interesting/valuable to explore. Those might be searched deeper, or they might be the starting point for actually generating some games, which is a second-level and maybe better indicator of win percentage. I would consider this because there are certainly positions where limited-depth search is fallible. I was looking at some of the Sozin/Velimirovic lines recently (B86/B87) and lots of those are razor sharp and full of "only" moves. You can think you are ok but one wrong move deep down the PV could kill you.

Another thought: at least for chess I think the book should store both a predicated win percentage and draw percentage. The score for a draw depends on the contempt setting, and so by having both win and draw %, you can optimize your play based on the opponent. (This could lead to even more draws than are common now, but if you want to optimize the engine's scoring percentage, that is what you would do).

--Jon

[koedem]

Not sure if this has been suggested like that before, but I just had an idea for book creation without a large set of games behind it already. Thinking about it further it is actually somewhat similar to Leela's search so I might as well describe it as such.

So in the book creation step you basically create a PUCT search tree of the start position. My thinking is that the policies of a position could be calculated from a multi-PV search. You then repeatedly expand that tree like you would in PUCT, only that at the leaf that you expand you do actually do a full playout of the game. (or maybe you stop after, say 20 or 30 moves and use the evaluation there as Q of the leaf you expanded)
Then after doing that for a large number of times you could use that as a book by choosing moves e.g. proportionally to visit count (or include the moves Q in the weighting) down to some cutoff point of visits or eval which you exclude from selection.

The problem I see with this is it might be quite slow to generate a book. However it might work reasonably well in an environment where there's not a lot of games already and where one might not trust the engines short time evaluation. (as well as the search will eventually explore moves the engines thinks are bad)

[Rémi Coulom]

Hi,

I have also been generating an opening book automatically.

My approach is simply to use MCTS to grow the book, using a long search to evaluate the leaves, and negamax backup. It is a bit similar to the drop-out expansion approach of the Othello book algorithms, but I like the MCTS approach better as a method to grow the tree.

The nice aspect of having a book with evaluations and negamax is that I can do very efficient book-learning when playing online by marking the leaves of lost (or drawn) games as losing. This way the program avoids repeating bad games very efficiently (and also repeats winning games very efficiently if the opponent does not avoid repeating games).

I implemented this book algorithm in my generic Alpha Zero framework. I made my renju book available online, and it became very popular with renju players. I also have a very small chess book. I don't expect it to be great because it was produced by a small neural network with a short search. All my books are browsable online:
https://www.crazy-sensei.com/book/chess/
https://www.crazy-sensei.com/book/shogi/
https://www.crazy-sensei.com/book/renju_15x15/
https://www.crazy-sensei.com/book/gomoku_15x15/

MCTS with negamax backup is a very powerful and flexible approach for book generation. It can generate an opening book without any prior game-record data, but makes it also easy to explore hand-picked variations, or game records of strong players. In the future, I will add a new feature to my crazy-sensei website to allow visitors to request a book expansion manually.