Index   Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

GoSafetyUtil.h

Go to the documentation of this file.
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


Sun Mar 13 2011 Doxygen 1.7.1