Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages

# SgBookBuilder.h

Go to the documentation of this file.
```00001 //----------------------------------------------------------------------------
00002 /** @file SgBookBuilder.hpp
00003  */
00004 //----------------------------------------------------------------------------
00005
00006 #ifndef SG_BOOKBUILDER_HPP
00007 #define SG_BOOKBUILDER_HPP
00008
00009 #include "SgSystem.h"
00010 #include "SgMove.h"
00011 #include <cmath>
00012 #include <iostream>
00013 #include <iomanip>
00014 #include <vector>
00015
00016 //----------------------------------------------------------------------------
00017
00018 /** @defgroup openingbook Automatic Opening Book Construction
00019     Game independent Opening Book Construction.
00020
00021     Code is based on Thomas R. Lincke's paper "Strategies for the
00022     Automatic Construction of Opening Books" published in 2001.
00023
00024     We make the following adjustments:
00025     - Neither side is assumed to be the book player, so the expansion
00026       formula is identical for all nodes (see page 80 of the paper). In other
00027       words, both sides can play sub-optimal moves.
00028     - A single node for each state is stored, such that transpositions
00029       are not re-computed. Hence the book forms a DAG of states, not a tree.
00030     - Progressive widening is used on internal nodes to restrict the
00031       search initially.
00032
00033     We also think there is a typo with respect to the formula of epo_i on
00034     page 80. Namely, since p_i is the negamax of p_{s_j}s, then we should
00035     sum the values to find the distance from optimal, not subtract. That is,
00036     we use epo_i = 1 + min(s_j) (epb_{s_j} + alpha*(p_i + p_{s_j}) instead.
00037 */
00038
00039 //----------------------------------------------------------------------------
00040
00041 /** State in the Opening Book.
00042     @ingroup openingbook
00043  */
00044 class SgBookNode
00045 {
00046 public:
00047     //------------------------------------------------------------------------
00048
00049     /** Priority of newly created leaves. */
00050     static const float LEAF_PRIORITY = 0.0;
00051
00052     //------------------------------------------------------------------------
00053
00054     /** Heuristic value of this state. */
00055     float m_heurValue;
00056
00057     /** Minmax value of this state. */
00058     float m_value;
00059
00060     /** Expansion priority. */
00061     float m_priority;
00062
00063     /** Number of times this node was explored. */
00064     unsigned m_count;
00065
00066     //------------------------------------------------------------------------
00067
00068     SgBookNode();
00069
00070     SgBookNode(float heuristicValue);
00071
00072     SgBookNode(const std::string& str);
00073
00074     /** Returns true if this node is a leaf in the opening book, ie,
00075         its count is zero. */
00076     bool IsLeaf() const;
00077
00078     /** Returns true if propagated value is a win or a loss. */
00079     bool IsTerminal() const;
00080
00081     /** Increment the node's counter. */
00082     void IncrementCount();
00083
00084     /** Outputs node in string form. */
00085     std::string ToString() const;
00086
00087 private:
00088     void FromString(const std::string& str);
00089 };
00090
00091 inline SgBookNode::SgBookNode()
00092 {
00093 }
00094
00095 inline SgBookNode::SgBookNode(float heuristicValue)
00096     : m_heurValue(heuristicValue),
00097       m_value(heuristicValue),
00098       m_priority(LEAF_PRIORITY),
00099       m_count(0)
00100 {
00101 }
00102
00103 inline SgBookNode::SgBookNode(const std::string& str)
00104 {
00105     FromString(str);
00106 }
00107
00108 inline void SgBookNode::IncrementCount()
00109 {
00110     m_count++;
00111 }
00112
00113 /** Extends standard stream output operator for SgBookNodes. */
00114 inline std::ostream& operator<<(std::ostream& os, const SgBookNode& node)
00115 {
00116     os << node.ToString();
00117     return os;
00118 }
00119
00120 //----------------------------------------------------------------------------
00121
00122 /** @page bookrefresh Book Refresh
00123     @ingroup openingbook
00124
00125     Due to transpositions, it is possible that a node's value changes,
00126     but because the node has not been revisited yet the information is
00127     not passed to its parent. Refreshing the book forces these
00128     propagations.
00129
00130     SgBookBuilder::Refresh() computes the correct propagation value for
00131     all internal nodes given the current set of leaf nodes. A node in
00132     which SgBookNode::IsLeaf() is true is treated as a leaf even
00133     if it has children in the book (ie, children from transpositions)
00134 */
00135
00136 //----------------------------------------------------------------------------
00137
00138 /** Base class for automated book building.
00139
00140     @ingroup openingbook
00141 */
00142 class SgBookBuilder
00143 {
00144 public:
00145     SgBookBuilder();
00146
00147     virtual ~SgBookBuilder();
00148
00149     //---------------------------------------------------------------------
00150
00151     /** Expands the book by expanding numExpansions leaves. */
00152     void Expand(int numExpansions);
00153
00154     /** Propagates leaf values up through the entire tree.
00155         @ref bookrefresh. */
00156     void Refresh();
00157
00158     /** Performs widening on all internal nodes that require it. Use
00159         this after increasing ExpandWidth() or decreasing
00160         ExpandThreshold() on an already existing book to update all
00161         the internal nodes with the new required width. Will do
00162         nothing unless parameters were changed accordingly.
00163
00164         Does not propagate values up tree, run Refresh() afterwards to
00165         do so. */
00166     void IncreaseWidth();
00167
00168     //---------------------------------------------------------------------
00169
00170     float ComputePriority(const SgBookNode& parent, const float childValue,
00171                           const float childPriority) const;
00172
00173     /** Returns the evaluation from other player's perspective. */
00174     virtual float InverseEval(float eval) const = 0;
00175
00176     /** Returns true if the eval is a loss. */
00177     virtual bool IsLoss(float eval) const = 0;
00178
00179     /** Returns the value of the state according this node.
00180         Ie, takes into account swap moves, etc. */
00181     virtual float Value(const SgBookNode& node) const = 0;
00182
00183     //---------------------------------------------------------------------
00184
00185     /** The parameter alpha controls state expansion (big values give
00186         rise to deeper lines, while small values perform like a
00187         BFS). */
00188     float Alpha() const;
00189
00190     /** See Alpha() */
00191     void SetAlpha(float alpha);
00192
00193     /** Expand only the top ExpandWidth() children of a node
00194         initially, and after every ExpansionThreshold() visits add
00195         ExpandWidth() more children. */
00196     bool UseWidening() const;
00197
00198     /** See UseWidening() */
00199     void SetUseWidening(bool flag);
00200
00201     /** See UseWidening() */
00202     std::size_t ExpandWidth() const;
00203
00204     /** See UseWidening() */
00205     void SetExpandWidth(std::size_t width);
00206
00207     /** See UseWidening() */
00208     std::size_t ExpandThreshold() const;
00209
00210     /** See UseWidening() */
00211     void SetExpandThreshold(std::size_t threshold);
00212
00213 protected:
00214     /** See Alpha() */
00215     float m_alpha;
00216
00217     /** See UseWidening() */
00218     bool m_use_widening;
00219
00220     /** See UseWidening() */
00221     std::size_t m_expand_width;
00222
00223     /** See UseWidening() */
00224     std::size_t m_expand_threshold;
00225
00226     /** Number of iterations after which the db is flushed to disk. */
00227     std::size_t m_flush_iterations;
00228
00229     //------------------------------------------------------------------------
00230
00231     virtual void PrintMessage(std::string msg) = 0;
00232
00233     virtual void PlayMove(SgMove move) = 0;
00234
00235     virtual void UndoMove(SgMove move) = 0;
00236
00237     /** Reads node. Returns false if node does not exist. */
00238     virtual bool GetNode(SgBookNode& node) const = 0;
00239
00240     /** Writes node. */
00241     virtual void WriteNode(const SgBookNode& node) = 0;
00242
00243     virtual void FlushBook() = 0;
00244
00245     /** If current state does not exist, evaluate it and store in the
00246         book. */
00247     virtual void EnsureRootExists() = 0;
00248
00249     /** Generates the set of moves to use in the book for this state. */
00250     virtual bool GenerateMoves(std::vector<SgMove>& moves, float& value) = 0;
00251
00252     /** Returns all legal moves; should be a superset of those moves
00253         returned by GenerateMoves() */
00254     virtual void GetAllLegalMoves(std::vector<SgMove>& moves) = 0;
00255
00256     /** Evaluate the children of the current state, return the values
00257         in a vector of pairs. */
00258     virtual void EvaluateChildren(const std::vector<SgMove>& childrenToDo,
00259                     std::vector<std::pair<SgMove, float> >& scores) = 0;
00260
00261     /** Hook function: called before any work is done.
00262         Default implementation does nothing. */
00263     virtual void Init();
00264
00265     /** Hook function: called after all work is complete.
00266         Default implementation does nothing. */
00267     virtual void Fini();
00268
00269     /** Hook function: called at start of iteration.
00270         Default implementation does nothing. */
00271     virtual void StartIteration(int interation);
00272
00273     /** Hook function: called at end of iteration.
00274         Default implementation does nothing. */
00275     virtual void EndIteration();
00276
00277     virtual void BeforeEvaluateChildren();
00278
00279     virtual void AfterEvaluateChildren();
00280
00281     virtual void ClearAllVisited() = 0;
00282
00283     virtual void MarkAsVisited() = 0;
00284
00285     virtual bool HasBeenVisited() = 0;
00286
00287 private:
00288     std::size_t m_num_evals;
00289
00290     std::size_t m_num_widenings;
00291
00293
00295
00296     std::size_t m_internal_nodes;
00297
00298     std::size_t m_leaf_nodes;
00299
00300     std::size_t m_terminal_nodes;
00301
00302     //---------------------------------------------------------------------
00303
00304     std::size_t NumChildren(const std::vector<SgMove>& legal);
00305
00306     void UpdateValue(SgBookNode& node, const std::vector<SgMove>& legal);
00307
00308     void UpdateValue(SgBookNode& node);
00309
00310     SgMove UpdatePriority(SgBookNode& node);
00311
00312     void DoExpansion(std::vector<SgMove>& pv);
00313
00314     bool Refresh(bool root);
00315
00316     void IncreaseWidth(bool root);
00317
00318     bool ExpandChildren(std::size_t count);
00319 };
00320
00321 //----------------------------------------------------------------------------
00322
00323 inline float SgBookBuilder::Alpha() const
00324 {
00325     return m_alpha;
00326 }
00327
00328 inline void SgBookBuilder::SetAlpha(float alpha)
00329 {
00330     m_alpha = alpha;
00331 }
00332
00333 inline bool SgBookBuilder::UseWidening() const
00334 {
00335     return m_use_widening;
00336 }
00337
00338 inline void SgBookBuilder::SetUseWidening(bool flag)
00339 {
00340     m_use_widening = flag;
00341 }
00342
00343 inline std::size_t SgBookBuilder::ExpandWidth() const
00344 {
00345     return m_expand_width;
00346 }
00347
00348 inline void SgBookBuilder::SetExpandWidth(std::size_t width)
00349 {
00350     m_expand_width = width;
00351 }
00352
00353 inline std::size_t SgBookBuilder::ExpandThreshold() const
00354 {
00355     return m_expand_threshold;
00356 }
00357
00358 inline void SgBookBuilder::SetExpandThreshold(std::size_t threshold)
00359 {
00360     m_expand_threshold = threshold;
00361 }
00362
00363 //----------------------------------------------------------------------------
00364
00365 #endif // SG_BOOKBUILDER_HPP
```

17 Jun 2010 Doxygen 1.4.7