Base class for automated book building. More...
#include <SgBookBuilder.h>
Public Member Functions | |
| SgBookBuilder () | |
| virtual | ~SgBookBuilder () |
| void | Expand (int numExpansions) |
| Expands the book by expanding numExpansions leaves. | |
| void | Cover (int requiredExpansions, bool additive, const std::vector< std::vector< SgMove > > &lines) |
| Ensures each node in each line has at least the given number of expansions. | |
| void | Refresh () |
| Propagates leaf values up through the entire tree. | |
| void | IncreaseWidth () |
| Performs widening on all internal nodes that require it. | |
| float | Alpha () const |
| The parameter alpha controls state expansion (big values give rise to deeper lines, while small values perform like a BFS). | |
| void | SetAlpha (float alpha) |
| See Alpha(). | |
| bool | UseWidening () const |
| Expand only the top ExpandWidth() children of a node initially, and after every ExpansionThreshold() visits add ExpandWidth() more children. | |
| void | SetUseWidening (bool flag) |
| See UseWidening(). | |
| std::size_t | ExpandWidth () const |
| See UseWidening(). | |
| void | SetExpandWidth (std::size_t width) |
| See UseWidening(). | |
| std::size_t | ExpandThreshold () const |
| See UseWidening(). | |
| void | SetExpandThreshold (std::size_t threshold) |
| See UseWidening(). | |
| float | ComputePriority (const SgBookNode &parent, const float childValue, const float childPriority) const |
| Computes the expansion priority for the child using Alpha(), the value of the parent, and the provided values of child. | |
| virtual float | InverseEval (float eval) const =0 |
| Returns the evaluation from other player's perspective. | |
| virtual bool | IsLoss (float eval) const =0 |
| Returns true if the eval is a loss. | |
| virtual float | Value (const SgBookNode &node) const =0 |
| Returns the value of the state according this node. | |
Protected Member Functions | |
| virtual std::string | MoveString (SgMove move) const =0 |
| Converts move to a string (game dependent). | |
| virtual void | PrintMessage (std::string msg)=0 |
| Print a message to a log/debug stream. | |
| virtual void | PlayMove (SgMove move)=0 |
| Plays a move. | |
| virtual void | UndoMove (SgMove move)=0 |
| Undo last move. | |
| virtual bool | GetNode (SgBookNode &node) const =0 |
| Reads node. | |
| virtual void | WriteNode (const SgBookNode &node)=0 |
| Writes node. | |
| virtual void | FlushBook ()=0 |
| Save the book. | |
| virtual void | EnsureRootExists ()=0 |
| If current state does not exist, evaluate it and store in the book. | |
| virtual bool | GenerateMoves (std::vector< SgMove > &moves, float &value)=0 |
| Generates the set of moves to use in the book for this state. | |
| virtual void | GetAllLegalMoves (std::vector< SgMove > &moves)=0 |
| Returns all legal moves; should be a superset of those moves returned by GenerateMoves(). | |
| virtual void | EvaluateChildren (const std::vector< SgMove > &childrenToDo, std::vector< std::pair< SgMove, float > > &scores)=0 |
| Evaluate the children of the current state, return the values in a vector of pairs. | |
| virtual void | Init () |
| Hook function: called before any work is done. | |
| virtual void | Fini () |
| Hook function: called after all work is complete. | |
| virtual void | StartIteration () |
| Hook function: called at start of iteration. | |
| virtual void | EndIteration () |
| Hook function: called at end of iteration. | |
| virtual void | BeforeEvaluateChildren () |
| virtual void | AfterEvaluateChildren () |
| virtual void | ClearAllVisited ()=0 |
| virtual void | MarkAsVisited ()=0 |
| virtual bool | HasBeenVisited ()=0 |
Protected Attributes | |
| float | m_alpha |
| See Alpha(). | |
| bool | m_useWidening |
| See UseWidening(). | |
| std::size_t | m_expandWidth |
| See UseWidening(). | |
| std::size_t | m_expandThreshold |
| See UseWidening(). | |
| std::size_t | m_flushIterations |
| Number of iterations after which the db is flushed to disk. | |
Private Member Functions | |
| std::size_t | NumChildren (const std::vector< SgMove > &legal) |
| void | UpdateValue (SgBookNode &node, const std::vector< SgMove > &legal) |
| void | UpdateValue (SgBookNode &node) |
| Updates the node's value, taking special care if the value is a loss. | |
| SgMove | UpdatePriority (SgBookNode &node) |
| Re-computes node's priority and returns the best child to expand. | |
| void | DoExpansion (std::vector< SgMove > &pv) |
| bool | Refresh (bool root) |
| Refresh's each child of the given state. | |
| void | IncreaseWidth (bool root) |
| bool | ExpandChildren (std::size_t count) |
| Creates a node for each of the leaf's first count children that have not been created yet. | |
Private Attributes | |
| std::size_t | m_numEvals |
| std::size_t | m_numWidenings |
| std::size_t | m_valueUpdates |
| std::size_t | m_priorityUpdates |
| std::size_t | m_internalNodes |
| std::size_t | m_leafNodes |
| std::size_t | m_terminalNodes |
Base class for automated book building.
Definition at line 157 of file SgBookBuilder.h.
| SgBookBuilder::SgBookBuilder | ( | ) |
Definition at line 56 of file SgBookBuilder.cpp.
| SgBookBuilder::~SgBookBuilder | ( | ) | [virtual] |
Definition at line 65 of file SgBookBuilder.cpp.
| void SgBookBuilder::AfterEvaluateChildren | ( | ) | [protected, virtual] |
Definition at line 86 of file SgBookBuilder.cpp.
Referenced by ExpandChildren().
| float SgBookBuilder::Alpha | ( | ) | const |
The parameter alpha controls state expansion (big values give rise to deeper lines, while small values perform like a BFS).
Definition at line 355 of file SgBookBuilder.h.
References m_alpha.
| void SgBookBuilder::BeforeEvaluateChildren | ( | ) | [protected, virtual] |
Definition at line 81 of file SgBookBuilder.cpp.
Referenced by ExpandChildren().
| virtual void SgBookBuilder::ClearAllVisited | ( | ) | [protected, pure virtual] |
Referenced by IncreaseWidth(), and Refresh().
| float SgBookBuilder::ComputePriority | ( | const SgBookNode & | parent, | |
| const float | childValue, | |||
| const float | childPriority | |||
| ) | const |
Computes the expansion priority for the child using Alpha(), the value of the parent, and the provided values of child.
Definition at line 417 of file SgBookBuilder.cpp.
References InverseEval(), m_alpha, SgBookNode::m_value, and SG_ASSERT.
Referenced by UpdatePriority().
| void SgBookBuilder::Cover | ( | int | requiredExpansions, | |
| bool | additive, | |||
| const std::vector< std::vector< SgMove > > & | lines | |||
| ) |
Ensures each node in each line has at least the given number of expansions.
Definition at line 152 of file SgBookBuilder.cpp.
References DoExpansion(), EndIteration(), EnsureRootExists(), Fini(), FlushBook(), GetNode(), SgTimer::GetTime(), Init(), SgBookNode::IsTerminal(), SgBookNode::m_count, m_flushIterations, m_numEvals, m_numWidenings, PlayMove(), PrintMessage(), StartIteration(), SgTimer::Stop(), UndoMove(), UpdatePriority(), and UpdateValue().
| void SgBookBuilder::DoExpansion | ( | std::vector< SgMove > & | pv | ) | [private] |
Definition at line 462 of file SgBookBuilder.cpp.
References ExpandChildren(), GetNode(), SgBookNode::IncrementCount(), SgBookNode::IsLeaf(), SgBookNode::IsTerminal(), SgBookNode::m_count, m_expandThreshold, m_expandWidth, m_numWidenings, m_useWidening, PlayMove(), SG_ASSERT, UndoMove(), UpdatePriority(), UpdateValue(), and WriteNode().
| void SgBookBuilder::EndIteration | ( | ) | [protected, virtual] |
Hook function: called at end of iteration.
Default implementation does nothing.
Definition at line 76 of file SgBookBuilder.cpp.
| virtual void SgBookBuilder::EnsureRootExists | ( | ) | [protected, pure virtual] |
| virtual void SgBookBuilder::EvaluateChildren | ( | const std::vector< SgMove > & | childrenToDo, | |
| std::vector< std::pair< SgMove, float > > & | scores | |||
| ) | [protected, pure virtual] |
Evaluate the children of the current state, return the values in a vector of pairs.
Referenced by ExpandChildren().
| void SgBookBuilder::Expand | ( | int | numExpansions | ) |
Expands the book by expanding numExpansions leaves.
Definition at line 101 of file SgBookBuilder.cpp.
References DoExpansion(), EndIteration(), EnsureRootExists(), Fini(), FlushBook(), GetNode(), SgTimer::GetTime(), Init(), SgBookNode::IsTerminal(), m_flushIterations, m_numEvals, m_numWidenings, PrintMessage(), StartIteration(), and SgTimer::Stop().
| bool SgBookBuilder::ExpandChildren | ( | std::size_t | count | ) | [private] |
Creates a node for each of the leaf's first count children that have not been created yet.
Returns true if at least one new node was created, false otherwise.
Definition at line 307 of file SgBookBuilder.cpp.
References AfterEvaluateChildren(), BeforeEvaluateChildren(), EvaluateChildren(), GenerateMoves(), GetNode(), m_numEvals, PlayMove(), PrintMessage(), UndoMove(), and WriteNode().
Referenced by DoExpansion(), IncreaseWidth(), and UpdateValue().
| std::size_t SgBookBuilder::ExpandThreshold | ( | ) | const |
| std::size_t SgBookBuilder::ExpandWidth | ( | ) | const |
| void SgBookBuilder::Fini | ( | ) | [protected, virtual] |
Hook function: called after all work is complete.
Default implementation does nothing.
Definition at line 96 of file SgBookBuilder.cpp.
Referenced by Cover(), Expand(), IncreaseWidth(), and Refresh().
| virtual void SgBookBuilder::FlushBook | ( | ) | [protected, pure virtual] |
Save the book.
Referenced by Cover(), Expand(), IncreaseWidth(), and Refresh().
| virtual bool SgBookBuilder::GenerateMoves | ( | std::vector< SgMove > & | moves, | |
| float & | value | |||
| ) | [protected, pure virtual] |
Generates the set of moves to use in the book for this state.
Referenced by ExpandChildren().
| virtual void SgBookBuilder::GetAllLegalMoves | ( | std::vector< SgMove > & | moves | ) | [protected, pure virtual] |
Returns all legal moves; should be a superset of those moves returned by GenerateMoves().
Referenced by IncreaseWidth(), Refresh(), UpdatePriority(), and UpdateValue().
| virtual bool SgBookBuilder::GetNode | ( | SgBookNode & | node | ) | const [protected, pure virtual] |
Reads node.
Returns false if node does not exist.
Referenced by Cover(), DoExpansion(), Expand(), ExpandChildren(), IncreaseWidth(), NumChildren(), Refresh(), UpdatePriority(), and UpdateValue().
| virtual bool SgBookBuilder::HasBeenVisited | ( | ) | [protected, pure virtual] |
Referenced by IncreaseWidth(), and Refresh().
| void SgBookBuilder::IncreaseWidth | ( | ) |
Performs widening on all internal nodes that require it.
Use this after increasing ExpandWidth() or decreasing ExpandThreshold() on an already existing book to update all the internal nodes with the new required width. Will do nothing unless parameters were changed accordingly.
Does not propagate values up tree, run Refresh() afterwards to do so.
Definition at line 271 of file SgBookBuilder.cpp.
References ClearAllVisited(), Fini(), FlushBook(), SgTimer::GetTime(), Init(), m_numEvals, m_numWidenings, m_useWidening, PrintMessage(), and SgTimer::Stop().
Referenced by IncreaseWidth().
| void SgBookBuilder::IncreaseWidth | ( | bool | root | ) | [private] |
Definition at line 560 of file SgBookBuilder.cpp.
References ExpandChildren(), GetAllLegalMoves(), GetNode(), HasBeenVisited(), IncreaseWidth(), SgBookNode::IsLeaf(), SgBookNode::IsTerminal(), SgBookNode::m_count, m_expandThreshold, m_expandWidth, m_numWidenings, MarkAsVisited(), MoveString(), PlayMove(), PrintMessage(), and UndoMove().
| void SgBookBuilder::Init | ( | ) | [protected, virtual] |
Hook function: called before any work is done.
Default implementation does nothing.
Definition at line 91 of file SgBookBuilder.cpp.
Referenced by Cover(), Expand(), IncreaseWidth(), and Refresh().
| virtual float SgBookBuilder::InverseEval | ( | float | eval | ) | const [pure virtual] |
Returns the evaluation from other player's perspective.
Referenced by ComputePriority(), and UpdateValue().
| virtual bool SgBookBuilder::IsLoss | ( | float | eval | ) | const [pure virtual] |
Returns true if the eval is a loss.
Referenced by UpdateValue().
| virtual void SgBookBuilder::MarkAsVisited | ( | ) | [protected, pure virtual] |
Referenced by IncreaseWidth(), and Refresh().
| virtual std::string SgBookBuilder::MoveString | ( | SgMove | move | ) | const [protected, pure virtual] |
Converts move to a string (game dependent).
Referenced by IncreaseWidth(), and Refresh().
| std::size_t SgBookBuilder::NumChildren | ( | const std::vector< SgMove > & | legal | ) | [private] |
Definition at line 352 of file SgBookBuilder.cpp.
References GetNode(), PlayMove(), and UndoMove().
Referenced by UpdateValue().
| virtual void SgBookBuilder::PlayMove | ( | SgMove | move | ) | [protected, pure virtual] |
Plays a move.
Referenced by Cover(), DoExpansion(), ExpandChildren(), IncreaseWidth(), NumChildren(), Refresh(), UpdatePriority(), and UpdateValue().
| virtual void SgBookBuilder::PrintMessage | ( | std::string | msg | ) | [protected, pure virtual] |
Print a message to a log/debug stream.
Referenced by Cover(), Expand(), ExpandChildren(), IncreaseWidth(), Refresh(), and UpdateValue().
| bool SgBookBuilder::Refresh | ( | bool | root | ) | [private] |
Refresh's each child of the given state.
UpdateValue() and UpdatePriority() are called on internal nodes. Returns true if state exists in book. Book Refresh
Definition at line 513 of file SgBookBuilder.cpp.
References GetAllLegalMoves(), GetNode(), HasBeenVisited(), SgBookNode::IsLeaf(), SgBookNode::IsTerminal(), m_internalNodes, m_leafNodes, SgBookNode::m_priority, m_priorityUpdates, m_terminalNodes, m_valueUpdates, MarkAsVisited(), MoveString(), PlayMove(), PrintMessage(), Refresh(), UndoMove(), UpdatePriority(), UpdateValue(), Value(), and WriteNode().
| void SgBookBuilder::Refresh | ( | ) |
Propagates leaf values up through the entire tree.
Definition at line 236 of file SgBookBuilder.cpp.
References ClearAllVisited(), Fini(), FlushBook(), SgTimer::GetTime(), Init(), m_internalNodes, m_leafNodes, m_numEvals, m_numWidenings, m_priorityUpdates, m_terminalNodes, m_valueUpdates, PrintMessage(), and SgTimer::Stop().
Referenced by Refresh().
| void SgBookBuilder::SetAlpha | ( | float | alpha | ) |
| void SgBookBuilder::SetExpandThreshold | ( | std::size_t | threshold | ) |
| void SgBookBuilder::SetExpandWidth | ( | std::size_t | width | ) |
| void SgBookBuilder::SetUseWidening | ( | bool | flag | ) |
| void SgBookBuilder::StartIteration | ( | ) | [protected, virtual] |
Hook function: called at start of iteration.
Default implementation does nothing.
Definition at line 71 of file SgBookBuilder.cpp.
| virtual void SgBookBuilder::UndoMove | ( | SgMove | move | ) | [protected, pure virtual] |
Undo last move.
Referenced by Cover(), DoExpansion(), ExpandChildren(), IncreaseWidth(), NumChildren(), Refresh(), UpdatePriority(), and UpdateValue().
| SgMove SgBookBuilder::UpdatePriority | ( | SgBookNode & | node | ) | [private] |
Re-computes node's priority and returns the best child to expand.
Requires that UpdateValue() has been called on this node. Returns SG_NULLMOVE if node has no children.
Definition at line 429 of file SgBookBuilder.cpp.
References ComputePriority(), GetAllLegalMoves(), GetNode(), SgBookNode::m_priority, PlayMove(), SG_NULLMOVE, UndoMove(), and Value().
Referenced by Cover(), DoExpansion(), and Refresh().
| void SgBookBuilder::UpdateValue | ( | SgBookNode & | node | ) | [private] |
Updates the node's value, taking special care if the value is a loss.
In this case, widenings are performed until a non-loss child is added or no new children are added. The node is then set with the proper value.
Definition at line 392 of file SgBookBuilder.cpp.
References ExpandChildren(), GetAllLegalMoves(), IsLoss(), m_expandWidth, m_numWidenings, NumChildren(), PrintMessage(), UpdateValue(), and Value().
| void SgBookBuilder::UpdateValue | ( | SgBookNode & | node, | |
| const std::vector< SgMove > & | legal | |||
| ) | [private] |
Definition at line 366 of file SgBookBuilder.cpp.
References GetNode(), InverseEval(), SgBookNode::m_value, PlayMove(), UndoMove(), and Value().
Referenced by Cover(), DoExpansion(), Refresh(), and UpdateValue().
| bool SgBookBuilder::UseWidening | ( | ) | const |
Expand only the top ExpandWidth() children of a node initially, and after every ExpansionThreshold() visits add ExpandWidth() more children.
Definition at line 365 of file SgBookBuilder.h.
References m_useWidening.
| virtual float SgBookBuilder::Value | ( | const SgBookNode & | node | ) | const [pure virtual] |
Returns the value of the state according this node.
Ie, takes into account swap moves, etc.
Referenced by Refresh(), UpdatePriority(), and UpdateValue().
| virtual void SgBookBuilder::WriteNode | ( | const SgBookNode & | node | ) | [protected, pure virtual] |
Writes node.
Referenced by DoExpansion(), ExpandChildren(), and Refresh().
float SgBookBuilder::m_alpha [protected] |
See Alpha().
Definition at line 240 of file SgBookBuilder.h.
Referenced by Alpha(), ComputePriority(), and SetAlpha().
std::size_t SgBookBuilder::m_expandThreshold [protected] |
See UseWidening().
Definition at line 249 of file SgBookBuilder.h.
Referenced by DoExpansion(), ExpandThreshold(), IncreaseWidth(), and SetExpandThreshold().
std::size_t SgBookBuilder::m_expandWidth [protected] |
See UseWidening().
Definition at line 246 of file SgBookBuilder.h.
Referenced by DoExpansion(), ExpandWidth(), IncreaseWidth(), SetExpandWidth(), and UpdateValue().
std::size_t SgBookBuilder::m_flushIterations [protected] |
Number of iterations after which the db is flushed to disk.
Definition at line 252 of file SgBookBuilder.h.
std::size_t SgBookBuilder::m_internalNodes [private] |
Definition at line 328 of file SgBookBuilder.h.
Referenced by Refresh().
std::size_t SgBookBuilder::m_leafNodes [private] |
Definition at line 330 of file SgBookBuilder.h.
Referenced by Refresh().
std::size_t SgBookBuilder::m_numEvals [private] |
Definition at line 320 of file SgBookBuilder.h.
Referenced by Cover(), Expand(), ExpandChildren(), IncreaseWidth(), and Refresh().
std::size_t SgBookBuilder::m_numWidenings [private] |
Definition at line 322 of file SgBookBuilder.h.
Referenced by Cover(), DoExpansion(), Expand(), IncreaseWidth(), Refresh(), and UpdateValue().
std::size_t SgBookBuilder::m_priorityUpdates [private] |
Definition at line 326 of file SgBookBuilder.h.
Referenced by Refresh().
std::size_t SgBookBuilder::m_terminalNodes [private] |
Definition at line 332 of file SgBookBuilder.h.
Referenced by Refresh().
bool SgBookBuilder::m_useWidening [protected] |
See UseWidening().
Definition at line 243 of file SgBookBuilder.h.
Referenced by DoExpansion(), IncreaseWidth(), SetUseWidening(), and UseWidening().
std::size_t SgBookBuilder::m_valueUpdates [private] |
Definition at line 324 of file SgBookBuilder.h.
Referenced by Refresh().