00001 //---------------------------------------------------------------------------- 00002 /** @file GoLadder.cpp 00003 */ 00004 //---------------------------------------------------------------------------- 00005 00006 #include "SgSystem.h" 00007 #include "GoLadder.h" 00008 00009 #include <algorithm> 00010 #include <memory> 00011 #include "GoBoard.h" 00012 #include "GoBoardUtil.h" 00013 #include "GoModBoard.h" 00014 #include "SgVector.h" 00015 #include "SgStack.h" 00016 00017 using namespace std; 00018 using GoBoardUtil::NeighborsOfColor; 00019 using GoBoardUtil::PlayIfLegal; 00020 00021 //---------------------------------------------------------------------------- 00022 00023 namespace { 00024 00025 const int GOOD_FOR_PREY = 1000; 00026 00027 const int GOOD_FOR_HUNTER = -1000; 00028 00029 } // namespace 00030 00031 //---------------------------------------------------------------------------- 00032 00033 GoLadder::GoLadder() 00034 { 00035 } 00036 00037 inline bool GoLadder::CheckMoveOverflow() const 00038 { 00039 return (m_bd->MoveNumber() >= m_maxMoveNumber); 00040 } 00041 00042 void GoLadder::InitMaxMoveNumber() 00043 { 00044 // reserve is the maximum number of moves played before recursion 00045 // 5 is an optimistic bound 00046 const int RESERVE = 5; 00047 m_maxMoveNumber = min(m_bd->MoveNumber() + MAX_LADDER_MOVES, 00048 GO_MAX_NUM_MOVES - RESERVE); 00049 } 00050 00051 /** Marks all stones in the block p as part of the prey. 00052 If 'stones' is not 0, then append the stones to the existing list. 00053 */ 00054 void GoLadder::MarkStonesAsPrey(SgPoint p, SgVector<SgPoint>* stones) 00055 { 00056 SG_ASSERT(m_bd->IsValidPoint(p)); 00057 if (m_bd->Occupied(p)) 00058 { 00059 for (GoBoard::StoneIterator it(*m_bd, p); it; ++it) 00060 { 00061 SgPoint p = *it; 00062 m_partOfPrey.Include(p); 00063 if (stones) 00064 stones->PushBack(p); 00065 } 00066 } 00067 } 00068 00069 /** Filter out captured blocks, blocks not in atari, and blocks not adjacent 00070 to the prey. 00071 The latter are found by checking whether blocks adjacent to the block in 00072 question are the prey or not. Does not return the correct blocks if the 00073 prey has more than three liberties, but in that case, the prey has 00074 escaped anyway. 00075 */ 00076 void GoLadder::FilterAdjacent(GoPointList& adjBlocks) 00077 { 00078 GoPointList temp; 00079 for (GoPointList::Iterator it(adjBlocks); it; ++it) 00080 { 00081 SgPoint block = *it; 00082 if (m_bd->IsColor(block, m_hunterColor) 00083 && m_bd->InAtari(block) 00084 && BlockIsAdjToPrey(block, 1)) 00085 temp.PushBack(block); 00086 } 00087 ReduceToBlocks(temp); 00088 adjBlocks = temp; 00089 } 00090 00091 bool GoLadder::PointIsAdjToPrey(SgPoint p) 00092 { 00093 return m_partOfPrey[p - SG_NS] 00094 || m_partOfPrey[p - SG_WE] 00095 || m_partOfPrey[p + SG_WE] 00096 || m_partOfPrey[p + SG_NS]; 00097 } 00098 00099 bool GoLadder::BlockIsAdjToPrey(SgPoint p, int numAdj) 00100 { 00101 SG_ASSERT(m_bd->IsColor(p, m_hunterColor)); 00102 for (GoBoard::StoneIterator it(*m_bd, p); it; ++it) 00103 if (PointIsAdjToPrey(*it) && --numAdj == 0) 00104 return true; 00105 return false; 00106 } 00107 00108 /** Play hunter move and update all the relevant information. 00109 Play at one of the two liberties of the prey. 00110 */ 00111 int GoLadder::PlayHunterMove(int depth, SgPoint move, SgPoint lib1, 00112 SgPoint lib2, const GoPointList& adjBlk, 00113 SgVector<SgPoint>* sequence) 00114 { 00115 SG_ASSERT(move == lib1 || move == lib2); 00116 // TODO: only pass move and otherLib 00117 int result = 0; 00118 if (PlayIfLegal(*m_bd, move, m_hunterColor)) 00119 { 00120 // Find new adjacent blocks: only block just played can be new 00121 // in atari. 00122 // But other blocks previously in atari may have gained new liberties 00123 // because the move captured a stone, or the move may have extended a 00124 // block previously in atari. 00125 // If it was in atari before, and the move doesn't capture 00126 // anything, then the block will still be in atari afterwards - no 00127 // need to check again. 00128 GoPointList newAdj; 00129 if (m_bd->InAtari(move)) 00130 newAdj.PushBack(move); 00131 for (GoPointList::Iterator it(adjBlk); it; ++it) 00132 { 00133 SgPoint block = *it; 00134 if (! m_bd->AreInSameBlock(block, move)) 00135 { 00136 if (! m_bd->CapturingMove() || m_bd->InAtari(block)) 00137 newAdj.PushBack(block); 00138 } 00139 } 00140 if (move == lib1) 00141 lib1 = lib2; 00142 result = PreyLadder(depth + 1, lib1, newAdj, sequence); 00143 if (sequence) 00144 sequence->PushBack(move); 00145 m_bd->Undo(); 00146 } 00147 else 00148 { 00149 if (sequence) 00150 sequence->Clear(); 00151 result = GOOD_FOR_PREY - depth; 00152 } 00153 return result; 00154 } 00155 00156 /** Play prey move and update all the relevant information. 00157 Extend the prey by playing at its only liberty, or capture a block 00158 adjacent to the prey. 00159 */ 00160 int GoLadder::PlayPreyMove(int depth, SgPoint move, SgPoint lib1, 00161 const GoPointList& adjBlk, 00162 SgVector<SgPoint>* sequence) 00163 { 00164 int result = 0; 00165 GoPointList newAdj(adjBlk); 00166 SgVector<SgPoint> newLib; 00167 SgVector<SgPoint> newStones; 00168 SgVector<SgPoint> neighbors; 00169 if (move == lib1) 00170 { 00171 NeighborsOfColor(*m_bd, move, m_preyColor, &neighbors); 00172 for (SgVectorIterator<SgPoint> iter(neighbors); iter; ++iter) 00173 { 00174 SgPoint block = *iter; 00175 if (! m_partOfPrey[block]) 00176 { 00177 MarkStonesAsPrey(block, &newStones); 00178 GoPointList temp = 00179 GoBoardUtil::AdjacentStones(*m_bd, block); 00180 newAdj.PushBackList(temp); 00181 for (GoBoard::LibertyIterator it(*m_bd, block); it; ++it) 00182 newLib.Include(*it); 00183 } 00184 } 00185 m_partOfPrey.Include(move); 00186 } 00187 if (PlayIfLegal(*m_bd, move, m_preyColor)) 00188 { 00189 if (move == lib1) 00190 { 00191 NeighborsOfColor(*m_bd, move, SG_EMPTY, &neighbors); 00192 for (SgVectorIterator<SgPoint> iter(newLib); iter; ++iter) 00193 { 00194 SgPoint point = *iter; 00195 // Test for Empty is necessary because newLib will include 00196 // the move just played. 00197 if (m_bd->IsEmpty(point)) 00198 neighbors.Include(point); 00199 } 00200 } 00201 else 00202 { 00203 neighbors.PushBack(lib1); 00204 } 00205 if (m_bd->CapturingMove()) 00206 { // Add the points at the captured stones that are adjacent to the 00207 // prey to the liberties, at least if exactly one stone captured. 00208 for (GoPointList::Iterator it(m_bd->CapturedStones()); it; 00209 ++it) 00210 { 00211 SgPoint stone = *it; 00212 if (PointIsAdjToPrey(stone)) 00213 neighbors.Include(stone); 00214 } 00215 } 00216 SG_ASSERT(! neighbors.IsEmpty()); 00217 lib1 = neighbors[0]; 00218 SG_ASSERT(m_bd->IsEmpty(lib1)); 00219 SgSList<SgPoint,4> temp = 00220 NeighborsOfColor(*m_bd, move, m_hunterColor); 00221 newAdj.PushBackList(temp); 00222 FilterAdjacent(newAdj); 00223 00224 if (neighbors.Length() == 1) 00225 result = HunterLadder(depth + 1, lib1, newAdj, sequence); 00226 else if (neighbors.Length() == 2) 00227 { 00228 SgPoint lib2 = neighbors[1]; 00229 SG_ASSERT(m_bd->IsEmpty(lib2)); 00230 result = HunterLadder(depth + 1, lib1, lib2, newAdj, sequence); 00231 } 00232 else // 3 <= numLib 00233 { 00234 if (sequence) 00235 sequence->Clear(); 00236 result = GOOD_FOR_PREY - (depth + 1); 00237 } 00238 if (sequence) 00239 sequence->PushBack(move); 00240 m_bd->Undo(); 00241 } 00242 else 00243 { 00244 if (sequence) 00245 sequence->Clear(); 00246 result = GOOD_FOR_HUNTER + depth; 00247 } 00248 m_partOfPrey.Exclude(move); 00249 m_partOfPrey.Exclude(newStones); 00250 00251 return result; 00252 } 00253 00254 int GoLadder::PreyLadder(int depth, SgPoint lib1, 00255 const GoPointList& adjBlk, 00256 SgVector<SgPoint>* sequence) 00257 { 00258 if (CheckMoveOverflow()) 00259 return GOOD_FOR_PREY; 00260 int result = 0; 00261 for (GoPointList::Iterator iter(adjBlk); iter; ++iter) 00262 { 00263 SgPoint block = *iter; 00264 SgPoint move = *GoBoard::LibertyIterator(*m_bd, block); 00265 if (BlockIsAdjToPrey(block, 2)) 00266 { 00267 if (sequence) 00268 sequence->SetTo(move); 00269 result = GOOD_FOR_PREY - depth; 00270 } 00271 else if (move != lib1) 00272 { 00273 result = PlayPreyMove(depth, move, lib1, adjBlk, sequence); 00274 } 00275 if (0 < result) 00276 break; 00277 } 00278 if (result <= 0) 00279 { 00280 if (sequence) 00281 { 00282 SgVector<SgPoint> seq2; 00283 int result2 = PlayPreyMove(depth, lib1, lib1, adjBlk, &seq2); 00284 if (result < result2 || result == 0) 00285 { 00286 result = result2; 00287 sequence->SwapWith(&seq2); 00288 } 00289 } 00290 else 00291 { 00292 int result2 = PlayPreyMove(depth, lib1, lib1, adjBlk, 0); 00293 if (result < result2 || result == 0) 00294 result = result2; 00295 } 00296 } 00297 return result; 00298 } 00299 00300 int GoLadder::HunterLadder(int depth, SgPoint lib1, const GoPointList& adjBlk, 00301 SgVector<SgPoint>* sequence) 00302 { 00303 SG_UNUSED(adjBlk); 00304 if (CheckMoveOverflow()) 00305 return GOOD_FOR_PREY; 00306 if (sequence) 00307 sequence->SetTo(lib1); 00308 // TODO: should probably test for IsSnapback here, but don't have 00309 // the right information available. 00310 return GOOD_FOR_HUNTER + depth; 00311 } 00312 00313 int GoLadder::HunterLadder(int depth, SgPoint lib1, SgPoint lib2, 00314 const GoPointList& adjBlk, 00315 SgVector<SgPoint>* sequence) 00316 { 00317 if (CheckMoveOverflow()) 00318 return GOOD_FOR_PREY; 00319 int result = 0; 00320 if (m_bd->NumEmptyNeighbors(lib1) < m_bd->NumEmptyNeighbors(lib2)) 00321 { 00322 swap(lib1, lib2); 00323 } 00324 if (m_bd->NumEmptyNeighbors(lib1) == 3 00325 && ! SgPointUtil::AreAdjacent(lib1, lib2)) 00326 { 00327 // If not playing at lib1, then prey will play at lib1 and 00328 // get three liberties; little to update in this case. 00329 m_bd->Play(lib1, m_hunterColor); 00330 result = PreyLadder(depth + 1, lib2, adjBlk, sequence); 00331 if (sequence) 00332 sequence->PushBack(lib1); 00333 m_bd->Undo(); 00334 } 00335 else 00336 { 00337 // Two liberties, hunter to play, but not standard case. 00338 if (! adjBlk.IsEmpty() 00339 && *GoBoard::LibertyIterator(*m_bd, adjBlk[0]) == lib2) 00340 { 00341 swap(lib1, lib2); // protect hunter blocks in atari 00342 } 00343 result = PlayHunterMove(depth, lib1, lib1, lib2, 00344 adjBlk, sequence); 00345 if (0 <= result) // escaped 00346 { 00347 if (sequence) 00348 { 00349 SgVector<SgPoint> seq2; 00350 int result2 = PlayHunterMove(depth, lib2, lib1, lib2, 00351 adjBlk, &seq2); 00352 if (result2 < result) 00353 { result = result2; 00354 sequence->SwapWith(&seq2); 00355 } 00356 } 00357 else 00358 { 00359 int result2 = PlayHunterMove(depth, lib2, lib1, lib2, 00360 adjBlk, 0); 00361 if (result2 < result) 00362 result = result2; 00363 } 00364 } 00365 } 00366 return result; 00367 } 00368 00369 void GoLadder::ReduceToBlocks(GoPointList& stones) 00370 { 00371 // Single block is frequent case, don't compute block. 00372 if (stones.IsEmpty()) 00373 ; // nothing to do 00374 else if (stones.Length() <= 1) 00375 { 00376 if (m_bd->IsEmpty(stones[0])) 00377 stones.Clear(); 00378 } 00379 else 00380 { 00381 GoPointList visited; 00382 // TODO: create SgMarker member in GoLadder and use it for visited 00383 // points 00384 GoPointList result; 00385 for (GoPointList::Iterator it(stones); it; ++it) 00386 { 00387 SgPoint stone = *it; 00388 if (m_bd->Occupied(stone) && ! visited.Contains(stone)) 00389 { 00390 result.PushBack(stone); 00391 for (GoBoard::StoneIterator it(*m_bd, stone); it; ++it) 00392 visited.PushBack(*it); 00393 } 00394 } 00395 stones = result; 00396 } 00397 } 00398 00399 /** Main ladder routine */ 00400 int GoLadder::Ladder(const GoBoard& bd, SgPoint prey, SgBlackWhite toPlay, 00401 SgVector<SgPoint>* sequence, bool twoLibIsEscape) 00402 { 00403 GoModBoard modBoard(bd); 00404 m_bd = &modBoard.Board(); 00405 InitMaxMoveNumber(); 00406 if (sequence) 00407 sequence->Clear(); 00408 if (! m_bd->Occupied(prey)) 00409 return 0; 00410 if (CheckMoveOverflow()) 00411 return GOOD_FOR_PREY; 00412 int result = 0; 00413 m_preyColor = m_bd->GetStone(prey); 00414 m_hunterColor = SgOppBW(m_preyColor); 00415 int numLib = m_bd->NumLiberties(prey); 00416 if (2 < numLib) 00417 result = GOOD_FOR_PREY; 00418 else 00419 { 00420 GoBoard::LibertyIterator libit(*m_bd, prey); 00421 SgPoint lib1 = *libit; 00422 m_partOfPrey.Clear(); 00423 MarkStonesAsPrey(prey); 00424 GoPointList adjBlk = GoBoardUtil::AdjacentStones(*m_bd, prey); 00425 FilterAdjacent(adjBlk); 00426 if (toPlay == m_preyColor) 00427 { 00428 if (numLib == 1) 00429 result = PreyLadder(0, lib1, adjBlk, sequence); 00430 else if (twoLibIsEscape) // prey to play, numLib >= 2 00431 // For example, Explorer cannot treat this case as a ladder, 00432 // it messes up the logic 00433 result = GOOD_FOR_PREY; 00434 else 00435 { 00436 // Prey to play, two liberties. This is usually good, but 00437 // need to prove that there is some move that really 00438 // escapes laddercapture. 00439 // Try liberties of adjacent blocks with at most two 00440 // liberties, try lib1 and lib2, and try moves one away 00441 // from the two liberties. 00442 // Good example with three blocks that test this case: 00443 // (;GM[1]SZ[19]FF[3] 00444 // AB[qa][pa][pb][pd][pc][qe][re][rd][rc][se] 00445 // AW[pe][pf][qf][qd][qc][rb][qb][sa][sc][rf][rg][sg]) 00446 SgVector<SgPoint> movesToTry; 00447 00448 // Liberties of adj. blocks with at most two liberties. 00449 adjBlk = GoBoardUtil::AdjacentStones(*m_bd, prey); 00450 ReduceToBlocks(adjBlk); 00451 for (GoPointList::Iterator iterAdj(adjBlk); iterAdj; 00452 ++iterAdj) 00453 { 00454 SgPoint block = *iterAdj; 00455 SG_ASSERT(m_bd->IsColor(block, m_hunterColor)); 00456 SG_ASSERT(BlockIsAdjToPrey(block, 1)); 00457 if (m_bd->NumLiberties(block) <= 2) 00458 for (GoBoard::LibertyIterator it(*m_bd, block); it; 00459 ++it) 00460 movesToTry.PushBack(*it); 00461 } 00462 00463 // Liberties of blocks. 00464 ++libit; 00465 SgPoint lib2 = *libit; 00466 movesToTry.PushBack(lib1); 00467 movesToTry.PushBack(lib2); 00468 00469 // Moves one away from liberties. 00470 SgVector<SgPoint> neighbors; 00471 NeighborsOfColor(*m_bd, lib1, SG_EMPTY, &neighbors); 00472 movesToTry.Concat(&neighbors); 00473 NeighborsOfColor(*m_bd, lib2, SG_EMPTY, &neighbors); 00474 movesToTry.Concat(&neighbors); 00475 00476 // Try whether any of these moves lead to escape. 00477 for (SgVectorIterator<SgPoint> it(movesToTry); it; ++it) 00478 { 00479 if (PlayIfLegal(*m_bd, *it, m_preyColor)) 00480 { 00481 if (Ladder(bd, prey, m_hunterColor, 0, twoLibIsEscape) 00482 > 0) 00483 { 00484 if (sequence) 00485 sequence->PushBack(*it); 00486 result = GOOD_FOR_PREY; 00487 } 00488 m_bd->Undo(); 00489 } 00490 if (result != 0) 00491 break; 00492 } 00493 00494 // If none of those moves worked, prey can't escape. 00495 // This is a bit pessimistic, there may be other moves 00496 // that do lead to escape (e.g. approach moves), but 00497 // ladder algorithm doesn't know about those. 00498 if (result == 0) 00499 result = GOOD_FOR_HUNTER; 00500 } 00501 } 00502 else 00503 { 00504 if (IsSnapback(prey)) 00505 result = GOOD_FOR_PREY; 00506 else 00507 { 00508 ++libit; 00509 if (libit) // two liberties 00510 result = HunterLadder(0, lib1, *libit, adjBlk, sequence); 00511 else // one liberty 00512 result = HunterLadder(0, lib1, adjBlk, sequence); 00513 } 00514 } 00515 } 00516 if (sequence) 00517 sequence->Reverse(); // built as a stack, with first move at end. 00518 return result; 00519 } 00520 00521 /** Check whether the block at 'prey' is caught in a snapback. 00522 Snapback means that it can be captured, but it's only a single stone, and 00523 the prey can capture right back. 00524 */ 00525 bool GoLadder::IsSnapback(SgPoint prey) 00526 { 00527 bool isSnapback = false; 00528 if (m_bd->IsSingleStone(prey) && m_bd->InAtari(prey)) 00529 { 00530 SgPoint liberty = *GoBoard::LibertyIterator(*m_bd, prey); 00531 if (PlayIfLegal(*m_bd, liberty, SgOppBW(m_bd->GetStone(prey)))) 00532 { 00533 isSnapback = (m_bd->InAtari(liberty) 00534 && ! m_bd->IsSingleStone(liberty)); 00535 m_bd->Undo(); 00536 } 00537 } 00538 return isSnapback; 00539 } 00540 00541 //---------------------------------------------------------------------------- 00542 00543 bool GoLadderUtil::Ladder(const GoBoard& bd, SgPoint prey, 00544 SgBlackWhite toPlay, bool twoLibIsEscape, 00545 SgVector<SgPoint>* sequence) 00546 { 00547 SG_ASSERT(bd.IsValidPoint(prey)); 00548 SG_ASSERT(bd.Occupied(prey)); 00549 // AR: from Martin: for an unsettled block with 2 liberties, it 00550 // immediately says it can escape, but does not return a move. 00551 // Sequence is empty. So I have to special case this and look for 00552 // moves that escape from ladder myself. 00553 // ---> need to tell Martin if I find this 00554 #ifndef NDEBUG 00555 SgHashCode oldHash = bd.GetHashCode(); 00556 #endif 00557 GoLadder ladder; 00558 int result = ladder.Ladder(bd, prey, toPlay, sequence, twoLibIsEscape); 00559 #ifndef NDEBUG 00560 // Make sure Ladder didn't change the board position. 00561 SG_ASSERT(oldHash == bd.GetHashCode()); 00562 #endif 00563 SG_ASSERT(result != 0); 00564 return (result < 0); 00565 } 00566 00567 GoLadderStatus GoLadderUtil::LadderStatus(const GoBoard& bd, SgPoint prey, 00568 bool twoLibIsEscape, 00569 SgPoint* toCapture, 00570 SgPoint* toEscape) 00571 { 00572 SG_ASSERT(bd.IsValidPoint(prey)); 00573 SG_ASSERT(bd.Occupied(prey)); 00574 #ifndef NDEBUG 00575 SgHashCode oldHash = bd.GetHashCode(); 00576 #endif 00577 // Unsettled only if can capture when hunter plays first, and can escape 00578 // if prey plays first. 00579 GoLadder ladder; 00580 SgBlackWhite preyColor = bd.GetStone(prey); 00581 SgVector<SgPoint> captureSequence; 00582 GoLadderStatus status = GO_LADDER_ESCAPED; 00583 if (ladder.Ladder(bd, prey, SgOppBW(preyColor), &captureSequence, 00584 twoLibIsEscape) < 0) 00585 { 00586 SgVector<SgPoint> escapeSequence; 00587 if (ladder.Ladder(bd, prey, preyColor, &escapeSequence, 00588 twoLibIsEscape) < 0) 00589 status = GO_LADDER_CAPTURED; 00590 else 00591 { 00592 status = GO_LADDER_UNSETTLED; 00593 // Unsettled = ladder depends on who plays first, so there must 00594 // be a move that can be played. 00595 SG_ASSERT(captureSequence.NonEmpty()); 00596 // escapeSequence can be empty in 2 libs, prey to play case 00597 SG_ASSERT(twoLibIsEscape || escapeSequence.NonEmpty()); 00598 if (toCapture) 00599 *toCapture = captureSequence.Front(); 00600 if (toEscape) 00601 *toEscape = escapeSequence.IsEmpty() ? SG_PASS : 00602 escapeSequence.Front(); 00603 } 00604 } 00605 #ifndef NDEBUG 00606 // Make sure Ladder didn't change the board position. 00607 SG_ASSERT(oldHash == bd.GetHashCode()); 00608 #endif 00609 return status; 00610 } 00611 00612 bool GoLadderUtil::IsProtectedLiberty(const GoBoard& bd, SgPoint liberty, 00613 SgBlackWhite color) 00614 { 00615 bool ignoreLadder; 00616 bool ignoreKo; 00617 return IsProtectedLiberty(bd, liberty, color, ignoreLadder, ignoreKo, 00618 true); 00619 } 00620 00621 bool GoLadderUtil::IsProtectedLiberty(const GoBoard& bd1, SgPoint liberty, 00622 SgBlackWhite col, bool& byLadder, 00623 bool& isKoCut, bool tryLadder) 00624 { 00625 byLadder = false; 00626 isKoCut = false; 00627 GoModBoard mbd(bd1); 00628 GoBoard& bd = mbd.Board(); 00629 00630 const SgBlackWhite toPlay = bd1.ToPlay(); 00631 bd.SetToPlay(SgOppBW(col)); 00632 bool isProtected; 00633 if (! PlayIfLegal(bd, liberty)) 00634 isProtected = bd.LastMoveInfo(GO_MOVEFLAG_SUICIDE); 00635 // opponent cannot play there 00636 else 00637 { 00638 if (bd.LastMoveInfo(GO_MOVEFLAG_SUICIDE)) 00639 isProtected = true; 00640 else 00641 { 00642 if (bd.InAtari(liberty)) 00643 { 00644 if (bd.NumStones(liberty) > 1) 00645 isProtected = true; 00646 else 00647 { 00648 SgPoint p = bd.TheLiberty(liberty); 00649 if (PlayIfLegal(bd, p)) 00650 { 00651 isProtected = (bd.NumStones(p) != 1) 00652 || (bd.NumLiberties(p) != 1); 00653 // yes, can re-capture there 00654 bd.Undo(); 00655 } 00656 else 00657 isProtected = false; 00658 00659 if (! isProtected) 00660 isKoCut = true; 00661 } 00662 } 00663 else if (tryLadder) 00664 { 00665 isProtected = Ladder(bd, liberty, bd.ToPlay(), true); 00666 if (isProtected) 00667 byLadder = true; 00668 } 00669 else // don't try ladder 00670 isProtected = false; 00671 } 00672 bd.Undo(); 00673 } 00674 bd.SetToPlay(toPlay); 00675 return isProtected; 00676 } 00677 00678 /** try to escape/capture prey block 00679 Possible return values: 00680 - SG_PASS if already escaped/captured 00681 - the point to play 00682 - SG_NULLMOVE in case of failure 00683 */ 00684 SgPoint GoLadderUtil::TryLadder(const GoBoard& bd, SgPoint prey, 00685 SgBlackWhite firstPlayer) 00686 { 00687 SgVector<SgPoint> sequence; 00688 bool isCaptured = Ladder(bd, prey, firstPlayer, true, &sequence); 00689 // if move is same color as prey, we want to escape 00690 // else we want to capture. 00691 SgPoint p; 00692 if (isCaptured != (firstPlayer == bd.GetStone(prey))) 00693 p = sequence.IsEmpty() ? SG_PASS : sequence.Front(); 00694 else 00695 p = SG_NULLMOVE; 00696 return p; 00697 } 00698 00699 //---------------------------------------------------------------------------- 00700