 Timestamp:
 Mar 31, 2006, 3:31:07 AM (13 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/gamelogic.cxx
r28 r29 190 190 return abs(a.rowb.row) <= 1 && abs(a.colb.col) <= 1; 191 191 } 192 193 194 /// Is Patch a candidate for "superset detection" based on newly revealed Patch?195 /** This looks for the case where the unexplored area around a Patch is a proper196 * superset of a neighbour's (where one of the two is newly revealed). If it197 * is, and if the number of unexplored mines near the "superset" one is either198 * equal to that near the "subset" one, or the difference is equal to the size199 * difference of the unexplored areas, then the unexplored area near200 * the "superset" one that doesn't border on the "subset" patch is either all201 * clear or all mined, respectively.202 *203 * This logic comes into play at intelligence level 3.204 */205 class SuperSet206 {207 public:208 typedef set<pair<Coords,Coords>,CoordsPair> PairList;209 210 SuperSet(PairList &worklist, Coords nr, const Patch &newly_revealed) :211 m_worklist(worklist),212 m_revealed(newly_revealed),213 m_rc(nr)214 {215 assert(is_candidate(newly_revealed));216 }217 218 /// Can this patch possibly qualify for subset/superset recognition?219 static bool is_candidate(const Patch &p) throw ()220 {221 return p.revealed() && p.near_unknown();222 }223 224 void operator()(Coords c, const Patch &p)225 {226 if (&p != &m_revealed &&227 is_candidate(p) &&228 abs(c.rowm_rc.row) <= 2 && abs(c.colm_rc.col) <= 2 &&229 min(abs(c.rowm_rc.row),abs(c.colm_rc.col)) < 2)230 {231 const int areadiff = p.near_unknown()  m_revealed.near_unknown();232 if (areadiff > 0)233 consider(m_rc, m_revealed, c, p, areadiff);234 else if (areadiff < 0)235 consider(c, p, m_rc, m_revealed, areadiff);236 }237 }238 239 private:240 PairList &m_worklist;241 const Patch &m_revealed;242 Coords m_rc;243 244 /// How many neighbours do two patches a and b have in common?245 static int overlap(Coords a, Coords b) throw ()246 {247 assert(a < b  b < a);248 const int rowdiff = abs(a.rowb.row),249 coldiff = abs(a.colb.col);250 const int bigdiff = max(rowdiff,coldiff),251 smalldiff = min(rowdiff,coldiff);252 assert(bigdiff > 0);253 assert(bigdiff <= 2);254 assert(smalldiff >= 0);255 assert(smalldiff < 2);256 assert(smalldiff <= bigdiff);257 258 return (smalldiff == 1) ? 2 : ((bigdiff == 2) ? 3 : 4);259 }260 261 void consider(Coords subc, const Patch &subp,262 Coords supc, const Patch &supp,263 int areadiff)264 {265 assert(&subp != &supp);266 assert(areadiff > 0);267 if (subp.near_unknown() <= overlap(subc,supc) &&268 (supp.near_hiddenmines() == subp.near_hiddenmines() 269 supp.near_hiddenmines() == areadiff))270 m_worklist.insert(make_pair(subc,supc));271 }272 };273 274 275 /// Add unrevealed patches that are not neighbours of given patch to set276 class NotNear277 {278 public:279 NotNear(Coords c, set<Coords> &work) : m_worklist(work), m_remote(c) {}280 281 void operator()(Coords c, const Patch &p) const282 {283 if (!p.revealed() && !are_neighbours(c, m_remote)) m_worklist.insert(c);284 }285 286 private:287 set<Coords> &m_worklist;288 Coords m_remote;289 };290 192 291 193 } // namespace … … 527 429 for_zone<1,true>(i>row,i>col,set_add<ObviousPatch>(next)); 528 430 529 /* Recognize the case where two explored patches A and B have sets of 530 * unexplored neighbours U such that 531 * 1. U(A) is a proper subset of U(B), and 532 * 2. the numbers of unexplored nearby mines M satisfy either: 533 * (a) M(B)  M(A) = 0 (in which case U(B)\U(A) is all clear) or 534 * (b) M(B)  M(A) = U(B)\U(A) (in which case U(B)\U(A) is all mines). 535 * 536 * At the moment I don't see a clever way of implementing this with mere 537 * local scalar comparisons. Unless we count use of bitfields; the full set 538 * of neighbours for a Patch fits seductively well into a byte. But that 539 * would introduce unpleasant complexity. 431 /* Recognize cases where two patches' sets of nearby unrevealed patches 432 * overlap, such that one of the two difference sets can be concluded to be 433 * minefree and the other have only mined patches. One of the two 434 * difference sets may be empty. 540 435 */ 541 436 if (m_intelligence > 2) 542 437 { 543 SuperSet::PairList cand; 544 545 // First step: filter out the possible cases, based purely on numbers 546 for (set<Coords>::const_iterator i = area.begin(); i != area.end(); ++i) 547 { 548 const Patch &p = at(i>row, i>col); 549 if (SuperSet::is_candidate(p)) 550 for_neighbours(i>row, i>col, SuperSet(cand,*i,p)); 551 } 552 553 // Iterate through candidates to find the *real* superset cases 554 for (SuperSet::PairList::const_iterator i = cand.begin(); 555 i != cand.end(); 556 ++i) 557 { 558 assert(at(i>first.row,i>first.col).revealed()); 559 assert(at(i>second.row,i>second.col).revealed()); 560 561 int subset_togo = at(i>first.row,i>first.col).near_unknown(); 562 assert(subset_togo); 563 564 // Verify that the number of unrevealed patches among the pair's set of 565 // common neighbours accounts for all of the unrevealed neighbours of 566 // the first ("subset") of the two 567 for (int r = min(0, max(i>first.row,i>second.row)1); 568 r <= max(m_rows, min(i>first.row,i>second.row)+1); 569 ++r) 570 for (int c = min(0, max(i>first.col,i>second.col)1); 571 c <= max(m_cols, min(i>first.col,i>second.col)+1); 572 ++c) 573 if (!at(r,c).revealed()) 574 subset_togo; 575 576 assert(subset_togo >= 0); 577 578 if (!subset_togo) 579 { 580 // All unrevealed neighbours accounted for! All other unrevealed 581 // neighbours of the second patch that are not neighbours of the first 582 // can be revealed. 583 for_neighbours(i>second.row, i>second.col, NotNear(i>first, next)); 584 } 585 } 438 // TODO: TODO: TODO: 586 439 } 587 440
Note: See TracChangeset
for help on using the changeset viewer.