- 这个AI是基于JS语言实现的
- github上有教程地址
五子棋是一种博弈游戏
有完备信息的，确定性的，轮流行动的，两个游戏者的零和游戏
这些条件是必须的。
不满足这些条件的话，可能需要用到其它不同的算法。而五子棋，围棋，黑白棋，象棋等都是满足这些条件的，因此都可以用这套算法来实现。
就我下棋的经验来看的话，如果可以被称为下棋的话。考虑到场面的棋子，如果只凭借推测的话，我几乎一步都推算不了。//好羞耻 而高手可能能够推算到后面好几步（实际上，应该是根据以往的经验对一部分状态空间进行了排除，从而实现了简化）。从我的角度看，人类早就应该被打败了。。。人类显在的思考空间就我看来十分有限。
AI实现的基本思路-极大极小值搜索算法
硬核破解方法：列出每种情况：
那么我们如何才能知道哪一个分支的走法是最优的，我们就需要一个评估函数能对当前整个局势作出评估，返回一个分数。我们规定对电脑越有利，分数越大，对玩家越有利，分数越小，分数的起点是0。
var r = function(deep, alpha, beta, role, step, steps, spread) {
var _e = board.evaluate(role)
//evaluate是对当前棋盘局势的判断，评估函数
//连五，100000
//活四, 10000
//活三 1000
//活二 100
//活一 10
//死四, 1000
//死三 100
//死二 10
//等等，当然这个分数对于双方角色而言是相反的
var leaf = {
score: _e,
step: step,
steps: steps
}
return leaf
}
var best = {
score: MIN,
step: step,
steps: steps
}
// 双方个下两个子之后，开启star spread 模式
var points = board.gen(role)
//generator顾名思义，就是在每一步生成所有可以落子的点。
//并不是所有的空位我们又要搜索，很多位置明显不合适的我们可以直接排除。
if (!points.length) return leaf
for(var i=0;i<points.length;i++) {
var p = points[i]
board.put(p, role)
var _deep = deep-1
var _spread = spread
var _steps = steps.slice(0)
_steps.push(p)
var v = r(_deep, -beta, -alpha, R.reverse(role), step+1, _steps, _spread)
v.score *= -1
board.remove(p)
// 省略剪枝代码
}
return best
}
Alpha Beta 剪枝算法
Alpha Beta 剪枝算法是一种安全的剪枝策略，也就是不会对棋力产生任何负面影响。它的基本依据是：棋手不会做出对自己不利的选择。依据这个前提，如果一个节点明显是不利于自己的节点，那么就可以直接剪掉这个节点。
假设方框是极大值的节点，圆是极小值的节点，B的值为18，D的值为16，而C是极小值，因此C<=16，A取max(B,C)，因而没有必要考虑C的其他子节点。
很显然，这个剪枝的效果是取决于节点的排列顺序的~
如何排列节点，排列需要考虑的着子呢？
那么如何排序呢？就是给所有待搜索的位置进行打分，按照分数的高低来排序。注意这个打分算法是对某一个空位进行打分，和对整个棋盘进行打分的 evaluate 函数是不一样的。不过打分的基本原理是相同的。具体就是根据这个位置是否能成五，活四，活三等来进行打分。
启发式搜索
启发式搜索用于上面说过的每个位置的打分，是根据五子棋的经验来实现的。
迭代加深
迭代加深的优势
迭代加深就是先算4步看能不能赢，不行的话再多算算。
迭代加深可以在找到最优解的同时，只增加非常小的额外时间开销，很多时候甚至可以减少开销。假设我们平均一步 50种选择，那么可以证明，4层搜索只需要6层搜索 1/2500 分之一的时间，所以我们额外进行的浅层搜索即使全部没有找到结果，也额外增加了可以忽略不计的时间。另外很可能浅层搜索就能找到最优解，此时可以极大提升效率。
相比之下，如果是搜索到全部最高分解再比较路径长短，时间复杂度会成倍增加。
Zobrist 置换表
关于五子棋的主要思路就是这样了，具体细节如两个评估棋面、着点分数的函数得根据实际设计。
Zobrist 置换表相当于对于计算出来的决策树的保存。具体详见这里
