北京市大学生科学研究与创业行动计划

北京市大学生科学研究与创业行动计划立项申请书基于UCT搜索算法的亚马逊棋人机博弈软件的设计与实现团队成员：侯亮张婷学 院：信息工程学院专 业：计算机科学与技术指导老师：吴立成北京市大学生科学研究与创业行动计划立项申请正文北京市大学生科学研究与创业行动计划立项申请正文#□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□学术价值博弈是人工智能的重要研究主题， 人工智能的发展在很大程度上得益于博弈研究的发展。人类对机器博弈的研究衍生了大量的研究成果，这些成果对更广泛的领域产生了重要影响。1997年著名的深蓝计算机战胜国际象棋世界冠军卡斯帕罗夫成为轰动一时的新闻事件。人工智能的先驱们曾认真的表明：如果能掌握下棋的本质，也许就掌握了人类智能行为的核心，那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中。□□□□□□□□□□□□, □□□□□□□□□□□□□□□ ICGA□□□□□□□□赛的比赛指定棋类。目前在我国亚马逊棋的算法研究和搜索分析还只是刚刚起步，亚马逊棋的算法研究和开发还有很广阔的空间。亚马逊棋不仅为检验人工智能发展水平提高了良好环境，还有助于加强对人类认知能力的理解，而且更能进一步推动计算机博弈理论的发展，把亚马逊棋人人对弈的局面转到可以人机大战上来，并且这对宽带娱乐、棋类教学也是非常有意义和帮助的，所以亚马逊棋计算机博弈研究具有重要的理论意义和实用价值。团队优势：.□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□,□□□□□□ C++、JAVA等□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□,□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□2、项目组成员成绩优秀，获得过 “中央民族大学专业二等奖学金”和“信息工程学院电子设计大赛一等奖”等，理论知识和实践操作能力都非常优秀；3.□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,在□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ □□□□□□□□□□□□□ □□□□□□□□□ ,□□□□□□□□□□□□□□□□□□□□□□ □□□□□□□□□□□□□□ ,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

二、研究目标、内容、关键问题及解决方案研究目标□□□□□JAVA□□□□□□□□□□□□□□□□□, 通过使用UCT□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□研究内容.博弈界面的设计。包括对口界面、菜单选项等的设计，同时嵌入音效、动画等功能。□□□□□□□, □□□□□ JAVA语言进行开发，它不仅具有高移植性，并且拥有强大的界□□□□□□□□,□□□□□□□□□□□□□.搜索引擎的设计与优化。对已有的多种搜索算法进行测试、分析、调整，选择并设计□□□□□□□□□□□□□□,□□□□□□ UCT搜索算法提高软件的搜索效率。.软件的调试与测试，通过手动调整、自动对战、人机对战等方法对该博弈软件进行测□□□□,□□□□□□□□□□□□□□□□□□2.3软件各部分简述□□□□□□□□□□□□□□□□□□：□□□□□□□□□□□□□□□□□□□□□□□□.棋盘表示(BoardRepresentations)0~99进□□□□□□□□□□□□□□□, □□□□□□ 10*10二维矩阵表示棋盘， 0~99进□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□2.着法生成(MoveGeneration)□□□□□□□□□□□□ □□□□□□□□□□□□□□， □□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□3.□□□□(atuationFunction)□□□□□□□□□□□□□□□，□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□，□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□子灵活度估值、 基于QueenMove和KingMove的评估□□□□□□□□□□□□,□□□□□□□□□□□□,□□□□□□□□□□4.搜索技术 (searchTechniques)□□□□□□□□□□□,□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□ UCT搜索算法 □□□□□□□,□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□5.开局库 (OpeningBook)□□□□□□□□□□□□□□□□□,□□□□□,□□□□□□□□□□□□,□□□□□□，□□□□□□□□□□□□□□□□□□□□□□□□□，□□□□□□□□□□□□□□□2.4要解决的关键问题及解决方案1、UCT搜索算法在亚马逊棋中的运用UCT算法源于围棋，但同样使用于亚马逊棋，只是在将围棋中的算法复制到亚马逊棋中时，会有一定的变化。基本步骤：由当前局面建立根节点，生成根节点的子节点(1)．从根节点开始；(2)口利用 UCB公式计算每个子节点的 UCB值，选择最大值的子节点；(3)．若此节点不是叶节点，则从此节点开始，重复 (2)；(4)．直到遇到叶节点，如果叶节点曾经被模拟对局过 40次，为这个叶节点生成子节点，从此节点开始，重复 (2)；(5)．否则对这个叶节点进行模拟对局，得到胜负结果，将这个收益按对应颜色更新到该节点及它的每一级祖先节点上去；(6)．回到 (1)，除非时间结束或者达到预设循环次数；(7)．从根节点的子节点中挑选平均收益最高的，作为最佳点；UCB公式：UCB=X+k*ln(parentcount)

nodecount

UCB=X+k*X：由模拟对局输赢次数决定，表现该节点基本性质k：常数系数， k取大表示希望模拟更多的兄弟节点，取小表示希望走入更深的口中；parent_count：□□□□□□□□□□□；node_count：□□□□□□□□□□□□亚马逊棋中使用UCT算法需要额外确定的一些参数和变化：.节点被模拟多少次后决定展开：当一个节点被模拟对局一定次数后，才能初步得到此节点的统计学信息，并展开节点。.提前剪枝：亚马逊棋中每步的着法过于庞大，一般在 1000步左右，而许多着法可以很容易的判定为垃圾，所以一般进行提前剪枝，保留 400步左右的着法。.决定展开节点后，子节点需要用提前剪枝后的顺序排列，并且并不生成所有的子节点而是按顺序先生产一定数量的子节点，在父节点的访问量突破一定数量时，再决定下一步生产的子节点。.模拟对局层数的决定：一般选择 6至10层。.底层评估方法：一种为返回输赢，一种为返回输赢程度 。21开局库的设计□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□研究基础□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□ PC□□□□□□□ C++源代码，并已对其性能、算法和优缺点进行□□□□□□,□□□□□□□□□□□□□□□□□□PC□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□

本项目的主要特色及创新之处□□□□□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□件。□□□□□□□□□□□□,□□□□□ MC/UCT□□□□,□□□□□□□□□□□□□□□,□□□□□□□ PC□□□□□□□□□□□□□□□□□□□□□□□□JAVA语言编写。 JAVA语言是一种相当简洁的“面向对象”程序设计语言。口省略 C++语言中所有的难以理解、容易混淆的特性，例如头文件、指针、结构、单元、运算JAVA编JAVA编□□□□□□□□,□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□□4.对PC博弈软件界面及功能进行合理优化，保证程序在计算机中运行的良好性能。在人机□□□□□,□□□□□□□□,□□□□□□□□□□□□□□□三、预期效果与具体成果预期效果1.□□□□□□□□PC博弈软件能在计算机上运行，1.□□□□□□□□PC博弈软件能在计算机上运行，□□□□□□□□□□□□□□□面。2.□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□面。2.□□□□□□□□□□□,□□□□□□□□□□□□□□□□□□□□□3.□□□□□□□□PC博弈软件用JAVA3.□□□□□□□□PC博弈软件用JAVA语言编写，□□□□□□□□□□□□□□□□□□4.□□□□□□□MC/UCT搜索算法，能与高水平的亚马逊棋爱好者对弈，搜索效率高、4.□□□□□□□□□□□□□具体成果1口高棋力亚马逊棋 PC博弈软件1套2．研制报告一份，包括系统总体及各部分的设计书、软件源代码、仿真文件，以及试验结果等。

四、具体安排及进度第一阶段□4个月）软件的设计和编写：原有亚马逊棋程序的消化；计算、测试估值函数的准确性；测试选择最优的搜索算法，并组成搜索引擎；软件代码编写：1、界面开发；2、搜索引擎代码编写；3、算法代码实现4、组员共同讨论对程序的优化和完善。对软件整合后进行运行测试，解决运行中发现的问题，并修改不便之处；检验运行成功，软件初成品开发完成。第二阶段□1□□□□系统的初测试：让系统与性能低的亚马逊棋软件博弈，大约对弈 100到300口，记录全部对口数据；让系统与性能高亚马逊软件对弈，记录全部对弈数据第三阶段（2个月）ODDO：分析前期系统与各亚马逊棋软件的对弈数据， 列出具体的缺陷和不足；借鉴其他软件的优势，修改和补充系统的缺陷和不足，再次提高系统的性能；通过和其他软件进行对比，优化操作界面，使操作更人性化。第四阶段□□□□□人机博弈：•请棋手与系统进行对弈，测试系统的性能•咨询棋手，了解系统的性能、界面和软件是否存在“低级错误” 口第六阶段（2个月）DODD：•总结整个项目的开发过程和经验；•撰写论文和研究报告。五、经费预算DO说明经费DODD□□□□□□□ PC□□□□□□□□□□□□□□□□□□□□□□□□□□□□□： KadonEnterprises开发的“ Amazons”1000资料费购买书籍、论文及影印资料费等。250差旅交通费□□□□□□□□□□□□□火车票： 600*2=12003100食宿费： 550*2=1100□□□□□： 800参赛报名费参加全国大学生计算机博弈大赛报名费500总计4850六、参考文献[1]乔治，黄鸿.□□□□□□□□□□ [R].北京理工大学，2009Jens.Lieberum:AnevaluationfunctionforthegameofamazonsTheoretical.ComputerScience349(2005)230-244.J.Conway:OnNumbersandGames，AcademicPress，NewYork，1976.RichardJ.Lorentz:AmazonsDiscoverMonteCarlo.