略笨的五子棋AI


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

用WebGL实现Game of Life


最近有些空闲时间,于是打算开始造轮子计划,正巧在进行GPU加速最近,就写了一些小项目来练手。顺便进行了诸多的GPU加速实验。其中之一就是Game of Life也就是生命游戏,wiki页面在此,就不赘述介绍了。

Demo与Code

使用方法很简单,滚轮缩放,拖动复活cells。纯WebGL,没有任何第三方依赖。

Zhming

阅读全文 Read more ->

FreeType简易教程


最近接触了一下Freetype,投放了产品后对此库略懂了一二。犹豫了一下要不要写个教程,想想也没什么关系。虽然线上已经有不少的Freetype的教程了,但是他们都,太不友好(丑丑丑)了。于是,进入正题

为什么要Freetype?

FreeType是一个字形图glyph image产生工具,整个库的主要功能点集中在以下两点:

  • 解析几乎是所有的字体格式,例如常见的ttf,otf
  • 根据输入的单个Unicode返回该字的glyph也就是字形图。

其不包括或者说支持并不完善的功能有:

  • 颜色。
  • 处理字符串。

所以也就是说Freetype的基本功能就是把字变成图。最后怎么处理文字,还是由开发者来实现。

我要写什么

在这个教程里我会简单的讲一下如何使用该库来实现以下几个功能。

  • 输出字图
  • 渲染一个句子:调整字色,字号,字间距(tracking)
阅读全文 Read more ->

关于Zhming的新博客


Zhming

说起来,这是我第三次制作自己的博客了。第一次用的是Wordpress,第二次用的是纯Restful的Backbone.js + Clojure。第三次最为朴素,使用了简简单单的Jekyll + Disqus。第一次博客是因为好玩,第二次博客是想用潮流技术,第三次是想认真写点内容。我相信技术的转变这也标志着自己心态的变化,能够更清晰的看待事物的本质。也希望自己能坚持维护这个博客啦。

Jekyll制作博客的体验非常棒,尽可能的避免了开发者重新造轮子的现象。花了一两天迅速开发完前端,就可以有一个精简好用的博客了。在评论部分使用了Disqus的插件,简单美观好用并且还安全。

近期的工作主要集中在一个渲染引擎的开发上,希望能加快进度,提炼出来的值得分享的经验会尽量分享的。毕竟从我接触软件业的那天开始我就从开源中受益,总得尽量回馈。Cheers!