文档介绍：四子棋详细实验报告
实验算法：
局部UCT算法对朴素的蒙特卡洛算法加速：
更优化的算法，UCT算法。以下是算法：
给定一棵博弈树。
MCTNode nodes[MAXTREE];〃蒙特卡洛树
从博弈树的根点开始向下搜索，执行有足够的时间做模拟,则我们可以做以下的统计:设轮到一方进行决策时共有k个点可供选择，第i个节点具有参数vi,wi,i属于〔1,k］，分别一记录到该次模拟为止第 i 个节点被选中的次数以及在这 vi 次模拟中第 i 个节点获得胜利的次数。介绍构建蒙特卡罗规划的应用过程:首先,我们将待决策的盘面作为某子树的根节点 ;然后在可下点中随机选择一点Pi,i属于【1,k】进行以下模拟过程：
1）如果该节点第一次被选中，即vi=O,则将填入该节点后的盘面作为叶节点加入搜
索树中并采用随机投点的方式完成之后的行棋过程。在这一过程结束之后vi自动加 1,如果模拟至终盘得到胜利的结果 wi 加 1,如果终盘得到失败的结果 wi 保持不变。接着我们将叶节点的信息返回给上层节点,即让其父节点的访问次数加
1,获胜次数加上其子节点收益变化值的逻辑相反值!wi。如果父节点仍有父节点的话,则父节点的父节点访问次数加 1,获胜次数加上其子节点收益变化值的逻辑相反数wio以此类推，直至根节点为止,该次模拟结束并进行新一次模拟。
2）如果该点不是第一次被选中,即 vi ！=0,即填入该节点后的盘面已作为叶节点加入搜索树中,则我们以该盘面为子树的根节点再一次执行构建搜索树的过程。在模拟时间结束后,我们可以简单地计算根节点的每个儿子可下点的模拟胜
率:
ri=vi/wi;
而在k个可下点中胜率最高的可下点即为该次决策的结果。
蒙特卡洛算法加入UCT算法：
1）可下点的选择不是随机的，而是根据UCBI的信息上界索引值进行选择。如果可下点没有被访问,则可下点的上限信心索引值为正无穷大;如果可下点己被访问过,则可下点的上限信心索引值可以根据 UCBI 算法给出的上限信心索引值确定。在实际应用中,我们多采用 UCBI 给出的上线信心索引值确定上限信心索引值。当我们需要在众多可下点中选取一个时,我们要选择上限信心索引值最大的那一个。
2）当模拟结束后确定最终选择结果时,我们不再根据胜率做出判断,由于选择可下点进行访问的过程已经兼顾了极小极大算法的思想,所以,我们最终做出的决策结果是那个被访问了最多次的可下点。
由于 UCB 算法本身对于探索和利用的兼顾,所以利用 UCB 算法作为选点指导的UCT算法也具有该特点。它在探索和利用之间找到平衡,使得在模拟过程中, 那些表现良好的节点所在支路能够被更多次的走到 ,而一些不甚理想节点在少量访问后就不在被访问。这样做的优势是对那些较好的节点 ,我们可以更深入的进行探索以保证我们的选择更加接近最优解。因为这样的原因 ,我们在模拟过程中往往以UCT算法代替单纯的蒙特卡罗规划算法。
蒙特卡罗树搜索
蒙特卡罗树搜索是把离线学习的知识与在线搜索的过程相结合的一种最优有限的搜索方法。在蒙特卡罗树搜索过程中，我们沿用UCT方法进行在线搜索过程;同时加入离线的知识提高UCT方法的搜索效率。由于在线搜索过程以UCT算法为基础,所以,蒙特卡罗树搜索主要包括四个方面的主要