基本信息
- 项目名称：
- 棋类机器博弈系统研究与关键技术优化
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 信息技术
- 大类：
- 自然科学类学术论文
- 简介：
- 机器博弈是人工智能的一个传统研究课题。本文以六子棋，亚马逊棋，手机平台和自动对弈测试平台四个方面来论述一个机器博弈系统的构成。 六子棋在知识表示上采用棋局的动态更新，并在搜索算法中加入空着剪枝；亚马逊棋采用了蒙特卡洛搜索算法，并融合α-β算法，使估值更容易；自动对弈平台实现了程序的自动对弈，节约了测试时间；手机程序完成了跨平台移植，实现了博弈系统在手机平台的运行，也证明了程序和算法的优越性。
- 详细介绍：
- 机器博弈是人工智能的一个传统研究课题，其中，搜索算法和估值函数是难点。本文以六子棋，亚马逊棋，手机平台和自动对弈测试平台四个方面来论述一个机器博弈系统的构成。 1）六子棋方面，知识表示应用了棋局动态更新，逐步推进的方法，对局面进行动态存储，达到了简化局面估值复杂的目的；在基于α-β的NegaScout搜索算法中加入空着剪枝，保证了搜索效率；在某些节点选择性地采用单迫着和双迫着策略，提高了程序的估值效果和胜率。 2）亚马逊棋方面，采用了蒙特卡洛搜索算法，并融合传统的α-β算法，实现了基于不同约束条件的选择性着法生成；通过估值函数选取部分节点来进行模拟，再从中选取估值最高的着法，这样既增加了模拟的可靠性也减少了对估值的依赖。 3）自动对弈平台方面，为了更好的测试和验证程序，开发了这个平台，能够实现程序的自动对弈，节约了测试时间，同时使棋类博弈系统更加完善。 4）手机程序方面，完成了Windows平台下的程序向Android (Linux)平台下移植，实现了博弈系统在手机平台的运行，同时也证明了程序和算法的优越性。 在2010年中国机器博弈锦标赛中，基于上述思想的六子棋、亚马逊棋程序和手机程序都取得了良好的成绩，说明了本文研究工作的正确性、有效性和实用性。
作品图片
作品专业信息
撰写目的和基本思路
- 本文旨在棋类机器博弈系统的研究和关键技术的优化，以六子棋和亚马逊棋作为切入点，对机器博弈问题中的搜索算法和估值函数等问题进行探究，实现了自动对弈测试平台，并实现了程序向手机平台的移植。
科学性、先进性及独特之处
- 本文是设计和实现了计算机博弈程序，并在关键技术上进行优化：1）六子棋知识表示采用动态局面存储，简化估值函数，结合单迫着和双迫着处理残局；2）亚马逊棋采用蒙特卡洛搜索算法和α-β搜索算法的结合，加入了具有动态约束条件的着法生成，降低了对估值的依赖；3）完成了程序的自动对弈测试，减少人工参与，缩短了测试周期；4）实现了六子棋程序向手机平台的移植，并能够高效运行。
应用价值和现实意义
- 本文总结了在实践操作中一些经验和体会，分析了某些关键技术，并提出了优化的方法，增加了自动对弈测试功能，对机器博弈系统进行了很好的补充；并将六子棋程序移植到手机上，关注手机开发，在流行的手机平台上开发复杂的棋牌类游戏进行了探索，将理论研究与实践应用有机地结合。
学术论文摘要
- 机器博弈是人工智能的一个传统研究课题。本文以六子棋，亚马逊棋，手机平台和自动对弈测试平台四个方面来论述一个机器博弈系统的构成。 1）六子棋方面，知识表示应用了棋局动态更新，对局面进行动态存储，达到了简化局面估值复杂的目的；在基于α-β的NegaScout搜索算法中加入空着剪枝，保证了搜索效率；在某些节点选择性地采用单迫着和双迫着策略，提高了程序的估值效果和胜率。2）亚马逊棋方面，采用了蒙特卡洛搜索算法，并融合传统的α-β算法，实现了基于不同约束条件的选择性着法生成；通过估值函数选取部分节点来进行模拟，这样既增加了模拟的可靠性也减少了对估值的依赖。3）自动对弈平台方面，为了更好的测试和验证程序而开发，能够实现程序的自动对弈，节约了测试时间，同时使棋类博弈系统更加完善。4）手机程序方面，完成了Windows平台下的程序向Android (Linux)平台下移植，实现了博弈系统在手机平台的运行，同时也证明了程序和算法的优越性。 在2010年中国机器博弈锦标赛中，基于上述思想的六子棋、亚马逊棋程序和手机程序都取得了良好的成绩，说明了本文研究工作的正确性、有效性和实用性。
获奖情况
- 在2010年第四届中国机器博弈锦标赛中，获得以下奖项： 1）“东秦之星”六子棋程序获得了二等奖； 2）“六子灵童”六子棋手机程序获得了三等奖； 3）“东秦之星”亚马逊棋程序获得了二等奖。
鉴定结果
- 奖项属实
参考文献
- [1]Allis L V, Herik H.J van den, Huntjens M P H. Go-Moku Solved by New Search Techniques [J]. Journal of Computational Intelligence, 1995, 12(1): 7-24 [2]Wágner J, Virag I. Solving Renju [J]. ICGA Journal, 2001, 24(1): 30-34. [3]Hsieh Ming Yu, Tsai Shi-Chun, On the Fairness and Complexity of Generalized k-in-a-row Games [J]. Theoretical Computer Science, 2007, 385(1-3): 88-100. [4]李果, 六子棋计算机博弈及其系统的研究与实现[D], 重庆, 重庆大学, 2007. [5]Beal D F. Experiments with the null move [J]. In Advances in Computer Cehss 5. Elsevier Science. 1989: 65-79. [6]Beal D. Null Moves [J]. Advances in Computer Chess 5, 1987. [7]Tabibi O. D, Netanyahu N. S. Verified Null-Move Pruning {D, 2002 #155}[J]. ICGA Journal, 2002, 25(3): 153–161. [8]Schaseffer J. Experiments in Search and Knowledge [D]. Ph.D. Dissertation, University of Waterloo, 1986. [9]Chen B. N, Liu P. F, Hsu S. C, Hsu T. S. Hsu. Knowledge Inferencing on Chinese Chess Endgames [C]. Computers and Games 2008, LNCS 5131, 2008: 180-191.
同类课题研究水平概述
- 机器博弈的研究广泛而深入。早在上世纪五十年代，就有人设想利用机器智能来实现机器与人的对弈。国内外许多知名学者和知名科研机构都曾经涉足这方面的研究，历经半个多世纪，到目前为止已经取得了许多惊人的成就。如， 1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，使IBM的股票市值飙升了上百亿美元，引发了广泛而深远的影响。 2007年，由《Science》杂志评选的十大科技突破中，就包括了加拿大阿尔波特大学的科研成果——解决了西洋跳棋“博弈问题”也就是说，在西洋跳棋的博弈中计算机将永远“立于不败之地”。 虽然，机器博弈的研究取得了一些出乎意料的成果，但在“它的研究是否能揭示人类智能本质这个问题上”仍然争论不断。本文的工作从实践的角度出发，以设计和实现能够与人类大师水平相媲美的计算机程序为目标，避免探讨哲学、认知科学相关的话题。机器博弈研究的先驱者已经积累下来不少先进的算法，本文正是沿着先驱者的脚步，进行实践，提出问题，发现问题，并尝试去解决问题。 六子棋是从2005年才被提出的，因为六子棋比五子棋复杂的多，但目前六子棋的研究成果还借鉴五子棋，这是需要突破的。本文设计和实现了一个六子棋程序，旨在进一步研究六子棋问题，并寻求更优秀的解决方案，同时也在六子棋的知识表示方面做了一些新的尝试。 亚马逊棋是一种分支因子很大的棋类。国际象棋程序主要用确定性的搜索算法，如alpha-beta搜索进行求解，而大分支因子的程序用alpha-beta的效果一般比较差。在亚马逊棋中，基于选择性的搜索方法要稍好些，比如UCT，本文对两种方法都进行了尝试。 手机功能的开发已经受到广泛关注，由于其性能不断提升，使得拥有复杂算法的程序移植到手机平台成为可能。鉴于手机本身的方便性，在手机上玩棋牌游戏无疑将会受到棋迷们的欢迎。因此，本文将研究内容与流行技术进行有机结合，把“东秦之星”六子棋程序移植到了手机上，并成功地参加了2010年全国竞赛，受到了参赛者的关注。
