五子棋AI - 蒙特卡洛树搜索_五子棋深度搜索

动机

自高中时代做了一个带简单AI的五子棋游戏后，一直以来实现一个更加厉害的五子棋AI算是我的小目标。之前也尝试过使用 MinMax 算法，最终结果不甚理想。当然并不是算法问题，而是搭配这个算法需要许多领域知识，这些知识我并不了解，以至于结果与我的期望相去甚远。

我心目中满意的五子棋AI是这样的：

1. 不需要像 MinMax 那样去编写一个局面评估函数
2. 算法看上去很简单很傻也没关系，但可以通过训练提高棋力
3. 似乎真的可以理解局面

在 AlphaGO 出现之前，我的思路都是采用遗传算法，因为我确实看到过遗传算法在桌面游戏中的成功应用。但是遗传算法需要某些东西可以被遗传跟突变，我那时并没有想到哪些信息该编码进去，如果将棋形分数编码，应该还是会得到一个比较弱的AI。

后来 AlphaGO 出现了，它几乎就是我梦想中的 AI 了，除了需要人类棋谱。再后来 AlphaZero 出现了，不依赖人类棋谱，仅以自我对弈的方式就可以发现围棋的奥妙。于是，我决定以 AlphaZero 的实现方法为蓝本实现我的梦想五子棋 AI。AlphaZero 采用了深度学习和蒙特卡洛树搜索，深度学习我还没有接触过，为了不至于什么东西也做不出来，我打算先从蒙特卡洛树搜索开始。

关于蒙特卡洛树搜索我并不想再做介绍，已经有很多讲解的很好的文章了。我想实现一个稍微通用点的并且尽量教科书式的蒙特卡洛树搜索，方便自己或者他人阅读，今后也可以用于其他游戏。鉴于我了解 C++，我打算采用 C++ 来实现。

节点

树有节点，需要定义节点数据类型。考虑到蒙特卡洛树搜索运行所需要的数据，我把节点定义成如下样子：

template<class _State>
struct node_t {
  node_t<_State>* parent;
  typename _State::action_type action;
  double w;
  double n;
  double p;
  double q;
  std::vector<node_t<_State>> children;
};

其中，w 表示分数；n 表示节点访问次数；p = w/n；q = ln(n) * 2。p, q 是为了方便，将一些中间计算结果保存在了节点中，并不是必要的。children 采用 std::vector 主要是想把内存管理的事情简化掉，并且提高子节点遍历的效率。节点的模版参数看着很奇怪，其实只是为了与其他地方统一。

算法状态

蒙特卡洛算法运行需要知道根节点以及状态，我设计如下数据结构封装这两个数据。

template<class _State>
struct mcts_context {
  _State state;
  node_t<_State> root;
};

有了上面两个数据结构，蒙特卡洛树搜索的大致框架就有了。

template<class _State, class _Rep, class _Ra>
node_t<_State>* mct_search(mcts_context<_State>& ctx, std::chrono::duration<_Rep, _Ra> dur) {
  typedef node_t<_State> node_type;
 
  _State origState = ctx.state;
  auto t0 = std::chrono::system_clock::now();
 
  while (std::chrono::system_clock::now() - t0 < dur) {
    node_type* leaf = select(ctx);
    if (leaf->n > 0 && leaf->children.empty())
      leaf = expand(ctx, leaf);
    double score = -playout(ctx.state);
    back_propagate(leaf, score);
    ctx.state = origState;
  }
 
  return &*std::max_element(
    ctx.root.children.begin(), ctx.root.children.end(), 
    [](const node_type& a, const node_type& b)
    { 
      return a.n < b.n; 
    });
}

其中 select, expand, playout, back_propagate 对应算法的四个阶段。要注意的是 playout 的行为是，随机模拟结束后，若获胜方为当前行棋方（调用 playout 时当前局面的行棋方）则返回 1，对手获胜返回 -1， 平局返回 0。因为要做一个通用的算法，这里肯定不能假设黑方白方，但两人回合制游戏一定存在当前方。最终结果乘以 -1 的理由是，若当前算法要为白棋搜索最好着法，则根节点对应的局面为白方行棋，那么子节点对应白方每个合理着法之后的局面，而这些子节点对应局面的行棋方是黑方。如果子节点模拟结束后黑棋获胜，就表示白棋行棋后导致黑棋获胜，这显然不是我们想要的。我们肯定更希望白棋行棋后导致白棋获胜的着法，而行棋后的局面与局面当前行棋方总是相反关系，也就是说如果当前为白棋行棋则一定是黑棋走了一步棋造成的，所以最终结果乘以 -1。

由于节点只保存动作并未保存当前局面状态，所以我将局面状态绑定到 select, expand 阶段。在 select/expand 阶段选择出子节点的同时将 context 中的状态改变至节点对应的状态，在一轮结束后再将状态恢复至初始状态。有些实现会采用 do_move/undo_move 达到同样效果。

接下来就是实现框架中的每个阶段了。

Select

select 是选择出叶子节点，其中叶子节点的定义是还没有执行过随机模拟的节点或者终结节点，也就是 n 为 0 或者没有子节点的节点。

template<class _State>
node_t<_State>* select(mcts_context<_State>& ctx) {
  node_t<_State>* pNode = &ctx.root;
  while (pNode->n > 0 && !pNode->children.empty()) {
    pNode = &*std::max_element(
      pNode->children.begin(),
      pNode->children.end(),
      [pNode](const node_t<_State>& a, const node_t<_State>& b)
      {
        double x = a.p + std::sqrt(pNode->q / a.n);
        double y = b.p + std::sqrt(pNode->q / b.n);
        return x < y;
      }
    );
 
    ctx.state = next(ctx.state, pNode->action);
  }
 
  return pNode;
}

这里我引入了一个新函数 next()，它的作用是给定当前局面状态和动作，返回动作执行后的下个局面状态。由于是通用算法，局面状态的表示法还不确定，所以这里实际是留给局面状态实现方的接口。

Expand

expand 是扩展节点。

template<class _State>
node_t<_State>* expand(mcts_context<_State>& ctx, node_t<_State>* leaf) {
  typedef typename _State::action_type action_type;
 
  std::vector<action_type> a = actions(ctx.state);
  if (a.empty()) return leaf;
 
  leaf->children.resize(a.size());
 
  std::transform(
    a.begin(),
    a.end(),
    leaf->children.begin(),
    [leaf](const action_type& act)
    {
      return node_t<_State> {leaf, act, 0, 0, 0, 0};
    }
  );
 
  leaf = &leaf->children.first();
  ctx.state = next(ctx.state, leaf->action);
 
  return leaf;
}

这里引入了一个新的函数 actions() 用来获取当前局面状态的可行动作，如果没有可行动作则表示这是最终局面了。同 next() ,这也是留给局面状态实现方的接口。

Playout

playout 需要执行随机模拟和判断输赢，有太多根局面状态绑定的概念，所以也留给局面状态实现方。

Back propagate

back_propagate 就是把结果反向传播到根节点。

template<class _State>
void back_propagate(node_t<_State>* leaf, double score) {
  while (leaf) {
    if (score == 0) leaf->w += 0.5;
    else if (score == 1) leaf->w += 1;
    leaf->n += 1;
    leaf->p = leaf->w / leaf->n;
    leaf->q = std::log(leaf.n) * 2;
 
    leaf = leaf->parent;
    score = -score;
  }
}

总结

至此蒙特卡洛树搜索算法就算是完成了，我留了 3 个接口（next(), actions(), playout()）给外部，这三个函数的实现我将在接下来 局面状态 的文章中具体讲。整个结构肯定存在可以调整优化的地方，不过先不急。