五子棋游戏软件设计.doc

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