Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

HexAbSearch.hpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #ifndef HEXABSEARCH_HPP
00007 #define HEXABSEARCH_HPP
00008 
00009 #include "Hex.hpp"
00010 #include "HexEval.hpp"
00011 #include "SearchedState.hpp"
00012 #include "TransTable.hpp"
00013 
00014 _BEGIN_BENZENE_NAMESPACE_
00015 
00016 //----------------------------------------------------------------------------
00017 
00018 typedef TransTable<SearchedState> SearchTT;
00019 
00020 //----------------------------------------------------------------------------
00021 
00022 class HexBoard;
00023 
00024 /** Base Alpha-Beta search class. */
00025 class HexAbSearch
00026 {
00027 public:
00028     
00029     /** Constructor. */
00030     explicit HexAbSearch();
00031 
00032     /** Destructor. */
00033     virtual ~HexAbSearch();
00034 
00035     //------------------------------------------------------------------------
00036 
00037     /** Sets the transposition table to be used during search. */
00038     void SetTT(SearchTT* tt);
00039 
00040     /** Writes progress of search in guifx format after each root move
00041         completes. Off by default. */
00042     bool GuiFx() const;
00043 
00044     /** Sets whether guifx output should be dumped. 
00045         @see GuiFX(). */
00046     void SetGuiFx(bool flag);
00047 
00048     //------------------------------------------------------------------------
00049 
00050     /** Runs the AlphaBeta search. 
00051 
00052         @param brd       board to play one.
00053         @param color     color to play.
00054         @param plywidth  depth of the search set to plywidth.size()
00055                          and plywidth[j] top moves are explored.
00056         @param depths_to_search successive depths to search (like in ID).
00057         @param timelimit amount of time in which to finish search.
00058         @param PV        the principal variation will be stored here. 
00059         @returns         the evaluation of the PV.  
00060 
00061         If search is aborted by the user or the timelimit is reached,
00062         then the last valid result from interative deepening is
00063         returned.  If the first iteration has not completed, then a
00064         score of -EVAL_INFINITY and a PV containing only INVALID_POINT
00065         are returned.
00066     */
00067     HexEval Search(HexBoard& brd, HexColor color, 
00068                    const std::vector<int>& plywidth, 
00069                    const std::vector<int>& depths_to_search,
00070                    int timelimit,
00071                    std::vector<HexPoint>& PV);
00072    
00073     //------------------------------------------------------------------------
00074 
00075     /** Evaluates leaf position. */
00076     virtual HexEval Evaluate()=0;
00077 
00078     /** Generates moves for this position.  Moves will be played
00079         in the returned order. */
00080     virtual void GenerateMoves(std::vector<HexPoint>& moves)=0;
00081 
00082     /** Plays the given move. */
00083     virtual void ExecuteMove(HexPoint move)=0;
00084 
00085     /** Undoes the given move. */
00086     virtual void UndoMove(HexPoint move)=0;
00087 
00088     /** Hook function called upon entering new position. 
00089         Default implementation does nothing. */
00090     virtual void EnteredNewState();
00091 
00092     /** Hook function called at the very start of the search. 
00093         Default implementation does nothing. */
00094     virtual void OnStartSearch();
00095     
00096     /** Hook function called after the search has completed. 
00097         Default implementation does nothing. */
00098     virtual void OnSearchComplete();
00099 
00100     /** Hook function called after a states moves have been searched. 
00101         Default implementation does nothing. */
00102     virtual void AfterStateSearched();
00103 
00104     //------------------------------------------------------------------------
00105 
00106     /** Output stats from search. */
00107     std::string DumpStats();
00108 
00109 protected:
00110 
00111     /** The board we are playing on. */
00112     HexBoard* m_brd;
00113 
00114     /** Color of player to move next. */
00115     HexColor m_toplay;
00116 
00117     /** Transposition table to use during search, if any. */
00118     SearchTT* m_tt;
00119 
00120     /** @see GuiFx(). */
00121     bool m_use_guifx;
00122         
00123     /** Number of moves from the root. */
00124     int m_current_depth;
00125 
00126     /** Sequences of moves to the current state. */
00127     PointSequence m_sequence;
00128 
00129     /** If current state exists in TT, but TT state was not deep
00130         enough, this will hold the best move for that state; otherwise
00131         it will be INVALID_MOVE.  Could be used in GenerateMoves() to
00132         improve move ordering when using iterative deepening. */
00133     HexPoint m_tt_bestmove;
00134     bool m_tt_info_available;
00135 
00136 private:
00137 
00138     void ClearStats();
00139 
00140     void UpdatePV(int current_depth, HexEval value, std::vector<HexPoint>& cv);
00141 
00142     HexEval CheckTerminalState();
00143 
00144     /** Checks SgUserAbort() and sets m_aborted if true. */
00145     bool CheckAbort();
00146 
00147     HexEval SearchState(const std::vector<int>& plywidth,
00148                         int depth, HexEval alpha, HexEval beta,
00149                         std::vector<HexPoint>& cv);
00150 
00151     /** Search statistics. */
00152     struct Statistics
00153     {
00154         int numstates;
00155         int numleafs;
00156         int numterminal;
00157         int numinternal;
00158         int mustplay_branches;
00159         int total_branches;
00160         int visited_branches;
00161         int cuts;
00162         int tt_hits;
00163         int tt_cuts;
00164         double elapsed_time;
00165         HexEval value;
00166         std::vector<HexPoint> pv;
00167 
00168         Statistics()
00169             : numstates(0), numleafs(0), 
00170               numterminal(0), numinternal(0),
00171               mustplay_branches(0), total_branches(0),
00172               visited_branches(0), cuts(0), tt_hits(0),
00173               tt_cuts(0), elapsed_time(0.0), value(0)
00174         { };
00175 
00176         /** Prints statistics in human readable format. */
00177         std::string Dump() const;
00178     };
00179 
00180     Statistics m_statistics;
00181 
00182     /** Evaluations for each move from the root state. */
00183     std::vector<HexMoveValue> m_eval;
00184 
00185     /** True if the search was aborted due to timelimit or user
00186         intervention. */
00187     bool m_aborted;
00188 };
00189 
00190 inline void HexAbSearch::SetTT(SearchTT* tt)
00191 {
00192     m_tt = tt;
00193 }
00194 
00195 inline void HexAbSearch::SetGuiFx(bool flag)
00196 {
00197     m_use_guifx = flag;
00198 }
00199 
00200 inline bool HexAbSearch::GuiFx() const
00201 {
00202     return m_use_guifx;
00203 }
00204 
00205 //----------------------------------------------------------------------------
00206 
00207 _END_BENZENE_NAMESPACE_
00208 
00209 #endif // HEXABSEARCH_HPP


6 Jan 2011 Doxygen 1.6.3