Main   Namespaces   Classes   Hierarchy   Annotated   Files   Compound   Global   Pages  

DfpnSolver.cpp

Go to the documentation of this file.
00001 //----------------------------------------------------------------------------
00002 /** @file DfpnSolver.cpp
00003  */
00004 //----------------------------------------------------------------------------
00005 
00006 #include "BitsetIterator.hpp"
00007 #include "BoardUtils.hpp"
00008 #include "DfpnSolver.hpp"
00009 #include "PatternState.hpp"
00010 #include "EndgameUtils.hpp"
00011 #include "ProofUtil.hpp"
00012 #include "Resistance.hpp"
00013 
00014 #include <boost/filesystem/path.hpp>
00015 
00016 using namespace benzene;
00017 
00018 using std::ceil;
00019 
00020 //----------------------------------------------------------------------------
00021 
00022 /** Current version of the dfpn database.
00023     Update this if DfpnData changes to prevent old out-of-date
00024     databases from being loaded. */
00025 const std::string DfpnDB::DFPN_DB_VERSION("BENZENE_DFPN_DB_VER_0002");
00026 
00027 //----------------------------------------------------------------------------
00028 
00029 #ifndef NDEBUG
00030 void DfpnBounds::CheckConsistency() const
00031 {
00032     // Check range
00033     HexAssert(phi <= INFTY);
00034     HexAssert(delta <= INFTY);
00035     // one is 0 iff the other is infinity
00036     HexAssert(0 != phi || INFTY == delta);
00037     HexAssert(INFTY != phi || 0 == delta);
00038     HexAssert(0 != delta || INFTY == phi);
00039     HexAssert(INFTY != delta || 0 == phi);
00040 }
00041 #else
00042 void DfpnBounds::CheckConsistency() const
00043 {
00044 }
00045 #endif
00046 
00047 //----------------------------------------------------------------------------
00048 
00049 DfpnChildren::DfpnChildren()
00050 {
00051 }
00052 
00053 void DfpnChildren::SetChildren(const std::vector<HexPoint>& children)
00054 {
00055     m_children = children;
00056 }
00057 
00058 void DfpnChildren::PlayMove(int index, HexState& state) const
00059 {
00060     state.PlayMove(m_children[index]);
00061 }
00062 
00063 void DfpnChildren::UndoMove(int index, HexState& state) const
00064 {
00065     state.UndoMove(m_children[index]);
00066 }
00067 
00068 //----------------------------------------------------------------------------
00069 
00070 /** @page dfpnguifx Dfpn Progress Indication
00071     @ingroup dfpn
00072 
00073     It is difficult to present the user with meaningful progress
00074     indication in dfpn. The current method simply displays the current
00075     (phi, delta) bounds of each child of the root. This is output
00076     whenever a child's bound changes. This is reasonably useful,
00077     except in the case where only a single child remains and the
00078     search is stuck several ply deep.
00079 */
00080 
00081 DfpnSolver::GuiFx::GuiFx()
00082     : m_index(-1),
00083       m_timeOfLastWrite(0.0),
00084       m_delay(1.0)
00085 {
00086 }
00087 
00088 void DfpnSolver::GuiFx::SetChildren(const DfpnChildren& children,
00089                                     const std::vector<DfpnData>& data)
00090 {
00091     m_children = children;
00092     m_data = data;
00093 }
00094 
00095 void DfpnSolver::GuiFx::PlayMove(HexColor color, int index)
00096 {
00097     m_color = color;
00098     m_index = index;
00099 }
00100 
00101 void DfpnSolver::GuiFx::UndoMove()
00102 {
00103     m_index = -1;
00104 }
00105 
00106 void DfpnSolver::GuiFx::UpdateCurrentBounds(const DfpnBounds& bounds)
00107 {
00108     HexAssert(m_index != -1);
00109     m_data[m_index].m_bounds = bounds;
00110 }
00111 
00112 /** Always writes output. */
00113 void DfpnSolver::GuiFx::WriteForced()
00114 {
00115     DoWrite();
00116 }
00117 
00118 /** Writes output only if last write was more than m_delay seconds
00119     ago or if the move is different. */
00120 void DfpnSolver::GuiFx::Write()
00121 {
00122     double currentTime = SgTime::Get();
00123     if (m_indexAtLastWrite == m_index)
00124     {
00125         if (currentTime < m_timeOfLastWrite + m_delay)
00126             return;
00127     }
00128     m_timeOfLastWrite = currentTime;
00129     m_indexAtLastWrite = m_index;
00130     DoWrite();
00131 }
00132 
00133 /** Writes progress indication. */
00134 void DfpnSolver::GuiFx::DoWrite()
00135 {
00136     std::ostringstream os;
00137     os << "gogui-gfx:\n";
00138     os << "dfpn\n";
00139     os << "VAR";
00140     if (m_index != -1)
00141     {
00142         os << ' ' << (m_color == BLACK ? 'B' : 'W')
00143            << ' ' << m_children.FirstMove(m_index);
00144     }
00145     os << '\n';
00146     os << "LABEL";
00147     int numLosses = 0;
00148     for (std::size_t i = 0; i < m_children.Size(); ++i)
00149     {
00150         os << ' ' << m_children.FirstMove(i);
00151         if (0 == m_data[i].m_bounds.phi)
00152         {
00153             numLosses++;
00154             os << " L";
00155         }
00156         else if (0 == m_data[i].m_bounds.delta)
00157             os << " W";
00158         else
00159             os << ' ' << m_data[i].m_bounds.phi 
00160                << ':' << m_data[i].m_bounds.delta;
00161     }
00162     os << '\n';
00163     os << "TEXT ";
00164     os << numLosses << '/' << m_children.Size() << " proven losses\n";
00165     os << '\n';
00166     std::cout << os.str();
00167     std::cout.flush();
00168 }
00169 
00170 //----------------------------------------------------------------------------
00171 
00172 int DfpnData::PackedSize() const
00173 {
00174     return sizeof(m_bounds)
00175         + sizeof(m_bestMove)
00176         + sizeof(m_work)
00177         + sizeof(m_maxProofSet)
00178         + sizeof(m_evaluationScore)
00179         + sizeof(short) * (m_children.Size() + 1);
00180 }
00181 
00182 byte* DfpnData::Pack() const
00183 {
00184     static byte data[4096];
00185     byte* off = data;
00186     *reinterpret_cast<DfpnBounds*>(off) = m_bounds;
00187     off += sizeof(m_bounds);
00188     *reinterpret_cast<HexPoint*>(off) = m_bestMove;
00189     off += sizeof(m_bestMove);
00190     *reinterpret_cast<size_t*>(off) = m_work;
00191     off += sizeof(m_work);
00192     *reinterpret_cast<bitset_t*>(off) = m_maxProofSet;
00193     off += sizeof(m_maxProofSet);
00194     *reinterpret_cast<float*>(off) = m_evaluationScore;
00195     off += sizeof(m_evaluationScore);
00196     const std::vector<HexPoint>& moves = m_children.m_children;
00197     for (std::size_t i = 0; i < moves.size(); ++i)
00198     {
00199         *reinterpret_cast<short*>(off) = static_cast<short>(moves[i]);
00200         off += sizeof(short);
00201     }
00202     *reinterpret_cast<short*>(off) = static_cast<short>(INVALID_POINT);
00203     off += sizeof(short);
00204     if (off - data != PackedSize())
00205         throw BenzeneException("Bad size!");
00206     return data;
00207 }
00208 
00209 void DfpnData::Unpack(const byte* data)
00210 {
00211     m_bounds = *reinterpret_cast<const DfpnBounds*>(data);
00212     data += sizeof(m_bounds);
00213     m_bestMove = *reinterpret_cast<const HexPoint*>(data);
00214     data += sizeof(m_bestMove);
00215     m_work = *reinterpret_cast<const size_t*>(data);
00216     data += sizeof(m_work);
00217     m_maxProofSet = *reinterpret_cast<const bitset_t*>(data);
00218     data += sizeof(m_maxProofSet);
00219     m_evaluationScore = *reinterpret_cast<const float*>(data);
00220     data += sizeof(m_evaluationScore);
00221     std::vector<HexPoint> moves;
00222     while (true)
00223     {
00224         short s = *reinterpret_cast<const short*>(data);
00225         data += sizeof(short);
00226         HexPoint p = static_cast<HexPoint>(s);
00227         if (p == INVALID_POINT)
00228             break;
00229         moves.push_back(p);
00230     }
00231     m_children.SetChildren(moves);
00232 }
00233 
00234 void DfpnData::Rotate(const ConstBoard& brd)
00235 {
00236     if (m_bestMove != INVALID_POINT)
00237         m_bestMove = BoardUtils::Rotate(brd, m_bestMove);
00238     m_maxProofSet = BoardUtils::Rotate(brd, m_maxProofSet);
00239     std::vector<HexPoint>& moves = m_children.m_children;
00240     for (std::size_t i = 0; i < moves.size(); ++i)
00241         moves[i] = BoardUtils::Rotate(brd, moves[i]);
00242 }
00243 
00244 //----------------------------------------------------------------------------
00245 
00246 DfpnSolver::DfpnSolver()
00247     : m_positions(0),
00248       m_useGuiFx(false),
00249       m_timelimit(0.0),
00250       m_wideningBase(1),
00251       m_wideningFactor(0.25f),
00252       m_guiFx(),
00253       m_allEvaluation(-2.5, 2.0, 45),
00254       m_allSolvedEvaluation(-2.5, 2.0, 45),
00255       m_winningEvaluation(-2.5, 2.0, 45),
00256       m_losingEvaluation(-2.5, 2.0, 45)
00257 {
00258 }
00259 
00260 DfpnSolver::~DfpnSolver()
00261 {
00262 }
00263 
00264 void DfpnSolver::PrintStatistics(HexColor winner,
00265                                  const PointSequence& pv) const
00266 {
00267     std::ostringstream os;
00268     os << '\n'
00269        << "MID calls       " << m_numMIDcalls << '\n'
00270        << "VC builds       " << m_numVCbuilds << '\n'
00271        << "Terminal nodes  " << m_numTerminal << '\n'
00272        << "Work            " << m_numMIDcalls + m_numTerminal << '\n'
00273        << "Wasted Work     " << m_totalWastedWork
00274        << " (" << (m_totalWastedWork * 100.0 
00275                    / (m_numMIDcalls + m_numTerminal)) << "%)\n"
00276        << "Elapsed Time    " << m_timer.GetTime() << '\n'
00277        << "MIDs/sec        " << m_numMIDcalls / m_timer.GetTime() << '\n'
00278        << "VCs/sec         " << m_numVCbuilds / m_timer.GetTime() << '\n'
00279        << "Cnt prune sib   " << m_prunedSiblingStats.Count() << '\n'
00280        << "Avg prune sib   ";
00281     m_prunedSiblingStats.Write(os);
00282     os << '\n'
00283        << "Consider Size   ";
00284     m_considerSetSize.Write(os);
00285     os << '\n'
00286        << "Move Index      ";
00287     m_moveOrderingIndex.Write(os);
00288     os << '\n';
00289     os << "Move Percent    ";
00290     m_moveOrderingPercent.Write(os);
00291     os << '\n';
00292     os << "Delta Increase  ";
00293     m_deltaIncrease.Write(os);
00294     os << '\n'
00295        << "Winner          " << winner << '\n'
00296        << "PV              " << HexPointUtil::ToString(pv) << '\n';
00297     if (m_positions->Database())
00298         os << '\n' << m_positions->Database()->GetStatistics().Write() << '\n';
00299     if (m_positions->HashTable())    
00300         os << '\n' << m_positions->HashTable()->Stats() << '\n';
00301     LogInfo() << os.str();
00302 }
00303 
00304 std::string DfpnSolver::EvaluationInfo() const
00305 {
00306     std::ostringstream os;
00307     os << "All:\n";
00308     m_allEvaluation.Write(os);
00309     os << "All Solved:\n";
00310     m_allSolvedEvaluation.Write(os);
00311     os << "Winning:\n";
00312     m_winningEvaluation.Write(os);
00313     os << "Losing:\n";
00314     m_losingEvaluation.Write(os);
00315     return os.str();
00316 }
00317 
00318 HexColor DfpnSolver::StartSearch(const HexState& state, HexBoard& board,
00319                                  DfpnStates& positions, PointSequence& pv)
00320 {
00321     return StartSearch(state, board, positions, pv, 
00322                        DfpnBounds(DfpnBounds::MAX_WORK, DfpnBounds::MAX_WORK));
00323 }
00324 
00325 HexColor DfpnSolver::StartSearch(const HexState& state, HexBoard& board,
00326                                  DfpnStates& positions, PointSequence& pv,
00327                                  const DfpnBounds& maxBounds)
00328 {
00329     m_aborted = false;
00330     m_positions = &positions;
00331     m_numTerminal = 0;
00332     m_numMIDcalls = 0;
00333     m_numVCbuilds = 0;
00334     m_totalWastedWork = 0;
00335     m_prunedSiblingStats.Clear();
00336     m_moveOrderingPercent.Clear();
00337     m_moveOrderingIndex.Clear();
00338     m_considerSetSize.Clear();
00339     m_deltaIncrease.Clear();
00340     m_losingEvaluation.Clear();
00341     m_winningEvaluation.Clear();
00342     m_allEvaluation.Clear();
00343     m_allSolvedEvaluation.Clear();
00344 
00345     m_state.reset(new HexState(state));
00346     m_workBoard = &board;
00347     m_checkTimerAbortCalls = 0;
00348 
00349     // Skip search if already solved
00350     DfpnData data;
00351     if (TTRead(*m_state, data) && data.m_bounds.IsSolved())
00352     {
00353         LogInfo() << "Already solved!\n";
00354         HexColor w = data.m_bounds.IsWinning() 
00355             ? m_state->ToPlay() : !m_state->ToPlay();
00356         SolverDBUtil::GetVariation(*m_state, *m_positions, pv);
00357         LogInfo() << w << " wins!\n";
00358         LogInfo() << "PV: " << HexPointUtil::ToString(pv) << '\n';
00359         return w;
00360     }
00361 
00362     m_timer.Start();
00363     DfpnHistory history;
00364     MID(maxBounds, history);
00365     m_timer.Stop();
00366 
00367     SolverDBUtil::GetVariation(*m_state, *m_positions, pv);
00368     HexColor winner = EMPTY;
00369     if (TTRead(*m_state, data) && data.m_bounds.IsSolved())
00370         winner = data.m_bounds.IsWinning() 
00371             ? m_state->ToPlay() : !m_state->ToPlay();
00372     PrintStatistics(winner, pv);
00373 
00374     if (m_aborted)
00375         LogInfo() << "Search aborted.\n";
00376     return winner;
00377 }
00378 
00379 bool DfpnSolver::CheckAbort()
00380 {
00381     if (!m_aborted)
00382     {
00383         if (SgUserAbort()) 
00384         {
00385             m_aborted = true;
00386             LogInfo() << "DfpnSolver::CheckAbort(): Abort flag!\n";
00387         }
00388         else if (m_timelimit > 0)
00389         {
00390             if (m_checkTimerAbortCalls == 0)
00391             {
00392                 double elapsed = m_timer.GetTime();
00393                 if (elapsed > m_timelimit)
00394                 {
00395                     m_aborted = true;
00396                     LogInfo() << "DfpnSolver::CheckAbort(): Timelimit!\n";
00397                 }
00398                 else
00399                 {
00400                     if (m_numMIDcalls < 100)
00401                         m_checkTimerAbortCalls = 10;
00402                     else
00403                     {
00404                         size_t midsPerSec = static_cast<size_t>
00405                             (m_numMIDcalls / elapsed);
00406                         m_checkTimerAbortCalls = midsPerSec / 2;
00407                     }
00408                 }
00409             }
00410             else
00411                 --m_checkTimerAbortCalls;
00412         }
00413     }
00414     return m_aborted;
00415 }
00416 
00417 
00418 size_t DfpnSolver::MID(const DfpnBounds& maxBounds, DfpnHistory& history)
00419 {
00420     maxBounds.CheckConsistency();
00421     HexAssert(maxBounds.phi > 1);
00422     HexAssert(maxBounds.delta > 1);
00423 
00424     int depth = history.Depth();
00425     size_t prevWork = 0;
00426     bitset_t maxProofSet;
00427     float evaluationScore;
00428     HexColor colorToMove = m_state->ToPlay();
00429     DfpnChildren children;
00430     {
00431         DfpnData data;
00432         if (TTRead(*m_state, data)) 
00433         {
00434             children = data.m_children;
00435             maxProofSet = data.m_maxProofSet;
00436             prevWork = data.m_work;
00437             evaluationScore = data.m_evaluationScore;
00438             if (!maxBounds.GreaterThan(data.m_bounds))
00439                 // Estimated bounds are larger than we had
00440                 // anticipated. The calling state must have computed
00441                 // the max bounds with out of date information, so just
00442                 // return here without doing anything: the caller will
00443                 // now update to this new info and carry on.
00444                 return 0;
00445         }
00446         else
00447         {
00448             m_workBoard->GetPosition().SetPosition(m_state->Position());
00449             m_workBoard->ComputeAll(colorToMove);
00450             ++m_numVCbuilds;
00451 
00452             // Compute the maximum possible proof set if colorToMove wins.
00453             // This data is used to prune siblings of this state.
00454             maxProofSet = ProofUtil::MaximumProofSet(*m_workBoard, colorToMove);
00455 
00456             if (EndgameUtils::IsDeterminedState(*m_workBoard, colorToMove))
00457             {
00458                 ++m_numTerminal;
00459                 DfpnBounds terminal;
00460                 if (EndgameUtils::IsWonGame(*m_workBoard, colorToMove))
00461                     DfpnBounds::SetToWinning(terminal);
00462                 else 
00463                     DfpnBounds::SetToLosing(terminal);
00464                 
00465                 if (m_useGuiFx && depth == 1)
00466                 {
00467                     m_guiFx.UpdateCurrentBounds(terminal);
00468                     m_guiFx.Write();
00469                 }
00470                 TTWrite(*m_state, DfpnData(terminal, DfpnChildren(), 
00471                                   INVALID_POINT, 1, maxProofSet, 0.0));
00472                 return 1;
00473             }
00474             bitset_t childrenBitset 
00475                 = EndgameUtils::MovesToConsider(*m_workBoard, colorToMove);
00476 
00477             m_considerSetSize.Add(childrenBitset.count());
00478             Resistance resist;
00479             resist.Evaluate(*m_workBoard);
00480             evaluationScore = (colorToMove == BLACK) 
00481                 ? resist.Score() : -resist.Score();
00482             m_allEvaluation.Add(evaluationScore);
00483             std::vector<std::pair<HexEval, HexPoint> > mvsc;
00484             for (BitsetIterator it(childrenBitset); it; ++it) 
00485             {
00486                 HexEval score = resist.Score(*it);
00487                 mvsc.push_back(std::make_pair(-score, *it));
00488             }
00489             stable_sort(mvsc.begin(), mvsc.end());
00490             std::vector<HexPoint> sortedChildren;
00491             for (size_t i = 0; i < mvsc.size(); ++i)
00492                 sortedChildren.push_back(mvsc[i].second);
00493             children.SetChildren(sortedChildren);
00494         }
00495     }
00496 
00497     ++m_numMIDcalls;
00498     size_t localWork = 1;
00499 
00500     // Not thread safe: perhaps move into while loop below later...
00501     std::vector<DfpnData> childrenData(children.Size());
00502     for (size_t i = 0; i < children.Size(); ++i)
00503         LookupData(childrenData[i], children, i, *m_state);
00504     // Index used for progressive widening
00505     size_t maxChildIndex = ComputeMaxChildIndex(childrenData);
00506 
00507     if (m_useGuiFx && depth == 0)
00508         m_guiFx.SetChildren(children, childrenData);
00509 
00510     hash_t currentHash = m_state->Hash();
00511     HexPoint bestMove = INVALID_POINT;
00512     DfpnBounds currentBounds;
00513     do
00514     {
00515         UpdateBounds(currentBounds, childrenData, maxChildIndex);
00516 
00517         if (m_useGuiFx && depth == 1)
00518         {
00519             m_guiFx.UpdateCurrentBounds(currentBounds);
00520             m_guiFx.Write();
00521         }
00522 
00523         if (!maxBounds.GreaterThan(currentBounds))
00524             break;
00525 
00526         // Select most proving child
00527         int bestIndex = -1;
00528         DfpnBoundType delta2 = DfpnBounds::INFTY;
00529         SelectChild(bestIndex, delta2, childrenData, maxChildIndex);
00530         bestMove = children.FirstMove(bestIndex);
00531 
00532         // Compute maximum bound for child
00533         const DfpnBounds childBounds(childrenData[bestIndex].m_bounds);
00534         DfpnBounds childMaxBounds;
00535         childMaxBounds.phi = maxBounds.delta 
00536             - (currentBounds.delta - childBounds.phi);
00537         childMaxBounds.delta = std::min(maxBounds.phi, delta2 + 1);
00538         HexAssert(childMaxBounds.GreaterThan(childBounds));
00539         if (delta2 != DfpnBounds::INFTY)
00540             m_deltaIncrease.Add(childMaxBounds.delta - childBounds.delta);
00541 
00542         // Recurse on best child
00543         if (m_useGuiFx && depth == 0)
00544             m_guiFx.PlayMove(colorToMove, bestIndex);
00545         children.PlayMove(bestIndex, *m_state);
00546         history.Push(bestMove, currentHash);
00547         localWork += MID(childMaxBounds, history);
00548         history.Pop();
00549         children.UndoMove(bestIndex, *m_state);
00550 
00551         if (m_useGuiFx && depth == 0)
00552             m_guiFx.UndoMove();
00553 
00554         // Update bounds for best child
00555         LookupData(childrenData[bestIndex], children, bestIndex, *m_state);
00556 
00557         // Compute some stats when find winning move
00558         if (childrenData[bestIndex].m_bounds.IsLosing())
00559         {
00560             m_moveOrderingIndex.Add(bestIndex);
00561             m_moveOrderingPercent.Add(bestIndex / (double)childrenData.size());
00562             m_totalWastedWork += prevWork + localWork
00563                 - childrenData[bestIndex].m_work;
00564         }
00565         else if (childrenData[bestIndex].m_bounds.IsWinning())
00566             maxChildIndex = ComputeMaxChildIndex(childrenData);
00567 
00568         // Shrink children list using knowledge of bestMove child's proof set.
00569         // That is, if this child is losing, conclude what other children
00570         // must also be losing (i.e. cannot interfere with the proof set
00571         // that disproves this child).
00572         // And of course if this child is winning, no need to explore
00573         // these other siblings either.
00574         {
00575             /* @todo Perhaps track allChildren instead of recomputing? */
00576             bitset_t allChildren;
00577             for (std::vector<HexPoint>::iterator it
00578                      = children.m_children.begin();
00579                  it != children.m_children.end(); ++it)
00580             {
00581                 allChildren.set(*it);
00582             }
00583             bitset_t canPrune = allChildren
00584                 - childrenData[bestIndex].m_maxProofSet;
00585             canPrune.reset(bestMove);
00586             int pruneCount = canPrune.count();
00587 
00588             if (pruneCount)
00589             {
00590                 m_prunedSiblingStats.Add(pruneCount);
00591                 /*
00592                 LogInfo() << "Pruning " << pruneCount
00593                           << " moves via " << bestMove
00594                           << ".\nChildren:\n" << m_brd->Write(allChildren)
00595                           << "\nRemoving...\n" << m_brd->Write(canPrune)
00596                           << "\n";
00597                 */
00598                 DeleteChildren(children, childrenData, canPrune);
00599                 maxChildIndex = ComputeMaxChildIndex(childrenData);
00600                 if (m_useGuiFx && depth == 0)
00601                     m_guiFx.SetChildren(children, childrenData);
00602             }
00603         }
00604     } while (!CheckAbort());
00605 
00606     if (m_useGuiFx && depth == 0)
00607         m_guiFx.WriteForced();
00608 
00609     // Find the most delaying move for losing states, and the smallest
00610     // winning move for winning states.
00611     if (currentBounds.IsSolved())
00612     {
00613         m_allSolvedEvaluation.Add(evaluationScore);
00614         if (currentBounds.IsLosing())
00615         {
00616             m_losingEvaluation.Add(evaluationScore);
00617             std::size_t maxWork = 0;
00618             for (std::size_t i = 0; i < children.Size(); ++i)
00619             {
00620                 if (childrenData[i].m_work > maxWork)
00621                 {
00622                     maxWork = childrenData[i].m_work;
00623                     bestMove = children.FirstMove(i);
00624                 }
00625             }
00626         }
00627         else
00628         {
00629             m_winningEvaluation.Add(evaluationScore);
00630             std::size_t minWork = DfpnBounds::INFTY;
00631             for (std::size_t i = 0; i < children.Size(); ++i)
00632             {
00633                 if (childrenData[i].m_bounds.IsLosing() 
00634                     && childrenData[i].m_work < minWork)
00635                 {
00636                     minWork = childrenData[i].m_work;
00637                     bestMove = children.FirstMove(i);
00638                 }
00639             }
00640         }
00641     }
00642     
00643     // Store search results and notify listeners
00644     DfpnData data(currentBounds, children, bestMove, localWork + prevWork, 
00645                   maxProofSet, evaluationScore);
00646     TTWrite(*m_state, data);
00647     if (data.m_bounds.IsSolved())
00648         NotifyListeners(history, data);
00649     return localWork;
00650 }
00651 
00652 size_t DfpnSolver::ComputeMaxChildIndex(const std::vector<DfpnData>&
00653                                         childrenData) const
00654 {
00655     HexAssert(!childrenData.empty());
00656 
00657     int numNonLosingChildren = 0;
00658     for (size_t i = 0; i < childrenData.size(); ++i)
00659         if (!childrenData[i].m_bounds.IsWinning())
00660             ++numNonLosingChildren;
00661     if (numNonLosingChildren < 2)
00662         return childrenData.size();
00663 
00664     // this needs experimenting!
00665     int childrenToLookAt = WideningBase() + (int) ceil(numNonLosingChildren
00666                                                        * WideningFactor());
00667     // Must examine at least two children when have two or more live,
00668     // since otherwise delta2 will be set to infinity in SelectChild.
00669     HexAssert(childrenToLookAt >= 2);
00670 
00671     int numNonLosingSeen = 0;
00672     for (size_t i = 0; i < childrenData.size(); ++i)
00673     {
00674         if (!childrenData[i].m_bounds.IsWinning())
00675             if (++numNonLosingSeen == childrenToLookAt)
00676                 return i + 1;
00677     }
00678     return childrenData.size();
00679 }
00680 
00681 void DfpnSolver::DeleteChildren(DfpnChildren& children,
00682                                 std::vector<DfpnData>& childrenData,
00683                                 bitset_t deleteChildren) const
00684 {
00685     HexAssert(children.Size() == childrenData.size());
00686     bitset_t deleted;
00687     std::vector<HexPoint>::iterator it1 = children.m_children.begin();
00688     std::vector<DfpnData>::iterator it2 = childrenData.begin();
00689     while (it1 != children.m_children.end())
00690     {
00691         HexAssert(it2 != childrenData.end());
00692         if (deleteChildren.test(*it1))
00693         {
00694             HexAssert(!deleted.test(*it1));
00695             deleted.set(*it1);
00696             it1 = children.m_children.erase(it1);
00697             it2 = childrenData.erase(it2);
00698         }
00699         else
00700         {
00701             ++it1;
00702             ++it2;
00703         }
00704     }
00705     HexAssert(children.Size() > 0);
00706     HexAssert(children.Size() == childrenData.size());
00707     HexAssert(deleteChildren == deleted);
00708 }
00709 
00710 void DfpnSolver::NotifyListeners(const DfpnHistory& history,
00711                                  const DfpnData& data)
00712 {
00713     for (std::size_t i = 0; i < m_listener.size(); ++i)
00714         m_listener[i]->StateSolved(history, data);
00715 }
00716 
00717 void DfpnSolver::SelectChild(int& bestIndex, DfpnBoundType& delta2,
00718                              const std::vector<DfpnData>& childrenData,
00719                              size_t maxChildIndex) const
00720 {
00721     DfpnBoundType delta1 = DfpnBounds::INFTY;
00722 
00723     HexAssert(1 <= maxChildIndex && maxChildIndex <= childrenData.size());
00724     for (std::size_t i = 0; i < maxChildIndex; ++i)
00725     {
00726         const DfpnBounds& child = childrenData[i].m_bounds;
00727 
00728         // Store the child with smallest delta and record 2nd smallest delta
00729         if (child.delta < delta1)
00730         {
00731             delta2 = delta1;
00732             delta1 = child.delta;
00733             bestIndex = i;
00734         }
00735         else if (child.delta < delta2)
00736         {
00737             delta2 = child.delta;
00738         }
00739 
00740         // Winning move found
00741         if (child.IsLosing())
00742             break;
00743     }
00744     HexAssert(delta1 < DfpnBounds::INFTY);
00745 }
00746 
00747 void DfpnSolver::UpdateBounds(DfpnBounds& bounds, 
00748                               const std::vector<DfpnData>& childData,
00749                               size_t maxChildIndex) const
00750 {
00751     DfpnBounds boundsAll(DfpnBounds::INFTY, 0);
00752     HexAssert(1 <= maxChildIndex && maxChildIndex <= childData.size());
00753     for (std::size_t i = 0; i < maxChildIndex; ++i)
00754     {
00755         const DfpnBounds& childBounds = childData[i].m_bounds;
00756         // Abort on losing child (a winning move)
00757         if (childBounds.IsLosing())
00758         {
00759             DfpnBounds::SetToWinning(bounds);
00760             return;
00761         }
00762         boundsAll.phi = std::min(boundsAll.phi, childBounds.delta);
00763         HexAssert(childBounds.phi != DfpnBounds::INFTY);
00764         boundsAll.delta += childBounds.phi;
00765     }
00766     bounds = boundsAll;
00767 }
00768 
00769 void DfpnSolver::LookupData(DfpnData& data, const DfpnChildren& children, 
00770                             int childIndex, HexState& state)
00771 {
00772     children.PlayMove(childIndex, state);
00773     if (!TTRead(state, data))
00774     {
00775         data.m_bounds.phi = 1;
00776         data.m_bounds.delta = 1;
00777         data.m_work = 0;
00778     }
00779     children.UndoMove(childIndex, state);
00780 }
00781 
00782 bool DfpnSolver::TTRead(const HexState& state, DfpnData& data)
00783 {
00784     return m_positions->Get(state, data);
00785 }
00786 
00787 void DfpnSolver::TTWrite(const HexState& state, const DfpnData& data)
00788 {
00789     data.m_bounds.CheckConsistency();
00790     m_positions->Put(state, data);
00791 }
00792 
00793 //----------------------------------------------------------------------------
00794 
00795 void DfpnSolver::PropagateBackwards(const Game& game, DfpnStates& pos)
00796 {
00797     HexState state(game.Board(), BLACK);
00798     MoveSequence history(game.History());
00799     if (history.empty())
00800         return;
00801     do
00802     {
00803         HexPoint cell = history.back().point();
00804         state.UndoMove(cell);
00805         state.SetToPlay(history.back().color());
00806         history.pop_back();
00807         DfpnData data;
00808         if (!pos.Get(state, data))
00809             break;
00810         if (data.m_bounds.IsSolved())
00811             break;
00812         std::vector<DfpnData> childrenData(data.m_children.Size());
00813         for (size_t i = 0; i < data.m_children.Size(); ++i)
00814             LookupData(childrenData[i], data.m_children, i, state);
00815         size_t maxChildIndex = ComputeMaxChildIndex(childrenData);
00816         UpdateBounds(data.m_bounds, childrenData, maxChildIndex);
00817         pos.Put(state, data);
00818     } while(!history.empty());
00819 }
00820 
00821 //----------------------------------------------------------------------------
00822 


6 Jan 2011 Doxygen 1.6.3