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

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


    另外,恰当层次的表示能改变对运行时子任务的依赖,例如,战术分析,死活分析,或实地评估。 
 
2.2 走子 
    棋手在禁止自杀和同型反复(劫)的规则限制下轮流把棋子投放在空的交叉点(包括角和边)。象国际象棋一样,围棋在给定位置的上下文中只有所有合法走法中的 一部分是有效的。围棋的平均分枝因子是很大的,大约是国际象棋的六倍(200对35,Burmeister & Wiles,1995)。 
    注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如,直接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。 
    实际的走子是个复杂的问题:参见3.4部分。 
 
2.3 目标状态 
    围棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地:建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态,因为实地的获 得是靠慢慢积累起来的(不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上)。由于在接近终局前很难精确地计算实地,故启发式估计用的较多。 这样的启发方式通常要归并组件和指示领地安全潜力的(例如死活组和影响)次要目标(例如国际象棋里的材料优势)。 
    当对局双方依次弃权时结束。棋手通常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上,要确定对局结束(即何时弃权)是相当困难的。 人们下棋,计算结果时如果遇到有关死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中,如果程序出现算法不能解决的得分争执,计分就由组织比赛的 人员来做。 
 
2.4 评估函数 
    在判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的,并且是典型的通过战术搜索(参见3.5部分)或死活搜索(参见3.6部分)来 获得的。有意思的是,另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势:如果要一个棋块在劫争中是可活的(即它必须赢得打劫来使自己活下来),就 必须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势,打劫分析会变得更复杂

评估的结果有时不确定,因为明确的死活定义在受限的战术搜索里也许是不可能的,即一个绝对的死活回答可能超出了战术或死活搜索的范围。  [Page]
    从复杂的类型分析看,由一个绝对位置来确定赢家是P空间难题(Lichtenstein & Sipser,1980),决定一个棋手能否左右输赢需指数时间来完成(Robson,1983),由此也就不奇怪要用到启发式了。这些理论结果显示不存 在从一个绝对局势出发决定领地结果的多项式时间算法。 
 
3. 参赛程序里的博弈树搜索和人工智能技术 
    当前活跃在各电脑围棋赛事里的程序有Martin Muller(1995)的Explorer(EX),陈恳(陈,1989;1990;1992)的Go Intellect(GI),Michael Reiss 的Go4++(Go4),陈志行的HandTalk(HT)以及David Fotland 的Many Faces of Go(MFG)。针对第2节讨论的博弈树搜索和围棋专用的人工智能技术:战术搜索,死活搜索和势函数,我们报告这些程序的细节。 
 
3.1 位置表示 
    所有的程序都有子、串、块的表示,确认串属于某个组的典型方式是采用基于模式的启发来确定串与串之间的关联性。敌方(或块)表示也被用在EX和GI 中,启发式用来确定敌方的影响(GI)和领地区域(EX)。 


 

相关文章

文章评论