搜索
北京市大学生科学研究与创业行动计划立项申请书基于UCT搜索算法的亚马逊棋人机博弈软件的设计与实现团队成员：侯亮张婷学院：信息工程学院专业：计算机科学与技术指导老师：吴立成北京市大学生科学研究与创业行动计划立项申请正文2目录一、立项依据……………………………………………………………………31.1亚马逊棋人机博弈的研究现状……………………………………………31.2项目可行性分析……………………………………………………………41.3学术价值……………………………………………………………………61.4团队优势……………………………………………………………………6二、研究目标、内容、关键问题及解决方案…………………………72.1研究目标……………………………………………………………………72.2研究内容……………………………………………………………………72.3软件各部分简述……………………………………………………………72.4要解决的关键问题及解决方案……………………………………………82.5研究基础……………………………………………………………………92.6本项目的主要特色及创新之处……………………………………………10三、预期效果与具体成果…………………………………………………103.1预期效果……………………………………………………………………103.2具体成果……………………………………………………………………10四、具体安排及进度………………………………………………………11五、经费预算………………………………………………………………11六、参考文献………………………………………………………………12北京市大学生科学研究与创业行动计划立项申请正文3一、立项依据1.1亚马逊棋人机博弈的研究现状亚马逊棋（GameoftheAmazons），是由阿根廷人WalterZamkauska在1988年推出的两人棋类，是欧美国家的一个棋种，在亚洲并不常见，它由国际象棋中后的走法衍生而来，与著名的八皇后问题类似。亚马逊棋是计算机博弈（ComputerGames）的重要组成内容，也是全国大学生计算机博弈大赛以及ICGA国际计算机博弈大赛的比赛指定棋类。1998年举行了国际电脑亚马逊棋锦标赛，2001年亚马逊棋正式成为电脑奥林匹克大赛项目之一。在人类文明发展的初期，人们便开始进行棋类博弈的游戏了。近几十年来，随着计算机硬件和软件技术的不断发展，人们开始对计算机能否战胜人脑这个话题产生了浓厚的兴趣。从1980开始，电脑博弈便开始逐渐大规模地向人类智能发起了挑战，到了1997年，IBM超级电脑DeeperBlue击败了当时的国际象棋冠军卡斯帕罗夫，成为了人工智能挑战人类智能发展的一个重要里程碑。然而计算机博弈在我国发展起步较晚，2006年我国举办了首届中国象棋博弈大赛。在2007年举办的首届全国计算机博弈大赛中，亚马逊棋被引入。亚马逊棋的棋盘由10*10的格子组成，每方各拥有4枚棋子（4个Amazons），以不同的两色区分敌我，每个棋子都相当于国际象棋中的皇后，它们的行棋方法与皇后相同，可以在八个方向（上、下、左、右、左上、左下、右上、右下）上任意行走，但不能穿过阻碍；当轮到一方行棋时，此方只能而且必须移动四个Amazons中的一个，并在移动完成后，必须由当前移动的棋子释放一个障碍，障碍的释放方法与棋子的移动方法相同(可在八个方向上释放，但不能穿过阻碍）。当某方完成某次移动后，使另一方四个棋子均不能再移动，此时棋子不能移动一方将输掉比赛；整个比赛中双方均不能吃掉对方或己方的棋子或障碍。正是由于这种特殊的走法规则导致了亚马逊棋每步的走法非常多，平均在1000多种左右，而且对大多数走法的评估也具有很大的不确定性。这些特点导致了亚马逊棋并不太适合人与人之间对弈，但却非常合适用于人工智能、机器博弈方面的研究。当前亚马逊棋计算机博弈主要搜索算法有传统的负极大方法、剪枝算法、MC方法（即蒙特卡洛方法）、UCT算法、Alpha-Beta搜索。其中UCT算法是机器博弈领域最新的搜索算法，它很好的解决了传统搜索算法无法在亚马逊棋搜索中遍历更深层节点的问题。本软件就是基于UCT算法开发的亚马逊人机博弈程序，通过提高对弈过程中计算机的搜索效率，解决现有亚马逊PC博弈程序搜索时间长、运行速度慢的问题。北京市大学生科学研究与创业行动计划立项申请正文4图1.亚马逊棋棋盘图2.亚马逊棋对局画面1.2项目可行性分析项目组现已拥有大量亚马逊棋机器博弈的相关资料，并且能继承和借鉴现有的亚马逊棋博弈程序的优点，开发出效率更高、算法更精良的亚马逊博弈软件。大量资料表明，MC/UCT搜索算法在亚马逊棋搜索中能得到较好的运用。UCT是机器博弈领域最新的搜索算法，它很好的解决了传统搜索算法无法在亚马逊棋搜索中遍历更深层节点的问题。JensLieberum在他自己的关于亚马逊棋评估的文章中,对亚马逊棋的评估方法做了详细的讨论，这篇文章也是现在亚马逊棋评估方法的主要来源。项目组通过仔细研读相关文献，对亚马逊棋博弈软件的研究有如下可行性分析。亚马逊棋的走法生成：亚马逊棋的走法分为两步，首先要移动一个棋子，然后由当前被移动的棋子放置一个障碍，棋子的移动和障碍的放置都遵循皇后的走法，所以在生成一步的所有可行走法时，走法的结构中应该至少包括3个数据：起点，终点，障碍放置点。由于亚马逊棋走法存在上述的特点，导致每一步的可行走法数量十分庞大，平均在1000多种左右，第一步有2176种可行走法。亚马逊棋的局面评估：亚马逊棋的行棋目的是用障碍或自身棋子将对方棋子堵死，使其不能移动，而对于可以在八个方向任意行走的Queen来说，将其堵死又谈何容易，所以另一种思路则是圈地思想，北京市大学生科学研究与创业行动计划立项申请正文5用障碍或己方棋子为自己圈出足够大的地盘（对方棋子不能进入的区域），这样当自身获得足够的地盘时，对方会因为没有地方可走而自己将自己堵死。现在用的主要是后一种控制区域（地盘）的思想，当评估一个局面的好坏时，主要看对方棋子控制的区域和己方棋子控制区域的多少，至于什么样的区域算是己方的控制区域，现在多数用QueenMove的方法。在对局初期，当棋盘比较空旷时，通过人的观察和判断很难确定一步棋的好坏。这时的亚马逊棋和围棋很相近，都存在地盘的思想，初期的许多走法更像是布局而非具体的争夺，而到了对局的中后期，当棋盘上的障碍逐渐增多，每块地盘的形状已经明朗时，亚马逊棋的行棋思路则又和象棋相近，需要通过更深层的搜索来确定具体某块区域的争夺和归属情况。亚马逊棋的评估方式与围棋的不同点在于，围棋更强调布局，亚马逊棋则更为直观，所以真人与电脑对局基本不会赢。亚马逊棋的搜索：1、传统的负极大方法：用负极大方法为搜索的主体时，由于亚马逊棋每步的可行走法数量十分庞大，所以可以向下展开的层数很少，两层就会有数百万个叶子节点。因此需要大量运用剪枝算法配合提前排序。2、MC方法，即蒙特卡洛方法：以蒙特卡洛方法为主体的搜索方法也在亚马逊棋中大量运用，但与围棋中的MC方法不同的是，亚马逊棋中的MC模拟并不模拟到局面的终了，而是只模拟到一定的层数。3、UCT算法：UCT算法源于围棋，但同样使用于亚马逊棋。UCT方法是MC方法的发展，它的实质是运用了这样一种思想，就是尽量在有价值的节点上作较多的模拟对局，什么是有价值的节点，就是敌我对局时大家都愿意选择的节点，这些节点的层层确定是通过minmax方法，而这些节点的得分的获得则是通过MC方法，所以UCT方法实际上是一种minmax和MC的混合，使用MC模拟对局，通过minmax确定路径（下一次对局选用的节点），从而使有限次模拟对局的结果更准确地反映出节点的性质。由于亚马逊棋的搜索空间很大、计算机难于处理模糊概念且难于设计学习算法，造成了计算机亚马逊棋程序的搜索效率难以提高。还因为亚马逊棋特殊的规则，导致了亚马逊棋平均每步的合法走法多达1000多种(第一步有2176种)，如果仅向下搜索一层，则所需要评估的所有节点数已经超过百万，即使加入较好的剪枝算法，亚马逊棋庞大的节点数仍然让传统的基于minmax的搜索方法望而却步。项目组通过对亚马逊棋的规则及算法的进一步研究，吸北京市大学生科学研究与创业行动计划立项申请正文6取并借鉴各搜索算法的优势，为传统搜索算法无法在亚马逊棋环境中遍历更深层节点的问题找到解题的思路，提高亚马逊棋人机博弈的算法效率。1.3学术价值博弈是人工智能的重要研究主题，人工智能的发展在很大程度上得益于博弈研究的发展。人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。1997年著名的深蓝计算机战胜国际象棋世界冠军卡斯帕罗夫成为轰动一时的新闻事件。人工智能的先驱们曾认真的表明：如果能掌握下棋的本质，也许就掌握了人类智能行为的核心，那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。亚马逊棋近几年才传入我国，是全国大学生计算机博弈大赛以及ICGA国际计算机博弈大赛的比赛指定棋类。目前在我国亚马逊棋的算法研究和搜索分析还只是刚刚起步，亚马逊棋的算法研究和开发还有很广阔的空间。亚马逊棋不仅为检验人工智能发展水平提高了良好环境，还有助于加强对人类认知能力的理解，而且更能进一步推动计算机博弈理论的发展，把亚马逊棋人人对弈的局面转到可以人机大战上来，并且这对宽带娱乐、棋类教学也是非常有意义和帮助的，所以亚马逊棋计算机博弈研究具有重要的理论意义和实用价值。1.4团队优势：1.本团队共有两名成员，全部来自计算机科学与技术专业。有着良好的专业知识基础，比较好的数学基础以及软件工程基础，能够熟练运用C++、JAVA等高级语言，为软件实现打下良好的基础。并具有较强的实践能力和创新精神，在以前参赛过程中，通过长期的培训和不断努力，培养了团队成员坚持不懈和迎难而上的科研精神。2、项目组成员成绩优秀，获得过“中央民族大学专业二等奖学金”和“信息工程学院电子设计大赛一等奖”等，理论知识和实践操作能力都非常优秀；3.指导老师长期从事机器人学、智能控制、轨迹规划及试验平台研制等方面的研究，在电子电路设计与软件开发方面有着多年的实践经验。曾指导本科生课外科技活动获清华大学挑战杯二等奖、“创新奖”及“最佳展示奖”（水上漂浮机器人），及“浪潮杯”首届中国计算机博弈锦标赛“新秀奖”（“棋乐无穷”象棋博弈软件），以及“北科杯”首届全国大学生计算机博弈大赛暨第五届全国计算机博弈锦标赛优秀指导教师奖和六子棋比赛“二等奖”。北京市大学生科学研究与创业行动计划立项申请正文7二、研究目标、内容、关键问题及解决方案2.1研究目标本项目将用JAVA语言开发一套亚马逊棋的人机博弈软件，通过使用UCT搜索算法使博弈引擎合理优化，并完成对系统的调试、测试及人机对战演练，最终实现一个高水平棋力的亚马逊棋人机博弈软件。2.2研究内容1.博弈界面的设计。包括对弈界面、菜单选项等的设计，同时嵌入音效、动画等功能。在编程语言方面，我们选择用JAVA语言进行开发，它不仅具有高移植性，并且拥有强大的界面制作工具和组件，在界面制作方面更具有优势。2.搜索引擎的设计与优化。对已有的多种搜索算法进行测试、分析、调整，选择并设计出最适合本博弈软件的搜索引擎，我们主要采用UCT搜索算法提高软件的搜索效率。3.软件的调试与测试，通过手动调整、自动对战、人机对战等方法对该博弈软件进行测试和优化，对众多的参数权值、估值方式进行调整。2.3软件各部分简述设计的计算机亚马逊棋博弈软件主要包括：棋盘生产、着法产生、搜索算法、估值核心四大部分。1.棋盘表示(BoardRepresentations)为了能快速获取个棋子的位置坐标，本项目将采用10*10二维矩阵表示棋盘，用0~99进行棋盘位置编码。并根据对称性，对双方棋子进行编码以方便对其进行估值等操作。2.着法生成(MoveGeneration)软件运行时需要进行频繁、复杂的判断和搜索才能确定着法，该过程是软件性能的瓶颈。着法生产模块主要解决如何快速高效地确定当前