现在的位置: 首页 > 综合 > 正文

【五子棋AI循序渐进】重新整理

2013年06月21日 ⁄ 综合 ⁄ 共 758字 ⁄ 字号 评论关闭

        这些天重新整理了一下整个程序,头发都白了几十根。对整个程序进行了初步的重新设计,现在可以2秒内搜索8层,搜索速度仅仅有七八千(棋力比以前要高,执黑执白都基本能和F6下到40手以上,呵呵,不过输多。可能代码中还有某些错误导致极少数情况下棋型识别或评价不正确,我还没找到)。涉及到前面的几个话题,重新认识一下:

1、棋盘表示:使用前一篇提到的原理,逐个手工矫正9长度棋型两万来个,并由它生成了5-15长度的其他棋型,但是因为使用内存和初始化速度的原因,没有生成9以上的XML,只保存了5-9的XML,9以上的进行计算。这应该是整个程序速度限制的最大原因了。

2、局面评估、走法生成:这都是由棋盘表示法决定的,因为我们有冲棋分值,所以很容易计算每个点的得分。局面评估只需要根据冲棋值和作差计算。

3、空招剪裁、静态搜索、冲棋延伸技术:空招剪裁、静态搜索现在被舍弃。原因很简单,因为五子棋不会出现下一步棋之后评价降低的情况所以不用空招剪裁。因为采用冲棋延伸技术后,完全可以到达胜利局面或相对平静局面(没有冲棋局面),于是也不使用静态搜索。冲棋延伸技术还是使用原来的代码。但是现在在思考这样一个问题:程序往往可以查找三十甚至六十步的冲棋(冲棋延伸对搜索速度的影响较小相对于贡献完全可以忽略,而且根本就用不到神马连冲判断),所以应该改变代码使得置换表正确记录计算过的延伸步)。

4、置换表:采用了两组置换表,其实原来有7组,但是因为内存溢出啊,无奈只好保留了2组。原来的7组有一组是局面置换表另外6组分别用于10-15长度棋型,速度提升非常多(十几倍),但实际上它们只是局面置换表的补充,所以最后归并到一起并只用了很少的一块内存(1<<18)。

现在代码中还有一些小问题,等修复之后、更新置换表算法完成会公开这个版本的源码。

抱歉!评论已关闭.