TalkChess.com

Dear all,

has anyone tried to generate opening books from scratch with engines?!

I mean why should we work with standard books from ELO 2400-2800 players if Stockfish / Komodo, Houdinis have 3300 and can generate the first N ply and more for us?!?

Best Regards
Stefan Edlich

edlich wrote:Dear all,

has anyone tried to generate opening books from scratch with engines?!

I mean why should we work with standard books from ELO 2400-2800 players if Stockfish / Komodo, Houdinis have 3300 and can generate the first N ply and more for us?!?

Best Regards
Stefan Edlich

http://www.zipproth.de/#Brainfish

Because humans are much stronger than "2400-2800" in the opening.
Openings you can systematically study as the possibilities are limited and this is what has happened over the past centuries.

Engines are different. They make less tactical mistakes in the middle and endgame giving them their huge ratings but are still limited in their long term strategical insight needed to play openings well. You can't just teach them concepts applicable to this or that particular opening only. They see things one "general" way and sometimes misplay particular positions according to our understanding.

Thanks a lot for the insightful answers!

There is also the fundamental problem that with engines you can only approximately know the correct eval with a limited depth search, and you only know that eval at the leaves of the tree you have visited (evals farther up the tree are even more approximate due to the horizon effect).

So extrapolating from this to finding the best move, especially in the early opening, is problematic. There are branches you haven't visited, and the branches you have visited have only approximate values.

That isn't to say you can't make a semi-decent book with engine evals. But for example in correspondence play, very often you see lines that look equal for a long time, making plausible moves from the engines, and then eventually the eval changes and one side is winning. So the horizon effect is real and will bite you if you try to rely on eval alone.

--Jon

It's important to realize that while humans are weaker than computers, openings from human vs human play are based on analysis of humans + computers. If there would be a way to make a stronger opening book top humans would latch onto it immediately and improve their own play.

That being said from a theoretical point of view your question is still interesting in my opinion. While in chess we have large databases with millions of game files this is not necessarily the case for other chess variants or games, it's a rather interesting bootstrapping problem. Furthermore what is good for one player may not be good for another. Humans may accept positions which are theoretically somewhat worse but gives them practical chances, but this may not be enough for engines. Computers may accept positions which are theoretically equal, but requires near perfect play from one player, but this may not be enough for a human.

Finally when working with your own engine there can be the motivation to generate something which is more truly "yours" and to reinvent the wheel. While an exercise in futility I think having a completely new approach in such things is both fun and a great way to learn new things.

Indeed. I am currently working on an opening book for mini-Shogi, where there are no games available I know of. And just a hand full of engines.

And opening theory is very important there, as most moves turn out to be 'singular', i.e. any move other than the best makes you take a large hit in evaluation. Very often the evaluations along an opening line look pretty much OK at the largest depth you can practically search, but some 20 moves deep it goes sour for one of the players. Then when you propagate the winning advantage back towards the start position, it turns out that the losing player had no alternative for his last 20+ moves, so that the game was basically already lost in the opening. But there is no way any search is going to see that at that point. Mini-Shogi is a lot like a maze with very long, crooked corridors, where at the end of each corridor there is either a pot of gold, or your head will be chopped off. Having a map of the maze is then cruicial...

edlich wrote:Dear all,

has anyone tried to generate opening books from scratch with engines?!

I mean why should we work with standard books from ELO 2400-2800 players if Stockfish / Komodo, Houdinis have 3300 and can generate the first N ply and more for us?!?

Best Regards
Stefan Edlich

Thomas Lincke wrote the quintessential paper on the topic.

The computer technique is called "Dropout Expansion" and it works very well for the game of checkers. In fact, the 2002 World Checkers Computer Championship held in Las Vegas featured all of the programs using this technique. I believe the current version of the Kingsrow program has 1.8 million opening book entries.

It is game-independent, but doing it for chess would take a very long time. And, some openings, like the Queen's Gambit or the Sicilian, might never evolve without being forced.

One link to get you started:

http://www.fierz.ch/strategy4.htm

I've been working on something similar, just not for chess.

Recently I saw a couple of threads here talking about things regarding to automated opening book generation / persistent database and I can make a TODO list from my experience by taking the architecture of a standard MCTS:

- Position evaluation (e.g. SF)
- Move sieving (e.g. NN or shallow multi-pv searcher)
- Database that supports fast access to billions of rows
- Indexing scheme that compresses well and preferably information complete
- Scoring algorithm that prevents your results turning into min-max
- Thousands of CPU cores or enough patience

Good news is it is totally do-able and it will mostly outperform human knowledge or statistic results, also having the ability to learn from mistakes and correct itself.

Bad news is that in order to take on a real fight or see some satisfied results, I estimate that you may need to wait for about 2000 modern CPU core years, and by then all you wish is someone else will do the same with different implementations so yours can learn their results.

The most important thing here is the shape of your ever-growing game tree, since a proper back propagation algorithm should smooth out biased child scores.

hgm wrote:Indeed. I am currently working on an opening book for mini-Shogi, where there are no games available I know of. And just a hand full of engines.

And opening theory is very important there, as most moves turn out to be 'singular', i.e. any move other than the best makes you take a large hit in evaluation. Very often the evaluations along an opening line look pretty much OK at the largest depth you can practically search, but some 20 moves deep it goes sour for one of the players. Then when you propagate the winning advantage back towards the start position, it turns out that the losing player had no alternative for his last 20+ moves, so that the game was basically already lost in the opening. But there is no way any search is going to see that at that point. Mini-Shogi is a lot like a maze with very long, crooked corridors, where at the end of each corridor there is either a pot of gold, or your head will be chopped off. Having a map of the maze is then cruicial...

I do not see why a search cannot see very long forced lines.
You can extend lines when the opponent has no alternative.

The problem is of course which lines to extend if there are also many non winning lines when the opponent has no alternative so you practically cannot extend all forced lines.