继续之前的造轮子计划。本来只是打算做一个简单五子棋的和妹子一起玩,后来发现做个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对战有种奇异的快感有兴趣的童鞋也可以玩一玩哦