Computer based Opening theory

[mcostalba]

I've generated a 4 ply opening book using nothing more than my engine.

Very nice and original idea Lucas !

After the first set of 50K opening have been found you can further proceed for instance searching up to depth 13 with a bit lower threshold so to further nail down the set.

But another more interesting approach would be to perform a multi PV of 3 on each position with depth 12 and filter all the positions for which at least one of the PV lines is below threshold. In this way you drop all the playable but forced positions and just keep the ones that allow the engine to freely choose how to continue.

[Joerg Oster]

Interesting. Why not?
Engines should be able to deal with even the oddest openings, imho.

This is one of the drawbacks in the Stockfish Testing Framework. Too less diversity. IIRC, ECO B, for example, is much overemphasized.

[lucasart]

Engines should be able to deal with even the oddest openings, imho.

Yes, that's exactly the starting point of my reasoning. I want to do as if the engine plays without book (shallowness), while not repeating the same game all the time (diversity).

I redid the generation, introducing further constraints:
* depth=13 score within +/-45cp
* prune quiet moves that do not improve the static eval. That way we only select moves of a developping nature (so you don't see things like Nb1c3 followed by Nc3b1 for example).

Now the branching factor is somewhat smaller:

Code: Select all

$ wc -l ./book*.epd
      1 ./book0.epd
     20 ./book1.epd
    230 ./book2.epd
   2041 ./book3.epd
  17926 ./book4.epd

I'm generating the 5-ply one now, and expecting 150k-200k unique positions there. That will be more than enough for all testing purposes, and will bring a lot of diversity into the games.

I'll probably run a second filter using Critter on the book5.epd, to get a second opinion engine (and a deeper search). Stay tuned!

[Rein Halbersma]

In checkers/draughts, and also in other games, so-called dropout expansion has been very successful. See Ch. 3 of Thomas Lincke's Phd Thesis. It places all the nodes of the current book in a priority queue and repeatedly calling a search on the top node, expanding the book, and then recomputing the priorities. The priority can be user-configured, e.g. to emphasize breadth over depth, or vice versa. You can also guide it to expand specific opening lines (e.g. based on published play). It is also very easy to parallize, and e.g. let a few idle cores (OK, this paper was published before systematic large-scale testing!) expand the book around the clock.

[kranium]

The idea would be to create entirely computer based opening theory. Human opening theory is flawed and biaised: very poor diversity and many dubious lines that comp analysis show to be unsound.

i completely agree Lucas...
i'd love to see tournaments where the engines played the whole game instead of being forced into positions it would never chose for itself.
the typical argument against this is 'duplicate games', but i've analyzed large tournaments without opening book and found the # of repeated games to be 0.

another interesting take on your project would be:
instead of using perft...play top engines against each other without opening book (from the start position)

this way, you'd get useful lines without the rather dubious 1. f3, 1.h4 stuff
probably almost all: 1. e4, 1. d4, 1.c4, 1. Nf3, 1. g3, etc.
my guess is that the engines would mostly enter main lines of human opening theory
(Ruy Lopez, Queens Gambit, etc.)
and quite possibly play novelties or rarities once in awhile, thereby enhancing/enriching what we already know.

best regards-
Norm

[xmas79]

this way, you'd get useful lines without the rather dubious 1. f3, 1.h4 stuff

Why these lines are doubious? Because all of us would never play such moves doesn't mean they are not a good start...

probably almost all: 1. e4, 1. d4, 1.c4, 1. Nf3, 1. g3, etc.
my guess is that the engines would mostly enter main lines of human opening theory
(Ruy Lopez, Queens Gambit, etc.)
and quite possibly play novelties or rarities once in awhile, thereby enhancing/enriching what we already know.

Engines will never give a pawn in the opening, so remove every gambit from the list....

[mvk]

In checkers/draughts, and also in other games, so-called dropout expansion has been very successful. See Ch. 3 of Thomas Lincke's Phd Thesis. It places all the nodes of the current book in a priority queue and repeatedly calling a search on the top node, expanding the book, and then recomputing the priorities. The priority can be user-configured, e.g. to emphasize breadth over depth, or vice versa. You can also guide it to expand specific opening lines (e.g. based on published play). It is also very easy to parallize, and e.g. let a few idle cores (OK, this paper was published before systematic large-scale testing!) expand the book around the clock.

I'm using dropout expansion as one of my book extending mechanisms. I found that, in a node to be expanded, expanding one move at a time (instead of all moves at once) works better for me. It is also necessary to choose the expansion set more carefully than by using the simple omega method: more "best-first" for deep nodes, and more "shallowest-first" near the root. The diagram below gives a dropout-like diagram of the current book in red, with the expansion set in green.



In each green node I would expand the best move that is leaving the book. I have added an 'exclude <move> ...' command to my program to help find this move. Each expansion leads to 2 new searches to be performed: one for the child node, and a new exclusion search in the parent node to establish the next book-leaving move there. Visually in the dropout diagram that means that each expanded dot splits into two: one moving up 1 ply and staying at roughly the same value, and one moving a bit to the right on the value axis.

Progression is slow, but steady. However, I also have a couple of other book expansion methods to speed up learning. I don't believe that dropout expansion alone would be fast enough to maintain a good book for chess.

[Lyudmil Tsvetkov]

I've generated a 4 ply opening book using nothing more than my engine. Basically I start from the starting position, do a perft(4) and eliminate all nodes (interior and leaves) where a 12-ply search returns a score outside acceptable bounds +/-70cp:
http://open-chess.org/viewtopic.php?f=5&t=2551

This was really a fun experiment, and provided me with a great opening suite for testing my engine. It's as diversified and shallow as it can be, and contains 52967 positions which enough for most engine testing purposes.

But it could be improved and generalized:
* code it in a GUI like XBoard, so it can be engine agnostic.
* make the diversity of the book (branching factor) tunable in a couple of ways: using multi PV feature of the engine (fixed factor) or tweaking the 70cp threshold.
* genrate a proper book in PolyGlot format, rather than an EPD file.
* parallelize the book generation, and do it recursively with a global hash table to eliminate more efficiently transpositions.

Has anyone ever done that ?
Is anyone interested ? HGM ?

It would be really great. The idea would be to create entirely computer based opening theory. Human opening theory is flawed and biaised: very poor diversity and many dubious lines that comp analysis show to be unsound.

PS: I can't attach files on this forum, so I use Open Chess. Ideally please answer on Open Chess instead (but most people are here and Open Chess is a bit dead).

Now, undertaking as a whole is great. There is big room for tuning better engine parameters in the opening and a similar book could help in that sense.

My remarks to implementation details:

- if you want the book to be useful for successful engine testing, you need to create the book with a top engine (I would not say if Houdini and Komodo are better for the purpose than Stockfish, or vice-versa, but it has to be one of those engines)

- setting eval margins larger than 20cps would do you no good, it would simply be harmful to engine testing, regardless of the level of the engine tested. Bearing in mind that because of the right of first move white has some 15cps advantage, I would include only moves with +15cps advantage for white to +5cps advantage for black.

- with that in mind, your 4-plies book can never be larger than 2000 authentic lines. With 6 plies you can reach some 10000 - 15000 positions, which should suit even the most demanding testers. Doing a 5-ply book is not good, as it would be nice that white starts the game in all positions.

- if you would want a perfect book, you should include only lines starting with 1.e4, 1.d4 or 1.Nf3, as elsewhere black gets immediate equality.

- as tactics is not so predominant in the first 4 to 6 plies, engines will not be able to come up with anything new as theory there; where engine advice starts getting very valuable, is already a bit further down the search tree. So I would regard this exercise as mainly an attempt to ensure a variety of play for engines with them starting thinking at an early stage.

The above being said, I wish every success to the project.

[jdart]

I don't think even that is going to help. There are some very complex openings where in some cases the latest theory comes from correspondence games where 1 hour/move is considered a fast time control. I could give many examples, but some are the Botvinnik Semi-Slav, the Bishop sac in the 6. Ne5 Slav, some lines of the King's Gambit (John Shaw has a very detailed new book on this with deep analysis), etc.

Better IMO to take a decent book as a starting point, evaluate the leaf positions, and minimax back up to to the root. You are not going to discover the truth about openings starting from the root and working forward. The branching factor is too large and there are too many cases where only very deep search reveals the right way to go.

--Jon

[mvk]

How would you avoid convergence to the same position after one, or a few, moves into the game?