00001 //---------------------------------------------------------------------------- 00002 /** @file GoBoard.cpp 00003 See GoBoard.h 00004 */ 00005 //---------------------------------------------------------------------------- 00006 00007 #include "SgSystem.h" 00008 #include "GoUctBoard.h" 00009 00010 #include <boost/static_assert.hpp> 00011 #include <algorithm> 00012 #include "GoBoardUtil.h" 00013 #include "SgNbIterator.h" 00014 #include "SgStack.h" 00015 00016 using namespace std; 00017 00018 //---------------------------------------------------------------------------- 00019 00020 namespace { 00021 00022 /** Do a consistency check. 00023 Check some data structures for consistency after and before each play 00024 (and at some other places). 00025 This is an expensive check and therefore has to be enabled at compile 00026 time. 00027 */ 00028 const bool CONSISTENCY = false; 00029 00030 } // namespace 00031 00032 //---------------------------------------------------------------------------- 00033 00034 GoUctBoard::GoUctBoard(const GoBoard& bd) 00035 : m_const(bd.Size()) 00036 { 00037 m_size = -1; 00038 Init(bd); 00039 } 00040 00041 GoUctBoard::~GoUctBoard() 00042 { 00043 } 00044 00045 void GoUctBoard::CheckConsistency() const 00046 { 00047 if (! CONSISTENCY) 00048 return; 00049 for (SgPoint p = 0; p < SG_MAXPOINT; ++p) 00050 { 00051 if (IsBorder(p)) 00052 continue; 00053 int c = m_color[p]; 00054 SG_ASSERT_EBW(c); 00055 int n = 0; 00056 for (SgNb4Iterator it(p); it; ++it) 00057 if (m_color[*it] == SG_EMPTY) 00058 ++n; 00059 SG_ASSERT(n == NumEmptyNeighbors(p)); 00060 n = 0; 00061 for (SgNb4Iterator it(p); it; ++it) 00062 if (m_color[*it] == SG_BLACK) 00063 ++n; 00064 SG_ASSERT(n == NumNeighbors(p, SG_BLACK)); 00065 n = 0; 00066 for (SgNb4Iterator it(p); it; ++it) 00067 if (m_color[*it] == SG_WHITE) 00068 ++n; 00069 SG_ASSERT(n == NumNeighbors(p, SG_WHITE)); 00070 if (c == SG_BLACK || c == SG_WHITE) 00071 CheckConsistencyBlock(p); 00072 if (c == SG_EMPTY) 00073 SG_ASSERT(m_block[p] == 0); 00074 } 00075 } 00076 00077 void GoUctBoard::CheckConsistencyBlock(SgPoint point) const 00078 { 00079 SG_ASSERT(Occupied(point)); 00080 SgBlackWhite color = GetColor(point); 00081 GoPointList stones; 00082 Block::LibertyList liberties; 00083 SgMarker mark; 00084 SgStack<SgPoint,SG_MAXPOINT> stack; 00085 stack.Push(point); 00086 bool anchorFound = false; 00087 const Block* block = m_block[point]; 00088 while (! stack.IsEmpty()) 00089 { 00090 SgPoint p = stack.Pop(); 00091 if (IsBorder(p) || ! mark.NewMark(p)) 00092 continue; 00093 if (GetColor(p) == color) 00094 { 00095 stones.PushBack(p); 00096 if (p == block->m_anchor) 00097 anchorFound = true; 00098 stack.Push(p - SG_NS); 00099 stack.Push(p - SG_WE); 00100 stack.Push(p + SG_WE); 00101 stack.Push(p + SG_NS); 00102 } 00103 else if (GetColor(p) == SG_EMPTY) 00104 liberties.PushBack(p); 00105 } 00106 SG_ASSERT(anchorFound); 00107 SG_ASSERT(color == block->m_color); 00108 SG_ASSERT(stones.SameElements(block->m_stones)); 00109 SG_ASSERT(liberties.SameElements(block->m_liberties)); 00110 SG_ASSERT(stones.Length() == NumStones(point)); 00111 } 00112 00113 void GoUctBoard::AddLibToAdjBlocks(SgPoint p, SgBlackWhite c) 00114 { 00115 if (NumNeighbors(p, c) == 0) 00116 return; 00117 SgReserveMarker reserve(m_marker2); 00118 m_marker2.Clear(); 00119 Block* b; 00120 if (m_color[p - SG_NS] == c && (b = m_block[p - SG_NS]) != 0) 00121 { 00122 m_marker2.Include(b->m_anchor); 00123 b->m_liberties.PushBack(p); 00124 } 00125 if (m_color[p + SG_NS] == c && (b = m_block[p + SG_NS]) != 0 00126 && m_marker2.NewMark(b->m_anchor)) 00127 b->m_liberties.PushBack(p); 00128 if (m_color[p - SG_WE] == c && (b = m_block[p - SG_WE]) != 0 00129 && m_marker2.NewMark(b->m_anchor)) 00130 b->m_liberties.PushBack(p); 00131 if (m_color[p + SG_WE] == c && (b = m_block[p + SG_WE]) != 0 00132 && ! m_marker2.Contains(b->m_anchor)) 00133 b->m_liberties.PushBack(p); 00134 } 00135 00136 void GoUctBoard::AddStoneToBlock(SgPoint p, Block* block) 00137 { 00138 // Stone already placed 00139 SG_ASSERT(IsColor(p, block->m_color)); 00140 block->m_stones.PushBack(p); 00141 if (IsEmpty(p - SG_NS) && ! IsAdjacentTo(p - SG_NS, block)) 00142 block->m_liberties.PushBack(p - SG_NS); 00143 if (IsEmpty(p - SG_WE) && ! IsAdjacentTo(p - SG_WE, block)) 00144 block->m_liberties.PushBack(p - SG_WE); 00145 if (IsEmpty(p + SG_WE) && ! IsAdjacentTo(p + SG_WE, block)) 00146 block->m_liberties.PushBack(p + SG_WE); 00147 if (IsEmpty(p + SG_NS) && ! IsAdjacentTo(p + SG_NS, block)) 00148 block->m_liberties.PushBack(p + SG_NS); 00149 m_block[p] = block; 00150 } 00151 00152 void GoUctBoard::CreateSingleStoneBlock(SgPoint p, SgBlackWhite c) 00153 { 00154 // Stone already placed 00155 SG_ASSERT(IsColor(p, c)); 00156 SG_ASSERT(NumNeighbors(p, c) == 0); 00157 Block& block = m_blockArray[p]; 00158 block.InitSingleStoneBlock(c, p); 00159 if (IsEmpty(p - SG_NS)) 00160 block.m_liberties.PushBack(p - SG_NS); 00161 if (IsEmpty(p - SG_WE)) 00162 block.m_liberties.PushBack(p - SG_WE); 00163 if (IsEmpty(p + SG_WE)) 00164 block.m_liberties.PushBack(p + SG_WE); 00165 if (IsEmpty(p + SG_NS)) 00166 block.m_liberties.PushBack(p + SG_NS); 00167 m_block[p] = █ 00168 } 00169 00170 bool GoUctBoard::IsAdjacentTo(SgPoint p, 00171 const GoUctBoard::Block* block) const 00172 { 00173 return m_block[p - SG_NS] == block 00174 || m_block[p - SG_WE] == block 00175 || m_block[p + SG_WE] == block 00176 || m_block[p + SG_NS] == block; 00177 } 00178 00179 void GoUctBoard::MergeBlocks(SgPoint p, const SgSList<Block*,4>& adjBlocks) 00180 { 00181 // Stone already placed 00182 SG_ASSERT(IsColor(p, adjBlocks[0]->m_color)); 00183 SG_ASSERT(NumNeighbors(p, adjBlocks[0]->m_color) > 1); 00184 Block* largestBlock = 0; 00185 int largestBlockStones = 0; 00186 for (SgSList<Block*,4>::Iterator it(adjBlocks); it; ++it) 00187 { 00188 Block* adjBlock = *it; 00189 int numStones = adjBlock->m_stones.Length(); 00190 if (numStones > largestBlockStones) 00191 { 00192 largestBlockStones = numStones; 00193 largestBlock = adjBlock; 00194 } 00195 } 00196 largestBlock->m_stones.PushBack(p); 00197 SgReserveMarker reserve(m_marker); 00198 m_marker.Clear(); 00199 for (Block::LibertyIterator lib(largestBlock->m_liberties); lib; ++lib) 00200 m_marker.Include(*lib); 00201 for (SgSList<Block*,4>::Iterator it(adjBlocks); it; ++it) 00202 { 00203 Block* adjBlock = *it; 00204 if (adjBlock == largestBlock) 00205 continue; 00206 for (Block::StoneIterator stn(adjBlock->m_stones); stn; ++stn) 00207 { 00208 largestBlock->m_stones.PushBack(*stn); 00209 m_block[*stn] = largestBlock; 00210 } 00211 for (Block::LibertyIterator lib(adjBlock->m_liberties); lib; ++lib) 00212 if (m_marker.NewMark(*lib)) 00213 largestBlock->m_liberties.PushBack(*lib); 00214 } 00215 m_block[p] = largestBlock; 00216 if (IsEmpty(p - SG_NS) && m_marker.NewMark(p - SG_NS)) 00217 largestBlock->m_liberties.PushBack(p - SG_NS); 00218 if (IsEmpty(p - SG_WE) && m_marker.NewMark(p - SG_WE)) 00219 largestBlock->m_liberties.PushBack(p - SG_WE); 00220 if (IsEmpty(p + SG_WE) && m_marker.NewMark(p + SG_WE)) 00221 largestBlock->m_liberties.PushBack(p + SG_WE); 00222 if (IsEmpty(p + SG_NS) && m_marker.NewMark(p + SG_NS)) 00223 largestBlock->m_liberties.PushBack(p + SG_NS); 00224 } 00225 00226 void GoUctBoard::UpdateBlocksAfterAddStone(SgPoint p, SgBlackWhite c, 00227 const SgSList<Block*,4>& adjBlocks) 00228 { 00229 // Stone already placed 00230 SG_ASSERT(IsColor(p, c)); 00231 int n = adjBlocks.Length(); 00232 if (n == 0) 00233 CreateSingleStoneBlock(p, c); 00234 else 00235 { 00236 if (n == 1) 00237 AddStoneToBlock(p, adjBlocks[0]); 00238 else 00239 MergeBlocks(p, adjBlocks); 00240 } 00241 } 00242 00243 void GoUctBoard::Init(const GoBoard& bd) 00244 { 00245 if (bd.Size() != m_size) 00246 InitSize(bd); 00247 m_prisoners[SG_BLACK] = bd.NumPrisoners(SG_BLACK); 00248 m_prisoners[SG_WHITE] = bd.NumPrisoners(SG_WHITE); 00249 m_koPoint = bd.KoPoint(); 00250 m_lastMove = bd.GetLastMove(); 00251 m_secondLastMove = bd.Get2ndLastMove(); 00252 m_toPlay = bd.ToPlay(); 00253 for (GoBoard::Iterator it(bd); it; ++it) 00254 { 00255 SgPoint p = *it; 00256 SgBoardColor c = bd.GetColor(p); 00257 m_color[p] = c; 00258 m_nuNeighbors[SG_BLACK][p] = bd.NumNeighbors(p, SG_BLACK); 00259 m_nuNeighbors[SG_WHITE][p] = bd.NumNeighbors(p, SG_WHITE); 00260 m_nuNeighborsEmpty[p] = bd.NumEmptyNeighbors(p); 00261 if (bd.IsEmpty(p)) 00262 m_block[p] = 0; 00263 else if (bd.Anchor(p) == p) 00264 { 00265 SgBoardColor c = m_color[p]; 00266 Block& block = m_blockArray[p]; 00267 block.InitNewBlock(c, p); 00268 for (GoBoard::StoneIterator it2(bd, p); it2; ++it2) 00269 { 00270 block.m_stones.PushBack(*it2); 00271 m_block[*it2] = █ 00272 } 00273 for (GoBoard::LibertyIterator it2(bd, p); it2; ++it2) 00274 block.m_liberties.PushBack(*it2); 00275 } 00276 } 00277 CheckConsistency(); 00278 } 00279 00280 void GoUctBoard::InitSize(const GoBoard& bd) 00281 { 00282 m_size = bd.Size(); 00283 m_nuNeighbors[SG_BLACK].Fill(0); 00284 m_nuNeighbors[SG_WHITE].Fill(0); 00285 m_nuNeighborsEmpty.Fill(0); 00286 m_block.Fill(0); 00287 for (SgPoint p = 0; p < SG_MAXPOINT; ++p) 00288 { 00289 if (bd.IsBorder(p)) 00290 { 00291 m_color[p] = SG_BORDER; 00292 m_isBorder[p] = true; 00293 } 00294 else 00295 m_isBorder[p] = false; 00296 } 00297 m_const.ChangeSize(m_size); 00298 } 00299 00300 void GoUctBoard::NeighborBlocks(SgPoint p, SgBlackWhite c, 00301 SgPoint anchors[]) const 00302 { 00303 SG_ASSERT(IsEmpty(p)); 00304 SgReserveMarker reserve(m_marker); 00305 SG_UNUSED(reserve); 00306 m_marker.Clear(); 00307 int i = 0; 00308 if (NumNeighbors(p, c) > 0) 00309 { 00310 if (IsColor(p - SG_NS, c) && m_marker.NewMark(Anchor(p - SG_NS))) 00311 anchors[i++] = Anchor(p - SG_NS); 00312 if (IsColor(p - SG_WE, c) && m_marker.NewMark(Anchor(p - SG_WE))) 00313 anchors[i++] = Anchor(p - SG_WE); 00314 if (IsColor(p + SG_WE, c) && m_marker.NewMark(Anchor(p + SG_WE))) 00315 anchors[i++] = Anchor(p + SG_WE); 00316 if (IsColor(p + SG_NS, c) && m_marker.NewMark(Anchor(p + SG_NS))) 00317 anchors[i++] = Anchor(p + SG_NS); 00318 } 00319 anchors[i] = SG_ENDPOINT; 00320 } 00321 00322 void GoUctBoard::AddStone(SgPoint p, SgBlackWhite c) 00323 { 00324 SG_ASSERT(IsEmpty(p)); 00325 SG_ASSERT_BW(c); 00326 m_color[p] = c; 00327 --m_nuNeighborsEmpty[p - SG_NS]; 00328 --m_nuNeighborsEmpty[p - SG_WE]; 00329 --m_nuNeighborsEmpty[p + SG_WE]; 00330 --m_nuNeighborsEmpty[p + SG_NS]; 00331 SgArray<int,SG_MAXPOINT>& nuNeighbors = m_nuNeighbors[c]; 00332 ++nuNeighbors[p - SG_NS]; 00333 ++nuNeighbors[p - SG_WE]; 00334 ++nuNeighbors[p + SG_WE]; 00335 ++nuNeighbors[p + SG_NS]; 00336 } 00337 00338 /** Remove liberty from adjacent blocks and kill opponent blocks without 00339 liberties. 00340 As a side effect, computes adjacent blocks of own color to avoid a 00341 second call to GetAdjacentBlocks() in UpdateBlocksAfterAddStone(). 00342 */ 00343 void GoUctBoard::RemoveLibAndKill(SgPoint p, SgBlackWhite opp, 00344 SgSList<Block*,4>& ownAdjBlocks) 00345 { 00346 SgReserveMarker reserve(m_marker); 00347 m_marker.Clear(); 00348 Block* b; 00349 if ((b = m_block[p - SG_NS]) != 0) 00350 { 00351 m_marker.Include(b->m_anchor); 00352 b->m_liberties.Exclude(p); 00353 if (b->m_color == opp) 00354 { 00355 if (b->m_liberties.Length() == 0) 00356 KillBlock(b); 00357 } 00358 else 00359 ownAdjBlocks.PushBack(b); 00360 } 00361 if ((b = m_block[p - SG_WE]) != 0 && m_marker.NewMark(b->m_anchor)) 00362 { 00363 b->m_liberties.Exclude(p); 00364 if (b->m_color == opp) 00365 { 00366 if (b->m_liberties.Length() == 0) 00367 KillBlock(b); 00368 } 00369 else 00370 ownAdjBlocks.PushBack(b); 00371 } 00372 if ((b = m_block[p + SG_WE]) != 0 && m_marker.NewMark(b->m_anchor)) 00373 { 00374 b->m_liberties.Exclude(p); 00375 if (b->m_color == opp) 00376 { 00377 if (b->m_liberties.Length() == 0) 00378 KillBlock(b); 00379 } 00380 else 00381 ownAdjBlocks.PushBack(b); 00382 } 00383 if ((b = m_block[p + SG_NS]) != 0 && ! m_marker.Contains(b->m_anchor)) 00384 { 00385 b->m_liberties.Exclude(p); 00386 if (b->m_color == opp) 00387 { 00388 if (b->m_liberties.Length() == 0) 00389 KillBlock(b); 00390 } 00391 else 00392 ownAdjBlocks.PushBack(b); 00393 } 00394 } 00395 00396 void GoUctBoard::KillBlock(const Block* block) 00397 { 00398 SgBlackWhite c = block->m_color; 00399 SgBlackWhite opp = SgOppBW(c); 00400 SgArray<int,SG_MAXPOINT>& nuNeighbors = m_nuNeighbors[c]; 00401 for (Block::StoneIterator it(block->m_stones); it; ++it) 00402 { 00403 SgPoint p = *it; 00404 AddLibToAdjBlocks(p, opp); 00405 m_color[p] = SG_EMPTY; 00406 ++m_nuNeighborsEmpty[p - SG_NS]; 00407 ++m_nuNeighborsEmpty[p - SG_WE]; 00408 ++m_nuNeighborsEmpty[p + SG_WE]; 00409 ++m_nuNeighborsEmpty[p + SG_NS]; 00410 --nuNeighbors[p - SG_NS]; 00411 --nuNeighbors[p - SG_WE]; 00412 --nuNeighbors[p + SG_WE]; 00413 --nuNeighbors[p + SG_NS]; 00414 m_capturedStones.PushBack(p); 00415 m_block[p] = 0; 00416 } 00417 int nuStones = block->m_stones.Length(); 00418 m_prisoners[c] += nuStones; 00419 if (nuStones == 1) 00420 // Remember that single stone was captured, check conditions on 00421 // capturing block later 00422 m_koPoint = block->m_anchor; 00423 } 00424 00425 void GoUctBoard::Play(SgPoint p) 00426 { 00427 SG_ASSERT(p >= 0); // No special move, see SgMove 00428 SG_ASSERT(p == SG_PASS || (IsValidPoint(p) && IsEmpty(p))); 00429 CheckConsistency(); 00430 m_koPoint = SG_NULLPOINT; 00431 m_capturedStones.Clear(); 00432 SgBlackWhite opp = SgOppBW(m_toPlay); 00433 if (p != SG_PASS) 00434 { 00435 AddStone(p, m_toPlay); 00436 SgSList<Block*,4> adjBlocks; 00437 if (NumNeighbors(p, SG_BLACK) > 0 || NumNeighbors(p, SG_WHITE) > 0) 00438 RemoveLibAndKill(p, opp, adjBlocks); 00439 UpdateBlocksAfterAddStone(p, m_toPlay, adjBlocks); 00440 if (m_koPoint != SG_NULLPOINT) 00441 if (NumStones(p) > 1 || NumLiberties(p) > 1) 00442 m_koPoint = SG_NULLPOINT; 00443 SG_ASSERT(HasLiberties(p)); // Suicide not supported by GoUctBoard 00444 } 00445 m_secondLastMove = m_lastMove; 00446 m_lastMove = p; 00447 m_toPlay = opp; 00448 CheckConsistency(); 00449 } 00450 00451 //----------------------------------------------------------------------------