Search-Based Opening Book Construction

[jack512]

Search-Based Opening Book Construction
Abstract – An algorithm is described for constructing a chess opening book, to be used in play against an opponent using another book that is given. The book under construction is represented as a Directed Acyclic Graph, with chess positions as nodes and moves as directed arcs between nodes. Each position carries a position probability that a game played between the given and being-constructed book will eventually reach that position. Books for White and Black are constructed separately. Assuming a book is being constructed for White, a priority queue repeatedly chooses the highest-probability unexpanded position for expansion. If it is Black’s turn to move, moves with move probabilities for the position are copied from the given book. If it is White’s turn to move, a search determines the best move, which is added with move probability one. Depth of search is controlled as a function of position probability. Several books for White, representing a range of build CPU time, were constructed to play against the book that comes with Crafty version 25.0.1, B25.0.1. The strongest, B29, took 12 CPU-days to build. In 1000-game matches against Black/B25.0.1 (Black using B25.0.1 book), White/B29 scored 64 ELO points higher than did White/B25.0.1.

Full manuscript here: https://drive.google.com/open?id=0B2pvW ... HhtWTUwZFE
Revision of: https://drive.google.com/open?id=0B2pvW ... UpkRE0tem8

[jdart]

I don't know why you would expect a book constructed in this way to underperform the default book. In other words, that it outperforms is unsurprising, given that it is a larger book, that the engine using it will often exit the book later (as is noted), and that is uses the established principle of dropout expansion.

I wonder how much of the gain is due to the fact that the book basically has pre-computed the searches, and validating the book by self-play (with the same engine) maximizes the chances that the engine using the computed book will stay in book .. a different engine with a different eval is more likely to deviate from the lines in the book, I think.

I also would not dismiss so easily books built from historical games, if in that you included engine games and correspondence games. Moves from these games often come from deep search by strong engines, in the case of correspondence using far greater depths than the book construction process can use. Lines from such games are also often found in engine books by professional authors.

--Jon

[Dann Corbit]

We have clear confirmation of this. The cerebellum book is mechanically constructed and in tests it is the first or second rated book in all the contests that I have seen.

Now, this is surprising historically, because computer generated books used to be awful until perhaps five years ago.

Machines and programs both lacked the necessary horsepower to compete with 10^21 operations per second of the human brain together with centuries of analysis.

It is now possible to mine the data from the big contests like CCRL, CEGT, TCEC and places like playchess to collect stupendous quantities of data. This data can also be refined mechanically to create information with enormous compute power backing.

[Frank Quisinsky]

Hi Jon,

after all my experience in building opening books and three years I checked engines games by hand from my FCP Rating List ...

Correspondence games don't have a better quality. I think that correspondence chess player are thinking ... I have enough time and should try that my opp. is out of book. A lot of dubious moves are in correspondence databases.

I reject much more material from correspondence databases comparing to GM databases. GMs hold more the good and known systems or try new lines of opening theory.

An other example:
If an opening book tuned with one engine (not important how strong) in a group of other engines are around 10% of moves from this book aren't balanced enough. The main problem the available books have.

To give Wasp an book tuned for Stockfish is the same as I would say ...
Karpov have to open the games with the opening knowledge of Shirow.

A very interesting observation to that topic is:
To A00-E99 theory of a very high GM and correspondence level 10-15% of possible good moves never played (three moves afer ECO Codes based). So engines can find a lot of interesting things and all that material should be included for a strong computer chess opening book. To used only GM and correspondence material is very boring.

Maybe later I will public stats to that observation. So written book writers will have a lot of material for new written books to openings. I am thinking that in maybe 1-2 years to each of new opening books are engine analyzes included.

The last advantage humans have ... the opening theory ... comparing to chess programs is know very slow over. I think that a good sorted combination of chess programs can be produced better material to all the opening lines.

If I wrote ... 15% of possible good moves are not included in stronger GM games / correspondence games 3 moves after the ECO codes was formed ... I am sure ... 4 moves after the ECO codes was builded we have maybe 25%.

With computer chess we can make the theory much better ... sure here! But again we need many different engines in playing style for it.

Best
Frank

A very good example how bad are correspondece theory are D08 / D09 lines if I am looking here what strong correspondence chess players try out for absurdity moves. Best written books lines I checked are the great books from John Shaw. Playing 1. e4 Caro-Kann, 1 ... e5 & Minor Lines or "The King's Gambit" are really fantastic material. I am sure John used a group of very strong engines for his analysis. And a third book will follow this year ... waiting here very impartient.

[jdart]

I think the principle is ok but you are relying on the engine eval being an "oracle" that can predict how well the game turns out, and unless you can actually search into a known result or a known endgame it is an imperfect oracle. So it is always possible that you steer into a line that is not really good.

Also I see a lot of cases especially in the correspondence game where players enter lines that don't look good even at fairly deep search depths but over time whatever imbalance there appeared to be disappears. So either they are searching it out until the eval changes or they have good intuition, or they have the information from prior games that it is a playable position despite what the engine says initially.

--Jon

[Dann Corbit]

I think a hybrid approach is good.
Collect engine statistics for a position (eval, depth, bm, expected response).
Collect win/loss/draw statistics (historical).
Collect engine win/loss/draw statistics.

Every time you play a game, you update the statistics.
Eventually, the book will play better and better, because losing moves must at some point get bad statistics

[Frank Quisinsky]

Hi Jon,

thats right!

Not easy to give the information better is correspondence or GM chess four building opening books. I can see in correspondence games great opening combination but more often as in GM chess engines find errors.

Example:
In the time I am working on my older FCP Live Book during my FCP Rating List I rejected 7700 lines. Sure here maybe 1.000 or lesser unjustly / wrongfully. Means if an engine gave more as 0.8 ... often Smarthink, Texel, Fizbo others gave to high evals and after a short test I am thinking "bad line" and reject without I checked that in detail. No time to make that with so many games I produced. But with the years and more knowledge I know the ECO codes and checked only in detail if I am uncertain.

7700 ... is the topic!

I have for all what I do databases and can see from which source the games
comes. From GM chess ... correspondence or from eng-eng games.

Most I rejected comes from eng-eng games ...
Example: After each test run from my older rating list I added moves undo move number 10-12 ... often my book goes to move number 6, 8, 10! The Problem is that new lines engine found other engines deleted directly with the next test-run.

Smarthink give 0.3 and all is OK and Houdini give 0.9 ... and rejected.

If I compare gm and correspondence chess ...
From GM chess around 1.400 bad lines from Correspondence chess around 2.550 lines are included in the 7.700 database.

Very complicated to build a good opening book with all the different playing styles. But I think I have found a good way to do that today ...

Today the material I have is really good ... after many years I collected with SWCR Rating List, FCP Rating List and strong game material I found in written books or other sources.

Not perfect but the best I can do with the ideas I have. And today with all the knowledge I have I build a new book ... now the lines I am using are better selected and a wild mixed from written books, eng-eng game, correspondence games, gm material. I think the combination of all is the secret.

Sure here that we need a lot of engines for checked the game material for opening books. Engines should be strong in the openings (should not lost many games very fast). Wasp is very strong here as engine not in the group of TOP-20. Booot, Chiron, Andscacs are very interesting in the first gaming phase. Fire reserved with the eval but often aggressive too.

Sure that I have a good mixed from engine ... 10 for an example and all analysed the positions the book will be to 97-99% perfect for the other engines, not analysed the same positions

Best
Frank

Your engine is strong too ... I like Arasan a lot and the work you do so many years. I am sure you have much more experience to that topic and you have also a very strong book. Never I am satisfiend and thinking I must try to make it better. More often the own results are bad but better as to do nothing.

[jdart]

I have been thinking about taking my existing book, evaluating all the terminal positions and using minimax values in move selection. Then possibly using dropout expansion. Currently it correctly avoids a lot of bad lines and selects good ones, but the move weights are probably not very optimal. I have not done this yet. There would be some decisions to make - for example should moves manually flagged as "don't play" be kept that way or should you actually let the eval do the selection or should you use some weighting of prior information and eval?

--Jon

[Frank Quisinsky]

Hi Jon,

my bad English, but if I understand the last way is most interesting. Weighting of prior information _and_ eval.

I am thinking ...
If 10 engines, different in playing style, cleaned a database each programmer can do a lot with the material.

Example: If I have a clean database with 24.000 positions, checked by TOP-10 without move transpostion and an other engine analysed the cleaned database again and found 100 of the 24.000 lines as bad line ... I think the eval must be improved or something is wrong here.

A german Excel expert and computer chess lover in the past is at the moment working on really good Excel files to my book project. All what we need are a lot of engine analysis. Working on it ...

Example ... engine give often in E99 as bad lines with much higher evals as the TOP-10 ... programmer can search and try to improved the eval. Better can see it very fast and can try to fix it.

If you are working with Arasan on new opening book ideas please let me know. Very interesting what you do here with the ideas you have.

Logical ... I can checked the files I have with Arasan. But my book project is a long time project ... not ready undo end of the year. Enough time to checked my own files with Arasan later ...

Best
Frank

[noobpwnftw]

my advice: drop all probability factors, and never ever minimax your results, use generalization algorithm.

your engine can use it as a PV line suggester and let the search verifies/self-play against it so that while you boost your search you are also expanding the book.