莫里斯九子棋的搜索算法的研究及应用开题报告

1. 研究目的与意义（文献综述）

莫里斯九子棋又称“成三棋”或“直棋”，是一款非常古老的智力游戏。它的规则较简单，易学易懂，其历史甚至可以追溯到公元前1400多年的古埃及时代。在国内文化里也有它的身影，是一款传统的棋类游戏^[7]，于公元前500多年在我国出现，历史悠久，在湖北鄂南地区，80后们小时候十分流行，是一种老少皆宜的棋类活动。方寸之间，便能突显弈者的奇思妙想。然而现在该棋类的知名度不敌围棋、象棋，已逐渐衰落，面临失传的风险，关于九子棋的机器博弈研究也所见无几，本文对这一古老的传统游戏进行研究，与现代计算机博弈相结合，使其成为莫里斯九子棋的新型娱乐方式，用这种新的娱乐方式进行普及和传承，由此来凸显现代计算机科技传承传统与引领未来的双重价值，弘扬传统文化，促进中华民族传统文化与世界文化的繁荣^[14]。

机器博弈也称为计算机博弈（computergames），是人工智能领域挑战性最强的研究方向之一。从狭义上看，机器博弈主要是让计算机像人类一样思考和决策棋牌类竞技游戏，从广义上看，此过程所积累的理论与技术可以解决现实生活中的诸多博弈问题，并推动博弈论的基础研究^[2]。目前，机器博弈除了在棋牌类游戏的运用^[10]之外，还在智慧医疗、智能交通、航空航天等多个领域的产业中都发挥着积极作用，尤其是在军事国防领域，机器博弈助推了多种新型武器与系统的发展。计算机博弈经过了长期的发展，在一些博弈项目中已经取得了令人瞩目的成就^[8]。美国ibm公司开发的计算机国际象棋博弈程序深蓝利用历史棋局不断对博弈树进行搜索从而找到最优博弈方案，并用这种方法在1997年正式击败了当时的世界国际象棋冠军卡斯帕罗夫。2016年deepmind在《自然》发表了论文，利用蒙特卡罗树搜索^[17]和深层卷积神经网络使围棋智能体达到人类大师水平，并相继击败李世石与柯洁，是人工智能的优秀结晶。

博弈程序的核心部分是搜索算法的设计与优化^[18]。本毕业设计将以搜索算法为研究对象，包括极大极小算法，负大极值算法，α-β剪枝算法^[1]等。博弈算法在国际象棋^[5]、中国象棋^[3]、黑白棋^[9]的计算机实现中已经有了一定的应用与优化，其中α-β剪枝算法在其算法的应用中占有重要比重。本文将从莫里斯九子棋入手，对几种常用的搜索算法做一个全面的总结，并以α-β剪枝^[15]算法为重点。以现有的算法作为参考，研究α-β剪枝算法^[6]的一些新的应用。

2. 研究的基本内容与方案

基本目标：

以莫里斯九子棋为研究对象，对几种常用的搜索算法做一个全面的总结，并以α-β剪枝算法^[18]为重点。以现有的算法作为参考，研究α-β剪枝算法的一些新的应用。引入强化学习算法改进传统机器博弈算法，提高算法效率与实用性。

内容：

3. 研究计划与安排

4. 参考文献（12篇以上）

[1] donald e. knuth and ronald w. moore. ananalysis of alpha-beta pruning[j]. artificial intelligence, vol. 6, 1975:293-326.

[2] rajeev motwani, prabhakar raghavan. 随机算法[m]. 北京：高等教育出版社,2008.

[3] 岳金朋,冯速. 中国象棋alpha-beta搜索算法[j]. 北京师范大学学报（自然科学版）,2009.45(2):156-160.