Search-Based Opening Book Construction

[jack512]

Search-Based Opening Book Construction
Abstract - A procedure is given to construct a chess opening book (OB) to be played against another, given OB. OBs for White and Black are constructed separately. The chess positions of the OB being constructed are represented as nodes in a Directed Acyclic Graph (DAG) from the starting position. Each position carries a probability that a game played between the given and being-constructed OB will eventually reach that position. Assuming an OB is being constructed for White, a priority queue repeatedly chooses the highest-probability unexpanded node for expansion. If it is Black’s turn to move, the children are assigned probabilities according to the given OB. If it is White’s turn to move, a search is performed to find the best move at the node, which is assigned probability one. Depth of search is controlled as a function of the probability of the node being expanded. Several OBs for White, representing a range of build effort, were constructed to play against the OB that comes with Crafty version 25.0.1. The strongest took 12 cpu-days to build, and scored 62.7% in a 1000-game match against the 25.0.1 OB, demonstrating the effectiveness of the approach.

Acknowledgment
Thanks go to Prof. Robert Hyatt, who has made available in Crafty a useful open-source platform for experimentation in computer chess.

Full manuscript here: https://drive.google.com/open?id=0B2pvW ... UpkRE0tem8

[jwes]

Interesting article. I have a few questions:
1. How do you change the tree into a DAG?
a. If you use the naive approach and assume a hash hit is a transposition, a false hit is almost guaranteed to crash your program.
b. How do you ensure it is acyclic?
2. If you change your engine, do you have to recalculate your book?
3. Is the source code available?

[jack512]

1. How do you change the tree into a DAG?

First of all, one general thing to keep in mind is that space and time efficiency are very much secondary considerations in my data structures and algorithms. My DAG and Priority Queue and Binary Tree manipulations and Given Book lookups are only done in between complete standard Crafty alpha-beta searches. No matter how wasteful I am, my time and space requirements are insignificant compared to the time and space requirements of the alpha-beta search.

I use a standard linked-list representation for a DAG. Chess positions are nodes, moves are arcs from one position to another. The position contains the fenstring characterizing the position, and a linked list of the moves into this position, and a linked list of the moves out of the position. Each move in the list contains a pointer to the position it is a move to or from.

I also have a binary-tree lookup structure for all positions, patterned after Cormen Leiserson & Rivest’s Intro to Algorithms 1993. Each node of the binary tree has a pointer to its position. The priority queue is patterned after Sedgwick’s Algorithms in C 1990.

If I want to add a position to the DAG, I first look for it using the binary tree. If it’s not there, I create a new position and add the move to its parent list and its parent’s child list, and add the position to the binary tree and priority queue. If it is there, I first check to see if adding it to the DAG would create a cycle. If it would I don’t add the position to the DAG: it is as though that move doesn’t exist. If no cycle danger, I add the move to the child’s parent list and the parent’s child list.

a. If you use the naive approach and assume a hash hit is a transposition, a false hit is almost guaranteed to crash your program.

As mentioned earlier, a binary tree with fenstring key is used for transposition lookup, so no false hits.

b. How do you ensure it is acyclic?

As mentioned earlier, I check to see if adding a transposition move would create a cycle. This check is done by following all possible paths back to the DAG root looking for the position. Again, this is one of those obscenely inefficient things we wouldn’t normally do, but it is insignificant compared to the time spent on searches. These cycles are very rare, and did not happen at all in OB17 thru OB28, only a handful in OB29. Of course they have to be detected and handled in the OB builder, but ignoring the move is ok because they happen rarely and only deep in the OB where the position’s probability is very low, like several parts per million. So the effect of ignoring the move is that once in a blue moon in a game, a potential repeated position will occur, and White will go out of book because its OB ignores the move. But the White engine will still do the right thing because it has its game history to deal with repeated positions.

2. If you change your engine, do you have to recalculate your book?

Yes. That would be advisable. As I emphasize in the manuscript, one of the things we’ve learned in the history of computer chess is that the OB should be well-matched to the engine. This is also a good reason why the OB should be handled by the chess program, not the GUI.

3. Is the source code available?

After I port my code, which is about 1,000 lines of code, to version 25.1 of Crafty, I will be sending it to Prof. Hyatt and anybody else who sends me their email address.

[Milos]

Search-Based Opening Book Construction
Abstract - A procedure is given to construct a chess opening book (OB) to be played against another, given OB. OBs for White and Black are constructed separately. The chess positions of the OB being constructed are represented as nodes in a Directed Acyclic Graph (DAG) from the starting position. Each position carries a probability that a game played between the given and being-constructed OB will eventually reach that position. Assuming an OB is being constructed for White, a priority queue repeatedly chooses the highest-probability unexpanded node for expansion. If it is Black’s turn to move, the children are assigned probabilities according to the given OB.

Another effort like Brainfish, lol.
Why ppl think it takes any effort to realize minimax with pruning based on score and have need to use obscure terminology???
And translating score to probability is really not much of achievement.

[Milos]

a. If you use the naive approach and assume a hash hit is a transposition, a false hit is almost guaranteed to crash your program.

Gee, just increase number of hash bits. Ever heard ppl got perft(14) and no hash misses, imagine???

[Milos]

Full manuscript here: https://drive.google.com/open?id=0B2pvW ... UpkRE0tem8

One more thing, you are testing against Crafty book, how do you maintain that both engines leave the book at the same time?
If that is not maintained than the engine with the longer book will almost always score better not because its book is better, but because it will have more thinking time!

[Dann Corbit]

Search-Based Opening Book Construction
Abstract - A procedure is given to construct a chess opening book (OB) to be played against another, given OB. OBs for White and Black are constructed separately. The chess positions of the OB being constructed are represented as nodes in a Directed Acyclic Graph (DAG) from the starting position. Each position carries a probability that a game played between the given and being-constructed OB will eventually reach that position. Assuming an OB is being constructed for White, a priority queue repeatedly chooses the highest-probability unexpanded node for expansion. If it is Black’s turn to move, the children are assigned probabilities according to the given OB.

Another effort like Brainfish, lol.
Why ppl think it takes any effort to realize minimax with pruning based on score and have need to use obscure terminology???
And translating score to probability is really not much of achievement.

Brain fish was enormously successful. These attempts to improve openings are very interesting to those who would like to see our knowledge advanced.

It is nice to see people trying new ways to advance our understanding of the game of chess.

Did you ever see a project that you actually liked or do you just hate everything?

[Dann Corbit]

P.S.
The Brain fish approach clearly works:
http://spcc.beepworld.de

[Milos]

Did you ever see a project that you actually liked or do you just hate everything?

I do actually like Brainfish, which I said quite a few times at this forum, I don't know how you realized I don't like it??? I don't appreciate their approach to have the free book only in their (SF) format, not making it publicly available in other formats, except as a commercial, but that's another story.
I like Stockfish, Arena, Winboard and many other projects.
This work is clearly replicating what Brainfish is doing, but it seams far from optimal realization.
Do you think that some projects are beyond critic???

[Dann Corbit]

Did you ever see a project that you actually liked or do you just hate everything?

I do actually like Brainfish, which I said quite a few times at this forum, I don't know how you realized I don't like it??? I don't appreciate their approach to have the free book only in their (SF) format, not making it publicly available in other formats, except as a commercial, but that's another story.
I like Stockfish, Arena, Winboard and many other projects.
This work is clearly replicating what Brainfish is doing, but it seams far from optimal realization.
Do you think that some projects are beyond critic???

Nothing is beyond criticism, and nothing is toxic to praise.
It seems a lot of interesting projects you find disturbing for some reason.
That is OK but I find it puzzling.
Sometimes it is possible to tell that some approach will not work well from first principles.
This project has similarities to Brain fish but there are some important differences.
I don't see anything negative about this work and his publication of the source means that other can repeat or even expand his experiments.