摘 要

人工智能研究模拟人类智能的理论方法及其应用的一门技术科学。计算机博弈作为人工智能中的一个重要的课题，体现了人工智能的发展水平。目前，棋类AI不断出现在公众的视野之中。比如象棋方面，在1997年，IBM的“深蓝”战胜了卡斯帕罗夫。在围棋方面，在2016年,谷歌的人工智“AlphaGo”以4:1战胜了李世石。棋类AI的不断进步让我们看到了人工智能的飞速发展。不过，虽然国际上对于象棋和围棋AI的研究都非常的深入，但是在五子棋AI的研究和应用方面一直处于相对落后的局面，至今并没有出现五子棋AI战胜人类顶尖五子棋大师的对局。

论文主要研究了人工智能的经典算法及其实现，包括极大极小博弈树算法、Alpha-Beta剪枝算法等。并研究其在人机对战五子棋中的运用，结合Android平台开发的相关知识，成功地设计并实现了一个Android平台上的五子棋的人工智能。

在功能上实现了玩家可以在有禁手和无禁手两种规则下与AI对弈，并且可以由玩家通过控制博弈树的最大搜索深度来调整对弈AI的棋力强弱，从而让不同段位的五子棋棋手都可以通过和该软件的AI进行对弈来满足训练与提高的目的。全文围绕“AI算法在人机对战五子棋中的运用研究”的课题，遵循软件开发的基本流程，在使用Java语言编码实现的过程中详细介绍了经典的人工智能算法。

关键词: Android Java 五子棋 人工智能算法

ABSTRACT

Artificial intelligence is a study of human intelligence theory and application of a technical science. Computer game as an important topic in artificial intelligence, embodies the level of development of artificial intelligence. At present, chess class AI constantly appear in the public view. Such as chess, in 1997, IBM's "dark blue" beat Kasparov. In Go, in 2016, Google's Artificial Intelligence "AlphaGo" to 4: 1 victory over Li Shishi. Chess class AI's continuous progress so that we see the rapid development of artificial intelligence. Although the international community for the study of chess and Go AI are very in-depth, But in the Gobang AI research and application has been in a relatively backward situation, so far there is no backgammon AI beat the top of the world backgammon game.

This paper mainly studies the classical algorithm of artificial intelligence and its implementation, including the Minimax game tree algorithm and Alpha-Beta pruning algorithm. And to study its use in man-machine battle backgammon, combined with the development of Android platform related knowledge, successfully designed and implemented an Android platform on the backgammon artificial intelligence. In the function , the players can chess with AI in two rules of banning hand and no banning hand. And the ability to adjust the ability of AI is controlled by the player by controlling the maximum search depth of the game tree, So that different sections of the backgammon players can be play with the AI to match the purpose of the training and improving. In this paper, the classical AI algorithm is introduced in detail in the process of using Java language coding to follow the basic process of software development, which is based on the research of "AI algorithm in man-machine game".

Key Words：Android；Java；Gobang；Artificial intelligence algorithm;

目 录

第1章 绪论 1

1.1 论文的背景和意义 1

1.2 国内外研究现状 1

1.3 论文研究内容 2

1.4 论文章节组织 2

第2章 系统设计与实现 4

2.1 系统关键技术介绍 4

2.1.1 Android平台 4

2.1.2 人工智能算法 4

2.2 系统设计 5

2.2.1 系统功能设计 5

2.2.2 系统流程 5

2.3 系统实现 7

2.3.1 游戏界面实现 7

2.3.2 落子与悔棋数据更新实现 8

2.3.3 胜负判断模块实现 8

2.3.4 禁手判定模块实现 9

第3章 算法分析与实现 11

3.1 局面评估模块实现 11

3.2 极大极小博弈树算法与实现 12

3.2.1 极大极小博弈树算法 12

3.2.2 极大极小博弈树具体实现 13

3.3 Alpha-Beta剪枝算法与实现 16

3.3.1 Alpha-Beta剪枝算法 16

3.3.2 Alpha-Beta剪枝算法具体实现 16

第4章 运行与测试 19

4.1 界面初始化模块测试 19

4.2 胜负判定模块测试 19

4.3 棋型评估模块测试 19

4.4 禁手判定模块测试 20

第5章 总结与展望 21

5.1 总结 21

5.2 展望 21

参考文献 22

致 谢 23

第1章绪论

1.1论文的背景和意义

人工智能（AI）是研究如何让计算机拥有类似人的智能^[1]。人工智能最早可以追溯到三千多年前形式逻辑的诞生，不过它真正被作为“Artificial Intelligence”一词提出是在1956年的达特茅斯会议上，当时与会的包括后来被称为“人工智能之父”的麦卡锡、香农等一批知名科学家，其中还有神经网络的鼻祖之一皮茨、编写了第一个真正的AI程序的科学家塞弗里奇等，在会上“Artificial Intelligence”击败了包括“machine Intelligence”等词汇最终成为这一学科的名称^[2]。世界上第一个可以聊天的机器人是在1964年出现的，它的名字叫ELIZA，实现了人与机器的交流。

五子棋是起源于上古中国的黑白棋种，相传在尧帝创造围棋之前，民间人士就已经创造出来了五子棋，因为古代的五子棋和围棋的棋子和棋盘都是完全一样的，所以上古时代的五子棋盘是17×17的，和上古围棋棋盘一致^[3]。《山海经》中就记载了黑白棋子的制作方法。根据史料记载，中国的五子棋先是传到高丽，后在17世纪传入日本，经过数百年的发展，在19世纪末期形成了现代的五子棋比赛规则，也就是禁手规则。禁手规则包含三三禁手、四四禁手、三三四禁手、四四三禁手和长连禁手，是为了限制五子棋先手的巨大优势而出现的。因为经过多年的摸索研究，五子棋的职业棋手们探索出来了一系列先手必胜的棋路，所以加入了这些禁手规则用来限制黑棋的某些棋型的出现^[4]。后来在20世纪，又有棋手研究出了禁手规则下的先手必胜棋路，于是规则再度修改，出现了被称为“三手交换，五手两打”的规则，同样是限制五子棋先手特定棋型的出现，这些对于五子棋规则的完善不仅体现了人类对于五子棋的热爱，更体现了人类在博弈领域的进步。