Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

PatternState.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file PatternState.cpp */
00003 //----------------------------------------------------------------------------
00004 
00005 #include "BitsetIterator.hpp"
00006 #include "BoardUtils.hpp"
00007 #include "PatternState.hpp"
00008 
00009 using namespace benzene;
00010 
00011 //----------------------------------------------------------------------------
00012 
00013 const PatternMatcherData* PatternMatcherData::Get(const ConstBoard* brd)
00014 {
00015     static std::vector<const PatternMatcherData*> data;
00016     for (std::size_t i=0; i<data.size(); ++i) 
00017     {
00018         if (*brd == *data[i]->brd)
00019             return data[i];
00020     }
00021 
00022     LogFine() << "Data does not exist. Creating..." << '\n';
00023 
00024     data.push_back(new PatternMatcherData(brd));
00025     return data.back();
00026 }
00027 
00028 PatternMatcherData::PatternMatcherData(const ConstBoard* brd)
00029     : brd(brd)
00030 {
00031     Initialize();
00032 }
00033 
00034 /** For each cell, store the slice and godel for every other cell. */
00035 void PatternMatcherData::Initialize()
00036 {
00037     LogFine() << "PatternMatcherData::Initialize " 
00038           << "(" << brd->Width() << " x " << brd->Height() <<")" << '\n';
00039 
00040     memset(played_in_slice, 0, sizeof(played_in_slice));
00041     memset(played_in_godel, 0, sizeof(played_in_godel));
00042     memset(played_in_edge,  0, sizeof(played_in_edge));
00043     memset(inverse_slice_godel, 0, sizeof(inverse_slice_godel));
00044 
00045     for (BoardIterator ip1=brd->Interior(); ip1; ++ip1) 
00046     {
00047         int x, y;
00048         HexPoint p1 = *ip1;
00049         HexPointUtil::pointToCoords(p1, x, y);
00050 
00051         for (int s=0; s<Pattern::NUM_SLICES; s++) 
00052         {
00053             int fwd = s;
00054             int lft = (s + 2) % NUM_DIRECTIONS;
00055         
00056             int x1 = x + HexPointUtil::DeltaX(fwd); 
00057             int y1 = y + HexPointUtil::DeltaY(fwd);
00058 
00059             for (int i=1, g=0; i<=Pattern::MAX_EXTENSION; i++) 
00060             {
00061                 int x2 = x1;
00062                 int y2 = y1;
00063                 for (int j=0; j<i; j++) 
00064                 {
00065                     // handle obtuse corner: both colors get it. 
00066                     if (x2 == -1 && y2 == brd->Height()) 
00067                     {
00068                         // southwest obtuse corner
00069                         played_in_edge[p1][SOUTH - FIRST_EDGE][s] 
00070                             |= (1 << g);
00071                         played_in_edge[p1][WEST - FIRST_EDGE][s]
00072                             |= (1 << g);
00073                     } 
00074                     // handle obtuse corner: both colors get it. 
00075                     else if (x2 == brd->Width() && y2 == -1) 
00076                     {
00077                         // northeast obtuse corner
00078                         played_in_edge[p1][NORTH - FIRST_EDGE][s] 
00079                             |= (1 << g);
00080                         played_in_edge[p1][EAST - FIRST_EDGE][s]
00081                             |= (1 << g);
00082                     } 
00083                     else 
00084                     {
00085                         // handle all valid interior cells and edges
00086                         HexPoint p2 
00087                             = BoardUtils::CoordsToPoint(*brd, x2, y2);
00088 
00089                         if (p2 != INVALID_POINT) 
00090                         {
00091                             if (HexPointUtil::isEdge(p2)) 
00092                             {
00093                                 played_in_edge[p1][p2 - FIRST_EDGE][s] 
00094                                     |= (1 << g);
00095                             } 
00096                             else 
00097                             {
00098                                 played_in_slice[p1][p2] = s;
00099                                 played_in_godel[p1][p2] = (1 << g);
00100                             }
00101                             inverse_slice_godel[p1][s][g] = p2;
00102                         }
00103                     }
00104 
00105                     x2 += HexPointUtil::DeltaX(lft);
00106                     y2 += HexPointUtil::DeltaY(lft);
00107                     g++;
00108                 }
00109                 x1 += HexPointUtil::DeltaX(fwd);
00110                 y1 += HexPointUtil::DeltaY(fwd);
00111             }
00112         }
00113     }
00114 }
00115 
00116 HexPoint PatternMatcherData::GetRotatedMove(HexPoint cell, int slice, 
00117                                             int bit, int angle) const
00118 {
00119     slice = (slice + 6 - angle) % Pattern::NUM_SLICES;
00120     return inverse_slice_godel[cell][slice][bit];
00121 }
00122 
00123 //----------------------------------------------------------------------------
00124 
00125 PatternState::PatternState(StoneBoard& brd)
00126     : m_brd(brd),
00127       m_data(PatternMatcherData::Get(&m_brd.Const())),
00128       m_update_radius(Pattern::MAX_EXTENSION)
00129 {
00130     ClearGodels();
00131 }
00132 
00133 PatternState::~PatternState()
00134 {
00135 }
00136 
00137 //----------------------------------------------------------------------------
00138 
00139 void PatternState::UpdateRingGodel(HexPoint cell)
00140 {
00141     HexAssert(m_brd.Const().IsCell(cell));
00142     HexColor color = m_brd.GetColor(cell);
00143     HexAssert(HexColorUtil::isBlackWhite(color));
00144     
00145     /** @note if Pattern::NUM_SLICES != 6, this won't work!! This also
00146         relies on the fact that slice 3 is opposite 0, 4 opposite 1,
00147         etc. */
00148     HexAssert(Pattern::NUM_SLICES == 6);
00149     for (int opp_slice = 3, slice = 0; slice < Pattern::NUM_SLICES; ++slice) 
00150     {
00151         HexPoint p = m_data->inverse_slice_godel[cell][slice][0];
00152         m_ring_godel[p].AddColorToSlice(opp_slice, color);
00153         m_ring_godel[p].RemoveColorFromSlice(opp_slice, EMPTY);
00154         if (++opp_slice == Pattern::NUM_SLICES) opp_slice = 0;
00155     }
00156 }
00157 
00158 void PatternState::Update(HexPoint cell)
00159 {
00160     if (HexPointUtil::isSwap(cell)) 
00161         return;
00162 
00163     HexAssert(m_brd.Const().IsLocation(cell));
00164 
00165     int r = m_update_radius;
00166     HexColor color = m_brd.GetColor(cell);
00167     HexAssert(HexColorUtil::isBlackWhite(color));
00168 
00169     if (HexPointUtil::isEdge(cell)) 
00170         goto handleEdge;
00171     
00172     for (BoardIterator p = m_brd.Const().Nbs(cell, r); p; ++p) 
00173     {
00174         int slice = m_data->played_in_slice[*p][cell];
00175         int godel = m_data->played_in_godel[*p][cell];
00176         m_slice_godel[*p][color][slice] |= godel;
00177 
00178         // Update *p's ring godel if we played next to it
00179         if (godel == 1)
00180         {
00181             m_ring_godel[*p].AddColorToSlice(slice, color);
00182             m_ring_godel[*p].RemoveColorFromSlice(slice, EMPTY);
00183         }
00184     }
00185     return;
00186 
00187  handleEdge:
00188 
00189     int edge = cell - FIRST_EDGE;
00190     for (BoardIterator p = m_brd.Const().Nbs(cell, r); p; ++p) 
00191     {
00192         for (int slice = 0; slice < Pattern::NUM_SLICES; ++slice)
00193         {
00194             int godel = m_data->played_in_edge[*p][edge][slice];
00195             m_slice_godel[*p][color][slice] |= godel;
00196 
00197             // Update *p's ring godel if we played next to it.
00198             // Must use AddColorToSlice instead of SetSliceToColor
00199             // because the obtuse corner is both black and white.
00200             if ((godel & 1) == 1)
00201             {
00202                 m_ring_godel[*p].AddColorToSlice(slice, color);
00203                 m_ring_godel[*p].RemoveColorFromSlice(slice, EMPTY);
00204             }
00205         }            
00206     }
00207 }
00208 
00209 void PatternState::Update(const bitset_t& changed)
00210 {
00211     for (BitsetIterator p(changed); p; ++p) 
00212     {
00213         HexAssert(m_brd.IsOccupied(*p));
00214         Update(*p);
00215     }
00216 }
00217 
00218 void PatternState::Update()
00219 {
00220     ClearGodels();
00221     for (BitsetIterator p(m_brd.GetBlack() | m_brd.GetWhite()); p; ++p) 
00222         Update(*p);
00223 }
00224 
00225 void PatternState::ClearGodels()
00226 {
00227     memset(m_slice_godel, 0, sizeof(m_slice_godel));
00228     for (BoardIterator p(m_brd.Const().Interior()); p; ++p)
00229         m_ring_godel[*p].SetEmpty();
00230 }
00231 
00232 void PatternState::CopyState(const PatternState& other)
00233 {
00234     HexAssert(m_brd.Const() == other.m_brd.Const());
00235     m_update_radius = other.m_update_radius;
00236     memcpy(m_slice_godel, other.m_slice_godel, sizeof(m_slice_godel));
00237     memcpy(m_ring_godel, other.m_ring_godel, sizeof(m_ring_godel));
00238 }
00239 
00240 //----------------------------------------------------------------------------
00241 
00242 void PatternState::MatchOnCell(const HashedPatternSet& patset, 
00243                                HexPoint cell, MatchMode mode,
00244                                PatternHits& hits) const
00245 {
00246     const RingGodel& ring_godel = m_ring_godel[cell];
00247     const RotatedPatternList& rlist = patset.ListForGodel(ring_godel);
00248     RotatedPatternList::const_iterator it = rlist.begin();
00249     for (; it != rlist.end(); ++it) 
00250     {
00251         std::vector<HexPoint> moves1, moves2;
00252         if (CheckRotatedPattern(cell, *it, moves1, moves2)) 
00253         {
00254             hits.push_back(PatternHit(it->pattern(), moves1, moves2));
00255             if (mode == STOP_AT_FIRST_HIT)
00256                 break;
00257         }
00258     }
00259 }
00260 
00261 bitset_t PatternState::MatchOnBoard(const bitset_t& consider, 
00262                                     const HashedPatternSet& patset, 
00263                                     MatchMode mode, 
00264                                     std::vector<PatternHits>& hits) const
00265 {
00266     bitset_t ret;
00267     bitset_t lookat = consider & Board().Const().GetCells();
00268     for (BitsetIterator p(lookat); p; ++p)
00269     {
00270         MatchOnCell(patset, *p, mode, hits[*p]);
00271         if (!hits[*p].empty())
00272             ret.set(*p);
00273     }
00274     return ret;
00275 }
00276 
00277 bitset_t PatternState::MatchOnBoard(const bitset_t& consider, 
00278                                     const HashedPatternSet& patset) const
00279 {
00280     bitset_t ret;    
00281     bitset_t lookat = consider & Board().Const().GetCells();
00282     for (BitsetIterator p(lookat); p; ++p) 
00283     {
00284         PatternHits hits;
00285         MatchOnCell(patset, *p, STOP_AT_FIRST_HIT, hits);
00286         if (!hits.empty())
00287             ret.set(*p);
00288     }
00289     return ret;
00290 }
00291 
00292 //-----------------------------------------------------------------------------
00293 
00294 /** Checks the pre-rotated pattern against the board. Returns true if
00295     it matches.  Pattern encoded moves are stored in moves. */
00296 bool PatternState::CheckRotatedPattern(HexPoint cell, 
00297                                        const RotatedPattern& rotpat,
00298                                        std::vector<HexPoint>& moves1,
00299                                        std::vector<HexPoint>& moves2) const
00300 {
00301     HexAssert(m_brd.Const().IsCell(cell));
00302 
00303     m_statistics.pattern_checks++;
00304 
00305     bool matches = CheckRingGodel(cell, rotpat);
00306 
00307     const Pattern* pattern = rotpat.pattern();
00308     if (matches && pattern->extension() > 1)
00309         matches = CheckRotatedSlices(cell, rotpat);
00310 
00311     if (matches) 
00312     {
00313         if (pattern->getFlags() & Pattern::HAS_MOVES1) 
00314         {
00315             for (unsigned i = 0; i < pattern->getMoves1().size(); ++i) 
00316             {
00317                 int slice = pattern->getMoves1()[i].first;
00318                 int bit = pattern->getMoves1()[i].second;
00319                 moves1.push_back(m_data->GetRotatedMove(cell, slice, bit, 
00320                                                         rotpat.angle()));
00321             }
00322         }
00323 
00324         if (pattern->getFlags() & Pattern::HAS_MOVES2) 
00325         {
00326             for (unsigned i = 0; i < pattern->getMoves2().size(); ++i) 
00327             {
00328                 int slice = pattern->getMoves2()[i].first;
00329                 int bit = pattern->getMoves2()[i].second;
00330                 moves2.push_back(m_data->GetRotatedMove(cell, slice, bit, 
00331                                                         rotpat.angle()));
00332             }
00333         }
00334         return true;
00335     }
00336     return false;
00337 }
00338 
00339 /** Convenience method. */
00340 bool PatternState::CheckRotatedSlices(HexPoint cell, 
00341                                       const RotatedPattern& rotpat) const
00342 {
00343     return CheckRotatedSlices(cell, *rotpat.pattern(), rotpat.angle());
00344 }
00345 
00346 /** Returns true if pattern's slices rotated by angle match the board
00347     when pattern is centered at cell. */
00348 bool PatternState::CheckRotatedSlices(HexPoint cell, const Pattern& pattern,
00349                                       int angle) const
00350 {
00351     const int *gb = m_slice_godel[cell][BLACK];
00352     const int *gw = m_slice_godel[cell][WHITE];
00353     const Pattern::slice_t* pat = pattern.getData();
00354 
00355     bool matches = true;
00356     for (int i = 0; matches && i < Pattern::NUM_SLICES; ++i) 
00357     {
00358         m_statistics.slice_checks++;
00359         
00360         int j = (angle + i) % Pattern::NUM_SLICES;
00361      
00362         int black_b = gb[i] & pat[j][Pattern::FEATURE_CELLS];
00363         int white_b = gw[i] & pat[j][Pattern::FEATURE_CELLS];
00364         int empty_b = black_b | white_b;
00365 
00366         int black_p = pat[j][Pattern::FEATURE_BLACK];
00367         int white_p = pat[j][Pattern::FEATURE_WHITE];
00368         int empty_p = pat[j][Pattern::FEATURE_CELLS] - 
00369                       pat[j][Pattern::FEATURE_BLACK] -
00370                       pat[j][Pattern::FEATURE_WHITE];
00371 
00372         // black cells on the board must be a superset of the
00373         // black cells in the pattern since the obtuse corner
00374         // is both black and white. 
00375 
00376         // @todo all cells to be black/white/empty (ie, dead cells),
00377         // in which case we would use ((empty_b & empty_p) != empty_p)
00378 
00379         if (empty_b & empty_p)
00380             matches = false;
00381         else if ((black_b & black_p) != black_p)
00382             matches = false;
00383         else if ((white_b & white_p) != white_p)
00384             matches = false;
00385     }
00386     return matches;
00387 }
00388 
00389 /** Returns true if the pattern's ring godel matches the board. */
00390 bool PatternState::CheckRingGodel(HexPoint cell, 
00391                                   const RotatedPattern& rotpat) const
00392 {
00393     return CheckRingGodel(cell, *rotpat.pattern(), rotpat.angle());
00394 }
00395 
00396 /** Returns true if the pattern's ring godel matches the board. */
00397 bool PatternState::CheckRingGodel(HexPoint cell, 
00398                                   const Pattern& pattern, int angle) const
00399 {
00400     m_statistics.ring_checks++;
00401     return pattern.RingGodel(angle).MatchesGodel(m_ring_godel[cell]);
00402 }
00403 
00404 //----------------------------------------------------------------------------
00405 
00406 void PatternState::ClearPatternCheckStats()
00407 {
00408     m_statistics.pattern_checks = 0;
00409     m_statistics.ring_checks = 0;
00410     m_statistics.slice_checks = 0;
00411 }
00412 
00413 std::string PatternState::DumpPatternCheckStats() const
00414 {
00415     std::ostringstream os;
00416     os << std::endl;
00417     os << "    Patterns Checked: " << m_statistics.pattern_checks << '\n';
00418     os << " Ring Godels Checked: " << m_statistics.ring_checks << '\n';
00419     os << "      Slices Checked: " << m_statistics.slice_checks << '\n';
00420     os << " Avg Rings Per Check: " 
00421        << std::setprecision(4) 
00422        << static_cast<double>(m_statistics.ring_checks) 
00423         / static_cast<double>(m_statistics.pattern_checks) << '\n';
00424     os << "Avg Slices Per Check: " 
00425        << std::setprecision(4) 
00426        << static_cast<double>(m_statistics.slice_checks)
00427         / static_cast<double>(m_statistics.pattern_checks) << '\n';
00428     return os.str();
00429 }
00430 
00431 //----------------------------------------------------------------------------


6 Jan 2011 Doxygen 1.6.3