Automatic Opening Book Construction

---

Detailed Description

Game independent Opening Book Construction.

Code is based on Thomas R. Lincke's paper "Strategies for the Automatic Construction of Opening Books" published in 2001.

We make the following adjustments:

• Neither side is assumed to be the book player, so the expansion formula is identical for all nodes (see page 80 of the paper). In other words, both sides can play sub-optimal moves.
• A single node for each state is stored, such that transpositions are not re-computed. Hence the book forms a DAG of states, not a tree.
• Progressive widening is used on internal nodes to restrict the search initially.

We also think there is a typo with respect to the formula of epo_i on page 80. Namely, since p_i is the negamax of p_{s_j}s, then we should sum the values to find the distance from optimal, not subtract. That is, we use epo_i = 1 + min(s_j) (epb_{s_j} + alpha*(p_i + p_{s_j}) instead.

Classes
class	SgBookNode
	State in the Opening Book. More...
class	SgBookBuilder
	Base class for automated book building. More...

Book Refresh

Due to transpositions, it is possible that a node's value changes, but because the node has not been revisited yet the information is not passed to its parent.

Refreshing the book forces these propagations.

SgBookBuilder::Refresh() computes the correct propagation value for all internal nodes given the current set of leaf nodes. A node in which SgBookNode::IsLeaf() is true is treated as a leaf even if it has children in the book (ie, children from transpositions)

---

17 Jun 2010 Doxygen 1.4.7