摘 要

黑白棋是一个相当易学，而且很受欢迎的游戏。近年来，随着机器性能的提高和相关理论的完善，人工智能这一领域变得越来越重要，在实际生活中的运用也越来越广泛。为了学习简单的人工智能，我决定用Python开发一个简单易用的黑白棋游戏程序。

本系统主要完成人机对战、双人对战、复盘、编辑残局四种游戏模式，具备提示，悔棋，编辑棋盘，播放背景音乐等基本功能。在人机对战中，通过使用alpha-beta剪枝算法和合适的估价函数来实现了一个简单的黑白棋AI。在AI的测试过程中，发现AI与AI对战的结果每次都相同，即AI每次都会以同一种方式输或赢。为了解决这一问题，使用了游戏的历史记录来优化AI的搜索算法，通过历史记录，AI可以改变下棋的策略，从而达到改善AI的目的。

关键字：黑白棋；alpha-beta搜索；电脑AI；历史记录

Abstract

Reversi is a fairly easy to learn and very popular game. In recent years, with the improvement of machine performance and the improvement of related theories, the field of artificial intelligence has become more and more important and its use in real life has become more and more extensive. In order to study simple artificial intelligence, I decided to develop an easy-to-use Reversi program in Python.

This system mainly completes four game modes: man-machine competition, double-player, replay, and editorial game. It has the basic functions of prompting, repenting, editing chessboard, and playing background music. In the man-machine battle, a simple Reversi AI was implemented using an alpha-beta pruning algorithm and a suitable valuation function. During the testing of the AI, it was found that the results of the AI and AI battles were the same each time, that is, the AI lost or won each time in the same way. In order to solve this problem, the history of the game is used to optimize the AI's search algorithm. Through historical records, the AI can change the strategy of playing chess, so as to achieve the purpose of improving the AI.

Key words：Reversi；alpha-beta pruning；computer ai；game log

目录

摘 要 I

Abstract II

目录 1

第1章 绪论 3

1.1 系统开发的背景 3

1.2 国内外发展现状 3

1.3 论文研究的意义 3

1.4 论文的整体结构介绍 4

第2章 系统设计 5

2.1 开发技术的选择 5

2.1.1 开发语言和GUI框架的选择 5

2.1.2 加速Python的运行 5

2.2 功能设计 7

2.2.1 功能模块 8

2.2.2 算法模块 8

第3章 系统实现 9

3.1 四大模式的实现 9

3.1.1 人机对战和双人对战模式 9

3.1.2 编辑棋局模式 11

3.1.3 复盘功能 11

3.2 功能模块的实现 13

3.2.1 保存棋局功能 13

3.2.2 悔棋功能 14

3.2.3 提示功能 15

3.2.4 音乐播放功能 16

3.3 算法模块的实现 17

3.3.1 棋盘的数据结构 17

3.3.2 找到所有合法落子位置的算法 18

3.3.3 翻转棋盘的算法 19

3.3.4 判断胜负算法 19

3.3.5 估价函数的选择 20

3.3.6 Alpha-Beta剪枝算法 24

3.4 AI算法的优化 26

3.4.1 优化的原因 26

3.4.2 优化的方法 26

3.4.3 优化的结果 27

3.4.4 算法实现的细节 27

第4章 黑白棋游戏的测试 28

4.1 悔棋功能的测试 29

4.2 提示功能的测试 30

4.3 复盘模式的测试 31

4.4 编辑棋盘模式的测试 33

第5章 总结与体会 34

参考文献 35

致谢 36

1. 绪论
   1. 系统开发的背景

近年来，随着生活水平的不断提高，人们对游戏的需求也在慢慢地提高。国内虽然象棋、五子棋、围棋等棋类游戏，但是国人对这些游戏都很熟悉，玩起来没有新鲜感。黑白棋是这些游戏的一个很好替代品，其游戏规则简单，用户很容易上手，但是变化繁多，不容易精通。因此我打算开发一个棋力不错的黑白棋AI来提高人们的游戏水平，丰富人们的业余生活。

• 1. 国内外发展现状

黑白棋的AI国外很早就有在研究，其中最厉害的AI之一是Michael Buro的Logistello，他没有将人工调整的策略死硬地写在程序中，而是由程序通过实战的结果来改进策略。因为Logistello在根本方法上的改进、先进的算法、编写方面的高效率和准确性等等，一直在黑白棋界保持为世界程式冠军。

在90年代中期互联网开始普及，冒出了一些大型的黑白棋游戏对战网站。原先黑白棋在国内集中在3个游戏对战平台，分别是中游、联众和边锋。黑白棋的发展实际上是伴随着中国网络的发展。三大平台鼎盛时期也是中国黑白棋的发展的鼎盛时期。在这期间高手辈出，新人不断。现在国内最强的一批高手也是从那个时期成长起来的。如今，随着网络游戏的兴起，这种节奏缓慢的游戏早已退出历史的舞台。

• 1. 论文研究的意义

研究这个课题的意义以下几点：

第一，通过编写一个界面美观，功能完善的黑白棋软件，可以充分地利用大学四年里学到的程序设计与开发相关知识。在整个项目的开发过程中，基本上遵循了软件工程的做法，首先对项目进行了需求分析，明确了软件必备的功能。然后选择了软件开发的技术路线。随后对系统进行了概要设计，即设计了游戏的界面，然后就进入了编码阶段，最后就是测试阶段。经过一系列的阶段，使我对开发复杂系统的流程有了一定的了解。

第二，最近几年来，随着机器学习、人工智能等技术的应用不断扩大，Python也接着这股东风变得越来越流行。使用Python开发此系统，对我以后的学习也有很大的帮助。

第三，因为棋类游戏规则简单，内涵丰富，所以向来是新的人工智能技术试验的温床，通过开发黑白棋的AI，可以让我对人工智能产生初步的认识。

• 1. 论文的整体结构介绍

本课题以黑白棋游戏为主题，叙述其具体的开发过程及所应用到的技术。总结了这款游戏软件开发过程中遇到的问题，软件开发步骤在文中有具体的体现。下面对论文的整体结构进行介绍。

第1章介绍论文的研究背景，讲述了黑白棋发展的历史和国内外黑白棋的发展，对整篇论文的整体结构进行介绍。

第2章从功能设计开始，描述了系统的主要功能模块，并且对各个模块进行了简要的说明。对系统开发环境及相关技术的介绍，介绍了完成开发所应用到的软件技术。

第3章对各个功能模块的实现进行了详细的说明，讨论了算法模块中的搜索算法和估价函数及对AI的优化。

第4章是对黑白棋游戏的测试说明，对黑白棋游戏系统的主要功能进行了黑盒测试。

第5章是总结与体会。对本次毕业设计工作进行总结，回顾开发过程中学到的知识和积累的经验。

1. 系统设计
   1. 开发技术的选择

本次设计的黑白棋游戏采用Python和PyQt 完成整个程序的开发，并且使用Cython来重写了游戏Ai中性能薄弱的模块，改善了Ai的运行效率。运用面向对象的程序设计方法，开发此款黑白棋游戏。

• • 1. 开发语言和GUI框架的选择

Python是一种高级程序设计语言，拥有多种编程范式，有类似于C拥有的命令式编程范式和类似Java的面向对象编程范式，也有函数式编程的特点。在开发本程序的过程中，三种编程范式都有涉及到。开发GUI时利用了面向对象的继承与封装，重写鼠标点击事件是利用的Python的lambda表达式。

本程序之所以选择Python作为开发语言，是因为它具有多种编程范式，语法简洁，开发的效率很高。

Python中科学计算的框架很多，但是GUI框架很少，而且大多数不好用。我使用过的GUI框架有Python自带的tkinter，专门用来开发游戏的Pygame，以及Qt在Python上的移植PyQt。

tkinter的开发资料比较少，而且功能简单，所以不适合用来开发交互负责的游戏界面。

Pygame也比较简陋，很多组件都不支持，例如写一个按钮都需要先画一个方框，然后通过检测用户鼠标的位置来判断按钮是否被点击。

PyQt相比前两个框架更加成熟。PyQt是Qt的Python版本，使用Qt可以开发出跨平台的游戏界面。PyQt主要分为两大模块，分别是“QtCore”和“QtUI”模块。“QtCore”模块主要包含了一些非GUI的基础功能，包含事件循环与Qt的信号机制以及对多线程的支持等。“QtGui”模块包含了大多数的GUI类型。包含按钮、文本框、列表等常见控件，还包含了基于MVC设计模式的列表、表格、树型控件。

使用Qt编写图形界面有两种方式，第一是直接写代码，这种方式比较繁琐，因此在实际开发中很少用到。第二是使用拖控件的方式。

Qt设计器是的可视化UI设计器，它使用拖拉操作来设计图形界面，当窗体很复杂或者整个程序需要大量的窗体时，Qt设计器可以节省大量的代码。不过稍有改变的是，设计好窗体后需要运行pyuic5这个脚本，将窗体文件转换成Python代码。

• • 1. 加速Python的运行

Python是一门很简洁的语言，但这并不代表它很简单，简简单单的一个函数调用转化为c语言是可能变成几十行。

Python的执行效率和性能不够理想，因此有必要进行一定的代码优化来提高程序的执行效率。

一般来说，优化Python程序性能的方法有两种，一是改进算法，二是用Cython或类似的技术改写Python程序中使用频繁的模块。

Python程序运行速度慢的主要原因是Python中的变量时动态类型，及变量的类型只有在运行的时候才能确定，因此确定变量的类型要浪费很多时间。

Cython的优点是所有的Python程序都是合法的Cython程序。因此可以通过对Python程序进行少量的修改来获得巨大的性能提升。缺点是每次修改时都需要重新编译成动态链接库，然后在Python程序中调用。因此修改不方便，而且难以debug。

综上所述，Cython适合用来改写使用频繁并且不需要经常修改的模块。在本程序中，使用Cython改写了棋盘操作的算法，

• 1. 功能设计

通过前期对游戏系统需求的调研，经过分析，确定了系统有双人对战、人机对战、复盘和编辑棋局四个模式。

双人对战模式实现人与人之间的对局，这个模式有悔棋，提示，保存棋局功能。人机对战实现的人与电脑AI的对局，拥有提示，悔棋，保存棋局功能。复盘模式使用户可以选择一局已经保存的棋局来复盘。在编辑棋局模式下，用户可以自定义一个合法的棋局状态，然后和人或AI下棋，类似于象棋的残局。

通过对每个模式的分析，确定程序具有悔棋，提示，保存棋局这三个基本功能，为了丰富用户的游戏体验，给每个模式增加了音乐功能。由上面的分析可知，程序具有悔棋，提示，保存棋局，音乐功能。

功能结构图就是按照功能的从属关系画成的图表，图中的每一个框都称为一个功能模块。功能模块可以根据具体情况分的大一点或小一点，分解得最小功能模块可以是一个程序中的每个处理过程，而较大的功能模块则可能是完成某一个任务的一组程序。根据所游戏功能设计的要求，可以得出黑白棋游戏的功能模块图，如下图所示。

图 2.1 黑白棋游戏的功能模块图

下面根据功能模块图对每个模块实现的功能进行必要的说明。因为上面已经对程序的四大模式进行了详细的说明，所以下面只对功能模块和算法模块进行说明。

• • 1. 功能模块

本模块的主要功能是实现了程序的功能，主要有保存棋局、悔棋、复盘、提示功能。

在游戏过程中，程序会记录棋盘的状态，若用户点击悔棋按钮，程序就会将游戏回退到用户指定的状态。悔棋的次数没有限制，可以回退到任何一个由当前用户下棋的状态。

用户可以将游戏记录保存在指定的文件中，下次游戏的时候可以载入已经保存的棋局。

程序具有提示功能，当用户点击提示按钮时，棋盘的合法落子位置上会出现棋子，用户可以清楚的看到那些位置可以落子。

程序有简单的音乐功能，当用户落子时，程序会发出落子成功的音效。当游戏结束时，会发出结束音乐。当按上下键时可以调整音量，而且还可以切换背景音乐。

• • 1. 算法模块

本模块是整个系统的重点之一，包括棋盘操作，人人对弈、人机对弈中设计到的算法。

本程序使用两个64位整型数表示棋盘，所以需要用位运算来完成对棋盘的操作，本程序使用位运算实现了找到合法的落子位置，翻转棋盘的操作。

人人对弈，实现同一个电脑同一个棋盘上两人轮流下棋功能，不涉及到对弈算法问题，只需根据棋盘形式做出胜负判断即可。

人机对弈，实现同一个棋盘上用户与电脑轮流下棋功能，此模块不但需要根据棋盘状态做出胜负判断，还涉及到AI算法问题。AI算法主要涉及下面两个方面，第一个是估价函数，AI需要根据估价函数计算得到的数值来评估落子位置的好坏，因此估价函数对AI的棋力有很大的影响。另一个是搜索函数，下棋是一个搜索问题，向前搜索得越深，就越容易选择好的落子位置，因此一个高效的搜索算法也很重要。

1. 系统实现
   1. 四大模式的实现
      1. 人机对战和双人对战模式

实现人机和双人对战两种模式的模块主要分为三部分，第一部分是人人对战，第二部分是人机对战，第三部分是输入检测。

输入检测部分，这部分是用来检测用户的要在棋盘的那个位置下棋，并判断位置是否合法。实现方式是重写棋盘界面的鼠标点击事件。当鼠标点击棋盘界面时，得到鼠标指针的位置，再减去边框的长度，转化成棋盘坐标。

图 3.1 输入检测流程图

人人对战功能需要在完成输入检测后，检查是黑棋或白棋下棋，然后翻转棋盘并刷新棋盘界面。

人机对战功能相比人人对战更加复杂，因为AI可以自发地下棋，即当鼠标没有被点击的时候，AI也能够下棋，而且对鼠标点击事件的响应也与人人对战有所不同。具体实现方法是设置timer，当timer的时间到了的时候判断是否轮到AI下棋，若是则调用AI算法。

图 3.2 人机对战流程图

由于我将timer的周期设置我了1000ms，ai算法每隔1000ms都会启动一次，当搜索空间比较大，算法花费的时间会比较长，如果超过一分钟，就会产生多个ai算法同时执行的情况。为了避免这种情况，我设置了Thinking状态，当一个ai算法开始执行时，将Thinking状态置为True，其他的ai算法在执行时首先检查Thinking状态，若为True则说明已经有一个ai正在执行，然后直接退出。通过设置Thinking状态可以有效的避免多个ai算法同时执行。

• • 1. 编辑棋局模式

用户可以自定义棋局，这和象棋里面编辑残局的功能类似，用户把棋局编辑成自己想要的局面，然后和其他玩家或者AI对战。用户想要在某个位置放置棋子时，先要将鼠标移到对应的位置上，然后按下w键放置白棋，b键放置黑棋。实现的方式是重写编辑界面的按键点击事件，当用户点击w或b按键时，先获取到用户的鼠标位置，将位置转换为棋盘坐标，然后在棋盘上放置指定颜色的棋子。当用户要退出时，可以按1或2键保存退出，1代表黑棋先下，2代表白棋先下。如果用户要保存的局面不合法，比如棋盘上只有一种棋，就会发出错误提示音提醒用户。

图 3.3 编辑棋局界面

• • 1. 复盘功能

复盘就是将已经下过的棋局重复一遍。因为当游戏过程结束时，查询会自动保存棋局的历史记录，当用户点击复盘按钮时，可以从已经下过的棋局里面选择一个棋局作为数据来源来复盘，用户可以使用“上一步”，“下一步”两个按钮来控制棋局的状态。

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：