ucas某菜鸡的五子棋作业UCAS-Renju.zip

# 介绍 这学期的五子棋对我来说真是意义非凡，他驱动我从一个只是对c语言略知一二的几乎纯小白学会了很多东西，上网查资料，翻阅各种博客，提前预习一些数据结构，一个学期一大半空闲时间都花在了写五子棋，从最初的完全无从下手,到能够自己创新出一些优化的东西。 依稀记得我的五子棋第一次动起来会堵人那个晚上，内心激动无比，感觉我就是“c语言大佬”QAQ，不过后来发现其实都是bug，会堵人纯属意外。 我这学期第一个月写出了能和我这个五子棋小白对打的版本，但后续的改进陷入了瓶颈，大部分时间花在了改进时间性能，没有优化算法，最后甚至没时间仔细研究一下VCT和VCF，棋力很一般，和几个网上找到的几个AI下都是完败，为此还是有些遗憾。 最后期末比赛中决赛平局，我们双方都是黑胜白负，最后猜大小输了喜提亚军。不过和冠军在小组赛比赛时我是黑白都负，所以这个亚军一点也不冤。 参考资料： + 象棋百科全书：<https://www.xqbase.com/> + gobang：<https://github.com/lihongxun945/gobang> + 清月连珠：<https://www.cnblogs.com/zcsor/p/3383090.html> + 《PC游戏编程(人机博弈)》 王小春 # 实现的东西 本AI采用PVS改进的alphabeta剪枝算法为主干，通过启发评估早期裁剪选出每步15-20个走法实现9层搜索加15层算杀。 + PVS主要变例搜索 + 迭代加深 + 位棋盘生成走法 + 5-15长度行评分缓存 + 早期裁剪 # 未实现的东西 当初立下壮志，结果最后一个星期成了小阳人，加上最后也有点懒惰，一些已经有了思路的东西最终没有实现。 ## **冲棋点哈希表** 我预先缓存了一行最多15个棋子所有情况对应的评分，因此大大缩短了评估时间。 事实上不仅可以缓存评分，还可以缓存对应棋盘的冲棋信息，即一行哪些点可以冲棋，是活三还是冲四，如此一来在获取走法的时候也会相当迅速，特别是在已经有活三冲四的情况下，我们很多时候只需要搜索冲四活四点进行防守或反击，在五子棋中后阶段大多都是这种情况。更精确更少的走法同时也意味着更深的深度。 ## **开局库** 已经证明即使有禁手，黑棋也是必胜的。我在网上也找到了一些开局的必胜谱，但是我不知道怎么解析这些lib文件，貌似是什么静态库，虽然通过Renlib软件打开可以看谱，但是总不能纯靠手打录入这些信息吧，最后还是放弃了。 ## **威胁空间搜索** 原文应该是Go-Moku and Threat-Space Search，作者：LV Allis，H.J. Van Den Herik，MPH Huntjens，不过国内十多年前的某篇五子棋论文里面有雷同的中文版，大概就是阐述了VCT和VCF的理论基础，给出了一个找致胜威胁的具体方法。 # 一些被弃用的东西 ## **空着裁剪** 参考<https://www.xqbase.com/computer/advanced_nullmove.htm>，其实就是一步不下棋，然后给对方下，最后返回值仍然好到超过该层的beta值，说明正常下那肯定也会超过beta，那就直接返回beta。 ## **zobrist置换表** 因为刚开始没有接触哈希表这种东西，一直想不通怎么才能实现这个置换表，查了好多资料终于实现以后却发现效果非常一般，占了好几百兆也就快了20%左右，然而评价方式改为局部刷新后，存储整个局面分的置换表感觉就不太有用了，但是这种哈希表缓存的思想特别有用。 ## **历史表排序** alpha-beta剪枝的顺序特别重要，因此可以通过迭代加深获取浅层节点的历史评分对节点进行排序，为每层搜索的最好节点和beta截断节点设置一个历史分，根据历史分排序显著提高速度，实现简单效果立竿见影。不过为了早期剪枝，同时有了评分表，就放弃了这种排序，直接通过评分排序。 ## **MTD(f)搜索算法** mtd(f)和pvs都是alphabeta剪枝的优化算法，只需要加几行就可以带来一定的速度优化，不过mtd(f)要略复杂一点，并且非常依赖于每次搜索的评分期望值，因此mtd(f)耗时不稳定。据说mtd(f)在并行计算上有优势，奈何本人水平太次，看不懂c语言并行计算的部分。