继续之前的造轮子计划。本来只是打算做一个简单五子棋的和妹子一起玩，后来发现做个AI也挺有意思。就开始工作了。 本次的五子棋用纯HTML5实现。AI使用了简单的决策树和Alpha-Beta剪枝。 本来想使用ClojureScript作为AI的脚本，但是后来发现ClojureScript的性能差不多只有原生Javascript的1 / 100。 于是放弃，使用了原生的JS。

Demo与Code

Zhming

显示: HTML5 Canvas

显示部件使用了很简单的Canvas去画。关于悬停选框，使用了双层Canvas来实现。不得不说Canvas的性能确实相当不错，比起直接的DOM操作在移动端效果要好太多了。

人工智能：

AI部件实现了一个无状态的AI，付出了性能作为代价增加了开发速度哈。本来是想试试ClojureScript的，结果性能让我跪在地上了。即使是使用了advanced的编译，依然慢的不得了。虽然总有人说clojure好好利用可以很快，但是我认为开发者不应当承担这种无意义的优化成本。 于是我就投奔了JS。本来以为用JS代码会变得很长，结果也就100+行。摊手。。。。

这里人工智能的原理非常简单。核心函数有两个。

  1. chance函数，根据当前棋盘状态和当前玩家推算出一个优势值。其基本原理就是对于不同的串算不同的分数。譬如我方活4子串对应x分，我方半活4子串对应y分，敌方活3子串对应z分。之类的。在分数设计中需要遵循以下几个原则。
    • 分数应该分等级。及 p1, p2, p3...
    • 因为等级存在优先关系，譬如一个活4子比数个活3子要珍贵的多，所以等级关系必须清晰。也就是，p(i) >> p(i-1) 或者说 p(i) > N * p(i-1)，上级要远大于下级。
    • 等级必须考虑先后手问题，同样的子数，先手（未下）比后手（已下）优先级要高。

  2. think函数，能够递归的进行决策树推算，并且根据父子兄弟节点的chance来进行剪枝。这个函数的参数是当前棋盘，当前玩家，递归层数，返回值是[当前玩家最大胜率，对应步]，其基本逻辑如下：

     （假定当前玩家为A，敌方为B）
 A 遍历所有步。
 针对每一步，都更新棋盘后调用B的think，并传入减1的递归层数。
 选取某一步，这一步使B的胜率最小。这一步就是答案。

除去这些之外，还有一些优化的要点:

  • 减少遍历区域，只选择已下位置的相邻位子作为候选。
  • Alpha-Beta剪枝。基本原理很简单：当A进行遍历时，例如遍历位置1得出了B的胜率为c，那么再遍历止位置2时，就告知B的think，如果计算过程中胜率大于c，就剪枝。

总结

最后的结果是，这个AI可以在1秒的时间内递归3层，跟网上看到的一下数据差不多。 跟网上的一些别的AI下过，胜率不差。 跟自己做个AI对战有种奇异的快感有兴趣的童鞋也可以玩一玩哦