00001 //---------------------------------------------------------------------------- 00002 /** @file GoSafetyUtil.h 00003 Utility functions for the static and search-based safety solvers. */ 00004 //---------------------------------------------------------------------------- 00005 00006 #ifndef GO_SAFETYUTIL_H 00007 #define GO_SAFETYUTIL_H 00008 00009 #include "SgBlackWhite.h" 00010 #include "SgBoardColor.h" 00011 #include "SgMiaiStrategy.h" 00012 #include "SgPoint.h" 00013 #include "SgVector.h" 00014 00015 class GoBoard; 00016 class GoRegion; 00017 class GoRegionBoard; 00018 class SgBWSet; 00019 class SgPointSet; 00020 00021 //---------------------------------------------------------------------------- 00022 00023 namespace GoSafetyUtil 00024 { 00025 00026 /** Add pts to *safe[color] */ 00027 void AddToSafe(const GoBoard& board, const SgPointSet& pts, 00028 SgBlackWhite color, SgBWSet* safe, const char* reason, 00029 int depth, bool addBoundary); 00030 00031 /** Stronger version of IsTerritory that uses region information 00032 This version checks for opponent nakade inside the area. 00033 Useful for proving safe semeai test cases after resolving semeai. */ 00034 bool ExtendedIsTerritory(const GoBoard& board, GoRegionBoard* regions, 00035 const SgPointSet& pts, 00036 const SgPointSet& safe, SgBlackWhite color); 00037 00038 /** See FindDameAndUnsurroundablePoints */ 00039 SgPointSet FindDamePoints(const GoBoard& board, const SgPointSet& empty, 00040 const SgBWSet& safe); 00041 00042 /** Find dame and unsurroundable points. 00043 Given sets of empty points and safe points, compute subset of dame 00044 points. Given safe B+W stones, find empty which are surely dame, 00045 using the algorithm of [Mueller1995]. 00046 Unsurroundable points are empty points that can not be surrounded 00047 by either player because they are adjacent to both player's safe 00048 stones. However, they can potentially have an effect on unsafe stones 00049 or on other empty points. Dame points are a subset of unsurroundable 00050 points that have no effect on other points - no matter if they will 00051 be occupied by Black, White, or remain empty. */ 00052 void FindDameAndUnsurroundablePoints(const GoBoard& bd, 00053 const SgPointSet& empty, 00054 const SgBWSet& safe, 00055 SgPointSet* dame, 00056 SgPointSet* unsurroundable); 00057 00058 /** Check if one player has already won */ 00059 SgEmptyBlackWhite GetWinner(const GoBoard& bd); 00060 00061 /** Simple static territory check for surrounded area */ 00062 bool IsTerritory(const GoBoard& board, const SgPointSet& pts, 00063 const SgPointSet& safe, SgBlackWhite color); 00064 00065 /** Given set of stones, reduce to block anchors */ 00066 void ReduceToAnchors(const GoBoard& board, const SgPointSet& stones, 00067 SgVector<SgPoint>* anchors); 00068 00069 /** Helper function for 1-vitality test. 00070 Try to find two matching liberties for point p, subtract them from 00071 libs if found. */ 00072 bool Find2Libs(SgPoint p, SgPointSet* libs); 00073 00074 /** Helper function for 1-vitality test. 00075 Similar to Find2Libs(), but try to find miaiPair of two best liberties 00076 (not shared with other interior points). */ 00077 bool Find2BestLibs(SgPoint p, const SgPointSet& libs, 00078 SgPointSet interior, SgMiaiPair* miaiPair); 00079 00080 /** Extended version of MightMakeLife. 00081 Recognizes some nakade shapes as dead. Useful mostly for semeai 00082 solver. */ 00083 bool ExtendedMightMakeLife(const GoBoard& board, GoRegionBoard* regions, 00084 const SgPointSet& area, const SgPointSet& safe, 00085 SgBlackWhite color); 00086 00087 /** Test whether color can make 2 eyes inside a surrounded area. 00088 Precondition: area surrounded by safe stones of opponent. 00089 Basic test, handles 1 and 2 point eyes only. */ 00090 bool MightMakeLife(const GoBoard& board, const SgPointSet& area, 00091 const SgPointSet& safe, SgBlackWhite color); 00092 00093 /** Write statistics about the safe points */ 00094 void WriteStatistics(const std::string& heading, 00095 const GoRegionBoard* regions, 00096 const SgBWSet* safe); 00097 00098 } // namespace GoSafetyUtil 00099 00100 //---------------------------------------------------------------------------- 00101 00102 #endif // GO_SAFETYUTIL_H