text: //----------------------------------------------------------------------------
  /** @file GoUctSearch.cpp */
  //----------------------------------------------------------------------------
  
  #include "../smartgame/SgSystem.h"
  #include "../gouct/GoUctSearch.h"
  
  #include <fstream>
  #include <iostream>
  #include "../go/GoBoardUtil.h"
  #include "../go/GoNodeUtil.h"
  #include "../gouct/GoUctUtil.h"
  #include "../smartgame/SgDebug.h"
  #include "../smartgame/SgGameWriter.h"
  #include "../smartgame/SgNode.h"
  #include "../smartgame/SgUctTreeUtil.h"
  
  using namespace std;
  
  //----------------------------------------------------------------------------
  
  namespace {
  
  //----------------------------------------------------------------------------
  
  const int MOVERANGE = SG_PASS + 1;
  
  SgNode* AppendChild(SgNode* node, const string& comment)
  {
      SgNode* child = node->NewRightMostSon();
      child->AddComment(comment);
      return child;
  }
  
  SgNode* AppendChild(SgNode* node, SgBlackWhite color, SgPoint move)
  {
      SgNode* child = node->NewRightMostSon();
      SgPropID propId =
          (color == SG_BLACK ? SG_PROP_MOVE_BLACK : SG_PROP_MOVE_WHITE);
      child->Add(new SgPropMove(propId, move));
      return child;
  }
  
  /** Append game to saved simulations (used if m_keepGames is true) */
  void AppendGame(SgNode* node, SgUctValue gameNumber, unsigned int threadId,
                  SgBlackWhite toPlay, const SgUctGameInfo& info)
  {
      ////SG_ASSERT(node != 0);
      {
          ostringstream comment;
          comment << "Thread " << threadId << '\n'
                  << "Game " << gameNumber << '\n';
          node = AppendChild(node, comment.str());
      }
      size_t nuMovesInTree = info.m_inTreeSequence.size();
      for (size_t i = 0; i < nuMovesInTree; ++i)
      {
          node = AppendChild(node, toPlay, info.m_inTreeSequence[i]);
          toPlay = SgOppBW(toPlay);
      }
      SgNode* lastInTreeNode = node;
      SgBlackWhite lastInTreeToPlay = toPlay;
      for (size_t i = 0; i < info.m_eval.size(); ++i)
      {
          node = lastInTreeNode;
          toPlay = lastInTreeToPlay;
          ostringstream comment;
          comment << "Playout " << i << '\n'
                  << "Eval " << info.m_eval[i] << '\n'
                  << "Aborted " << info.m_aborted[i] << '\n';
          node = AppendChild(node, comment.str());
          for (size_t j = nuMovesInTree; j < info.m_sequence[i].size(); ++j)
          {
              node = AppendChild(node, toPlay, info.m_sequence[i][j]);
              toPlay = SgOppBW(toPlay);
          }
      }
  }
  
  //----------------------------------------------------------------------------
  
  } // namespace
  
  //----------------------------------------------------------------------------
  
  GoUctState::AssertionHandler::AssertionHandler(const GoUctState& state)
      : m_state(state)
  {
  }
  
  void GoUctState::AssertionHandler::Run()
  {
      m_state.Dump(SgDebug());
  }
  
  //----------------------------------------------------------------------------
  
  GoUctState::GoUctState(unsigned int threadId, const GoBoard& bd)
      : SgUctThreadState(threadId, MOVERANGE),
        m_assertionHandler(*this),
        m_uctBd(bd),
        m_synchronizer(bd)
  {
      m_synchronizer.SetSubscriber(m_bd);
      m_isInPlayout = false;
  }
  
  void GoUctState::Dump(ostream& out) const
  {
      out << "GoUctState[" << m_threadId << "] ";
      if (m_isInPlayout)
          out << "playout board:\n" << m_uctBd;
      else
          out << "board:\n" << m_bd;
  }
  
  void GoUctState::Execute(SgMove move)
  {
      ////SG_ASSERT(! m_isInPlayout);
      ////SG_ASSERT(move == SG_PASS || ! m_bd.Occupied(move));
      // Temporarily switch ko rule to SIMPLEKO to avoid slow full board
      // repetition test in GoBoard::Play()
      GoRestoreKoRule restoreKoRule(m_bd);
      m_bd.Rules().SetKoRule(GoRules::SIMPLEKO);
      m_bd.Play(move);
      ////SG_ASSERT(! m_bd.LastMoveInfo(GO_MOVEFLAG_ILLEGAL));
      ++m_gameLength;
  }
  
  void GoUctState::ExecutePlayout(SgMove move)
  {
      ////SG_ASSERT(m_isInPlayout);
      ////SG_ASSERT(move == SG_PASS || ! m_uctBd.Occupied(move));
      m_uctBd.Play(move);
      ++m_gameLength;
  }
  
  void GoUctState::GameStart()
  {
      m_isInPlayout = false;
      m_gameLength = 0;
  }
  
  void GoUctState::StartPlayout()
  {
      m_uctBd.Init(m_bd);
  }
  
  void GoUctState::StartPlayouts()
  {
      m_isInPlayout = true;
  }
  
  void GoUctState::StartSearch()
  {
      m_synchronizer.UpdateSubscriber();
  }
  
  void GoUctState::TakeBackInTree(std::size_t nuMoves)
  {
      for (size_t i = 0; i < nuMoves; ++i)
          m_bd.Undo();
  }
  
  void GoUctState::TakeBackPlayout(std::size_t nuMoves)
  {
      m_gameLength -= nuMoves;
  }
  
  //----------------------------------------------------------------------------
  
  GoUctSearch::GoUctSearch(GoBoard& bd, SgUctThreadStateFactory* factory)
      : SgUctSearch(factory, MOVERANGE),
        m_keepGames(false),
        m_liveGfxInterval(5000),
        m_toPlay(SG_BLACK),
        m_bd(bd),
        m_root(0),
        m_liveGfx(GOUCT_LIVEGFX_NONE)
  {
      SetRaveCheckSame(true);
  }
  
  GoUctSearch::~GoUctSearch()
  {
      if (m_root != 0)
          m_root->DeleteTree();
      m_root = 0;
  }
  
  std::string GoUctSearch::MoveString(SgMove move) const
  {
      return SgPointUtil::PointToString(move);
  }
  
  void GoUctSearch::OnSearchIteration(SgUctValue gameNumber,
                                      unsigned int threadId,
                                      const SgUctGameInfo& info)
  {
      SgUctSearch::OnSearchIteration(gameNumber, threadId, info);
  
      if (m_liveGfx != GOUCT_LIVEGFX_NONE && threadId == 0
          && gameNumber > m_nextLiveGfx)
      {
          m_nextLiveGfx = gameNumber + m_liveGfxInterval;
          DisplayGfx();
      }
      if (! LockFree() && m_root != 0)
          AppendGame(m_root, gameNumber, threadId, m_toPlay, info);
  }
  
  void GoUctSearch::DisplayGfx()
  {
      SgDebug() << "gogui-gfx:\n";
      switch (m_liveGfx)
      {
      case GOUCT_LIVEGFX_COUNTS:
          GoUctUtil::GfxBestMove(*this, m_toPlay, SgDebug());
          GoUctUtil::GfxMoveValues(*this, m_toPlay, SgDebug());
          GoUctUtil::GfxCounts(Tree(), SgDebug());
          GoUctUtil::GfxStatus(*this, SgDebug());
          break;
      case GOUCT_LIVEGFX_SEQUENCE:
          GoUctUtil::GfxSequence(*this, m_toPlay, SgDebug());
          GoUctUtil::GfxStatus(*this, SgDebug());
          break;
      case GOUCT_LIVEGFX_NONE:
          ////SG_ASSERT(false); // Should only be called when LiveGfx is enabled
          break;
      }
      SgDebug() << '\n';
  }
  
  void GoUctSearch::OnStartSearch()
  {
      SgUctSearch::OnStartSearch();
  
      if (m_root != 0)
      {
          m_root->DeleteTree();
          m_root = 0;
      }
      if (m_keepGames)
      {
          m_root = GoNodeUtil::CreateRoot(m_bd);
          if (LockFree())
              SgWarning() <<
                  "GoUctSearch: keep games will be ignored"
                  " in lock free search\n";
      }
      m_toPlay = m_bd.ToPlay(); // Not needed if SetToPlay() was called
      for (SgBWIterator it; it; ++it)
          m_stones[*it] = m_bd.All(*it);
      int size = m_bd.Size();
      // Limit to avoid very long games if m_simpleKo
      int maxGameLength = min(3 * size * size,
                              GO_MAX_NUM_MOVES - m_bd.MoveNumber());
      SetMaxGameLength(maxGameLength);
      m_boardHistory.SetFromBoard(m_bd);
  
      m_nextLiveGfx = m_liveGfxInterval;
  }
  
  void GoUctSearch::SaveGames(const string& fileName) const
  {
      if (MpiSynchronizer()->IsRootProcess())
      {
      if (m_root == 0)
          throw SgException("No games to save");
      ofstream out(fileName.c_str());
      SgGameWriter writer(out);
      writer.WriteGame(*m_root, true, 0, 1, 19);
      }
  }
  
  void GoUctSearch::SaveTree(std::ostream& out, int maxDepth) const
  {
      GoUctUtil::SaveTree(Tree(), m_bd.Size(), m_stones, m_toPlay, out,
                          maxDepth);
  }
  
  SgBlackWhite GoUctSearch::ToPlay() const
  {
      return m_toPlay;
  }
  
  //----------------------------------------------------------------------------
  
  SgPoint GoUctSearchUtil::TrompTaylorPassCheck(SgPoint move,
                                                const GoUctSearch& search)
  {
      const GoBoard& bd = search.Board();
      bool isFirstPass = (bd.GetLastMove() != SG_PASS);
      bool isTrompTaylorRules = bd.Rules().CaptureDead();
      if (move != SG_PASS || ! isTrompTaylorRules || ! isFirstPass)
          return move;
      float komi = bd.Rules().Komi().ToFloat();
      float trompTaylorScore = GoBoardUtil::TrompTaylorScore(bd, komi);
      if (search.ToPlay() != SG_BLACK)
          trompTaylorScore *= -1;
      const SgUctTree& tree = search.Tree();
      const SgUctNode& root = tree.Root();
      SgUctValue value = root.Mean();
      SgUctValue trompTaylorWinValue = (trompTaylorScore > 0 ? 1 : 0);
      if (value < trompTaylorWinValue)
          return move;
      SgDebug() << "GoUctSearchUtil::TrompTaylorPassCheck: bad pass move value="
                << value << " trompTaylorScore=" << trompTaylorScore << '\n';
      vector<SgMove> excludeMoves;
      excludeMoves.push_back(SG_PASS);
      const SgUctNode* bestChild = search.FindBestChild(root, &excludeMoves);
      if (bestChild == 0)
      {
          SgDebug() <<
              "GoUctSearchUtil::TrompTaylorPassCheck: "
              "(no second best move found)\n";
          return move;
      }
      return bestChild->Move();
  }
  
  //----------------------------------------------------------------------------
  