Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

VCBuilder.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file VCBuilder.cpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #include "Hex.hpp"
00007 #include "Time.hpp"
00008 #include "BitsetIterator.hpp"
00009 #include "GraphUtils.hpp"
00010 #include "ChangeLog.hpp"
00011 #include "VCBuilder.hpp"
00012 #include "VCSet.hpp"
00013 #include "VCPattern.hpp"
00014 #include "VCUtils.hpp"
00015 
00016 #include <boost/filesystem/path.hpp>
00017 
00018 using namespace benzene;
00019 
00020 //----------------------------------------------------------------------------
00021 
00022 VCBuilderParam::VCBuilderParam()
00023     : max_ors(4),
00024       and_over_edge(false),
00025       use_patterns(true),
00026       use_non_edge_patterns(true),
00027       use_greedy_union(true),
00028       abort_on_winning_connection(false)
00029 {
00030 }
00031 
00032 //----------------------------------------------------------------------------
00033 
00034 VCBuilder::VCBuilder(VCBuilderParam& param)
00035     : m_orRule(*this), 
00036       m_param(param)
00037 {
00038     LoadCapturedSetPatterns();
00039 }
00040 
00041 VCBuilder::~VCBuilder()
00042 {
00043 }
00044 
00045 void VCBuilder::LoadCapturedSetPatterns()
00046 {
00047     using namespace boost::filesystem;
00048     path filename = path(ABS_TOP_SRCDIR) / "share" / "vc-captured-set.txt";
00049     filename.normalize();
00050 
00051     std::vector<Pattern> patterns;
00052     Pattern::LoadPatternsFromFile(filename.native_file_string().c_str(), 
00053                                   patterns);
00054 
00055     LogFine() << "--LoadCapturedSetPatterns()\n";    
00056     LogFine() << "Read " << patterns.size() << " patterns.\n";
00057     for (std::size_t i = 0; i < patterns.size(); ++i)
00058     {
00059         m_capturedSetPatterns[WHITE].push_back(patterns[i]);
00060         patterns[i].flipColors();
00061         m_capturedSetPatterns[BLACK].push_back(patterns[i]);
00062     }
00063     for (BWIterator c; c; ++c) 
00064         m_hash_capturedSetPatterns[*c].hash(m_capturedSetPatterns[*c]);
00065 }
00066 
00067 //----------------------------------------------------------------------------
00068 
00069 // Static VC construction
00070 
00071 void VCBuilder::Build(VCSet& con, const Groups& groups, 
00072                       const PatternState& patterns)
00073 {
00074     m_con = &con;
00075     m_color = con.Color();
00076     m_groups = &groups;
00077     m_brd = &m_groups->Board();
00078     m_log = 0;
00079 
00080     double s = Time::Get();
00081     m_con->Clear();
00082     m_statistics = &m_statsForColor[m_color];
00083     m_queue.clear();
00084 
00085     ComputeCapturedSets(patterns);
00086     AddBaseVCs();
00087     if (m_param.use_patterns)
00088         AddPatternVCs();
00089     DoSearch();
00090 
00091     double e = Time::Get();
00092     LogFine() << "  " << (e-s) << "s to build vcs.\n";
00093 }
00094 
00095 /** Computes the 0-connections defined by adjacency.*/
00096 void VCBuilder::AddBaseVCs()
00097 {
00098     HexColorSet not_other = HexColorSetUtil::ColorOrEmpty(m_color);
00099     for (GroupIterator x(*m_groups, not_other); x; ++x) 
00100     {
00101         for (BitsetIterator y(x->Nbs() & m_brd->GetEmpty()); y; ++y) 
00102         {
00103             VC vc(x->Captain(), *y);
00104             m_statistics->base_attempts++;
00105             if (m_con->Add(vc, m_log))
00106             {
00107                 m_statistics->base_successes++;
00108                 m_queue.push(std::make_pair(vc.x(), vc.y()));
00109             }
00110         }
00111     }
00112 }
00113 
00114 /** Adds vcs obtained by pre-computed patterns. */
00115 void VCBuilder::AddPatternVCs()
00116 {
00117     const VCPatternSet& patterns 
00118         = VCPattern::GetPatterns(m_brd->Width(), m_brd->Height(), m_color);
00119     for (std::size_t i=0; i<patterns.size(); ++i) 
00120     {
00121         const VCPattern& pat = patterns[i];
00122         if (!m_param.use_non_edge_patterns
00123             && !HexPointUtil::isEdge(pat.Endpoint(0))
00124             && !HexPointUtil::isEdge(pat.Endpoint(1)))
00125             continue;
00126         if (pat.Matches(m_color, *m_brd)) 
00127         {
00128             bitset_t carrier = pat.NotOpponent() - m_brd->GetColor(m_color);
00129             carrier.reset(pat.Endpoint(0));
00130             carrier.reset(pat.Endpoint(1));
00131             VC vc(pat.Endpoint(0), pat.Endpoint(1), carrier, VC_RULE_BASE);
00132 
00133             m_statistics->pattern_attempts++;
00134             if (m_con->Add(vc, m_log))
00135             {
00136                 m_statistics->pattern_successes++;
00137                 m_queue.push(std::make_pair(vc.x(), vc.y()));
00138             }
00139         }
00140     }
00141 }
00142 
00143 void VCBuilder::ComputeCapturedSets(const PatternState& patterns)
00144 {
00145     SG_UNUSED(patterns);
00146     for (BoardIterator p(m_brd->Const().EdgesAndInterior()); p; ++p)
00147     {
00148         m_capturedSet[*p] = EMPTY_BITSET;
00149         if (m_brd->GetColor(*p) == EMPTY)
00150         {
00151             PatternHits hits;
00152             patterns.MatchOnCell(m_hash_capturedSetPatterns[m_color],
00153                                  *p, PatternState::STOP_AT_FIRST_HIT, hits);
00154             for (std::size_t i = 0; i < hits.size(); ++i)
00155             {
00156                 const std::vector<HexPoint>& moves = hits[0].moves2();
00157                 bitset_t carrier;
00158                 for (std::size_t j = 0; j < moves.size(); ++j)
00159                     m_capturedSet[*p].set(moves[j]);
00160                 //LogInfo() << "Captured " << *p
00161                 //          << m_brd->Write(m_capturedSet[*p]) << '\n';
00162             }
00163         }
00164     }
00165 }
00166 
00167 //----------------------------------------------------------------------------
00168 // Incremental VC construction
00169 
00170 void VCBuilder::Build(VCSet& con, const Groups& oldGroups,
00171                       const Groups& newGroups, const PatternState& patterns,
00172                       bitset_t added[BLACK_AND_WHITE], ChangeLog<VC>* log)
00173 {
00174     HexAssert((added[BLACK] & added[WHITE]).none());
00175 
00176     m_con = &con;
00177     m_color = con.Color();
00178     m_groups = &newGroups;
00179     m_brd = &m_groups->Board();
00180     m_log = log;
00181 
00182     double s = Time::Get();
00183     m_statistics = &m_statsForColor[m_color];
00184     m_queue.clear();
00185 
00186     ComputeCapturedSets(patterns);
00187     Merge(oldGroups, added);
00188     if (m_param.use_patterns)
00189         AddPatternVCs();
00190     DoSearch();
00191 
00192     double e = Time::Get();
00193     LogFine() << "  " << (e-s) << "s to build vcs incrementally.\n" ;
00194 }
00195 
00196 /** @page mergeshrink Incremental Update Algorithm
00197     
00198     The connection set is updated to the new state of the board in a
00199     single pass. In this pass connections touched by opponent stones
00200     are destroyed, connections touched by friendly stones are resized,
00201     and connections in groups that are merged into larger groups are
00202     merged into the proper connection lists. This entire process is
00203     called the "merge".
00204     
00205     The merge begins by noting the set of "affected" stones. These are
00206     the stones that were just played as well as those groups adjacent
00207     to the played stones.
00208 
00209     Any list with either endpoint in the affected set will need to
00210     either pass on its connections to the list now responsible for
00211     that group or recieve connections from other lists that it is now
00212     responsible for. Lists belonging to groups that are merge into
00213     other groups are not destroyed, they remain so that undoing this
00214     merge is more efficient.
00215 
00216     Every list needs to be checked for shrinking.
00217     
00218     TODO Finish this documentation!
00219             
00220 */
00221 void VCBuilder::Merge(const Groups& oldGroups, bitset_t added[BLACK_AND_WHITE])
00222 {
00223     // Kill connections containing stones the opponent just played.
00224     // NOTE: This *must* be done in the original state, not in the
00225     // state with the newly added stones. If we are adding stones of
00226     // both colors there could be two groups of our stones that are
00227     // going to be merged, but we need to kill connections touching
00228     // the opponent stones before we do so. 
00229     RemoveAllContaining(oldGroups, added[!m_color]);
00230         
00231     // Find groups adjacent to any played stone of color; add them to
00232     // the affected set along with the played stones.
00233     bitset_t affected = added[m_color];
00234     for (BitsetIterator x(added[m_color]); x; ++x)
00235         for (BoardIterator y(m_brd->Const().Nbs(*x)); y; ++y)
00236         {
00237             const Group& grp = oldGroups.GetGroup(*y);
00238             if (grp.Color() == m_color)
00239                 affected.set(grp.Captain());
00240         }
00241 
00242     MergeAndShrink(affected, added[m_color]);
00243 }
00244 
00245 void VCBuilder::MergeAndShrink(const bitset_t& affected,
00246                                const bitset_t& added)
00247 {
00248     HexColorSet not_other = HexColorSetUtil::NotColor(!m_color);
00249     for (BoardIterator x(m_brd->Stones(not_other)); x; ++x) 
00250     {
00251         if (!m_groups->IsCaptain(*x) && !affected.test(*x)) 
00252             continue;
00253         for (BoardIterator y(m_brd->Stones(not_other)); *y != *x; ++y) 
00254         {
00255             if (!m_groups->IsCaptain(*y) && !affected.test(*y)) 
00256                 continue;
00257             HexPoint cx = m_groups->CaptainOf(*x);
00258             HexPoint cy = m_groups->CaptainOf(*y);
00259 
00260             // Lists between (cx, cx) are never used, so only do work
00261             // if it's worthwhile. This can occur if y was recently
00262             // played next to group x, now they both have the same
00263             // captain, so no point merging old connections into
00264             // (captain, captain).
00265             if (cx != cy) 
00266             {
00267                 m_queue.push(std::make_pair(cx, cy));
00268                 MergeAndShrink(added, *x, *y, cx, cy);
00269             }
00270         }
00271     }
00272 }
00273 
00274 void VCBuilder::MergeAndShrink(const bitset_t& added, 
00275                                HexPoint xin, HexPoint yin,
00276                                HexPoint xout, HexPoint yout)
00277 {
00278     HexAssert(xin != yin);
00279     HexAssert(xout != yout);
00280 
00281     VCList* fulls_in = &m_con->GetList(VC::FULL, xin, yin);
00282     VCList* semis_in = &m_con->GetList(VC::SEMI, xin, yin);
00283     VCList* fulls_out= &m_con->GetList(VC::FULL, xout, yout);
00284     VCList* semis_out= &m_con->GetList(VC::SEMI, xout, yout);
00285 
00286     HexAssert((fulls_in == fulls_out) == (semis_in == semis_out));
00287     bool doing_merge = (fulls_in != fulls_out);
00288 
00289     std::list<VC> removed;
00290     std::list<VC>::iterator it;
00291 
00292     // 
00293     // Shrink all 0-connections.
00294     //
00295     // If (doing_merge) transfer remaining connections over as well. 
00296     //
00297     fulls_in->removeAllContaining(added, removed, m_log);
00298     if (doing_merge) 
00299     { 
00300         // Copied vc's will be set to unprocessed explicitly.
00301         /** @bug There could be supersets of these fulls in semis_out! */
00302         fulls_out->add(*fulls_in, m_log);
00303     }
00304 
00305     for (it = removed.begin(); it != removed.end(); ++it) 
00306     {
00307         VC v = VC::ShrinkFull(*it, added, xout, yout);
00308         /** @bug There could be supersets of these fulls in semis_out! */
00309         if (fulls_out->add(v, m_log))
00310             m_statistics->shrunk0++;
00311     }
00312 
00313     //
00314     // Shrink all 1-connections.
00315     // if (doing_merge) transfer remaining connections
00316     // over as well. 
00317     //
00318     removed.clear();
00319     semis_in->removeAllContaining(added, removed, m_log);
00320     if (doing_merge) 
00321     {
00322         // Copied vc's will be set to unprocessed explicitly.
00323         /** @bug These could be supersets of fulls_out. */
00324         semis_out->add(*semis_in, m_log);
00325     }
00326 
00327     // Shrink connections that touch played cells.
00328     // Do not upgrade during this step. 
00329     for (it = removed.begin(); it != removed.end(); ++it) 
00330     {
00331         if (!added.test(it->key())) 
00332         {
00333             VC v = VC::ShrinkSemi(*it, added, xout, yout);
00334             /** @bug These could be supersets of fulls_out. */
00335             if (semis_out->add(v, m_log))
00336                 m_statistics->shrunk1++;
00337         }
00338     }
00339 
00340     // Upgrade semis. Need to do this after shrinking to ensure
00341     // that we remove all sc supersets from semis_out.
00342     for (it = removed.begin(); it != removed.end(); ++it) 
00343     {
00344         if (added.test(it->key())) 
00345         {
00346             VC v = VC::UpgradeSemi(*it, added, xout, yout);
00347             if (fulls_out->add(v, m_log))
00348             {
00349                 // Remove supersets from the semi-list; do not
00350                 // invalidate list intersection since this semi was a
00351                 // member of the list. Actually, this probably doesn't
00352                 // matter since the call to removeAllContaining()
00353                 // already clobbered the intersections.
00354                 semis_out->removeSuperSetsOf(v.carrier(), m_log, false);
00355                 m_statistics->upgraded++;
00356             }
00357         }
00358     }
00359 }
00360 
00361 /** Removes all connections whose intersection with given set is
00362     non-empty. Any list that is modified is added to the queue, since
00363     some unprocessed connections could have been brought under the
00364     softlimit.
00365 */
00366 void VCBuilder::RemoveAllContaining(const Groups& oldGroups,
00367                                     const bitset_t& bs)
00368 {
00369     // Use old groupset, but skip old groups that are 
00370     // now the opponent's color--don't need to do anything for those.
00371     HexColorSet not_other = HexColorSetUtil::NotColor(!m_color);
00372     for (GroupIterator x(oldGroups, not_other); x; ++x) 
00373     { 
00374         HexPoint xc = x->Captain();
00375     if (m_groups->GetGroup(xc).Color() == !m_color)
00376         continue;
00377         for (GroupIterator y(oldGroups, not_other); &*y != &*x; ++y) 
00378         {
00379             HexPoint yc = y->Captain();
00380         if (m_groups->GetGroup(yc).Color() == !m_color)
00381             continue;
00382             int cur0 = m_con->GetList(VC::FULL, xc, yc)
00383                 .removeAllContaining(bs, m_log);
00384             m_statistics->killed0 += cur0; 
00385             int cur1 = m_con->GetList(VC::SEMI, xc, yc)
00386                 .removeAllContaining(bs, m_log);
00387             m_statistics->killed1 += cur1;
00388             if (cur0 || cur1)
00389                 m_queue.push(std::make_pair(xc, yc));
00390         }
00391     }
00392 }
00393 
00394 //----------------------------------------------------------------------------
00395 // VC Construction methods
00396 //----------------------------------------------------------------------------
00397 
00398 void VCBuilder::ProcessSemis(HexPoint xc, HexPoint yc)
00399 {
00400     VCList& semis = m_con->GetList(VC::SEMI, xc, yc);
00401     VCList& fulls = m_con->GetList(VC::FULL, xc, yc);
00402 
00403     bitset_t capturedSet = m_capturedSet[xc] | m_capturedSet[yc];
00404     bitset_t uncapturedSet = capturedSet;
00405     uncapturedSet.flip();
00406 
00407     // Nothing to do, so abort. 
00408     if ((semis.hardIntersection() & uncapturedSet).any())
00409         return;
00410 
00411     int soft = semis.softlimit();
00412     VCList::iterator cur = semis.begin();
00413     VCList::iterator end = semis.end();
00414     std::list<VC> added;
00415 
00416     for (int count=0; count<soft && cur!=end; ++cur, ++count) 
00417     {
00418         if (!cur->processed()) 
00419         {
00420             m_statistics->doOrs++;
00421             if (m_orRule(*cur, &semis, &fulls, added, m_param.max_ors, 
00422                          m_log, *m_statistics))
00423             {
00424                 m_statistics->goodOrs++;
00425             }
00426 
00427             cur->setProcessed(true);
00428             
00429             if (m_log)
00430                 m_log->push(ChangeLog<VC>::PROCESSED, *cur);
00431         }
00432     }
00433 
00434     // If no full exists, create one by unioning the entire list
00435     if (fulls.empty()) 
00436     {
00437         bitset_t carrier = m_param.use_greedy_union 
00438             ? semis.getGreedyUnion() 
00439             : semis.getUnion();
00440 
00441         fulls.add(VC(xc, yc, carrier | capturedSet, VC_RULE_ALL), m_log);
00442         // @note No need to remove supersets of v from the semi
00443         // list since there can be none!
00444     } 
00445 }
00446 
00447 void VCBuilder::ProcessFulls(HexPoint xc, HexPoint yc)
00448 {
00449     VCList& fulls = m_con->GetList(VC::FULL, xc, yc);
00450     int soft = fulls.softlimit();
00451     VCList::iterator cur = fulls.begin();
00452     VCList::iterator end = fulls.end();
00453     for (int count=0; count<soft && cur!=end; ++cur, ++count) 
00454     {
00455         if (!cur->processed()) 
00456         {
00457             andClosure(*cur);
00458             cur->setProcessed(true);
00459             if (m_log)
00460                 m_log->push(ChangeLog<VC>::PROCESSED, *cur);
00461         }
00462     }
00463 }
00464 
00465 void VCBuilder::DoSearch()
00466 {
00467     bool winning_connection = false;
00468     while (!m_queue.empty()) 
00469     {
00470         HexPointPair pair = m_queue.front();
00471         m_queue.pop();
00472 
00473         ProcessSemis(pair.first, pair.second);
00474         ProcessFulls(pair.first, pair.second);
00475         
00476         if (m_param.abort_on_winning_connection && 
00477             m_con->Exists(HexPointUtil::colorEdge1(m_color),
00478                           HexPointUtil::colorEdge2(m_color),
00479                           VC::FULL))
00480         {
00481             winning_connection = true;
00482             break;
00483         }
00484     }        
00485     HexAssert(winning_connection || m_queue.empty());
00486 
00487     if (winning_connection) 
00488         LogFine() << "Aborted on winning connection." << '\n';
00489             
00490     // Process the side-to-side semi list to ensure we have a full if
00491     // mustplay is empty.
00492     // TODO: IS THIS STILL NEEDED?
00493     ProcessSemis(m_groups->CaptainOf(HexPointUtil::colorEdge1(m_color)),
00494                  m_groups->CaptainOf(HexPointUtil::colorEdge2(m_color)));
00495 }
00496 
00497 //----------------------------------------------------------------------------
00498 
00499 /** Computes the and closure for the vc. Let x and y be vc's
00500     endpoints. A single pass over the board is performed. For each z,
00501     we try to and the list of fulls between z and x and z and y with
00502     vc. This function is a major bottleneck. Every operation in it
00503     needs to be as efficient as possible.
00504 */
00505 void VCBuilder::andClosure(const VC& vc)
00506 {
00507     HexColor other = !m_color;
00508     HexColorSet not_other = HexColorSetUtil::NotColor(other);
00509 
00510     HexPoint endp[2];
00511     endp[0] = m_groups->CaptainOf(vc.x());
00512     endp[1] = m_groups->CaptainOf(vc.y());
00513     HexColor endc[2];
00514     endc[0] = m_brd->GetColor(endp[0]);
00515     endc[1] = m_brd->GetColor(endp[1]);
00516 
00517     if (endc[0] == other || endc[1] == other) {
00518         LogInfo() << *m_brd << '\n';
00519         LogInfo() << vc << '\n';
00520     }
00521 
00522     bitset_t vcCapturedSet = m_capturedSet[endp[0]] | m_capturedSet[endp[1]];
00523    
00524     HexAssert(endc[0] != other);
00525     HexAssert(endc[1] != other);
00526     for (GroupIterator g(*m_groups, not_other); g; ++g) 
00527     {
00528         HexPoint z = g->Captain();
00529         if (z == endp[0] || z == endp[1]) continue;
00530         if (vc.carrier().test(z)) continue;
00531         bitset_t capturedSet = vcCapturedSet | m_capturedSet[z];
00532         bitset_t uncapturedSet = capturedSet;
00533         uncapturedSet.flip();
00534         for (int i=0; i<2; i++)
00535         {
00536             int j = (i + 1) & 1;
00537             if (m_param.and_over_edge || !HexPointUtil::isEdge(endp[i])) 
00538             {
00539                 VCList* fulls = &m_con->GetList(VC::FULL, z, endp[i]);
00540                 if ((fulls->softIntersection() & vc.carrier()
00541                      & uncapturedSet).any())
00542                     continue;
00543                 
00544                 AndRule rule = (endc[i] == EMPTY) ? CREATE_SEMI : CREATE_FULL;
00545                 doAnd(z, endp[i], endp[j], rule, vc, capturedSet, 
00546                       &m_con->GetList(VC::FULL, z, endp[i]));
00547             }
00548         }
00549     }
00550 }
00551 
00552 /** Compares vc to each connection in the softlimit of the given list.
00553     Creates a new connection if intersection is empty, or if the
00554     intersection is a subset of the captured set. Created connections
00555     are added with AddNewFull() or AddNewSemi().
00556 */
00557 void VCBuilder::doAnd(HexPoint from, HexPoint over, HexPoint to,
00558                       AndRule rule, const VC& vc, const bitset_t& capturedSet, 
00559                       const VCList* old)
00560 {
00561     if (old->empty())
00562         return;
00563 
00564     int soft = old->softlimit();
00565     VCList::const_iterator i = old->begin();
00566     VCList::const_iterator end = old->end();
00567     for (int count=0; count<soft && i!=end; ++i, ++count) 
00568     {
00569         if (!i->processed())
00570             continue;
00571         if (i->carrier().test(to))
00572             continue;
00573         bitset_t intersection = i->carrier() & vc.carrier();
00574         if (intersection.none())
00575         {
00576             if (rule == CREATE_FULL)
00577             {
00578                 m_statistics->and_full_attempts++;
00579                 if (AddNewFull(VC::AndVCs(from, to, *i, vc)))
00580                     m_statistics->and_full_successes++;
00581             }
00582             else if (rule == CREATE_SEMI)
00583             {
00584                 m_statistics->and_semi_attempts++;
00585                 if (AddNewSemi(VC::AndVCs(from, to, *i, vc, over)))
00586                     m_statistics->and_semi_successes++;
00587             }
00588         }
00589         else if (BitsetUtil::IsSubsetOf(intersection, capturedSet))
00590         {
00591             if (rule == CREATE_FULL)
00592             {
00593                 m_statistics->and_full_attempts++;
00594                 if (AddNewFull(VC::AndVCs(from, to, *i, vc, capturedSet)))
00595                     m_statistics->and_full_successes++;
00596             }
00597             else if (rule == CREATE_SEMI)
00598             {
00599                 m_statistics->and_semi_attempts++;
00600                 if (AddNewSemi(VC::AndVCs(from, to, *i, vc, capturedSet, over)))
00601                     m_statistics->and_semi_successes++;
00602             }
00603         }
00604     }
00605 }
00606 
00607 /** Runs over all subsets of size 2 to max_ors of semis containing vc
00608     and adds the union to out if it has an empty intersection. This
00609     function is a major bottleneck and so needs to be as efficient as
00610     possible.
00611 
00612     TODO: Document this more!
00613 
00614     TODO: Check if unrolling the recursion really does speed it up.
00615 
00616     @return number of connections successfully added.
00617 */
00618 int VCBuilder::OrRule::operator()(const VC& vc, 
00619                                   const VCList* semi_list, 
00620                                   VCList* full_list, 
00621                                   std::list<VC>& added, 
00622                                   int max_ors,
00623                                   ChangeLog<VC>* log, 
00624                                   VCBuilderStatistics& stats)
00625 {
00626     if (semi_list->empty())
00627         return 0;
00628     
00629     // copy processed semis (unprocessed semis are not used here)
00630     m_semi.clear();
00631     int soft = semi_list->softlimit();
00632     VCList::const_iterator it = semi_list->begin();
00633     VCList::const_iterator end = semi_list->end();
00634     for (int count=0; count<soft && it!=end; ++count, ++it)
00635         if (it->processed())
00636             m_semi.push_back(*it);
00637 
00638     if (m_semi.empty())
00639         return 0;
00640 
00641     std::size_t N = m_semi.size();
00642 
00643     // for each i in [0, N-1], compute intersection of semi[i, N-1]
00644     if (m_tail.size() < N)
00645         m_tail.resize(N);
00646     m_tail[N-1] = m_semi[N-1].carrier();
00647     for (int i = static_cast<int>(N - 2); i >= 0; --i)
00648         m_tail[i] = m_semi[i].carrier() & m_tail[i+1];
00649 
00650     max_ors--;
00651     HexAssert(max_ors < 16);
00652 
00653     // compute the captured-set union for the endpoints of this list
00654     bitset_t capturedSet = m_builder.m_capturedSet[semi_list->getX()] 
00655                          | m_builder.m_capturedSet[semi_list->getY()];
00656     bitset_t uncapturedSet = capturedSet;
00657     uncapturedSet.flip();
00658 
00659     std::size_t index[16];
00660     bitset_t ors[16];
00661     bitset_t ands[16];
00662 
00663     ors[0] = vc.carrier();
00664     ands[0] = vc.carrier();
00665     index[1] = 0;
00666     
00667     int d = 1;
00668     int count = 0;
00669     while (true) 
00670     {
00671         std::size_t i = index[d];
00672 
00673         // the current intersection (some subset from [0, i-1]) is not
00674         // disjoint with the intersection of [i, N), so stop. Note that
00675         // the captured set is not considered in the intersection.
00676         if ((i < N) && (ands[d-1] & m_tail[i] & uncapturedSet).any())
00677             i = N;
00678 
00679         if (i == N) 
00680         {
00681             if (d == 1) 
00682                 break;
00683             
00684             ++index[--d];
00685             continue;
00686         }
00687         
00688         ands[d] = ands[d-1] & m_semi[i].carrier();
00689         ors[d]  =  ors[d-1] | m_semi[i].carrier();
00690 
00691         if (ands[d].none()) 
00692         {
00693             /** Create a new full.
00694                 
00695                 @note We do no use AddNewFull() because if add is
00696                 successful, it checks for semi-supersets and adds the
00697                 list to the queue. Both of these operations are not
00698                 needed here.
00699             */
00700             VC v(full_list->getX(), full_list->getY(), ors[d], VC_RULE_OR);
00701 
00702             stats.or_attempts++;
00703             if (full_list->add(v, log) != VCList::ADD_FAILED) 
00704             {
00705                 count++;
00706                 stats.or_successes++;
00707                 added.push_back(v);
00708             }
00709         
00710             ++index[d];
00711         } 
00712         else if (BitsetUtil::IsSubsetOf(ands[d], capturedSet))
00713         {
00714             /** Create a new full.
00715                 This vc has one or both captured sets in its carrier.
00716             */
00717             bitset_t carrier = ors[d];
00718             if ((ands[d] & m_builder.m_capturedSet[semi_list->getX()]).any())
00719                 carrier |= m_builder.m_capturedSet[semi_list->getX()];
00720             if ((ands[d] & m_builder.m_capturedSet[semi_list->getY()]).any())
00721                 carrier |= m_builder.m_capturedSet[semi_list->getY()];
00722 
00723             VC v(full_list->getX(), full_list->getY(), carrier, VC_RULE_OR);
00724 
00725             stats.or_attempts++;
00726             if (full_list->add(v, log) != VCList::ADD_FAILED) 
00727             {
00728                 count++;
00729                 stats.or_successes++;
00730                 added.push_back(v);
00731             }
00732         
00733             ++index[d];
00734         }
00735         else if (ands[d] == ands[d-1]) 
00736         {
00737             // this connection does not shrink intersection so skip it
00738             ++index[d];
00739         }
00740         else 
00741         {
00742             // this connection reduces intersection, if not at max depth
00743             // see if more semis can reduce it to the empty set (or at least
00744             // a subset of the captured set).
00745             if (d < max_ors) 
00746                 index[++d] = ++i;
00747             else
00748                 ++index[d];
00749         }
00750     }
00751     return count;
00752 }
00753 
00754 /** Tries to add a new full-connection to list between (vc.x(), vc.y()).
00755 
00756     If vc is successfully added, then:
00757 
00758     1) Removes any semi-connections between (vc.x(), vc.y()) that are
00759     supersets of vc.
00760     
00761     2) Adds (vc.x(), vc.y()) to the queue if vc was added inside the
00762     softlimit.
00763 */
00764 bool VCBuilder::AddNewFull(const VC& vc)
00765 {
00766     HexAssert(vc.type() == VC::FULL);
00767     VCList::AddResult result = m_con->Add(vc, m_log);
00768     if (result != VCList::ADD_FAILED) 
00769     {
00770         // a semi that is a superset of a full is useless, so remove
00771         // any that exist.
00772         m_con->GetList(VC::SEMI, vc.x(), vc.y())
00773             .removeSuperSetsOf(vc.carrier(), m_log);
00774                 
00775         // add this list to the queue if inside the soft-limit
00776         if (result == VCList::ADDED_INSIDE_SOFT_LIMIT)
00777             m_queue.push(std::make_pair(vc.x(), vc.y()));
00778 
00779         return true;
00780     }
00781     return false;
00782 }
00783 
00784 /** Tries to add a new semi-connection to list between (vc.x(), vc.y()). 
00785         
00786     Does not add if vc is a superset of some full-connection between
00787     (vc.x(), and vc.y()).
00788     
00789     If vc is successfully added and intersection on semi-list is
00790     empty, then:
00791 
00792     1) if vc added inside soft limit, adds (vc.x(), vc.y()) to queue.
00793     
00794     2) otherwise, if no full exists between (vc.x(), vc.y()), adds the
00795     or over the entire semi list.
00796 */
00797 bool VCBuilder::AddNewSemi(const VC& vc)
00798 {
00799     VCList* out_full = &m_con->GetList(VC::FULL, vc.x(), vc.y());
00800     VCList* out_semi = &m_con->GetList(VC::SEMI, vc.x(), vc.y());
00801     
00802     if (!out_full->isSupersetOfAny(vc.carrier())) 
00803     {
00804         VCList::AddResult result = out_semi->add(vc, m_log);
00805         if (result != VCList::ADD_FAILED) 
00806         {
00807             if (out_semi->hardIntersection().none())
00808             {
00809                 if (result == VCList::ADDED_INSIDE_SOFT_LIMIT) 
00810                 {
00811                     m_queue.push(std::make_pair(vc.x(), vc.y()));
00812                 } 
00813                 else if (out_full->empty())
00814                 {
00815                     bitset_t carrier = m_param.use_greedy_union 
00816                         ? out_semi->getGreedyUnion() 
00817                         : out_semi->getUnion();
00818                     
00819                     VC v(out_full->getX(), out_full->getY(), 
00820                          carrier, VC_RULE_ALL);
00821 
00822                     out_full->add(v, m_log);
00823                 }
00824             }
00825             return true;
00826         }
00827     }
00828     return false;
00829 }
00830 
00831 //----------------------------------------------------------------------------
00832 
00833 std::string VCBuilderStatistics::ToString() const
00834 {
00835     std::ostringstream os;
00836     os << "["
00837        << "base=" << base_successes << "/" << base_attempts << '\n'
00838        << "pat=" << pattern_successes << "/" << pattern_attempts << '\n'
00839        << "and-f=" << and_full_successes << "/" << and_full_attempts << '\n'
00840        << "and-s=" << and_semi_successes << "/" << and_semi_attempts << '\n'
00841        << "or=" << or_successes << "/" << or_attempts << '\n'
00842        << "doOr()=" << goodOrs << "/" << doOrs << '\n'
00843        << "s0/s1/u1=" << shrunk0 << "/" << shrunk1 << "/"<< upgraded << '\n'
00844        << "killed0/1=" << killed0 << "/" << killed1 << '\n'
00845        << "]";
00846     return os.str();
00847 }
00848 
00849 //----------------------------------------------------------------------------
00850 
00851 /** @page workqueue VCBuilder Work Queue
00852 
00853     WorkQueue stores the endpoints of any VCLists that need further
00854     processing. Endpoints are pushed onto the back of the queue and
00855     popped off the front, in FIFO order. It also ensures only unique
00856     elements are added; that is, a list is added only once until it is
00857     processed.
00858 
00859     The implementation here is a simple vector with an index
00860     simulating the front of the queue; that is, push() uses
00861     push_back() to add elements to the back and pop() increments the
00862     index of the front. This means the vector will need to be as large
00863     as the number of calls to push(), not the maximum number of
00864     elements in the queue at any given time.
00865     
00866     On 11x11, the vector quickly grows to hold 2^14 elements if anding
00867     over the edge, and 2^13 if not. Since only unique elements are
00868     added, in the worst case this value will be the smallest n such
00869     that 2^n > xy, where x and y are the width and height of the
00870     board.
00871 
00872     This implementation was chosen for efficiency: a std::deque uses
00873     dynamic memory, and so every push()/pop() requires at least one
00874     call to malloc/free. The effect is small, but can be as
00875     significant as 1-3% of the total run-time, especially on smaller
00876     boards.
00877 */
00878 VCBuilder::WorkQueue::WorkQueue()
00879     : m_head(0), 
00880       m_array(128)
00881 {
00882 }
00883 
00884 bool VCBuilder::WorkQueue::empty() const
00885 {
00886     return m_head == m_array.size();
00887 }
00888 
00889 const HexPointPair& VCBuilder::WorkQueue::front() const
00890 {
00891     return m_array[m_head];
00892 }
00893 
00894 std::size_t VCBuilder::WorkQueue::capacity() const
00895 {
00896     return m_array.capacity();
00897 }
00898 
00899 void VCBuilder::WorkQueue::clear()
00900 {
00901     memset(m_seen, 0, sizeof(m_seen));
00902     m_array.clear();
00903     m_head = 0;
00904 }
00905 
00906 void VCBuilder::WorkQueue::pop()
00907 {
00908     m_seen[front().first][front().second] = false;
00909     m_head++;
00910 }
00911 
00912 void VCBuilder::WorkQueue::push(const HexPointPair& p)
00913 {
00914     HexPoint a = std::min(p.first, p.second);
00915     HexPoint b = std::max(p.first, p.second);
00916     if (!m_seen[a][b]) 
00917     {
00918         m_seen[a][a] = true;
00919         m_array.push_back(std::make_pair(a, b));
00920     }
00921 }
00922 
00923 //----------------------------------------------------------------------------


6 Jan 2011 Doxygen 1.6.3