Opening book trees

[Robert Pope]

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]

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

[phhnguyen]

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

[hgm]

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]

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]

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.