五子棋AI算法八 重构代码

为什么需要重构

之前的代码有很多松散的模块组合在一起。在把 Zobrist 集成进去时,会发现全部需要走棋的操作其实都需要进行一次 Zobrist 异或操作。另外在逻辑上,其实很多模块都是可以合并到同一个类的,所以这次把代码进行了一次大的重构。所以如果发现博客说的一些模块找不到了也是很正常的,因为大部分模块都被移到了 Board 类中。

这次重构主要的工作就是 把AI相关的代码分成了四个模块:

  1. Board ,所有和棋子相关的操作都在这里,包括打分,判断胜负,zobrist缓存,启发函数等。
  2. negamax 搜索模块
  3. checkmate 算杀模块
  4. 外壳,配置,一些辅助方法等,包括 ai.js, role.js

集成 Zobrist

把所有走棋操作都放到 Board 类中之后,只需要在 board 中进行 zobrist 异或操作就可以。可以避免在搜索或者算杀中进行Zobrist 操作。

具体的做法是在如下三个方法中都进行 zobrist 更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//下子
Board.prototype.put = function(p, role, record) {
this.board[p[0]][p[1]] = role;
this.zobrist.go(p[0], p[1], role);
this.updateScore(p);
if(record) this.steps.push(p);
}

//移除棋子
Board.prototype.remove = function(p) {
var r = this.board[p[0]][p[1]];
this.zobrist.go(p[0], p[1], r);
this.board[p[0]][p[1]] = R.empty;
this.updateScore(p);
}

//悔棋
Board.prototype.back = function() {
if(this.steps.length < 2) return;
var s = this.steps.pop();
this.zobrist.go(s[0], s[1], this.board[s[0]][s[1]]);
this.board[s[0]][s[1]] = R.empty;
this.updateScore(s);
var s = this.steps.pop();
this.zobrist.go(s[0], s[1], this.board[s[0]][s[1]]);
this.board[s[0]][s[1]] = R.empty;
this.updateScore(s);
}

这样任何时候完成走棋之后,都可以通过 board.zobrist.code 来获取当前的哈希值。然后在 Negamax 或者 checkmate 中就可以以这个code 为当前棋局的唯一标示来存储分数。

目前实现了一个最简单的方式,就是把每个棋局的分数存下来,下次如果遇到相同的棋局就不用打分了,而是直接取上次存储的分数。但是这里存储分数的时候要同时存储升深度,因为只有深度大于等于当前深度的分数才是有效的。具体实现可以看 Board 类中的代码。

这样的实际效果其实并不理想,大约 10%的命中率,虽然10%也是很客观的提升,但是其实对最终走棋速度影响并不大,也就是加不加这种方式的置换表并没有能感觉到的速度提升。
实际上对置换表最好的应用,应该是用在启发搜索中对待选节点进行筛选和排序,但是具体怎么实现暂时还是没有想好。