围棋落子搜索问题

9.3.1　围棋落子搜索问题

围棋落子模型是马尔科夫决策模型的一个实例。具体说来，当棋手面对一个待决策盘面时，他需要从多个可下点中选择一个进行行棋。于是，我们可以认为，一个待决策盘面是一个多臂匪徒机，每一个可行点都是一个手臂。而每一个可下点被选择后形成的盘面又可以被视为一个多臂匪徒机。

所以，如果我们有足够的时间做模拟，则我们可以做以下的统计：设轮到一方进行决策时共有k个点可供选择，第i个节点具有参数v_i、w_i（其中，（i∈［1，k］）），分别记录到该次模拟为止第i个节点被选中的次数及在这v_i模拟中第i个节点获得胜利的次数。下面我们将介绍构建蒙特卡罗规划的应用过程：首先，我们将待决策的盘面作为根节点；然后在可下点中随机选择一点p_i（其中，i∈［1，k］）进行以下模拟过程：①如果该节点第一次被选中，即v_i＝0，则将填入该节点后的盘面作为叶节点加入搜索树中并采用随机投点的方式完成之后的行棋过程。在这一过程结束之后自动v_i＋1，如果模拟至终盘得到胜利的结果，则w_i＋1，如果终盘得到失败的结果，则w_i保持不变。接着我们将叶节点的信息返回给上层节点，即让其父节点的访问次数加1，获胜次数加上其子节点收益变化值的逻辑相反值！w_i。如果父节点仍有父节点的话，则父节点的父节点访问次数加1，获胜次数加上其子节点收益变化值的逻辑相反数w_i。以此类推，直至根节点为止，该次模拟结束并进行新一次模拟。②如果该点不是第一次被选中，即v_i≠0，即填入该节点后的盘面已作为叶节点加入搜索树中，则我们以该盘面为子树的根节点再一次执行构建搜索树的过程。

在模拟时间结束后，我们可以简单地计算每个可下点的模拟胜率，即

而在k个可下点中胜率最高的可下点即为该次决策的结果；我们也可以利用极小极大搜索算法进行可下点的选择。算法9.2是蒙特卡罗规划用于解决围棋落子问题的伪码。

算法9.2　蒙特卡洛搜索树伪代码