#include <SgBookBuilder.h>
Definition at line 142 of file SgBookBuilder.h.
Public Member Functions | |
| SgBookBuilder () | |
| virtual | ~SgBookBuilder () |
| void | Expand (int numExpansions) |
| Expands the book by expanding numExpansions leaves. | |
| void | Refresh () |
| Propagates leaf values up through the entire tree. | |
| void | IncreaseWidth () |
| Performs widening on all internal nodes that require it. | |
| float | ComputePriority (const SgBookNode &parent, const float childValue, const float childPriority) const |
| 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. | |
| 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(). | |
Protected Member Functions | |
| virtual void | PrintMessage (std::string msg)=0 |
| virtual void | PlayMove (SgMove move)=0 |
| virtual void | UndoMove (SgMove move)=0 |
| virtual bool | GetNode (SgBookNode &node) const =0 |
| Reads node. | |
| virtual void | WriteNode (const SgBookNode &node)=0 |
| Writes node. | |
| virtual void | FlushBook ()=0 |
| 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 (int interation) |
| 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_use_widening |
| See UseWidening(). | |
| std::size_t | m_expand_width |
| See UseWidening(). | |
| std::size_t | m_expand_threshold |
| See UseWidening(). | |
| std::size_t | m_flush_iterations |
| 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_num_evals |
| std::size_t | m_num_widenings |
| std::size_t | m_value_updates |
| std::size_t | m_priority_updates |
| std::size_t | m_internal_nodes |
| std::size_t | m_leaf_nodes |
| std::size_t | m_terminal_nodes |
| SgBookBuilder::SgBookBuilder | ( | ) |
Definition at line 53 of file SgBookBuilder.cpp.
| SgBookBuilder::~SgBookBuilder | ( | ) | [virtual] |
Definition at line 62 of file SgBookBuilder.cpp.
| void SgBookBuilder::AfterEvaluateChildren | ( | ) | [protected, virtual] |
| 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 323 of file SgBookBuilder.h.
References m_alpha.
| void SgBookBuilder::BeforeEvaluateChildren | ( | ) | [protected, virtual] |
| 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 |
Definition at line 328 of file SgBookBuilder.cpp.
References InverseEval(), m_alpha, SgBookNode::m_value, and SG_ASSERT.
Referenced by UpdatePriority().
| void SgBookBuilder::DoExpansion | ( | std::vector< SgMove > & | pv | ) | [private] |
Definition at line 373 of file SgBookBuilder.cpp.
References ExpandChildren(), GetNode(), SgBookNode::IncrementCount(), SgBookNode::IsLeaf(), SgBookNode::IsTerminal(), SgBookNode::m_count, m_expand_threshold, m_expand_width, m_num_widenings, m_use_widening, PlayMove(), SG_ASSERT, UndoMove(), UpdatePriority(), UpdateValue(), and WriteNode().
Referenced by Expand().
| void SgBookBuilder::EndIteration | ( | ) | [protected, virtual] |
Hook function: called at end of iteration.
Default implementation does nothing.
Definition at line 74 of file SgBookBuilder.cpp.
Referenced by Expand().
| 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 99 of file SgBookBuilder.cpp.
References DoExpansion(), EndIteration(), EnsureRootExists(), Fini(), FlushBook(), GetNode(), SgTimer::GetTime(), Init(), SgBookNode::IsTerminal(), m_flush_iterations, m_num_evals, m_num_widenings, 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 218 of file SgBookBuilder.cpp.
References AfterEvaluateChildren(), BeforeEvaluateChildren(), EvaluateChildren(), GenerateMoves(), GetNode(), m_num_evals, 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 94 of file SgBookBuilder.cpp.
Referenced by Expand(), IncreaseWidth(), and Refresh().
| virtual void SgBookBuilder::FlushBook | ( | ) | [protected, pure virtual] |
Referenced by Expand(), IncreaseWidth(), and Refresh().
| virtual bool SgBookBuilder::GenerateMoves | ( | std::vector< SgMove > & | moves, | |
| float & | value | |||
| ) | [protected, pure virtual] |
| 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 DoExpansion(), Expand(), ExpandChildren(), IncreaseWidth(), NumChildren(), Refresh(), UpdatePriority(), and UpdateValue().
| virtual bool SgBookBuilder::HasBeenVisited | ( | ) | [protected, pure virtual] |
Referenced by IncreaseWidth(), and Refresh().
| void SgBookBuilder::IncreaseWidth | ( | bool | root | ) | [private] |
Definition at line 472 of file SgBookBuilder.cpp.
References ExpandChildren(), GetAllLegalMoves(), GetNode(), HasBeenVisited(), IncreaseWidth(), SgBookNode::IsLeaf(), SgBookNode::IsTerminal(), SgBookNode::m_count, m_expand_threshold, m_expand_width, m_num_widenings, MarkAsVisited(), PlayMove(), PrintMessage(), and UndoMove().
| 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 182 of file SgBookBuilder.cpp.
References ClearAllVisited(), Fini(), FlushBook(), SgTimer::GetTime(), Init(), m_num_evals, m_num_widenings, m_use_widening, PrintMessage(), and SgTimer::Stop().
Referenced by IncreaseWidth().
| void SgBookBuilder::Init | ( | ) | [protected, virtual] |
Hook function: called before any work is done.
Default implementation does nothing.
Definition at line 89 of file SgBookBuilder.cpp.
Referenced by 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] |
| virtual void SgBookBuilder::MarkAsVisited | ( | ) | [protected, pure virtual] |
Referenced by IncreaseWidth(), and Refresh().
| std::size_t SgBookBuilder::NumChildren | ( | const std::vector< SgMove > & | legal | ) | [private] |
Definition at line 263 of file SgBookBuilder.cpp.
References GetNode(), PlayMove(), and UndoMove().
Referenced by UpdateValue().
| virtual void SgBookBuilder::PlayMove | ( | SgMove | move | ) | [protected, pure virtual] |
Referenced by DoExpansion(), ExpandChildren(), IncreaseWidth(), NumChildren(), Refresh(), UpdatePriority(), and UpdateValue().
| virtual void SgBookBuilder::PrintMessage | ( | std::string | msg | ) | [protected, pure virtual] |
Referenced by 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 425 of file SgBookBuilder.cpp.
References GetAllLegalMoves(), GetNode(), HasBeenVisited(), SgBookNode::IsLeaf(), SgBookNode::IsTerminal(), m_internal_nodes, m_leaf_nodes, SgBookNode::m_priority, m_priority_updates, m_terminal_nodes, m_value_updates, MarkAsVisited(), PlayMove(), PrintMessage(), Refresh(), UndoMove(), UpdatePriority(), UpdateValue(), Value(), and WriteNode().
| void SgBookBuilder::Refresh | ( | ) |
Propagates leaf values up through the entire tree.
Definition at line 147 of file SgBookBuilder.cpp.
References ClearAllVisited(), Fini(), FlushBook(), SgTimer::GetTime(), Init(), m_internal_nodes, m_leaf_nodes, m_num_evals, m_num_widenings, m_priority_updates, m_terminal_nodes, m_value_updates, 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 | ( | int | interation | ) | [protected, virtual] |
Hook function: called at start of iteration.
Default implementation does nothing.
Definition at line 68 of file SgBookBuilder.cpp.
References SG_UNUSED().
Referenced by Expand().
| virtual void SgBookBuilder::UndoMove | ( | SgMove | move | ) | [protected, pure virtual] |
Referenced by 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 340 of file SgBookBuilder.cpp.
References ComputePriority(), GetAllLegalMoves(), GetNode(), SgBookNode::m_priority, PlayMove(), SG_NULLMOVE, UndoMove(), and Value().
Referenced by 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 303 of file SgBookBuilder.cpp.
References ExpandChildren(), GetAllLegalMoves(), IsLoss(), m_expand_width, m_num_widenings, NumChildren(), PrintMessage(), UpdateValue(), and Value().
| void SgBookBuilder::UpdateValue | ( | SgBookNode & | node, | |
| const std::vector< SgMove > & | legal | |||
| ) | [private] |
Definition at line 277 of file SgBookBuilder.cpp.
References GetNode(), InverseEval(), SgBookNode::m_value, PlayMove(), UndoMove(), and Value().
Referenced by 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 333 of file SgBookBuilder.h.
References m_use_widening.
| 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] |
float SgBookBuilder::m_alpha [protected] |
See Alpha().
Definition at line 215 of file SgBookBuilder.h.
Referenced by Alpha(), ComputePriority(), and SetAlpha().
std::size_t SgBookBuilder::m_expand_threshold [protected] |
See UseWidening().
Definition at line 224 of file SgBookBuilder.h.
Referenced by DoExpansion(), ExpandThreshold(), IncreaseWidth(), and SetExpandThreshold().
std::size_t SgBookBuilder::m_expand_width [protected] |
See UseWidening().
Definition at line 221 of file SgBookBuilder.h.
Referenced by DoExpansion(), ExpandWidth(), IncreaseWidth(), SetExpandWidth(), and UpdateValue().
std::size_t SgBookBuilder::m_flush_iterations [protected] |
Number of iterations after which the db is flushed to disk.
Definition at line 227 of file SgBookBuilder.h.
Referenced by Expand().
std::size_t SgBookBuilder::m_internal_nodes [private] |
std::size_t SgBookBuilder::m_leaf_nodes [private] |
std::size_t SgBookBuilder::m_num_evals [private] |
Definition at line 288 of file SgBookBuilder.h.
Referenced by Expand(), ExpandChildren(), IncreaseWidth(), and Refresh().
std::size_t SgBookBuilder::m_num_widenings [private] |
Definition at line 290 of file SgBookBuilder.h.
Referenced by DoExpansion(), Expand(), IncreaseWidth(), Refresh(), and UpdateValue().
std::size_t SgBookBuilder::m_priority_updates [private] |
std::size_t SgBookBuilder::m_terminal_nodes [private] |
bool SgBookBuilder::m_use_widening [protected] |
See UseWidening().
Definition at line 218 of file SgBookBuilder.h.
Referenced by DoExpansion(), IncreaseWidth(), SetUseWidening(), and UseWidening().
std::size_t SgBookBuilder::m_value_updates [private] |