围棋中电脑人智能技术(4)

时间:2008-11-21   来源:   网友评论:0   人气: 759 作者:


    MFG的评估是个多步过程,并且在很大程度上依赖于战术搜索。战术搜索检查所有少于四口和一部分有四口气的串以确定是不是死串。战术搜索也被用来鉴别联接 性和眼位。在这一环节,串组成了棋块。棋块的生命力由基于死活的考虑(例如,联接、眼位等)决定,并且用来确定黑白子在盘面每个点(在-50至+50的范 围之间)行使控制的总量统计。在总和每个点的值的基础上确定领地,给出最终的估计值。多达6轮的静态搜索可以被执行,有时用一个特殊的模式集找出能使形势 稳定下来的局部走法。 
    GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法,它就被选为要走的下一步。如果候选走法中有些走法的得分大致相 等,靠评估带来方便的全局搜索决定选择走哪一步。评估时,敌子的安全性是为盘上每个点指定一个在-64到+64之间的黑白控度的基础,所有点的分值加起来 返回一个评估值。全局搜索检查的步数不多于6到7步,搜索的深度不超过6层。

3.5 战术搜索  [Page]
    战术搜索是有选择的、面向目标的搜索,并且为一大堆目的而使用,包括确定串是死是活(Go4,MFG,EX,GI)、联接是安全的还是可被切断的 (Go4,MFG)、是否可以形成眼位(MFG)、产生候选走法(GI)和确定棋块的死活(EX)。就是在全局的水平,战术搜索也要用来做棋步产生和评 估。战术评估和全盘评估有区别,这跟搜索的目标(例如,一个串的气的数量)有关。由于时间上的制约,战术搜索通常在节点数、枝因子和层的深度上受到限制。 因此,尽管象死活这类的问题通常被认为是战术性的,棋子却可以在战略上就死去了,即使它们可能不能通过战术手段被抓获。由此,从围棋评估的方方面面看,战 术搜索只是一种启发式装备而已。 
    MFG提供了一个战术搜索操作的很好的例证(通过“战术家”):每个有三口或更少的气的串和许多有四口气的串被“战术家”检查过。每个串检查两次,一次白 先走一次黑先走。“战术家”决定一个串是否被抓(比如,即使它先走也不能活)、被威胁(比如,如果它先走则活,后走则死),或者是牢固的。“战术家”依靠 简单的启发式(例如,气数和联接性)。 
    “战术家”有两个分离的走子器;一个执行攻击走法,一个执行防卫走法。走子器建议的走法按一些规则分类,这些规则包括二次气(气的气)、切点和简单的眼 形。一旦分类,根据依赖走法分类的质量的搜索的表现,一种α-β深度优先搜索被派上用场。走子和分类解释了多数时间依靠战术搜索的原因。 
    战术搜索直接针对目标并被限制一个最大节点数。抓子时这个限制是大约100,然而当只有一步可走时就不考虑这个限制。采用这种方式,可以毫不费力地确定征 子的胜方。根据第一层走子产生赋予走法的分值,一次搜索的节点数分配到树枝中,因此不同的树枝可能在不同的深度结束。每一成功的层的枝因子被“战术家”逐 步强化;枝因子从第一层5降到第五层的1或2。 
    对局过程中,MFG作大约100,000-150,000次战术搜索,以每秒2,000-2,500个节点的速度遍历1.5-2百万个节点。平均起来每次战术搜索访问约10-20个节点,尽管由于一些搜索因节点限制而终止,许多搜索访问过节点数要少于5个。 
 
3.6 死活搜索 
    不是所有的程序都做明确的死活分析,很多程序对此使用了战术搜索。MFG用与它的战术搜索过程类似的方式作死活分析,除了它是在块上作死活分析而不是分析串。 


 

相关文章

文章评论