跳至主要內容

五子棋AI算法（4）

奇葩的灵梦2025/5/13大约 8 分钟五子棋算法Java
最近更新：

注意

此AI并非“人工智能”，而是我们早期意义上的传统AI，并无学习能力，纯粹用算法实现五子棋每一步棋的应对策略。

上一章我们用α-β剪枝和启发式搜索对博弈树搜索算法进行优化，大大提高了算法性能。这一章我们继续用更多的方法进行优化。

算杀

回顾一下我们上一章讲的剪枝，既然有剪枝，那么也有“增枝”。我们对少量特殊情况进行更深的处理，就可以提高算法的精确度。

我们知道，在下五子棋的过程中，我们经常连续走出“活三”“冲四”的先手棋，让对手必须响应。在连续下出多步这样的棋后，最后形成“双三”“双四”“四三”等对方无法顾及的局面，就可以获胜了。

那么我们只需要对“活三”“冲四”的先手棋进行更深入的处理就可以了。用伪代码可以表示为：

既然有“算杀”，自然也有“防杀”：

for ( int i = 0; i < Constant.MAX_LEN; i++ ) {
    for ( int j = 0; j < Constant.MAX_LEN; j++ ) {
        // if ( 下完这步棋之后，对方算杀，结果找到了一种杀招 ) {
            // continue; 我不能选择这种走法
        // }
    }
}
// 如果找到一步棋，对方算杀不成功，那么就防杀成功了
// 如果找不到这样的棋，则说明我已经输了

算杀和防杀也应该有一个步数上限，但这个步数应该长于博弈树搜索的步数，这就是所谓的“增枝”。

但是，还有一个小问题我们没有处理：在“算杀”的过程中，很有可能本来就有一个杀招，但由于我们遍历的顺序随机，可能会先去别的地方走出一系列“或三”“冲四”，最后才会回来走这个杀招，显得很“傻”。

解决方法也很简单，我们可以在“算杀”的过程中，慢慢增加步数，例如先计算4步之内的杀招、再计算6步之内、再计算8步之内，这样慢慢增加步数限制，就会优先找到步数最少的“杀招”了。

算杀和防杀的代码较为简单，这里就不详细列举了，感兴趣可以查看完整代码。

缓存

我们接下来考虑这样一些问题：

  • 之前算过的棋，如果我们存起来，下次就不用再重新算了。毕竟算一次也是需要挺久的时间的。
  • 根据之前的博弈树搜索算法可以看出，我们下一步棋到底应该下在哪里，只与当前盘面有关，与我之前是如何走出这个盘面的无关。换句话说，我按照1→2→3→4的顺序走出来，还是1→4→3→2的顺序走出来，只要当前盘面一样，不会影响我的下一步棋。

那么我们只需要一个Map存储，它的key是当前棋局，value是下一步我要下在哪里，就能节约大量计算时间。

众所周知，Map一般有两种，HashMap和TreeMap。我们应该用哪种呢？

TreeMap的底层是二叉搜索树，需要一个比较函数int compare ( 棋盘状态1, 棋盘状态2 ) 返回大于、等于、小于，显然每次都比较的话，尤其数据量大了之后，是不划算的。

而HashMap，底层是Hash表，需要一个int hash()函数，这个函数应该怎么写？一定要全遍历一遍这个棋盘，根据每个位置的状态（黑、白、空），才能写出来吗？这样的话，又要全遍历，就没什么意义了。

这样，我们就引出了 Zobrist Hashing 算法。

Zobrist Hashing

Zobrist Hashing 算法常用于棋类游戏的盘面Hash值计算中，尤其是五子棋、国际象棋等。它的基本思想是将棋盘上的每个位置和每种棋子（黑、白）都映射到一个随机数上，然后通过异或运算来计算当前棋盘的Hash值。

首先我们需要将每个格子赋值一个随机数，黑子和白子都需要分别赋值一个随机数：

int hash_value = random.nextInt();
int[][] white_hash = new int[Constant.MAX_LEN][Constant.MAX_LEN];
int[][] black_hash = new int[Constant.MAX_LEN][Constant.MAX_LEN];
for (int i = 0; i < Constant.MAX_LEN; i++) {
    for (int i = 0; i < Constant.MAX_LEN; i++) {
        white_hash[i][j] = random.nextInt();
        black_hash[i][j] = random.nextInt();
    }
}

每下一步棋，我执行一次下面的操作：

if (whose_turn == Constant.BLACK)
    hash_value ^= black_hash[x][y];
else
    hash_value ^= white_hash[x][y];

这里的^是“按位异或”运算符。

我们来思考一下，为什么可以用异或？

  • 假设原值是1，我们执行两次异或操作：1 ^ 1 = 0，0 ^ 1 = 1。我们发现，异或两次之后，又变为原先的值。
  • 假设原值是0，我们执行两次异或操作：0 ^ 1 = 1，1 ^ 1 = 0。我们发现，异或两次之后，也会变为原先的值。

换句话说，我把一个白棋放上去，异或一次之后，如果把它拿下来，再异或一次，盘面不变，Hash值也不变。黑棋同理。

hash()函数最基本的要求是，当盘面相同时，hash()函数的返回值必须相等，这一点我们已经实现。

这样一来，随着每下一步棋，Hash值跟着变动一次，Hash值的生成不需要遍历棋盘了，hash()的效率已经满足了。

第二个问题来了，Hash冲突怎么解决？

可能有人会说，棋盘有 15×15=22515 \times 15 = 225 个格子，黑白棋两种颜色，加上这个格子没有下棋，共有3种情况，那么总共有 32253^{225} 种棋盘状态。而一个long只能存2642^{64}种可能的数字，Hash冲突的概率应该很大吧？

其实并不能这样计算。首先，五子棋不像围棋一样存在提子，五子棋一定是轮流下棋，因此不可能出现全盘都是黑棋或者全盘都是白棋的情况。并且，很多已经成五的棋已经结束了，不会再继续下了，这样的盘面也不成立。再者，我们也不可能乱下，例如一直在版边或者角落下棋，即使我们这样下，AI算法也不会这样下的，因此这样的盘面也不会出现。

那么我们换一个角度思考，一局棋就算100步结束，下10000盘棋，不算重复情况都只有100万种局面，一个long能存264=1.8×10192^{64} = 1.8 \times 10^{19}种情况，这样一看，触发Hash冲突的概率就极低了吧？实际运用中一般是忽略Hash冲突的。

既然忽略了Hash冲突，我们就可以直接默认如果Hash值相同则棋局相同。

有了这个缓存，我们就可以干很多事情了，例如：

  • 缓存，已经算过的不用再重新算了。
  • 提前存储开局库。
  • 多线程运算，可以将计算结果存入到缓存中，方便线程之间的共享。
  • 玩家在下棋的过程中，算法也可以在后台进行计算，提前算出下一步棋应该下在哪里。
  • 还可以增加一些时间策略，例如计算6步花了10秒，而计算8步花了1分钟还没算出来，就可以提前返回计算6步的策略了。

后记

以上，就是我们五子棋AI算法的全部内容了。我们从最开始的简单的博弈树搜索算法，到后来的α-β剪枝、启发式搜索、算杀、缓存等一系列优化，最后实现了一个性能还不错的五子棋AI。

当然了，现代的机器学习技术已经可以实现更高效的五子棋AI了。我们在这里实现的五子棋AI算法只是一个简单的实现，更多的是为了让大家了解五子棋AI算法的基本原理和实现方法。

说到这里，我刚好也想到，我们可以把这个五子棋AI算法和机器学习结合起来。可以考虑的一种思路是：我们在前面的评估函数的设计时，用了很多个人经验来“云”出来的每一步多少分，这些分值肯定是有误差的，我们只需要通过机器学习的思路，持续训练这些数值，就可以让AI更加聪明。由于我对机器学习了解尚浅，这里我就不“班门弄斧”了。

到这里，本篇就基本完结了。可以看到，这个系列的文章跨度时间很久，也是我鸽了又鸽，最后终于补齐了。

完整代码

整个五子棋的代码（Go版和Java版）已经分享在：https://github.com/CuteReimu/gobang ，需要的可以自取。