动机
自高中时代做了一个带简单AI的五子棋游戏后,一直以来实现一个更加厉害的五子棋AI算是我的小目标。之前也尝试过使用 MinMax 算法,最终结果不甚理想。当然并不是算法问题,而是搭配这个算法需要许多领域知识,这些知识我并不了解,以至于结果与我的期望相去甚远。
我心目中满意的五子棋AI是这样的:
不需要像 MinMax 那样去编写一个局面评估函数算法看上去很简单很傻也没关系,但可以通过训练提高棋力似乎真的可以理解局面
在 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())给外部,这三个函数的实现我将在接下来 局面状态 的文章中具体讲。整个结构肯定存在可以调整优化的地方,不过先不急。