五子棋 AI（一）

博客搬家：最爱午后红茶

五子棋是一种两人对弈的纯策略型棋类游戏，通常双方分别使用黑白两色的棋子，下在棋盘直线与横线的交叉点上，先形成5子连线者获胜。

      想记下的是一些核心的内容，界面就直接跳过。

      要让计算机下棋，说白了就是让计算机在面对一个棋局的时候在所有可落子点选择一个对自己最有利的点行棋；因此棋类游戏的 AI 的核心部分就是选出下一个合适的落子点。

      已经有人证明五子棋“先行必胜”的猜测，所以五子棋有“禁手”的规则来平衡游戏的公平性，为分析的简单起见，我们采取“无禁手”的规则。

      计算机怎样找到那个合适的点呢？只能计算，毕竟不是人，只能通过计算所有可落子点对己方的价值是多少，然后选择价值最大的那个点。那怎样找到价值最大的点呢？判断棋形，这也是一个难点。

      五子棋比较重要的棋形有：(O 表示己方， @ 表示对方或边界，X 表示空点)

      成五：就是5枚同色棋子连成一排，也就是表示胜出    OOOOO

活四：有两个点可以成五的四，也就是  XOOOOX

冲四：有一个点可以成五的四，也就是  XOOOO@，OOXOO，OXOOO，等等

活三：再下一子可以形成活四，也就是  XOOOXX，XOXOOX，XOOXOX，等等

眠三：再下一子可以形成冲四，也就是  @OOOXX，XOOXO@，等等

活二：再下一子可以形成活三，也就是  XXOXOX，XXOOXX，XOXXOX，等等

死四：不能成五，@OOOO@，死三，死二类似

双冲四：就是己方有两个冲四

冲四活三：就是己方有一个冲四和一个活三

双活三：就是己方有两个活三

当然还有其他很多棋形，但分量比较低就不列出来了；接着就要对各种棋形进行评分了，这个我也是凭直觉再加上参考了别人的评分给出这样的方案：

成五：20000  

 —— 轮到己方下子，且己方可以一步成五，分值最高

活四：2000

双冲四：2000

冲四活三：2000

—— 轮到己方下子，且对方不能一步成五，则己方下子如可以形成以上三项之一则必胜

以上 4 类 称为绝杀棋（用词可能不准确~）

双活三：

—— 轮到己方下子，且对方不能一步成绝杀棋，则己方下子如可以形成双活三则必胜

连冲四：300

跳冲四：250

连活三（这种 xoooxx）：450

跳活三（这种 xoxoox）：300

眠三：50

连活二（这种xxooxx）：100

跳活二（这种xoxoxx）：70

死四，死三，死二：-10

那么怎样用这些分数计算落在某个空点上的价值呢？

假如有如下棋局，轮到计算机（黑子）下子：

那它会这样计算所有可落子点的价值：设该点为己方棋，把横向，竖向，左斜，右斜方向上的己方棋价值之和相加作为攻击力，然后设该点为对方棋，同样把横向，竖向，左斜，右斜方向上的对方棋价值之和相加作为防御力，最后把攻击力和防御力相加作为该点的价值；比如如果在下图标记处下子可产生的价值为：

攻击力：冲四 + 2 * 连活二 = 300 + 2 * 100 = 500

防御力：连活三 = 450

该点价值：500 + 450 = 950

难点在于正确并完整地提取所有棋形，方法应该有很多，计算某个点的价值我们可以把该点所在的行，列，左斜，右斜的信息提取出来存在数组里进行判断；以后提高智能还有要计算整个棋盘的价值也是用同样的方法（把二维的图转化为一维；一般规格的五子棋是 15 *15 的棋盘，所以有 15 行，15 列 ，29 左斜，29 右斜，共 88 条线，而左斜与右斜分别有 8 条线不能成五，所以需要判断总数为 72 条线）

这样就完成了五子棋简单的 AI ，其实不能说 AI 吧，只是一种贪心的方法，就是采用只顾眼前利益而不做长远计划的方案，相当于初学者的水平，优点是速度快，只需要扫描一次棋盘，缺点也很明显，对手脑子稍微拐下弯，想个两三步就能打败它。其实这相当于后面将讲的极大极小搜索的第一层搜索。

可以感受一下：gobang2