五子棋游戏软件设计

目 录 摘要 2 1 引 言 3 1.1 问题的提出 .3 1.2 国内外研究的现状 3 1.3 人工智能 .4 1.3.1 五子棋数学思想 4 1.3.2 五子棋人工智能 5 1.4 任务与分析 .5 2.总体设计方案 7 2.1 算法设计 7 2.1.1 总体框架图 7 2.1.2 五子棋胜负判断算法 8 2.1.2 五子棋人工智能算法 8 3 程序运行平台 11 1开发环境 11 2运行环境 11 4.模块分析 12 4.1 主界面模块 12 4.2 棋盘的设计模块 13 4.3 棋盘的鼠标事件操作模块 14 4.4 五子棋棋子设计模块 15 4.5 五子棋的胜负判断模块 15 4.6 五子棋的人工智能模块 17 5.系统测试 21 6.结论 25 致谢 26 参考文献 27 摘要 近来，随着计算机的快速发展，以 计算机作为对战平台，各种棋类游戏如雨 后春笋般纷纷冒出，使得那些喜爱下棋，有常常苦于没有对手的棋迷们能随时过 足棋瘾，而且这类软件个个水平颇高，大有与人 脑分庭抗礼之势。其中 战胜过国 际象棋世界冠军卡斯帕罗夫的“深蓝” 便是最具说 服力的代表。当我们与电脑对 战对时，您知道这些软件是怎 样像人脑一样进行思考的吗？总的来说（我们假定 您熟悉五子棋的基本规则），要让电脑知道该在哪一点下子，就要根据盘面的形 式，为每一可能落子点计算其重要程度，也就是当这 子落下后会形成什么模型， 然后通览全盘选出最重要的一点，这便是最基本的算法。当然， 仅靠当前盘面进 行判断是远远不够的，这样 下棋很容易掉进玩家设下的陷阱，因为它没有考虑以 后的变化。所以在此基础上我 们需要使用好的算法是电脑能预测出今后几步的 各种走法，以便做出最佳选择 ，这也是我们下棋时常 说的“ 想了几步”。怎样才能 达到这个程度呢？这是本文所要讨论的主要问题。作为一个五子棋游戏爱好者， 在使用了众多的五子棋游戏软件后，发现当今大多数五子棋游戏软件中电脑的 AI（人工智能） 值不是很高， 难与人脑抗衡， 这是基于以上的最基本算法扩展而出 的电脑最优落子算法不够优秀而造成的。本人使用 JAVA 语言作为开发工具，在 吸收别人所编的五子棋游戏软件的基础上，再融入自己的创新思想（最优落子算 法的改进），编写了这个五子棋游戏， 软件实现了人机 对弈和双人对弈的功能，游 戏软件界面美观，操作容易，电脑的 AI 值也较高。 关键字：五子棋、人工智能、JAVA 3 五子棋游戏软件设计 1 引 言 1.1 问题的提出 五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑 白棋种之一。发展于日本，流行于欧美。容易上手，老少皆宜，而且趣味横生， 引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。 五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五 子棋既有现代休闲的明显特征“短、平、快” ，又有古典哲学的高深学问“阴阳 易理” ；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高 水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既 有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的 结晶。 1.2 国内外研究的现状 近来，随着计算机的快速发展，以计算机作为对战平台，各种棋类游戏如 雨后春笋般纷纷冒出，使得那些喜爱下棋，有常常苦于没有对手的棋迷们能随 时过足棋瘾，而且这类软件个个水平颇高，大有与人脑分庭抗礼之势。其中战 胜过国际象棋世界冠军卡斯帕罗夫的“深蓝”便是最具说服力的代表。当我 们与电脑对战对时，您知道这些软件是怎样像人脑一样进行思考的吗？总的来 说（我们假定您熟悉五子棋的基本规则） ，要让电脑知道该在哪一点下子，就要 根据盘面的形式，为每一可能落子点计算其重要程度，也就是当这子落下后会 形成什么模型，然后通览全盘选出最重要的一点，这便是最基本的算法。当然， 仅靠当前盘面进行判断是远远不够的，这样下棋很容易掉进玩家设下的陷阱， 因为它没有考虑以后的变化。所以在此基础上我们需要使用好的算法是电脑能 预测出今后几步的各种走法，以便做出最佳选择，这也是我们下棋时常说的 “想了几步” 。怎样才能达到这个程度呢？这是本文所要讨论的主要问题。作为 一个五子棋游戏爱好者，在使用了众多的五子棋游戏软件后，发现当今大多数 五子棋游戏软件中电脑的 AI（人工智能）值不是很高，难与人脑抗衡，这是基 于以上的最基本算法扩展而出的电脑最优落子算法不够优秀而造成的。本人使 用 JAVA 语言作为开发工具，在吸收别人所编的五子棋游戏软件的基础上，再 融入自己的创新思想（最优落子算法的改进） ，编写了这个五子棋游戏，软件实 现了人机对弈和双人对弈的功能，游戏软件界面美观，操作容易，电脑的 AI 值 也较高。 1.3 人工智能 1.3.1 五子棋数学思想 可能很少有人注意到，五子连珠游戏其中包含着一个极为深刻的数学问题。 为什么不是四子连珠，或者是六子连珠？你可能会说，四子连珠，那就太容易 啦，下几步就胜了。而六子连珠呢，则太难了，谁也别想连成。这就说明，五 子连珠极可能是一个最佳攻守平衡值，一个达成连珠的最大值。增一子、减一 子都会打破这个平衡。四子连珠太易，攻方处于绝对优势；而六子连珠太难， 守方处于绝对优势。而游戏规则必须是让游戏双方处于平等的位置才可能进行， 否则游戏就不成其为游戏。要想黑白棋连珠成为一种符合游戏规则的智力游戏， 五子连珠无疑是一个最佳方案。中华民族的祖先在发明五子连珠的过程中，猜 想肯定也不是一蹴而就，而是极可能经历了四子连珠、六子连珠的尝试过程， 最后才确定为五子连珠，并流行开来。 这个问题，被当代科普作家傅小松称之为五子连珠问题，又称五子连珠猜 想。其准确表述是：在以横线、竖线互相交叉（一般各为 15 条）的方形平面 （棋盘）中，黑白两种“点”(棋子)先后沿横线、竖线排列（行棋） ，在平面 （棋盘）横线、竖线、斜线（无实线连接）上形成连续的同色“点” （棋子） ， 五个“点” （棋子）为可能达成连珠的最大值。五子连珠是黑白棋连珠的一个最 佳方案，这在实际中早已不会有人怀疑。并且，五子连珠已经存在并发展了几 千年，成为了一种趣味性强，同时技巧比较复杂、竞争激烈的棋类游戏，与围 棋、国际象棋、中国象棋的巧妙性、复杂性也有一拼。这似乎足以证明五子连 珠的最佳性。但从科学真理的角度看，一万次实践的证明也不能代替逻辑和数 学上的证明。要确定五子连珠是黑白棋连珠的一个最佳方案，五子连珠是一个 最佳值、最大值，必须进行数学上的证明。 “五子连珠问题”的证明可能非常复 杂，这是因为，第一，它不是一个静态的问题，而是一个动态的问题。棋盘是 5 五子棋游戏软件设计 一个静态的二维平面，但行棋博弈是一个的动态的过程。第二，这不是一个线 性和确定性问题的，而是一个非线性和模糊性问题。所谓“五子连珠”的最佳 值，是在千变万化的攻与防中达到的一种默契。因此，要解决“五子连珠猜想” ， 可能要运用到博弈论、模糊数学等工具。 1.3.2 五子棋人工智能 人工智能（Artificial Intelligence，简称 AI）是计算机学科的一个分支，二 十世纪七十年代以来被称为世界三大尖端技术之一（空间技术、能源技术、人 工智能） 。也被认为是二十一世纪（基因工程、纳米科学、人工智能）三大尖端 技术之一。这是因为近三十年来它获得了迅速的发展，在很多学科领域都获得 了广泛应用，并取得了丰硕的成果，人工智能已逐步成为一个独立的分支，无 论在理论和实践上都已自成一个系统。人工智能是研究使计算机来模拟人的某 些思维过程和智能行为（如学习、推理、思考、规划等）的学科，主要包括计 算机实现智能的原理、制造类似于人脑智能的计算机，使计算机能实现更高层 次的应用。人工智能将涉及到计算机科学、心理学、哲学和语言学等学科。可 以说几乎是自然科学和社会科学的所有学科，其范围已远远超出了计算机科学 的范畴，人工智能与思维科学的关系是实践和理论的关系，人工智能是处于思 维科学的技术应用层次，是它的一个应用分支。从思维观点看，人工智能不仅 限于逻辑思维，要考虑形象思维、灵感思维才能促进人工智能的突破性的发展， 数学常被认为是多种学科的基础科学，数学也进入语言、思维领域，人工智能 学科也必须借用数学工具，数学不仅在标准逻辑、模糊数学等范围发挥作用， 数学进入人工智能学科，它们将互相促进而更快地发展。 1.4 任务与分析 设计一程序能完成五子棋游戏功能。五子棋规则：双方各执一色棋子，轮 流下子（即将棋子放在棋盘的任一空交叉点上），直到有一方的棋子有 5 个排 成一线（无论是横向、竖向还是斜向均可），则棋局结束，该方胜利。 （1）设计游戏的核心算法； （2）设计可视化的界面且双方所使用的两色棋子和彩色棋盘得体大方、 比例当； （3）双方轮流用键盘或鼠标下子。只有当鼠标单击在棋盘网格交叉点附 近时才可下子，点击其他地方及已有子的位置不能下子，且应给出 相应提示； 7 五子棋游戏软件设计 2.总体设计方案 2.1 算法设计 2.1.1 总体框架图 主界面 开始游戏 （ 默认人下黑 棋 ， 电脑下白棋 ） 先手 o r 后手 人先在棋盘上下子 电脑先在棋盘上下 子 后手先手 电脑后在棋盘上下 子 五个颜色相同的棋子连成一 条线 （ 横 、 竖 、 撇 、 捺 四个 方向 ） 人后在棋盘上下子 否 否 黑棋 （ 白棋 ） 胜 是 图 2.1.1 系统总体框架图 2.1.2 五子棋胜负判断算法 五子棋的胜负（该软件默认是人下黑棋，电脑下白棋） ，在于判断棋盘上 是否有一个点，从这个点开始的右、下、右下、左下四个方向是否有连续的五 个同色棋子出现，如图下图所示： 图 11 判断胜负方向 2.1.2 算法流程图 每当在棋盘上下一个棋子后，需要判断这个棋子的四个方向是否有连续的 五个同色的棋子出现，这个需要一个二维数组来存储来存每个棋盘的坐标的颜 色，还需要在每次下了棋子之后，遍历该棋盘的所有获胜的组合，来实现判断 胜负。 2.1.2 五子棋人工智能算法 当人下了一个棋子之后（人作为后手的第一次除外） ，电脑需要对棋盘进行全面 的评估。 1、获胜组合是一个三维数组，它记录了所有取胜的情况。也就是说，对于 每一个落子坐标，获胜的组合一共有 15 * 11 * 2 + 11 * 11 * 2 = 572 种。 而对于每个坐标的获胜组合，应该设置一个1515572大小的三维数组。 在拥有了这些获胜组合之后，就可以参照每个坐标的 572 种组合给自己的 局面和玩家的局面进行打分，也就是根据当前盘面中某一方所拥有的获胜组合 多少进行权值的估算，给出最有利于自己的一步落子坐标。 9 五子棋游戏软件设计 由于是双方对弈，所以游戏的双方都需要一份获胜组合，也就是： private boolean white_Win = new boolean1515572; /电脑的获胜组合 private boolean black_Win = new boolean1515572; /人的获胜组合 在每次游戏初始化的时候，需要将每个坐标下可能的获胜组合都置为 true。 此外，还需要设置计算机和玩家在各个获胜组合中所填入的棋子数： private int win_Count = new int2572; /int0X 为人（黑棋）的获胜组合中的棋子数 / int1X 为电脑（白棋）的获胜组合中的棋子数 在初始化的时候，将每个棋子数置为 0。 2、每当一方落子后，都需要作如下处理： 如果己方此坐标的获胜组合仍为 true，且仍有可能在此获胜组合处添加棋 子，则将此获胜组合添加棋子数加 1； 如果对方此坐标的获胜组合仍为 true，则将对方此坐标的获胜组合置为 false，并将对方此获胜组合添加棋子数置为-1（不可能靠此组合获胜） 。 白棋为例： for (int i = 0; i = 140 xx = quotient_X * 35 + 140; if (compliment_Y 17) quotient_Y = quotient_Y + 1; yy = quotient_Y * 35 + 140; System.out.println(xx + “-“ + yy); 4.4 五子棋棋子设计模块 当记录下当前的坐标后，就要对棋盘进行画棋子（白棋和黑棋的绘制）： 黑棋为例： public void paint_BLACk(Graphics g, int xx, int yy) Graphics2D g2 = (Graphics2D) g; g2.setColor(Color.BLACK); g2.setStroke(new BasicStroke(2); g2.fillArc(xx - 14, yy - 14, 30, 30, 0, 360); 4.5 五子棋的胜负判断模块 当任意的一方下子后都要判断这个棋子的四个方向是否组成五个相同的颜色的 棋子（chess 存储当前棋盘所有的坐标棋子情况）： public boolean isWin(int x, int y, int temp) /*X 为横坐标， Y 为纵坐标， temp 为当前颜色，chess=0 表示当前坐标没有棋子，chess=1 表示当前坐 标为黑棋，chess=2 表示当前坐标为白棋*/ for (int i = 0; i = white_Temp_Score) white_x = i; white_y = j; white_Temp_Score = white_Scoreij; if (black_Scoreij = black_Temp_Score) black_x = i; black_y = j; 21 五子棋游戏软件设计 black_Temp_Score = black_Scoreij; if (white_Temp_Score = black_Temp_Score) x = white_x; y = white_y; else x = black_x; y = black_y; paint_WHITE(this.getGraphics(), x * 35 + 140, y * 35 + 140); white_Opera(x, y); 5.系统测试 1先将 tupian.jpg 放到 D: 下，运行 Eclipse，打开 FiveChess.java 文件，点击运行，出现 主界面： 图 5.1.1 主界面 2.点击先手，开始： 图 5.1.1 先手开始 23 五子棋游戏软件设计 3.、点击棋盘的位置，然后下棋，当点击以下过棋子的地方，则提示： 图 5.1.2 下棋界面 图 5.1.3 提示界面 4、当一方的五个相同的棋子连成一条线，则胜： 图 5.1.4 获胜界面 25 五子棋游戏软件设计 6.结论 首