Ai五子棋初解

Ai五子棋初解

目录

• 摘要

近来随着计算机的快速发展，各种棋类游戏被纷纷请进了电脑，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表；其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜爱；而此次C#应用开发综合实习课程便研究人工智能中入门的AI五子棋。

• 总体设计

1. 基本思想

AI其实体现的都是一种建模思想，把一个现实中的问题模型化，抽象化，得到其一般特征，再设计数据结构及算法。

1. 设计步骤

1.     建立棋盘 二维数组Table[15][15]  Table[15]表行 Table[][15]表每行对应的列。

2.     建立算法棋盘 三维数组Computer[15][15][4]和Player[15][15][4]。

（其中1代表玩家下子,2代表电脑下子,通过1和2数量判断下子者）

3.     设计算法，使电脑落子智能化。

4.     设计结束条件。

（根据基本思想，由此可以得出AI算法设计步骤）

AI算法设计步骤：

1. 五子棋中有不同的棋型（局势），有的局势则胜面大而有的小，当胜面不断积累的时候就构成赢面，因此建立棋型表

2. 用三维数组记录所有获胜的局势，即Computer[][][4] 和Player[][][4]存放的为每个对应点的横、竖、左斜、右斜得分。

3. 根据上一步的得分建立估分表gradeMyMap和gradeOppoMap，判断棋盘上每个点落子的得分。（满足某种棋型则加分）

4. 根据上一步得到估分表建立表数组，用冒泡算法得出最优解转换成内部坐标即为电脑落子的位置。

   • 基本结构

5. 程序结构

1. 数据字典

横纵点数  gameSize 15

一个格子的尺寸blockSize 30

棋子图片大小chessmanSize (图片尺寸24)

坐标偏移量 delta 42

有效距离的平方 eDistance 100

坐标点的文字大小和颜色 textSize textColor

判断棋子颜色 color = 1

棋子记录表  map

横向计数 hSum

纵向计数 vSum

左斜向计数 lSum

右斜向计数 rSum

计算后空间尺寸  boradSize

棋子数改变事件 OnChessmenNumChange

游戏结束事件OnGameEnd

1. • 核心设计

2. 初始化模块

3. 棋盘绘制

法一:画点连线

法二:画线建点

GameBoard.cs中drawLinesAndCircles方法

(画法)

方法: Point(x * blockSize + delta, y * blockSize + delta); //x为横坐标,y为纵坐标

从(delta, delta)为初始点，每个格子宽度为blockSize画线 for (int i = 0; i < gameSize; i++)

画出竖线和横线以及圆圈, 圆圈不需要显示出来

1. 坐标绘制

画出坐标for (int i = 0; i < gameSize; i++) 坐标需要水平居中和垂直居中,防止数字偏移

GameBoard.cs中drawCoordinateText方法

1. 背景绘制

GameBoard.cs中Createbackgroudimage方法

1. 循环控制模块

根据落子数目判断下子为玩家还是电脑

ChessmenNum.cs中Num方法

1. 玩家下子模块

2. 工具方法

用于玩家落子后将屏幕坐标转变为内部坐标

GameBoard.cs中ScreenToIndex方法

1. 有效落子点击判断

在棋盘绘制中以每个点画圆圈，如果点击位置在圆圈内部则为有效落子

○范围内则落子成功,是就返回内部坐标封装成CalDistance

GameBoard.cs中IsEffectiveArea方法

（工具方法：CalDistance 计算距离的平方）

1. 盘面分析填写棋型表

2. 棋盘计数

GameBoard.cs中AllDirectionsCount方法

连续上每有一个+1

水平方向计数hSum

垂直方向计数vSum

左斜方向计数lSum

右斜方向计数rSum

1. 越界判断

越界判断

GameBoard.AI.cs中NoCrossBorder方法

在没有越界的基础上判断是否存在同颜色的棋子

GameBoard.AI.cs中ExistSameColor方法

在没有越界的基础上判断某个点是否没有棋子

GameBoard.AI.cs中Empty方法

1. 建立估分表

int[,] gradeMyMap = new int[gameSize, gameSize];

int[,] gradeOppoMap = new int[gameSize, gameSize];

满足某种棋型的时候则加分

1. 建立表数组

GameBoard.AI.cs中GetBestPoint方法

用冒泡算法得出最优的解后返回内部坐标落子

1. 电脑下子模块

2. 工具方法

用于电脑落子后将内部坐标转变为屏幕坐标

GameBoard.cs中IndexToScreen方法

1. 下子返回内部坐标

落子建立估分表，判断落子位置

GameBoard.AI.cs中ComputerNextStep方法

1. 落子位置判断

根据估分表建立表数组用冒泡算法得出最优的解即为AI最优落子点

GameBoard.AI.cs中GetBestPoint方法

1. 胜负判断模块

GameBoard.cs中IsGameEnd方法

从返回的内部坐标中判断hSum >= 5 || vSum >= 5 || lSum >= 5 || rSum >= 5

横、竖、左斜、右斜方向判断是否五子连珠

1. 棋型判断模块

GameBoard.AI.cs中SituationType方法判断棋型

 

1. • 核心算法
2. 冒泡算法

根据电脑下子建立的估分表建立表数组，用冒泡算法找出最优解，之后返回坐标

1. 贪婪算法

2. 概述

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

1. 贪婪策略

1.      存入棋盘棋型。（让AI知道怎么样会赢）

2.      有不同的棋型，给不同棋型加权（有的棋型是必赢局有的是大概率会赢的局面）

这样电脑就知道了该在哪一个点下子，但不能只考虑自己。

3.      引入Computer[15][15][4]和Player[15][15][4]分别计算棋面得分

4.      引入估分表对map棋盘的每个位子计算分值

5.      冒泡(得出最高分)。当玩家得分大于电脑得分，则放弃优势落子堵玩家落子。

六、参考代码

^^^^^^^ 这个粘贴图片的工具有问题,不会自己导进来,不写了 

http://www.wtwalone.cn:8007/  放个前端大佬写的五子棋, 溜了

七、拓展算法

九、心得体会

初窥算法一角心得

前言:此文C#课程设计完成Ai五子棋后的一点心得

我不知道当初为什么脑袋发烧定题选择Ai五子棋,然后窥视了这冰山一角,深感前途渺茫,任重而道远.

初觉Ai五子棋并不难,草草在网上找了些参考程序和文档便执手开始写了,前期想的比较简单,建个画布建点连线画点, 初始化显示器、键盘、鼠等输入输出设备,一切按着应有节奏进行了,终于一个愚蠢的的憨批版本--初代Ai五子棋便诞生了,当然此时并不能称之为Ai,因为我前五步就五子连珠赢了.我发誓我要把这愚蠢的人机删掉,算了还是报告要紧,这个机器人当然不能随机下子啊,于是乎便开始网上脑补五子棋算法.

贪婪算法,最开始看见的便是贪婪算法了,能在当前局面上找到最优解,哦!老天!这不就是我最需要的吗?咦?这算法下面介绍是啥?五子棋??代码??我理所当然了成为了一个ctrl+c、ctrl+v战士。开心.jpg，花了一会时间捣腾，有幸第一节课完成最后一节课要交的报告，没有什么比这个来的开心和实在了。测试开始，嗯？五步赢不了，成功了！卧槽，成功了，IG牛皮！再来一次，也许是本人太强的原因，这电脑走不过几步。不行，这太蠢了，于是乎在代码上，我略作改动，判断每行每列之后大于2或者3便开始堵，四子连珠不用考虑了，直接堵。于是乎初代Ai五子棋2就坐在了我的对面，诶，我得让你先下好吧？嗯？你为什么不下棋盘中间？为什么？好吧，你还没告别愚蠢，我似乎似乎得让你也能想着赢吧？不然这个弱智。先等等，为什么还是这个憨逼？

我又一次点开了百度，双三、活四、冲四这都是神马东西，五子棋别搞得像围棋一样好不好？行，我明白了，来吧？给这些加权不就行了？然后考虑下横竖左右七上八下有不有这种情况就下，行吧。慢着，这是什么？每个位置上下左右打分，三维数组？我一个学到现在只用过二维数组的萌新得写个五子棋弄三维数组？在下必须得吹一波，在下还是很机智的。于是乎较大的颠覆了前面代码之后，在下写出了初代AI五子棋3。这次五子棋彻底告别愚蠢，算是知道下棋是为了赢，这次改动比较大，信息上整理了下，此代版本的Ai[][][4]三维数组存了了每个横纵左斜右斜方向落子的权数得分，还可以根据棋面上的情况来判断最优的落子方式，比如某个位置可以形成双活三。这个版本的五子棋我以为是不错了，不行，我得沾沾自喜一会！测试：一顿操作之后！好吧这个版本的五子棋告别了愚蠢，可还是一个憨批，我高兴早了。至少这个五子棋应该能判断玩家落子可能出现的必赢棋面活双三等情况，这就是我想的预测情况，革命成功尚早，同志仍需努力。

我最终考虑还是打开了百度，我发誓：这是我最后悔打开百度的一次，尽管这次我学到了很东西。我考虑过让自己的五子棋能预算一步的情况，我得想办法实现。我了解到了一个新的算法，博弈树算法，这是一个有深度的算法，我理解成这就是对于棋盘状况的一种穷举！这种算法能穷举出无数种可能出现的情况，而且不只是预测一步。每层的节点孩子的数目等于当前决策者所拥有的选择数量，所以博弈树每层节点的孩子数目逐层递减，每个节点对应一种情况、一种局面，也对应着一中算法可以算出如果局面对应的分数，也就是权值，或者说是胜面，最终走向胜利。

那种算法很难，但还有更重要的我没有考虑。我还可以考虑玩家的得分，当前局面玩家得分多少，Ai得分多少，在当前最优解不超过玩家下一步分的情况是不是可以不考虑自己的最优局面去封住玩家的最优局面，之后在使用博弈树算法来算出之后的情况。假设做在对面的玩家是最聪明的人，那么是不是可以得分=AI分数-玩家分数呢？需要建立三个棋盘来计算结果。会用到极大极小搜索算法，需要在决策层中如果用这种情况的话可能出现拓展结点，那么会创造出新的局面。在决策树中，轮到我方决策层时，我们总希望做出得分最高的决策（得分以我方标准来算）；而在敌方决策层时，我们假定敌方总能够做出得分最小的决策（我方得分最小便是相应敌方得分最高）。所以在博弈树中，每一层所要追求的结果，在极大分数和极小分数中不断交替。我考虑的够多了，我写不出来。而且这种算法需要大量的计算，可能需要一个计算集群。落子也是有时间限制的，不可能无限计算，还需要其他算法辅助。

第四个映出眼球的是α-β算法,Ai的思考程度越高，需要的时间和计算量恐怕是指数级的增长，不可能无限增长。这是一种基于深度优先搜索的剪枝算法。我不想了解那么多了。

有些累了。我想到了1997年的“深蓝”计算机，战胜了当时的世界冠军。我想到了2016年的“阿尔法围棋”和韩国李世石九段的五番棋比赛。这种计算机还有深度学习能力，每天能和自己下棋，并记录下2W多中棋盘，以后人怎么可能赢？

2016如实，2019年的今天，作为一个还未熟练掌握一门编程语言却要进入社会的码农，前途任重而道远。

//以后打死千万不要搞算法