Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

HexBoard.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file HexBoard.cpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #include "Time.hpp"
00007 #include "BoardUtils.hpp"
00008 #include "BitsetIterator.hpp"
00009 #include "Groups.hpp"
00010 #include "VCSet.hpp"
00011 #include "HexBoard.hpp"
00012 #include "VCUtils.hpp"
00013 
00014 using namespace benzene;
00015 
00016 //----------------------------------------------------------------------------
00017 
00018 HexBoard::HexBoard(int width, int height, const ICEngine& ice,
00019                    VCBuilderParam& param)
00020     : m_brd(width, height), 
00021       m_ice(&ice),
00022       m_groups(),
00023       m_patterns(m_brd),
00024       m_builder(param),
00025       m_use_vcs(true),
00026       m_use_ice(true),
00027       m_use_decompositions(true),
00028       m_backup_ice_info(true)
00029 {
00030     Initialize();
00031 }
00032 
00033 /** @warning This is not very maintainable! How to make this
00034     copy-constructable nicely, even though it has a scoped_ptr? */
00035 HexBoard::HexBoard(const HexBoard& other)
00036     : m_brd(other.m_brd),
00037       m_ice(other.m_ice),
00038       m_groups(other.m_groups),
00039       m_patterns(m_brd),
00040       m_builder(other.m_builder),
00041       m_history(other.m_history),
00042       m_inf(other.m_inf),
00043       m_use_vcs(other.m_use_vcs),
00044       m_use_ice(other.m_use_ice),
00045       m_use_decompositions(other.m_use_decompositions),
00046       m_backup_ice_info(other.m_backup_ice_info)
00047 {
00048     m_patterns.CopyState(other.GetPatternState());
00049     for (BWIterator color; color; ++color)
00050     {
00051         m_cons[*color].reset(new VCSet(*other.m_cons[*color]));
00052         m_log[*color] = m_log[*color];
00053     }
00054 }
00055 
00056 void HexBoard::Initialize()
00057 {
00058     GroupBuilder::Build(m_brd, m_groups);
00059     for (BWIterator c; c; ++c) 
00060         m_cons[*c].reset(new VCSet(Const(), *c));
00061     ClearHistory();
00062 }
00063 
00064 HexBoard::~HexBoard()
00065 {
00066 }
00067 
00068 //----------------------------------------------------------------------------
00069 
00070 void HexBoard::ComputeInferiorCells(HexColor color_to_move)
00071 {
00072     if (m_use_ice) 
00073     {
00074         InferiorCells inf;
00075         m_ice->ComputeInferiorCells(color_to_move, m_groups, m_patterns, inf);
00076         IceUtil::Update(m_inf, inf);
00077     }
00078 }
00079 
00080 void HexBoard::BuildVCs()
00081 {
00082     for (BWIterator c; c; ++c)
00083         m_builder.Build(*m_cons[*c], m_groups, m_patterns);
00084 }
00085 
00086 void HexBoard::BuildVCs(const Groups& oldGroups, 
00087                         bitset_t added[BLACK_AND_WHITE], bool use_changelog)
00088 {
00089     HexAssert((added[BLACK] & added[WHITE]).none());
00090     for (BWIterator c; c; ++c)
00091     {
00092         ChangeLog<VC>* log = (use_changelog) ? &m_log[*c] : 0;
00093         m_builder.Build(*m_cons[*c], oldGroups, m_groups, m_patterns, 
00094                         added, log);
00095     }
00096 }
00097 
00098 void HexBoard::MarkChangeLog()
00099 {
00100     m_log[BLACK].push(ChangeLog<VC>::MARKER, VC());
00101     m_log[WHITE].push(ChangeLog<VC>::MARKER, VC());
00102 }
00103 
00104 void HexBoard::RevertVCs()
00105 {
00106     for (BWIterator c; c; ++c)
00107         m_cons[*c]->Revert(m_log[*c]);
00108 }
00109 
00110 /** In non-terminal states, checks for combinatorial decomposition
00111     with a vc using BoardUtils::FindCombinatorialDecomposition().
00112     Plays the carrier using AddStones(). Loops until no more
00113     decompositions are found. */
00114 void HexBoard::HandleVCDecomposition(HexColor color_to_move, bool use_changelog)
00115 {
00116     if (!m_use_decompositions) 
00117         return;
00118 
00119     /** @todo Check for a vc win/loss here instead of just solid
00120     chains. */
00121     if (m_groups.IsGameOver()) 
00122         return;
00123 
00124     int decompositions = 0;
00125     for (;;) 
00126     {
00127         bool found = false;
00128         for (BWIterator c; c; ++c) 
00129         {
00130             bitset_t captured;
00131             if (BoardUtils::FindCombinatorialDecomposition(*this, *c,
00132                                captured))
00133             {
00134                 LogFine() << "Decomposition " << decompositions << ": for " 
00135               << *c << ".\n" << m_brd.Write(captured) << '\n';
00136             
00137                 AddStones(*c, captured, color_to_move, use_changelog);
00138                 m_inf.AddCaptured(*c, captured);
00139             
00140                 LogFine() << "After decomposition " << decompositions 
00141               << ": " << m_brd << '\n';
00142                 
00143                 decompositions++;
00144                 found = true;
00145                 break;
00146             } 
00147         }
00148         if (!found) 
00149             break;
00150     }
00151     LogFine() << "Found " << decompositions << " decompositions.\n";
00152 }
00153 
00154 void HexBoard::ComputeAll(HexColor color_to_move)
00155 {
00156     double s = Time::Get();
00157 
00158     m_patterns.Update();
00159     GroupBuilder::Build(m_brd, m_groups);
00160     m_inf.Clear();
00161 
00162     ComputeInferiorCells(color_to_move);
00163 
00164     if (m_use_vcs)
00165     {
00166         m_builder.ClearStatistics();
00167         BuildVCs();
00168         HandleVCDecomposition(color_to_move, false);
00169     }
00170 
00171     double e = Time::Get();
00172     LogFine() << (e-s) << "s to compute all.\n";
00173 }
00174 
00175 void HexBoard::PlayMove(HexColor color, HexPoint cell)
00176 {
00177     LogFine() << "Playing (" << color << ", " << cell << ")\n";
00178 
00179     double s = Time::Get();
00180     PushHistory(color, cell);
00181     bitset_t old_black = m_brd.GetColor(BLACK);
00182     bitset_t old_white = m_brd.GetColor(WHITE);
00183 
00184     m_brd.PlayMove(color, cell);
00185     m_patterns.Update(cell);
00186     Groups oldGroups(m_groups);
00187     GroupBuilder::Build(m_brd, m_groups);
00188 
00189     ComputeInferiorCells(!color);
00190 
00191     bitset_t added[BLACK_AND_WHITE];
00192     added[BLACK] = m_brd.GetColor(BLACK) - old_black;
00193     added[WHITE] = m_brd.GetColor(WHITE) - old_white;
00194 
00195     if (m_use_vcs)
00196     {
00197         m_builder.ClearStatistics();
00198         MarkChangeLog();
00199         BuildVCs(oldGroups, added, true);
00200         HandleVCDecomposition(!color, true);
00201     }
00202     double e = Time::Get();
00203     LogFine() << (e-s) << "s to play stones.\n";
00204 }
00205 
00206 void HexBoard::PlayStones(HexColor color, const bitset_t& played,
00207                           HexColor color_to_move)
00208 {
00209     LogFine() << "Playing (" << color << ","
00210               << HexPointUtil::ToString(played) << ")\n";
00211     HexAssert(BitsetUtil::IsSubsetOf(played, GetPosition().GetEmpty()));
00212 
00213     double s = Time::Get();
00214     PushHistory(color, INVALID_POINT);
00215     bitset_t old_black = m_brd.GetColor(BLACK);
00216     bitset_t old_white = m_brd.GetColor(WHITE);
00217 
00218     m_brd.AddColor(color, played);
00219     m_patterns.Update(played);
00220     Groups oldGroups(m_groups);
00221     GroupBuilder::Build(m_brd, m_groups);
00222 
00223     ComputeInferiorCells(color_to_move);
00224 
00225     bitset_t added[BLACK_AND_WHITE];
00226     added[BLACK] = m_brd.GetColor(BLACK) - old_black;
00227     added[WHITE] = m_brd.GetColor(WHITE) - old_white;
00228 
00229     if (m_use_vcs)
00230     {
00231         m_builder.ClearStatistics();
00232         MarkChangeLog();
00233         BuildVCs(oldGroups, added, true);
00234         HandleVCDecomposition(color_to_move, true);
00235     }
00236 
00237     double e = Time::Get();
00238     LogFine() << (e-s) << "s to play stones.\n";
00239 }
00240 
00241 /** Adds stones for color to board with color_to_move about to
00242     play next; added stones must be a subset of the empty cells.
00243     Does not affect the hash of this state. State is not pushed
00244     onto stack, so a call to UndoMove() will undo these changes
00245     along with the last changes that changed the stack. */
00246 void HexBoard::AddStones(HexColor color, const bitset_t& played,
00247                          HexColor color_to_move, bool use_changelog)
00248 {
00249     HexAssert(BitsetUtil::IsSubsetOf(played, GetPosition().GetEmpty()));
00250     LogFine() << "Adding (" << color << ", "
00251               << HexPointUtil::ToString(played) << ")\n";
00252 
00253     double s = Time::Get();
00254     bitset_t old_black = m_brd.GetColor(BLACK);
00255     bitset_t old_white = m_brd.GetColor(WHITE);
00256 
00257     m_brd.AddColor(color, played);
00258     m_patterns.Update(played);
00259     Groups oldGroups(m_groups);
00260     GroupBuilder::Build(m_brd, m_groups);
00261 
00262     ComputeInferiorCells(color_to_move);
00263 
00264     bitset_t added[BLACK_AND_WHITE];
00265     added[BLACK] = m_brd.GetColor(BLACK) - old_black;
00266     added[WHITE] = m_brd.GetColor(WHITE) - old_white;
00267 
00268     if (m_use_vcs)
00269         BuildVCs(oldGroups, added, use_changelog); 
00270 
00271     double e = Time::Get();
00272     LogFine() << (e-s) << "s to add stones.\n";
00273 }
00274 
00275 void HexBoard::UndoMove()
00276 {
00277     double s = Time::Get();
00278 
00279     PopHistory();
00280     m_patterns.Update();
00281 
00282     double e = Time::Get();
00283     LogFine() << (e-s) << "s to undo move.\n";
00284 }
00285 
00286 //----------------------------------------------------------------------------
00287 
00288 void HexBoard::ClearHistory()
00289 {
00290     m_history.clear();
00291 }
00292 
00293 void HexBoard::PushHistory(HexColor color, HexPoint cell)
00294 {
00295     m_history.push_back(History(m_brd, m_groups, m_inf, color, cell));
00296 }
00297 
00298 /** Restores the old board position, backs up ice info, and reverts
00299     virtual connections. */
00300 void HexBoard::PopHistory()
00301 {
00302     HexAssert(!m_history.empty());
00303 
00304     History hist = m_history.back();
00305     m_history.pop_back();
00306 
00307     m_brd.SetPosition(hist.board);
00308     if (m_backup_ice_info && hist.last_played != INVALID_POINT)
00309     {
00310         // Cells that were not marked as inferior in parent state
00311         // and are either dead or captured (for the color to play in the
00312         // parent state) are marked as dominated. 
00313         bitset_t a = m_brd.GetEmpty() - hist.inf.All();
00314         a &= m_inf.Dead() | m_inf.Captured(hist.to_play);
00315 
00316         for (BitsetIterator p(a); p; ++p) 
00317             hist.inf.AddDominated(*p, hist.last_played);
00318     }
00319     m_inf = hist.inf;
00320     m_groups = hist.groups;
00321     RevertVCs();
00322 }
00323 
00324 //----------------------------------------------------------------------------


6 Jan 2011 Doxygen 1.6.3