Generate Opening Book from Scratch

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
edlich
Posts: 8
Joined: Wed Jul 13, 2011 10:00 am
Location: Berlin
Contact:

Generate Opening Book from Scratch

Post by edlich » Mon Feb 27, 2017 12:26 pm

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

Milos
Posts: 3295
Joined: Wed Nov 25, 2009 12:47 am

Re: Generate Opening Book from Scratch

Post by Milos » Mon Feb 27, 2017 12:29 pm

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

Stan Arts
Posts: 177
Joined: Fri Feb 14, 2014 9:53 pm
Location: the Netherlands

Re: Generate Opening Book from Scratch

Post by Stan Arts » Mon Feb 27, 2017 12:39 pm

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.

User avatar
edlich
Posts: 8
Joined: Wed Jul 13, 2011 10:00 am
Location: Berlin
Contact:

Re: Generate Opening Book from Scratch

Post by edlich » Mon Feb 27, 2017 12:56 pm

Thanks a lot for the insightful answers!

jdart
Posts: 3677
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Generate Opening Book from Scratch

Post by jdart » Mon Feb 27, 2017 3:08 pm

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

jorose
Posts: 198
Joined: Thu Jan 22, 2015 2:21 pm
Location: Zurich, Switzerland
Full name: Jonathan Rosenthal

Re: Generate Opening Book from Scratch

Post by jorose » Thu Mar 02, 2017 9:16 am

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.

User avatar
hgm
Posts: 23008
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Generate Opening Book from Scratch

Post by hgm » Thu Mar 02, 2017 10:44 am

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

Ed Trice
Posts: 100
Joined: Fri Sep 19, 2014 3:03 am

Re: Generate Opening Book from Scratch

Post by Ed Trice » Sun Mar 05, 2017 12:24 am

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

noobpwnftw
Posts: 287
Joined: Sun Nov 08, 2015 10:10 pm

Re: Generate Opening Book from Scratch

Post by noobpwnftw » Mon Mar 06, 2017 12:16 am

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.

Uri Blass
Posts: 8335
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Generate Opening Book from Scratch

Post by Uri Blass » Mon Mar 06, 2017 6:54 am

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.

Post Reply