生成蒙特卡洛树的四个步骤:
从根节点出发root出发,向深度方向递归选择最优的子节点直至当前树的某一叶节点。
策略:在蒙特卡洛树的每一父层,优先选择当前父节点下未被探索的子节点,当所有的子节点都被探索以后,选择UCB值最大的子节点;重复进行,直到选择到当前树的某一个叶节点。
当到达叶节点node时,需要判断该叶节点所对应的游戏状态。如果游戏结束,则直接进入到步骤4,将胜负值反向传播,更新根节点root到当前叶节点路径经过的所有节点;如果游戏没有结束, 则对当前节点进行扩展,将所有可能的行动添加到当前节点下。
当树到达某个叶节点node并将其扩展以后,蒙特卡洛树需要评价当前选择的节点node的价值,这里就需要使用蒙特卡洛方法来评价此次落子的价值。 从当前棋盘状态开始,采用随机走子的办法进行n次走子,并判断哪位玩家获胜,如果当前落子的玩家获胜,则返回1,失败返回-1,n回合没有决出胜负则返回0。在这里需要注意,从当前状态开始,紧接着走子的对方棋手,因此从当前状态开始判断是否获胜获得的价值实际上是对方棋手获得 的价值,对于当前棋手需要采用价值的相反数对当前节点node进行更新,每次更新节点时,都需要对value取相反数,因为棋手下棋是交替进行的,每个节点的父节点都是对方棋手的走子。
获得当前节点node的价值并反向传播直至根节点,路径中的相邻的两个节点之间的价值互为相反数。
在这里实现了一种简单的蒙特卡洛树玩家,即每一步落子时生成一棵蒙特卡洛树,然后选择蒙特卡洛树第1层节点(根节点位于第0层)中遍历次数最多的节点(行动)。