算法-如何设计一个，永不输的五子棋算法

Question

就是人机对战，人永远赢不了机器。棋盘大小可以随意设置

Answer 1

问题描述：人们通常喜爱的五子棋。某方将结果连成五子即获胜。

问题规模：15x15棋盘。

算法：博弈树，极大极小算法+Alpha-Beta剪枝

法棋。

数据结构描述如下。

棋盘类：

棋盘为一个M*N的矩阵Tbl[M][N]（定义LEDGE为左边界，REDGE为右边界，TEDGE为上边界，BEDGE为下边界）。

每个棋盘矩阵有两个评估矩阵CpuPri[M][N][4]和UserPri[M][N][4]，矩阵的第三维分别记录了该点（[0]水平、[1]垂直、[2]左上—右下、[3]左下-右上）的棋子数。若该点上棋子为USER下的，则UserPri中有值，CpuPri中值为0，反之亦然。该点无子时，两个评估矩阵上该点评估值均为0.

CpuSum：CpuPri矩阵的所有元素之和。UserSum：UserPri矩阵的所有元素之和。

tag：tag=CpuSum/UserSum，CPU战术选择标记。当tag大于1时CPU进攻，小于1时CPU防守。

Depth：深度。标记该棋盘位于博弈图的层次。

Father：该棋盘的前驱。Child：该棋盘的孩子棋盘链。nextBro：兄弟节点。

Node：一个点类，标记该棋盘下子的点。

算法描述如下。

一、由于存在对抗性，CPU分为进攻和防守两种方式。Tag>1时进攻，tag<1时防守。Tag的实际含义是对敌我的一个评估，当我方比敌方有利时选择进攻，当敌方比我方有利时选择防守。

二、对任意一棋盘生成博弈图的算法。

算法2-1

当CPU接到一张已落子n个的棋盘时：

1、计算此棋盘的CpuSum值和UserSum值，并得出tag值决定进攻还是防守。此标志在本次生成整个博弈树时都不变，也就是决定了进攻或防守后，选择时都依据此标志。

2、以CPU身份在棋盘的每个未落子的点上分别下一步棋，生成M*N-n个已落子n+1个的棋盘，分别计算评估值，并生成博弈树第一层；

3、再以USER身份在每个棋盘（已落子n+1个）每个未落子的点上再下一步棋生成M*N-n-1个棋盘，分别计算评估值并加入博弈树第二层。

4、回到步骤2，依次类推，CPU的身份不断在CPU和USER之间变化，直到生成树的深度大于给定深度MAX_DEP时为止，停止建图。

5、此时，将叶子节点的CpuSum和UserSum计算出来。

6、若决定进攻，则极大极小过程如下：

1）若某步为CPU走（depth值为偶数），则应当选择CpuSum最大的一个棋盘，即CPU选择了对CPU最有利的一步。（极大过程）

2）若某步为USER走（depth值为奇数），则应当选择CpuSum最小的一个棋盘（即相当于此时用户防守），此时相当于USER选择了对CPU最不利的一步。（极小过程）

7、若决定防守，则极大极小过程如下：

1）若某步为CPU走（depth值为偶数），则应当选择UserSum最小的一个棋盘，即CPU选择了对USER最不利的一步。（极大过程）

2）若某步为USER走（depth值为奇数），则应当选择UserSum最大的一个棋盘（即相当于此时用户进攻），此时相当于USER选择了对USER最有利的一步。（极小过程）

8、按照6、7的选择算法，从下至上，得到第1层的（M*N-n）个棋盘的CpuSum值和UserSum值。注：向上传递时，同时传递CpuSum和UserSum值，不论如何挑选。但棋盘并不向上传递。

9、在第0层决定如何走下一步，方法同6（1）或7（1），取决于CPU是防守还是进攻。此时将最适合的棋局的棋盘（位于博弈树第1层）返回，即完成了原棋局下一步的选择过程。

10、删除该图，算法结束。

三、剪枝

一个已经落子n的棋盘按照上面的算法向前预测k步会产生((MN-n)!/(MN-n-k)!)个棋盘。

例如，最大生成深度为3时，若一个15x15的棋盘已经由用户走了1步，那么CPU在预测下一步时会产生224223222=11089344个棋盘。若每个棋盘大小为8k（1515+151522=2025个int），则空间大小为86635.5MB=86.6GB，同时会有极大的耗时，这是用户无法接受的。

由于向前预测时会进行大量计算，同时产生巨大的数据，所以必须进行剪枝。

首先使用书上给出的Alpha-Beta剪枝计算，取得了一定的效果，但仍有很大的空间消耗。为了追求更高的速度，经过自己分析，采用了一个变形的Alpha-Beta剪枝法。

剪枝算法如下：

算法3-1

在生成一个棋盘的子棋盘前，将该图的CpuSum值和UserSum值计算出来，用2-1-6和2-1-7类似的判别方法，（此处以CPU进攻为例），当其子棋盘CpuSum值小于该棋盘的CpuSum值时则舍弃不加入博弈树，否则加入博弈树。其他情况同理。

算法分析：该剪枝算法不能保证得到最优解（类贪心算法），但有更快的速度和更小的空间占用，而且也在短时间内有更大概率搜到Threat-Space。其弱点在于容易被对手用一定的战术蒙骗。实验证明，下棋时几乎感觉不到CPU计算的过程，用户输入后，CPU几乎立刻得出结果。

五、下棋

下棋时，只需把棋盘交给用户，让用户点一个棋子，再将该棋盘交给CPU处理，选择下一步后，再还给用户。当某方出现五子时，游戏结束，判定该方胜利。

引自 博客园：http://www.cnblogs.com/xiaoliango/archive/2011/11/15/2249864.html

以上是15*15 ，如果要永不输的话，嘿嘿，把棋盘干脆搞成无法达到5个子的就OK了！

Answer 2

有一些开局（开头的三个落子）已经被证明了是先手必胜了。另一些则被证明是后手必胜。正规的五子棋规则中有三手交换、五手两打的规则，所以实际上如果计算机后手对这些规则的确是必胜的。当然把必胜法的棋谱全存起来很费事。
另一些常规开局目前还不清楚有没有必胜法。不过从原理上来说既然后手方可以选择交换成先手方，那至少后手方能确保不败吧。
如果将来的计算机存储容量足够大、运算速度足够快，就可以把所有走法都找出对应招数，最后实现不管怎样人都下不赢计算机。目前还没有这种可能性，最快的博弈树算法也就是算个10步不到而已，人可以利用这致命的第11步下出计算机完全无法预测的棋谱来，所以还做不到必胜。
现在的五子棋程序已经非常强了，一般人根本下不过。不过正如前面所说，可以利用博弈树算法的致命弱点：只算10步的话，如果你落子在第11步会用到的要点上，计算机就会出现严重的判断失误。人当然也没法算这么远，但是人可以凭某种直觉性的洞察力发现某个点上可能将来会有所为，从这个方向上打败电脑。