对于五子棋引擎的设计者,Allis的“Searching for Solutions in Games and Artificial Intelligence”一文是很值得阅读的。这篇文章介绍了终结原始规则下的无禁手五子棋的两个核心技术——Proof-number Search (Pn-search)和Dependency-based Search (Db-search)。然而原文为了表达上的细致和严谨,写得比较长,读起来比较费时间。因最近在为Yixin增加独立的算杀模块,翻阅了一下曾经的阅读笔记,感觉这份笔记无论对于初次阅读者、还是文献回顾者都是有一定帮助的,所以决定分享一下这份总结。由于Allis的这篇文章有不止一个版本,为了引用的准确,总结中以这个版本为准。

对于这篇论文的阅读(和讲解),不建议按照顺序阅读,而建议先看例子。以下是总结原文。

Pn-search

例子: 23页下~25页上

伪代码: 25~28页

优化:

  1. 已经solved的子树在update后即可被删除。(29页)
  2. Pn^2-search:思想为建立两层树,上层是N个节点的树,对于树的每个叶子,对应一个即时建立即时删除的N个节点的树,可以在对效率影响不大的前提下减少空间。(空间是pn-search的1/2次幂。(30页)
  3. Update的过程中,遇到的第一个proof和disproof number都未改变的节点停止更新,并且下一轮的迭代从这个节点开始。(32页)
  4. 当一个节点被建立时,其proof和disproof number的初始化可以通过知识给定,比如若可以计算到该节点的儿子数(或约数),则可以令其proof number为1,disproof number为儿子数(或约数)。(34页)实际上还可以做其它方面的初始化设定,比如37页上半部分的例子。37页下~38页上给出了另一个例子,是对于gomoku的,可以用层数(ply)的一半来初始化(实际上是1+d/2取下整(148页))。论文中提到对于pn-search初始化问题仍缺乏合适的理解。(39页上)
  5. 置换表用于解决实际是DAG而非Tree中的pn-search问题,一种practical的做法是将DAG看做树,standard的做法是利用置换表解决该问题,论文提到经验上二者效果差不多。(40页)

Db-search

例子: 85页下~88页上

伪代码: 88页~90页

Solving gomoku

Db-search部分优化:

  1. global defensive:

    a) 在对方第i步棋后,目标是占有进攻方形成threat aj的区域,或我方应有的reply dj,使得j>=i。
    b) 在检查中,不再做攻方的global defensive检查。
    c) 只检查更高的威胁。
    (137页)
    对于138页中28 squares的解释:1是7,源于_ _ _ X X _ _是7格区域,其它解释相似。
    
  2. 如果在一次db-search中已经找到的potential winning threat sequences超过了T(也就是说明前T次都被找到了global sefensive),则终止。Gomoku中经验值为T=10。(140页)

  3. 如果防守方有category为c1的威胁,则攻击方的威胁c2必须小于c1。此优化在检查global defensive时需关掉(显然)。(140下~141上)
  4. 只有在fT2,g7不可用时才使用fT3,g6。(141页)

Pn-search部分优化:

  1. 置换表,注意还要检查8个同构形。(143下~144上)
  2. 限制黑棋(进攻方)的儿子数为10,排序标准是4分(可形成活三且有2个防点),3分(可形成活三有3个防点),2分(活二),1分(跳二)。(144)
  3. 相关区域:为了使得一个threat sequence可以对付多个move(主要是战场外的着法),先make一个null move,然黑棋(进攻方)找到一个threat sequence,然后根据此sequence定义相关区域。

    a) 定义:一个点属于相关区域,当且仅当其满足以下至少一点:(1)是威胁序列中的点(在line内即可,类似_ _ _ X X _ _的7格区域所有空点都是)。(2)与威胁序列中的白棋和原有白棋可形成新的威胁的点。(146)
    b) 在相关区域被定义后,对于区域中的一个点s,如果s落子后通过db-search判断确实没有对应threat sequence,则将s加入儿子,否则,利用找到的threat-sequence可以按照上述方法得到另一个相关区域,而这个相关区域与原相关区域的交作为新的相关区域。(147)
    
  4. 对于一个局面,在棋盘上的棋子大于等于9个的前提下,如果进攻方(黑棋),在白棋make一个null move后仍没有threat sequence,则将这个局面定义为白棋胜。(147)

  5. Proof number和disproof number的初始化均采用1+d/2取下整。(148)