浅谈六子棋程序设计的两大难点

文:z(悉尼)



        六子棋程序虽然起步晚,但在近两年内已经取得不小进展。由台湾国立交通大学吴毅成教授、学生張修逞和方炯珽开发的“交大六号”(NCTU6)在荣获第11届电脑奥林匹亚竞赛六子棋冠军后,又在首次公开人机对战中以44胜4败的骄人成绩凯旋而归。台湾东华大学的刘思源和颜士净开发的X6则后来居上,夺得今年电脑奥林匹亚的六子棋比赛桂冠。然而目前顶尖的六子棋程序尚还无法与人类高手匹敌。这与六子棋本身的复杂性不无关系。
 
        复杂性的根源在于六子棋庞大的分支因数(branching factor)。由于除第一步外每步需要布两子,若不剪枝的话,分枝便会逾万。如果像很多国际象棋程序那样(平均分枝约35)生成所有可能棋步的话,将会严重限制搜索深度。所以forward pruning似乎是不可避免的。以X6为例,它只考虑离已有棋子不超过3格的落点。NCTU6的move generator也是类似:首先快速选出单下一子的前n个局部最优落点,接着对这些情况分别选出前m个第二子的局部最优点,然后对候选棋步再作一次排序并进一步搜索前k个分枝。
 
        当棋局中出现冲四、活四等迫着(threats)时,搜索分枝便非常少了。以活四为例,可行的应着只有三种。这时采用迫着搜索(threat-space search)便可以在较短的时间内分析搜索深度很大的连杀序列──通常称作VCT(victory by continuous threats),又称VCF(victory by continuous fours)。在六子棋比赛中,十步以上的高深度连杀并不罕见。为了进一步加快迫着搜索的速度,有时可以牺牲一些搜索精度,靠较小的false negative换取大幅度的性能提升。比如,让防守方分别用两颗子挡住活四的两端,把三种可能降为一种。如此一来,只需要搜索进攻方的分枝即可──adversary search被简化为了single agent search,效果类似于null-move pruning。当然,这样过于保守的分析会错过不少连杀机会。实际应用时应当在精度和速度间寻求平衡。
 
         棋局评估(evaluation function)也是一个难点。一种简单的策略是选出一组容易快速计算的特征量,例如活二数、眠三数、局部棋形等等,然后加权求和。权重的选择除了靠手工调整外,也可以考虑使用reinforcement learning、genetic algorithm等方法进行自动学习。另一种广受围棋AI青睐、但尚未被六子棋界采纳、可能会颇为有效的方法是monte carlo simulation。它的优势在并行化计算时可能会更为明显。
arrow
arrow
    全站熱搜

    connect6 發表在 痞客邦 留言(0) 人氣()