00001 //---------------------------------------------------------------------------- 00002 /** @file GoUctUtil.h 00003 */ 00004 //---------------------------------------------------------------------------- 00005 00006 #ifndef GOUCT_UTIL_H 00007 #define GOUCT_UTIL_H 00008 00009 #include <iosfwd> 00010 #include "GoBoard.h" 00011 #include "GoBoardUtil.h" 00012 #include "GoEyeUtil.h" 00013 #include "GoModBoard.h" 00014 #include "GoUctBoard.h" 00015 #include "SgBlackWhite.h" 00016 #include "SgPoint.h" 00017 #include "SgRandom.h" 00018 #include "SgUctSearch.h" 00019 #include "SgUtil.h" 00020 00021 class SgBWSet; 00022 template<typename T,int N> class SgSList; 00023 class SgUctNode; 00024 class SgUctTree; 00025 00026 //---------------------------------------------------------------------------- 00027 00028 /** General utility functions used in GoUct. 00029 These functions are used in GoUct, but should not depend on other classes 00030 in GoUct to avoid cyclic dependencies. 00031 */ 00032 namespace GoUctUtil 00033 { 00034 /** reject random move if it was self atari */ 00035 const bool REMOVE_SELF_ATARI = false; 00036 /** reject random move if it was both atari and self atari */ 00037 const bool REMOVE_MUTUAL_ATARI = true; 00038 00039 const int SELF_ATARI_LIMIT = 8; 00040 const int MUTUAL_ATARI_LIMIT = 2; 00041 00042 /** Conservative clump correction. 00043 Only "very clumpy" moves are replaced. 00044 If false, more "clumps" are replaced. 00045 */ 00046 const bool CONSERVATIVE_CLUMP = true; 00047 00048 /** Used in clump correction. */ 00049 const int LINE_1_LIMIT = CONSERVATIVE_CLUMP ? 4 : 3; 00050 00051 /** Used in clump correction. */ 00052 const int LINE_2_OR_MORE_LIMIT = CONSERVATIVE_CLUMP ? 6 : 5; 00053 00054 void ClearStatistics(SgPointArray<SgUctStatistics>& stats); 00055 00056 /** Check if move is self-atari and find other liberty, if yes. 00057 This can be applied as a filter in the playout policy, after a move 00058 was generated. It is a useful correction to the move generation using 00059 GoBoardUtil::IsCompletelySurrounded, which prunes backfilling moves. 00060 Does not check if the move is legal, because this is usually already 00061 checked in the playout policy, and requires that the move is no 00062 suicide move (checked with an assertion). 00063 00064 1. If the move is a self-atari 00065 of more than 1 stone it is replaced by the liberty of the resulting 00066 block, unless it is also a self-atari. 00067 00068 2. If p is single stone self-atari, possibly replace by neighbor. 00069 If p is a single stone with only one liberty and it is not a capture 00070 move: check if neighboring point has more liberties. If 00071 yes, replace by neighbor. 00072 @param bd 00073 @param p A (legal) move 00074 @return The replacement move, if one was found, otherwise the 00075 original move. 00076 */ 00077 template<class BOARD> 00078 bool DoSelfAtariCorrection(const BOARD& bd, SgPoint& p); 00079 00080 /** Check if p makes ugly clump. Possibly replace by neighbor. 00081 If p is close to many own stones: 00082 check if neighboring point looks better. If 00083 yes, replace by neighbor. 00084 */ 00085 template<class BOARD> 00086 bool DoClumpCorrection(const BOARD& bd, SgPoint& p); 00087 00088 /** Check, if playing at a lib gains liberties. 00089 Does not handle capturing moves for efficiency. Not needed, because 00090 capturing moves have a higher priority in the playout. 00091 */ 00092 template<class BOARD> 00093 bool GainsLiberties(const BOARD& bd, SgPoint anchor, SgPoint lib); 00094 00095 /** Generate a forced opening move. 00096 This function can be used to generate opening moves instead of doing a 00097 Monte-Carlo tree search, which often returns random looking moves in 00098 the opening on large boards. Experiments showed also an improvement in 00099 playing strength if this function is used. The function currently 00100 generates a move on the 4-4 point of an empty corner under the 00101 following conditions: 00102 # The board size is 15 or larger 00103 # There are no more than 5 stones of each color on the board (avoids 00104 that the move generation triggers in positions containing lots of 00105 setup stones) 00106 # All points in the corner up to and including the 5th row are empty 00107 @return A randomly selected move that fulfills the conditions or 00108 SG_NULLPOINT if no such move exists. 00109 */ 00110 SgPoint GenForcedOpeningMove(const GoBoard& bd); 00111 00112 /** Filter for generating moves in random phase. 00113 Checks if a point (must be empty) is a legal move and 00114 GoBoardUtil::IsCompletelySurrounded() returns false. 00115 If a policy generates no pass move as long as there are still moves 00116 on the board that this function would return true for, then the 00117 end position can be scored with GoBoardUtil::ScoreSimpleEndPosition(). 00118 */ 00119 template<class BOARD> 00120 bool GeneratePoint(const BOARD& bd, SgBalancer& balancer, SgPoint p, 00121 SgBlackWhite toPlay); 00122 00123 /** Print information about search as Gfx commands for GoGui. 00124 Can be used for GoGui live graphics during the search or GoGui 00125 analyze command type "gfx" after the search (see http://gogui.sf.net). 00126 Best move and best response move as variation (shown as 00127 shadow stones in GoGui). 00128 @param search The search containing the tree and statistics 00129 @param toPlay The color toPlay at the root node of the tree 00130 @param out The stream to write the gfx commands to 00131 */ 00132 void GfxBestMove(const SgUctSearch& search, SgBlackWhite toPlay, 00133 std::ostream& out); 00134 00135 /** Print move counts as Gfx commands for GoGui. 00136 Can be used for GoGui live graphics during the search or GoGui 00137 analyze command type "gfx" after the search (see http://gogui.sf.net). 00138 Prints a LABEL command to display the move counts. 00139 @param tree 00140 @param out The stream to write the gfx commands to 00141 */ 00142 void GfxCounts(const SgUctTree& tree, std::ostream& out); 00143 00144 /** Print the move values as Gfx commands for GoGui. 00145 Can be used for GoGui live graphics during the search or GoGui 00146 analyze command type "gfx" after the search (see http://gogui.sf.net). 00147 The values of the moves in the root node are shown using an 00148 INFLUENCE gfx command. 00149 @param search The search containing the tree and statistics 00150 @param toPlay The color to play in the root node of the UCT tree 00151 @param out The stream to write the gfx commands to 00152 */ 00153 void GfxMoveValues(const SgUctSearch& search, SgBlackWhite toPlay, 00154 std::ostream& out); 00155 00156 /** Print best sequence of search in GoGui live-gfx format. */ 00157 void GfxSequence(const SgUctSearch& search, SgBlackWhite toPlay, 00158 std::ostream& out); 00159 00160 /** Print information about search as GoGui Gfx commands for text 00161 in the status line. 00162 Can be used for GoGui live graphics during the search or GoGui 00163 analyze command type "gfx" after the search (see http://gogui.sf.net). 00164 The following information is in the status line: 00165 - N = Number games 00166 - V = Value of root node 00167 - Len = Average simulation sequence length 00168 - Tree = Average/maximum moves of simulation sequence in tree 00169 - Abrt = Percentage of games aborted (due to maximum game length) 00170 - Gm/s = Simulations per second 00171 @param search The search containing the tree and statistics 00172 @param out The stream to write the gfx commands to 00173 */ 00174 void GfxStatus(const SgUctSearch& search, std::ostream& out); 00175 00176 /** Print territory statistics as GoGui gfx commands. 00177 Can be used for GoGui live graphics during the search or GoGui 00178 analyze command type "gfx" after the search (see http://gogui.sf.net). 00179 Uses INFLUENCE gfx command. 00180 */ 00181 void GfxTerritoryStatistics( 00182 const SgPointArray<SgUctStatistics>& territoryStatistics, 00183 const GoBoard& bd, std::ostream& out); 00184 00185 /** selfatari of a larger number of stones and also atari on opponent. */ 00186 template<class BOARD> 00187 bool IsMutualAtari(const BOARD& bd, SgBalancer& balancer, SgPoint p, 00188 SgBlackWhite toPlay); 00189 00190 /** Save tree contained in a search as a Go SGF file. 00191 The SGF file is written directly without using SgGameWriter to avoid 00192 a memory-intensive construction of an intermediate game tree. 00193 @param tree The tree 00194 @param boardSize The size of the board 00195 @param stones The Go position corresponding to the root node of the 00196 tree 00197 @param toPlay The color toPlay at the root node of the tree 00198 @param out The stream to save to tree to 00199 @param maxDepth Only save tree to a certain depth. -1 means no limit. 00200 */ 00201 void SaveTree(const SgUctTree& tree, int boardSize, const SgBWSet& stones, 00202 SgBlackWhite toPlay, std::ostream& out, int maxDepth = -1); 00203 00204 /** Select a random move from a list of empty points. 00205 The check if GeneratePoint() returns true for the point is done after 00206 the random selection to avoid calling this function for every point in 00207 the list. If GeneratePoint() returns false, the point is removed from 00208 the list and the process is repeated. 00209 @param bd The board 00210 @param toPlay The color to generate the move for 00211 @param emptyPts The list of empty points (will potentially be modified 00212 in this function for efficiency reasons) 00213 @param random The random generator 00214 @param balancer The balancer used in GeneratePoint() 00215 @return The move or SG_NULLMOVE if no empty point is a legal move that 00216 should be generated 00217 */ 00218 template<class BOARD> 00219 SgPoint SelectRandom(const BOARD& bd, SgBlackWhite toPlay, 00220 GoPointList& emptyPts, 00221 SgRandom& random, SgBalancer& balancer); 00222 00223 /** Utility function used in DoClumpCorrection() */ 00224 template<class BOARD> 00225 void SetEdgeCorrection(const BOARD& bd, SgPoint p, int& edgeCorrection); 00226 00227 /** Return statistics of all children of a node. 00228 @param search The search containing the tree and statistics 00229 @param bSort Whether sort the children 00230 @param node The node 00231 */ 00232 std::string ChildrenStatistics(const SgUctSearch& search, 00233 bool bSort, const SgUctNode& node); 00234 00235 /** check if anchors[] are subset of neighbor blocks of nb */ 00236 template<class BOARD> 00237 bool SubsetOfBlocks(const BOARD& bd, const SgPoint anchor[], SgPoint nb); 00238 } 00239 00240 //---------------------------------------------------------------------------- 00241 00242 template<class BOARD> 00243 bool GoUctUtil::DoClumpCorrection(const BOARD& bd, SgPoint& p) 00244 { 00245 // if not a clump, don't correct p. 00246 if (bd.NumEmptyNeighbors(p) != 1) 00247 return false; 00248 const SgBlackWhite toPlay = bd.ToPlay(); 00249 if (bd.Line(p) == 1) 00250 { 00251 if ( bd.Num8Neighbors(p, toPlay) < LINE_1_LIMIT 00252 || bd.NumNeighbors(p, toPlay) != 2 00253 ) 00254 return false; 00255 } 00256 else if ( bd.Num8Neighbors(p, toPlay) < LINE_2_OR_MORE_LIMIT 00257 || bd.NumNeighbors(p, toPlay) != 3 00258 ) 00259 return false; 00260 00261 // only swap if nb is better than p 00262 const SgPoint nb = GoEyeUtil::EmptyNeighbor(bd, p); 00263 int edgeCorrection_p = 0; 00264 int edgeCorrection_nb = 0; 00265 SetEdgeCorrection(bd, p, edgeCorrection_p); 00266 SetEdgeCorrection(bd, nb, edgeCorrection_nb); 00267 if ( bd.Num8Neighbors(nb, toPlay) + edgeCorrection_nb < 00268 bd.Num8Neighbors(p, toPlay) + edgeCorrection_p 00269 && bd.NumNeighbors(nb, toPlay) <= bd.NumNeighbors(p, toPlay) 00270 && 00271 ( bd.NumEmptyNeighbors(nb) >= 2 00272 || ! GoBoardUtil::SelfAtari(bd, nb) 00273 ) 00274 ) 00275 { 00276 if (CONSERVATIVE_CLUMP) // no further tests, nb is good 00277 { 00278 p = nb; 00279 return true; 00280 } 00281 else 00282 { 00283 // keep p if it was a connection move and nb does not connect at 00284 // least the same blocks 00285 SgPoint anchor[4 + 1]; 00286 bd.NeighborBlocks(p, toPlay, anchor); 00287 SG_ASSERT(anchor[0] != SG_ENDPOINT); // at least 1 block 00288 if (anchor[1] == SG_ENDPOINT // no connection, only 1 block 00289 || SubsetOfBlocks<BOARD>(bd, anchor, nb)) 00290 { 00291 p = nb; 00292 return true; 00293 } 00294 } 00295 } 00296 return false; 00297 } 00298 00299 template<class BOARD> 00300 inline bool GoUctUtil::DoSelfAtariCorrection(const BOARD& bd, SgPoint& p) 00301 { 00302 // Function is inline despite its large size, because it returns quickly 00303 // on average, which makes the function call an overhead 00304 00305 const SgBlackWhite toPlay = bd.ToPlay(); 00306 // no self-atari 00307 if (bd.NumEmptyNeighbors(p) >= 2) 00308 return false; 00309 if (bd.NumNeighbors(p, toPlay) > 0) // p part of existing block(s) 00310 { 00311 if (! GoBoardUtil::SelfAtari(bd, p)) 00312 return false; 00313 SgBlackWhite opp = SgOppBW(toPlay); 00314 SgPoint replaceMove = SG_NULLMOVE; 00315 // ReplaceMove is the liberty we would have after playing at p 00316 for (SgNb4Iterator it(p); it; ++it) 00317 { 00318 SgBoardColor c = bd.GetColor(*it); 00319 if (c == SG_EMPTY) 00320 replaceMove = *it; 00321 else if (c == toPlay) 00322 { 00323 for (typename BOARD::LibertyIterator it2(bd, *it); it2; ++it2) 00324 if (*it2 != p) 00325 { 00326 replaceMove = *it2; 00327 break; 00328 } 00329 } 00330 else if (c == opp && bd.InAtari(*it)) 00331 replaceMove = *it; 00332 if (replaceMove != SG_NULLMOVE) 00333 break; 00334 } 00335 SG_ASSERT(replaceMove != SG_NULLMOVE); 00336 if ( bd.IsLegal(replaceMove) 00337 && ! GoBoardUtil::SelfAtari(bd, replaceMove) 00338 ) 00339 { 00340 p = replaceMove; 00341 return true; 00342 } 00343 } 00344 else if (bd.NumEmptyNeighbors(p) > 0 && ! bd.CanCapture(p, toPlay)) 00345 // single stone with empty neighbors - possibly replace 00346 { 00347 // should we shift to nb? Is it better than p? 00348 const SgPoint nb = GoEyeUtil::EmptyNeighbor(bd, p); 00349 // Check if legal, could violate superko (with BOARD=GoBoard in 00350 // GoUctDefaultPriorKnowledge) 00351 if ( bd.IsLegal(nb) 00352 && ( bd.NumEmptyNeighbors(nb) >= 2 00353 || bd.CanCapture(nb, toPlay) 00354 ) 00355 ) 00356 { 00357 // nb seems better than p - switch. 00358 p = nb; 00359 return true; 00360 } 00361 } 00362 // no replacement found 00363 return false; 00364 } 00365 00366 template<class BOARD> 00367 bool GoUctUtil::GainsLiberties(const BOARD& bd, SgPoint anchor, SgPoint lib) 00368 { 00369 SG_ASSERT(bd.IsEmpty(lib)); 00370 SG_ASSERT(bd.Anchor(anchor) == anchor); 00371 const SgBlackWhite color = bd.GetStone(anchor); 00372 int nu = -2; // need 2 new libs (lose 1 lib by playing on lib itself) 00373 for (SgNb4Iterator it(lib); it; ++it) 00374 { 00375 SgEmptyBlackWhite c = bd.GetColor(*it); 00376 if (c == SG_EMPTY) 00377 { 00378 if (! bd.IsLibertyOfBlock(*it, anchor)) 00379 if (++nu >= 0) 00380 return true; 00381 } 00382 else if (c == color) // merge with block 00383 { 00384 const SgPoint anchor2 = bd.Anchor(*it); 00385 if (anchor != anchor2) 00386 for (typename BOARD::LibertyIterator it(bd, anchor2); it; 00387 ++it) 00388 if (! bd.IsLibertyOfBlock(*it, anchor)) 00389 if (++nu >= 0) 00390 return true; 00391 } 00392 // else capture - not handled, see function documentation 00393 } 00394 return false; 00395 } 00396 00397 template<class BOARD> 00398 inline bool GoUctUtil::IsMutualAtari(const BOARD& bd, SgBalancer& balancer, 00399 SgPoint p, SgBlackWhite toPlay) 00400 { 00401 int nuStones = 0; 00402 if ( GoBoardUtil::SelfAtari(bd, p, nuStones) 00403 && nuStones > MUTUAL_ATARI_LIMIT 00404 && ( nuStones > GoEyeUtil::NAKADE_LIMIT 00405 || ! GoEyeUtil::MakesNakadeShape(bd, p, toPlay) 00406 ) 00407 ) 00408 { 00409 SG_ASSERT(bd.ToPlay() == toPlay); 00410 SgBlackWhite opp = SgOppBW(toPlay); 00411 bool selfatari = 00412 bd.HasNeighbors(p, opp) && 00413 GoBoardUtil::SelfAtariForColor(bd, p, opp); 00414 if (selfatari && balancer.Play(toPlay)) 00415 { 00416 /* 00417 static int count = 0; 00418 if (++count < 30) 00419 SgDebug() << bd << "Removed mutual atari" 00420 << SgWriteMove(p, bd.ToPlay()) << '\n'; 00421 */ 00422 return true; 00423 } 00424 } 00425 return false; 00426 } 00427 00428 template<class BOARD> 00429 inline bool GoUctUtil::GeneratePoint(const BOARD& bd, SgBalancer& balancer, 00430 SgPoint p, SgBlackWhite toPlay) 00431 { 00432 SG_ASSERT(bd.IsEmpty(p)); 00433 SG_ASSERT(bd.ToPlay() == toPlay); 00434 if ( GoBoardUtil::IsCompletelySurrounded(bd, p) 00435 //|| GoEyeUtil::IsTwoPointEye(bd, p, toPlay) 00436 || ! bd.IsLegal(p, toPlay) 00437 ) 00438 return false; 00439 if (REMOVE_SELF_ATARI) 00440 { 00441 int nuStones = 0; 00442 if ( GoBoardUtil::SelfAtari(bd, p, nuStones) 00443 && nuStones > SELF_ATARI_LIMIT 00444 // todo: check for nakade shapes here. 00445 ) 00446 { 00447 //SgDebug() << bd << "Removed selfatari" 00448 //<< SgWriteMove(p, toPlay); 00449 return false; 00450 } 00451 } 00452 00453 if (REMOVE_MUTUAL_ATARI && IsMutualAtari(bd, balancer, p, toPlay)) 00454 return false; 00455 return true; 00456 } 00457 00458 template<class BOARD> 00459 inline SgPoint GoUctUtil::SelectRandom(const BOARD& bd, 00460 SgBlackWhite toPlay, 00461 GoPointList& emptyPts, 00462 SgRandom& random, 00463 SgBalancer& balancer) 00464 { 00465 while (true) 00466 { 00467 int length = emptyPts.Length(); 00468 if (length == 0) 00469 break; 00470 int index = random.Int(length); 00471 SgPoint p = emptyPts[index]; 00472 SG_ASSERT(bd.IsEmpty(p)); 00473 if (GeneratePoint(bd, balancer, p, toPlay)) 00474 return p; 00475 emptyPts[index] = emptyPts[length - 1]; 00476 emptyPts.PopBack(); 00477 } 00478 return SG_NULLMOVE; 00479 } 00480 00481 template<class BOARD> 00482 void GoUctUtil::SetEdgeCorrection(const BOARD& bd, SgPoint p, 00483 int& edgeCorrection) 00484 { 00485 if (bd.Line(p) == 1) 00486 { 00487 edgeCorrection += 3; 00488 if (bd.Pos(p) == 1) 00489 edgeCorrection += 2; 00490 } 00491 } 00492 00493 00494 template<class BOARD> 00495 bool GoUctUtil::SubsetOfBlocks(const BOARD& bd, const SgPoint anchor[], 00496 SgPoint nb) 00497 { 00498 SgPoint nbanchor[4 + 1]; 00499 bd.NeighborBlocks(nb, bd.ToPlay(), nbanchor); 00500 if (nbanchor[0] == SG_ENDPOINT) 00501 return false; 00502 for (int i = 0; anchor[i] != SG_ENDPOINT; ++i) 00503 if (! GoBoardUtil::ContainsAnchor(nbanchor, anchor[i])) 00504 return false; 00505 return true; 00506 } 00507 00508 //---------------------------------------------------------------------------- 00509 00510 #endif // GOUCT_UTIL_H