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

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


    一个静态死活评估器在多步过程中确定每个块的死活状态,而没有以从简单的结构中进一步产生复杂结构的方式向前搜索。静态死活评估器使用“战术家”并且为棋块中的每个合适的串至少调用两次。 
    死活搜索是直接面向目标的(例如,拯救或杀死一个棋块)。如果在一个特定点没有获得搜索目标,合适走法由死活搜索引擎自身的走法器产生,并继续搜索。为了 在一次死活搜索期间确定目标是否已经达到,静态死活评估器在每个点被调用。死活搜索引擎使用深度优先α、β搜索,每一个特定的枝的搜索深度由启发式决定。 搜索树的大小是强制性的,通常可以达到7层的深度和20个节点的大小。死活搜索是很慢的,整棵树要装到缓存里以减少花在重复搜索上的开销。死活搜索的缓慢 也意味着它不会被用在全盘评估中。  [Page]
 
3.7 势函数 
    势是一种围棋概念,它表明了每一方棋子对空点的最大可能的控制潜力。通过确保开局时子力投放不过于集中,棋手在后面的对局中将取得最大限度获得领地的机会。 
    势通过势函数建立可计算模型(Zobrist,1969;Ryder,1971;Chen,1989)。通常,子力以盘上每个点的辐射影响值的和(黑白子 辐射正负相反的值)对周边的点施加辐射影响(MFG的黑白子的势是分离的)。子力辐射按距离函数递减:GI是2的距离次方分之一,MFG是距离分之一。但 过于依赖势函数的程序表现不佳(EX和Go4不再使用势函数,尽管Go4的辐射函数很象一个势函数,EX采取另一些措施,象同色点或可联接点的距离)。 
    应用势的启发包括确定联接性和敌子(GI),以及确定领地(MFG)。MFG的块势初始值依赖于块的强度等,强壮的块比弱块或将死的块辐射更大的影响。这 也意味着死块辐射负影响等,因为它对敌方有利。在MFG和GI中势都没有通过子辐射;MFG也没有通过敌链辐射影响。 
 
4. 讨论 
    当前的围棋程序都使用了一定量的“知识”。由于建立在设计者下棋成功经验的启发之上,每个程序都可被看作一种(可能是含蓄的)围棋理论的一次以经验为依据 的实验。围棋理论成立的关键要靠数据结构的选择,因为它们决定了编码不同类型知识的难易和应用这些知识的计算开销。随着程序员同时在围棋和电脑围棋方面获 得技能,程序会有发展(例如,在过去的十五年中随着 Fotland 的棋力从15级发展到2段,MFG也增长了棋力并且代码长度增加到目前的4万行)。程序的性能由它最弱的部件决定,而向程序增加新知识的难易是提高程序性 能的重要部分。 
    由此可见,电脑围棋领域在关于怎样构筑一个围棋程序或者指配不同围棋知识的优先性(例如,Go4注重联接性而MFG注重死活)方面还没有一致性可言。必须 提到的一点是:关于人类是怎样下围棋的至今也没个一致的说法,这是目前认知科学研究的一个课题(见Saito & Yoshikawa,1977,作为回顾)。这个领域的任何进展都会对围棋理论有个直接的促进,并可能导致电脑围棋程序算法的改进。 
    本文对目前比较成功的几个程序作了比较。通过这项工作,我们在博弈树搜索的框架内分析了围棋,并通过对示例电脑围棋编程的观察把有关的问题暴露出来。这种 困难在电脑围棋领域是常识,但在更为广泛的人工智能范畴却很少被人们认识和接受。围棋全盘评估需要确定棋块的死活状态,不管是通过死活搜索还是战术搜索, 评估是非常消耗计算资源的。缺乏快速有效的评估函数是电脑围棋遭遇的一个基本问题,并且和巨大的树枝因素、用户和电脑比赛的实时需求(一般来说,相对于国 际象棋的每秒180步围棋每秒只有24步)等搅和在一起。因此,计算机国际象棋通常要用到的完全广度博弈树搜索在电脑围棋里是行不通的


 

相关文章

文章评论