蒙特卡洛搜索树MCTS

Alpha Zero and Monte Carlo Tree Search (joshvarty.github.io)

Alpha zero中的蒙特卡洛搜索树每一个节点表示一个局面，子节点表示此局面下一步走法，每个节点参数W/N，W表示经过此节点的路径最终胜利次数，N表示经过此节点的次数。

HpJcB.png

大家都知道蒙特卡洛方法其实就是基于采样和大数定理的一种估计方法，而蒙特卡洛搜索树是用蒙特卡洛方法估算每一种走法的胜率，即通过不断模拟某一种走法，直到平局或一方取得胜利，若某个步骤模拟次数为N，后续最终胜局次数为W，则课近似推算该走法胜率为W/N，我们可以通过对游戏进行推演来逐渐建立一棵不对称的搜索树。

emm~，类似于每下一步棋你就在脑子里想我这一步下了对方会怎么下，你又会怎么下，一直想到对局结束，然后你在从此估计该下哪一步。。。。。。

蒙特卡洛搜索树大致分为四个步骤：

  • 选择select
  • 拓展expansion
  • 模拟simulation
  • 反向传播 Back Propagation

选择

我们可以将节点分为三类：

  • 未评估：还没有评估过的局面，就是还没有思考过这个局面下下一步怎么走
  • 未完全展开：至少评估过一次，但未完全评估。子节点未完全访问。就是这个局面下可以走的步法没有都评估思考过
  • 完全展开：此局面的子节点全都被访问过，就是这局面下的走法全都思考过。

选择Select就是找出当前最有可能走到的未被评估的局面，就是选一个之前没走过的但最有可能胜利的走法。何为最有可能胜利呢？最直观的看法是直接按节点的胜率W/N选择，但是这样是不行的，因为最开始构建树的过程中，尽管中国节点不怎么好，但是一开始随机构建时恰巧赢了一把，那之后模拟就会一直走这个节点，所以我们根据UTC函数选择节点：
$$
UCT(v_i,v)=\frac{Q(v_i)}{N(v_i)}+c\sqrt{\frac{\log(N(v))}{N(v_i)}}
$$
其中Q(v)是该节点赢得次数W,N(v)是该节点模拟的次数，C是一个常数，类似于学习率。vi是子节点，v是父节点。

随着访问次数的增加，根号下内容嘴贱减小，我们就更倾向于选择那些访问次数少的节点。

扩展expand

走一步之前从未走过的走法，在该局面下增加一个子节点

模拟simulation

从当前局面(根节点)开始，模拟一整局游戏到分出胜负

反向传播backpropagation

就是模拟到了分出胜负，从最后一个子节点开始更新父节点的胜利次数和访问次数信息，比如上图中最后一个子节点没有赢得这局比赛，所以其数据未0/1，那么反向传播需要把其所有父节点的访问次数加1。

Alpha Zero

在alpha zero中，主要有几点不同：

  • 不在进行模拟，而是直接使用一个19层的CNN ResNet直接评估当前节点，也就是利用神经网络直接评估各节点的胜利失败概率。

  • 更改信任度上限树函数UCT为：
    $$
    UCT(v_i,v)=\frac{Q(v_i)}{N(v_i)}+cp(v,v_i)\sqrt{\frac{N(v)}{1+N(v_i)}}
    $$
    其中$p(v,v_i)$表示从状态$v_i$转移到v的概率，这个概率使用策略网络训练出来的，基于人类游戏数据集的监督学习。

MCTS实现井字棋和五子棋

完整代码可在我的Github下载：

yy-199908/MCTS-wuziqi (github.com)

简单来说总的逻辑就是：玩家每下一步，程序就把当前棋局作为MCT的根节点，通过simulation模拟一定数量的对局(这个数量自己设置，越多耗时越长，程序越“智能”)，再通过simulation对局的胜负对下一状态(程序下一步之后的局面)打分，通过计算其UCT选出最好的落子。

程序分为4个部分：

  • game.py包含了实现游戏状态和落子的类

  • mcts.py包含了实现MCT节点和MCTS搜索的类

  • play.py包含了实现对弈的类

  • gameui.py包含了实现GUI的类

编写MCTS程序时有几个需要注意的点：

  • 如何实现自对弈

  • 注意simulation时优先走没走过的局面。

  • 反向传播时对自己是正还是负，这里我用一个字典分别记录当前节点后赢、输、平局的次数

  • 获取所有合法落子get_legal_actions

  • 对弈的流程：

def callback(self,event):#鼠标点击的回调函数
        #玩家
        x=event.x
        y=event.y
        x=round((x-30)/(540/self.shape))
        y=round((y-30)/(540/self.shape))
        
        if x in range(self.shape)and y in range(self.shape):
            location=str(y)+','+str(x)
            move1 = get_action(self.c_state,location)
            self.c_state = self.c_state.move(move1)
            self.c_board = self.c_state.board
            self.draw(self.c_board)
            graphics(self.shape,self.c_board)
            flag=judge(self.c_state)
            if flag!=-1:
                self.end(flag)
                return None
            ##程序
            self.board_state = GameState(state=self.c_board, next_to_move=1)
            root = Node(state=self.board_state, parent=None)
            mcts = MCTSearch(root)
            best_node = mcts.best_action(self.sim_nums)
            self.c_state = best_node.state
            self.c_board = self.c_state.board
            self.draw(self.c_board)
            flag=judge(self.c_state)
            if flag!=-1:
                self.end(flag)
                return None
            return None

callback是鼠标点击下子的回调函数，该回调函数中先在玩家点击的地方下子，然后判断游戏是否结束，没结束就让程序simulation一定次数，然后选出最好的地方下子。

算法其实挺有趣，但是好慢好慢啊，对弈一个8x8棋盘的五子棋，simulation需要巨量的时间

我下了个8x8的五子棋局，程序每步simulation10000次，差不多一两分钟它才下一步，吐血~~

虽然放了一整片大海，我就当它赢了我吧，(●’◡’●)~~

HEKX3.png

对了，改成3x3的3子棋，或者叫井字棋还是米字棋的什么玩意儿，simulation 1000次基本上就一直是平局(如果你不放水让它赢的话)

HPUhm.png