六子棋计算机博弈及其系统的研究与实现

发布时间：2021-04-19 09:58

计算机博弈是人工智能领域一个极其重要且最具挑战性的研究方向之一,它的研究为人工智能带来了很多重要的方法和理论,产生了广泛的社会影响和学术影响以及大量的研究成果。在过去的半个世纪里,世界各地的学者花费了大量的心血对于计算机博弈包括奥赛罗、checker、国际象棋、中国象棋、五子棋、围棋进行研究。这是因为计算机博弈是人工智能的一块试金石,然而棋类游戏又是计算机博弈的一个标准性问题,各种搜索算法、模式识别及智能方法在计算机博弈中都可以得到广泛的应用。在长时间的研究中,涌现出大量令人震惊的成果,1997年“深蓝”战胜卡斯帕罗夫的比赛就在全世界范围内引发了震动。其他很多棋类的计算机水平都已达到了世界冠军的水平。目前,对于像五子棋、中国象棋等棋类游戏的计算机博弈算法研究已相对成熟,六子棋作为一个刚刚兴起不久的棋类游戏,其计算机博弈算法的研究还相对较少。即使目前已经出现六子棋的论坛以及比赛的平台,但只限于人人对弈。真正对于六子棋计算机博弈算法以及系统的研究还不多。六子棋的发明者台湾吴毅成教授给出了六子棋的公平性问题以及基于迫著(Threats)的胜利策略,但是对于其计算机博弈问题没有给出更加深刻的阐述,同时也没有全面解决六子棋计算机博弈问题。本文正是对六子棋计算机博弈技术的一个探索。本文中提出的六子棋计算机博弈系统可以分为四个主要部分:搜索引擎、走法生成、评估函数和开局库。搜索引擎模块包含了比较成熟的搜索算法,以及对他们的结合和优化;走法生成模块是对搜索的结果进行比较处理,确定当前的走法;评估函数模块中本文根据棋型特征构建了着子棋力的评估函数并提出用遗传算法来做评估函数参数的调整与优化的方法;开局库存储了大量的专家棋谱,可以避免在开局时由于搜索深度的不足而带来战略上的失误,同时大大提高了对战的效率。最后本文对六子棋计算机博弈系统进行了测试与评价,包括评估函数的准确度、搜索算法的效率以及系统的整体性能。
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2007
【分类号】：TP18;TP311.52

文章目录

摘要

ABSTRACT

1 绪论

1.1 引言

1.2 六子棋计算机博弈的研究意义

1.3 六子棋计算机博弈在国内外的研究现状

1.3.1 计算机博弈研究简史

1.3.2 六子棋计算机博弈的研究现状

1.4 六子棋计算机博弈的核心问题

1.4.1 搜索算法

1.4.2 评估函数

1.5 六子棋计算机博弈系统的评价方法

1.6 课题的提出和研究意义

1.6.1 课题的提出

1.6.2 研究的意义

1.7 本文的主要研究内容

2 六子棋平台介绍

2.1 背景

2.2 规则

2.3 公平性问题

2.3.1 五子棋的公平性问题

2.3.2 公平的定义

2.3.3 脱离战场

2.3.4 六子棋的公平性问题

2.4 复杂度

2.5 六子棋定石

2.6 六子棋诘棋

2.7 六子棋发展动向

2.7.1 台湾六子棋协会

2.7.2 第十一届奥林匹亚计算机赛局竞赛中六子棋比赛之结果

2.8 本章小结

3 棋类设计的通用方法和思想——计算机博弈

3.1 计算机博弈的要点

3.2 计算机博弈程序的组成

3.2.1 人机界面

3.2.2 棋盘和棋局表示－数据结构

3.2.3 着法生成

3.2.4 机器博弈、搜索技术

3.2.5 评估函数

3.3 本章小结

4 六子棋计算机博弈系统的平台构建

4.1 引言

4.2 棋盘状态空间表示

4.2.1 棋盘局势状态表示

4.2.2 落子的顺序表示

4.3 六子棋计算机博弈问题描述

4.4 搜索引擎

4.4.1 α-β剪枝搜索算法

4.4.2 启发式信息

4.5 走法生成

4.6 本章小结

5 基于遗传算法的六子棋计算机博弈系统的评估函数

5.1 引言

5.2 六子棋的常见棋型及其状态演变的形式化描述

5.2.1 六子棋的棋型

5.2.2 六子棋各棋型间的状态演变

5.3 六子棋评估函数的确定

5.4 遗传算法

5.5 遗传算法和六子棋评估函数的对应关系及计算机表示

5.6 适应度函数的计算——锦标赛算法

5.7 遗传操作过程

5.7.1 锦标赛选择

5.7.2 均匀交叉

5.7.3 变异

5.8 改进的遗传算法——自适应遗传算法

5.9 本章小结

6 开局库设计

6.1 引言

6.2 开局库的设计

6.3 本章小结

7 系统评价指标

7.1 评估函数准确度的评价指标

7.2 搜索算法效率的评价指标

7.3 系统整体性能的评价指标

7.4 本章小结

8 结论与展望

8.1 研究工作小结

8.2 本系统目前存在的问题和不足

8.3 后续工作

8.4 结语

致谢

参考文献

附录

A 作者在攻读硕士学位期间科研工作目录

B 作者在攻读硕士学位期间发表论文目录

【引证文献】