蒙特卡洛树_四子棋实验报告

四子棋详细实验报告实验算法：局部UCT算法对朴素的蒙特卡洛算法加速：更优化的算法，UCT算法。以下是算法：给定一棵博弈树。MCTNodenodes[MAXTREE];//蒙特卡洛树1)从博弈树的根点开始向下搜索，执行2）。2)遇到节点a(bestIndex)后，若a存在从未评估过的子节点，执行3），否则执行4）。3)通过蒙特卡洛方法imitate(intbestIndex)//模拟对局评估该子节点，得到收益值后更新该子节点至根节点路径上所有节点的平均收益值nodes[bestIndex].winRound++;//相应层的胜盘数加一nodes[bestIndex].totRound++;//总盘数加一，执行1）。4)计算每个子节点的UCB值，将UCB值最高的子节点作为节点a，执行2）。UCB=(double)nodes[index].winRound/((double)nodes[index].totRound+epsilon)+C*((double)log((double)nodes[fIndex].totRound+1)/((double)nodes[index].totRound+epsilon))+rand()*epsilon;5)算法可随时终止，达到给定时间后终止。{intBest()//选择最佳落子点}根节点下平均收益值最高的子节点作为算法的输出。（对于这个算法，有几点需要解释：1）博弈树的根节点指的是当前的局面。2）评估过的节点及其平均收益值将在程序运行过程中保存及更新。3）收益值设定合适的值。做法是将其设为1（胜）或0（负）。）详细说明蒙特卡洛算法：利用一维中的掷点法完成对围棋盘面的评估。具体来讲,当我们给定某一个棋盘局面时,程序在当前局面的所有可下点中随机选择一个点摆上棋子,并不断重复这个随机选择可下点(掷点)的过程,直到双方都没有可下点(即对弈结束),再把这个最终状态的胜负结果反馈回去,作为评估当前局面的依据。在随机选点的过程中,一些策略也可被加入进来。(因为本次实验我们没有足够的时间，所以在随机选点过程中，一些四子棋知识没有被加入进来)。当棋手面对一个待决策盘面时,他需要从多个可下点中选择一个行棋。所以,如果我们有足够的时间做模拟,则我们可以做以下的统计:设轮到一方进行决策时共有k个点可供选择,第i个节点具有参数vi,wi,i属于〔1,k],分别一记录到该次模拟为止第i个节点被选中的次数以及在这vi次模拟中第i个节点获得胜利的次数。介绍构建蒙特卡罗规划的应用过程:首先,我们将待决策的盘面作为某子树的根节点;然后在可下点中随机选择一点Pi,i属于【1,k】进行以下模拟过程:1)如果该节点第一次被选中,即vi=0,则将填入该节点后的盘面作为叶节点加入搜索树中并采用随机投点的方式完成之后的行棋过程。在这一过程结束之后vi自动加1,如果模拟至终盘得到胜利的结果wi加1,如果终盘得到失败的结果wi保持不变。接着我们将叶节点的信息返回给上层节点,即让其父节点的访问次数加1,获胜次数加上其子节点收益变化值的逻辑相反值!wi。如果父节点仍有父节点的话,则父节点的父节点访问次数加1,获胜次数加上其子节点收益变化值的逻辑相反数wi。以此类推,直至根节点为止,该次模拟结束并进行新一次模拟。2)如果该点不是第一次被选中,即vi！=0,即填入该节点后的盘面已作为叶节点加入搜索树中,则我们以该盘面为子树的根节点再一次执行构建搜索树的过程。在模拟时间结束后,我们可以简单地计算根节点的每个儿子可下点的模拟胜率:ri=vi/wi;而在k个可下点中胜率最高的可下点即为该次决策的结果。蒙特卡洛算法加入UCT算法：l)可下点的选择不是随机的,而是根据UCBI的信息上界索引值进行选择。如果可下点没有被访问,则可下点的上限信心索引值为正无穷大;如果可下点己被访问过,则可下点的上限信心索引值可以根据UCBI算法给出的上限信心索引值确定。在实际应用中,我们多采用UCBI给出的上线信心索引值确定上限信心索引值。当我们需要在众多可下点中选取一个时,我们要选择上限信心索引值最大的那一个。2)当模拟结束后确定最终选择结果时,我们不再根据胜率做出判断,由于选择可下点进行访问的过程已经兼顾了极小极大算法的思想,所以,我们最终做出的决策结果是那个被访问了最多次的可下点。由于UCB算法本身对于探索和利用的兼顾,所以利用UCB算法作为选点指导的UCT算法也具有该特点。它在探索和利用之间找到平衡,使得在模拟过程中,那些表现良好的节点所在支路能够被更多次的走到,而一些不甚理想节点在少量访问后就不在被访问。这样做的优势是对那些较好的节点,我们可以更深入的进行探索以保证我们的选择更加接近最优解。因为这样的原因,我们在模拟过程中往往以UCT算法代替单纯的蒙特卡罗规划算法。蒙特卡罗树搜索蒙特卡罗树搜索是把离线学习的知识与在线搜索的过程相结合的一种最优有限的搜索方法。在蒙特卡罗树搜索过程中,我们沿用UCT方法进行在线搜索过程;同时加入离线的知识提高UCT方法的搜索效率。由于在线搜索过程以UCT算法为基础,所以,蒙特卡罗树搜索主要包括四个方面的主要内容:l)搜索:通过UCT算法,递归的从博弈树的根节点向下搜索直至当前的叶子节点;2)扩展:对当前的博弈树叶子节点进行扩展;3)模拟:从当前的博弈树叶子节点开始进行蒙特卡罗模拟;4)更新:把蒙特卡罗模拟的结果更新到搜索过程中博弈树的每一个节点上。在这四个不同的方面,我们都可以加入离线学习的经验知识,使UCT算法升级为蒙特卡罗树搜索算法:搜索:使用知识进行UCT算法的初始化;扩展:使用知识控制博弈树的扩展。从具体情况上看又可以分为:可选落子点的排序策略:一般情况下,由于UCT算法的搜索时时间是有限的,叶子节点的访问次数很少。在同一层中,那些被排在后面的关键节点有可能由于位置的原因而不能被充分地探索到。所以,一个好的排序策略应该保证双方最强的应手在有限时间内均能被搜索到。这就要求我们利用知识,把那些在实际对战中更有利于获胜可选点排在所有节点的前列。实际应用中,E1一Rating根据离线知识,可以静态的对可下点进行排序。提高关键点被探索的可能性。可选落子点的扩展策略:从UCT算法的主要内容我们可以知道,如果当前节点为博弈树的叶子节点,则我们就会对其进行扩展,所有被扩展出的节点形成新的叶子节点。但是,一次性扩展所有节点很有可能造成时间和空间资源的浪费。这是显而易见的:假设现在的叶子子节点为Lp,我们扩展了它的k个叶子节点LCi,那么,我们不得不再次经过Lp这条路径k次刁有机会扩展Lp儿子的儿子节点。这样做,使得我们花更多的时间去观察那些表现平平的节点,同时还不得不为它们提供存储的空间,而这些空间很有可能会因为该节点从未被访问而成为被浪费掉的空间。所以,在实际应用中,我们通过Progressivewidening技术先扩展最强的落子点,然后根据访问时间,逐步扩展其他节点。可选落子点的剪枝策略:在博弈树上进行剪枝,是加快搜索效率的有效办法。将那些通过剪枝策略判定后确定不好的节点从博弈树中除去之后再考虑是否进行扩展,可以很好的缩小搜索的范围,提高搜索的速度。3)模拟:使用知识指导蒙特卡罗模拟;4)更新:保持与UCT算法的一致性,这样可以将离线知识和在线搜索的信息都返回搜索过程中博弈树的每一个节点上。从减少可选落子点的角度可以节点了剪枝的方法.评测结果：总体90的ddl,90%的胜率。但是大于90的ddl,由于完全采用蒙特卡洛方法，而随机下棋子中没有加入四子棋棋类知识（由于下棋时间的限制），胜率很低。