Opening book trees

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Robert Pope
Posts: 510
Joined: Sat Mar 25, 2006 7:27 pm

Opening book trees

Post by Robert Pope » Mon Feb 27, 2017 3:41 am

I decided I wanted to play around a bit with opening books for my engine, both deepening lines that get played, and making better selections than the current random picks.

I've translated my existing book of 9000 opening lines into a database of 50,000 positions, each with a search score and best move. I thought I would try minimaxing the leaf evaluations and see what that did, but I realized that a straight minimax will allow arbitrarily long sequences, due to piece shuffling, despite positions all coming from play lines of no more than 10 moves.

Any ideas how to deal with that?

Also, any suggestions of existing research that I should read up on?

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

Re: Opening book trees

Post by jdart » Mon Feb 27, 2017 4:06 am

I am not quite clear what the issue is. If it is repetitions you are worried about then you can just consider them book exits. I make my engine search instead of retrieve moves once a repetition is detected, so that it can decide if it wants to play for a draw or win. (I am not saying this is optimal but it is one solution). With no repetitions you have a DAG and you can minimax that.

You might take a look at http://www.bookbuilder.nl/ - I believe this does minimax.

--Jon

User avatar
phhnguyen
Posts: 383
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: Opening book trees

Post by phhnguyen » Mon Feb 27, 2017 5:22 am

Robert Pope wrote:I decided I wanted to play around a bit with opening books for my engine, both deepening lines that get played, and making better selections than the current random picks.

I've translated my existing book of 9000 opening lines into a database of 50,000 positions, each with a search score and best move. I thought I would try minimaxing the leaf evaluations and see what that did, but I realized that a straight minimax will allow arbitrarily long sequences, due to piece shuffling, despite positions all coming from play lines of no more than 10 moves.

Any ideas how to deal with that?

Also, any suggestions of existing research that I should read up on?
Just OT question: why you need to add a best move to each position? Look like your book may have trouble of consistency because of that

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

Re: Opening book trees

Post by hgm » Mon Feb 27, 2017 8:41 am

You should do a minimax search from the root, pruning all moves that leave the book, score repetitions as zero, and use the book score in positions where all moves leave the book. This assumes the book is connected, and that when you searched any daughter position, you searched the position to which the best move led. If the latter is not satisfied, you should allow 'stand pat' on the score of the node itself.

More precisely, you should first replace the score of a position by the (negated) score of the best-move daughter if the latter has equal or higher depth. (And thus keep the score of the node itself, when the best-move daughter is not in the book.) That gives you the best estimate of the score of the best move. If any of the other daughters would produce a higher score, you should use that score instead.

Robert Pope
Posts: 510
Joined: Sat Mar 25, 2006 7:27 pm

Re: Opening book trees

Post by Robert Pope » Mon Feb 27, 2017 3:28 pm

phhnguyen wrote:
Robert Pope wrote:I decided I wanted to play around a bit with opening books for my engine, both deepening lines that get played, and making better selections than the current random picks.

I've translated my existing book of 9000 opening lines into a database of 50,000 positions, each with a search score and best move. I thought I would try minimaxing the leaf evaluations and see what that did, but I realized that a straight minimax will allow arbitrarily long sequences, due to piece shuffling, despite positions all coming from play lines of no more than 10 moves.

Any ideas how to deal with that?

Also, any suggestions of existing research that I should read up on?
Just OT question: why you need to add a best move to each position? Look like your book may have trouble of consistency because of that
In essence, it adds another ply to the book, because we know not just the score of the leaf node, but the move that gave rise to it.

Robert Pope
Posts: 510
Joined: Sat Mar 25, 2006 7:27 pm

Re: Opening book trees

Post by Robert Pope » Mon Feb 27, 2017 3:36 pm

jdart wrote:I am not quite clear what the issue is. If it is repetitions you are worried about then you can just consider them book exits. I make my engine search instead of retrieve moves once a repetition is detected, so that it can decide if it wants to play for a draw or win. (I am not saying this is optimal but it is one solution). With no repetitions you have a DAG and you can minimax that.

You might take a look at http://www.bookbuilder.nl/ - I believe this does minimax.

--Jon
I think it's related to repetitions. If my minimax were to visit every node once, a full 20 ply search would hit every position and be done in a couple minutes. As it is, a 10 ply perft covers as many positions as are in the full book, and every ply about doubles that.

It didn't occur to me about excluding repetitions, since that's not something you check for in perft, but you would in a real search. So I expect that will address it - thanks.

Post Reply