| 【中文题名】 | 六子棋计算机博弈及其系统的研究与实现 |
| 【英文题名】 | Research and Realization of the Computer Game and System of Connect6 |
| 【学科专业】 | 模式识别与智能系统 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-10-25 |
| 【中关键词】 | 六子棋计算机博弈,博弈树,评估函数,锦标赛算法,遗传算法, |
| 【英关键词】 | Computer Game Of Connect6,Game Tree,Evaluation Function,Tournament Algorithm,Genetic Algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
计算机博弈是人工智能领域一个极其重要且最具挑战性的研究方向之一,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响以及大量的研究成果。在过去的半个世纪里,世界各地的学者花费了大量的心血对于计算机博弈包括奥赛罗、checker、国际象棋、中国象棋、五子棋、围棋进行研究。这是因为计算机博弈是人工智能的一块试金石,然而棋类游戏又是计算机博弈的一个标准性问题,各种搜索算法、模式识别及智能方法在计算机博弈中都可以得到广泛的应用。在长时间的研究中,涌现出大量令人震惊的成果,1997年“深蓝”战胜卡斯帕罗夫的比赛就在全世界范围内引发了震动。其他很多棋类的计算机水平都已达到了世界冠军的水平。
目前,对于像五子棋、中国象棋等棋类游戏的计算机博弈算法研究已相对成熟,六子棋作为一个刚刚兴起不久的棋类游戏,其计算机博弈算法的研究还相对较少。即使目前已经出现六子棋的论坛以及比赛的平台,但只限于人人对弈。真正对于六子棋计算机博弈算法以及系统的研究还不多。六子棋的发明者台湾吴毅成教授给出了六子棋的公平性问题以及基于迫著(Threats)的胜利策略,但是对于其计算机博弈问题没有给出更加深刻的阐述,... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
ABSTRACT |
4-11 |
|
1 绪论 |
11-19 |
|
1.1 引言 |
11 |
|
1.2 六子棋计算机博弈的研究意义 |
11-13 |
|
1.3 六子棋计算机博弈在国内外的研究现状 |
13-16 |
|
1.3.1 计算机博弈研究简史 |
13-14 |
|
1.3.2 六子棋计算机博弈的研究现状 |
14-16 |
|
1.4 六子棋计算机博弈的核心问题 |
16-17 |
|
1.4.1 搜索算法 |
16 |
|
1.4.2 评估函数 |
16-17 |
|
1.5 六子棋计算机博弈系统的评价方法 |
17 |
|
1.6 课题的提出和研究意义 |
17 |
|
1.6.1 课题的提出 |
17 |
|
1.6.2 研究的意义 |
17 |
|
1.7 本文的主要研究内容 |
17-19 |
|
2 六子棋平台介绍 |
19-29 |
|
2.1 背景 |
19 |
|
2.2 规则 |
19-20 |
|
2.3 公平性问题 |
20-22 |
|
2.3.1 五子棋的公平性问题 |
20 |
|
2.3.2 公平的定义 |
20-21 |
|
2.3.3 脱离战场 |
21 |
|
2.3.4 六子棋的公平性问题 |
21-22 |
|
2.4 复杂度 |
22 |
|
2.5 六子棋定石 |
22-26 |
|
2.6 六子棋诘棋 |
26 |
|
2.7 六子棋发展动向 |
26-27 |
|
2.7.1 台湾六子棋协会 |
26 |
|
2.7.2 第十一届奥林匹亚计算机赛局竞赛中六子棋比赛之结果 |
26-27 |
|
2.8 本章小结 |
27-29 |
|
3 棋类设计的通用方法和思想——计算机博弈 |
29-43 |
|
3.1 计算机博弈的要点 |
29 |
|
3.2 计算机博弈程序的组成 |
29-41 |
|
3.2.1 人机界面 |
29 |
|
3.2.2 棋盘和棋局表示－数据结构 |
29-31 |
|
3.2.3 着法生成 |
31-32 |
|
3.2.4 机器博弈、搜索技术 |
32-37 |
|
3.2.5 评估函数 |
37-41 |
|
3.3 本章小结 |
41-43 |
|
4 六子棋计算机博弈系统的平台构建 |
43-51 |
|
4.1 引言 |
43 |
|
4.2 棋盘状态空间表示 |
43-45 |
|
4.2.1 棋盘局势状态表示 |
43-44 |
|
4.2.2 落子的顺序表示 |
44-45 |
|
4.3 六子棋计算机博弈问题描述 |
45 |
|
4.4 搜索引擎 |
45-47 |
|
4.4.1 α-β剪枝搜索算法 |
46-47 |
|
4.4.2 启发式信息 |
47 |
|
4.5 走法生成 |
47-50 |
|
4.6 本章小结 |
50-51 |
|
5 基于遗传算法的六子棋计算机博弈系统的评估函数 |
51-77 |
|
5.1 引言 |
51 |
|
5.2 六子棋的常见棋型及其状态演变的形式化描述 |
51-58 |
|
5.2.1 六子棋的棋型 |
51-57 |
|
5.2.2 六子棋各棋型间的状态演变 |
57-58 |
|
5.3 六子棋评估函数的确定 |
58-62 |
|
5.4 遗传算法 |
62-64 |
|
5.5 遗传算法和六子棋评估函数的对应关系及计算机表示 |
64-65 |
|
5.6 适应度函数的计算——锦标赛算法 |
65-66 |
|
5.7 遗传操作过程 |
66-75 |
|
5.7.1 锦标赛选择 |
66-69 |
|
5.7.2 均匀交叉 |
69-71 |
|
5.7.3 变异 |
71-75 |
|
5.8 改进的遗传算法——自适应遗传算法 |
75-76 |
|
5.9 本章小结 |
76-77 |
|
6 开局库设计 |
77-79 |
|
6.1 引言 |
77 |
|
6.2 开局库的设计 |
77-78 |
|
6.3 本章小结 |
78-79 |
|
7 系统评价指标 |
79-81 |
|
7.1 评估函数准确度的评价指标 |
79 |
|
7.2 搜索算法效率的评价指标 |
79 |
|
7.3 系统整体性能的评价指标 |
79-80 |
|
7.4 本章小结 |
80-81 |
|
8 结论与展望 |
81-83 |
|
8.1 研究工作小结 |
81-82 |
|
8.2 本系统目前存在的问题和不足 |
82 |
|
8.3 后续工作 |
82 |
|
8.4 结语 |
82-83 |
|
致谢 |
83-84 |
|
参考文献 |
84-87 |
|
附录 |
87 |
|
A 作者在攻读硕士学位期间科研工作目录 |
87 |
|
B 作者在攻读硕士学位期间发表论文目录 |
87 |
|
| 【DOI】 | LunWen.ID:2.2008.389116 |
