围棋中电脑人智能技术

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

 电脑围棋中的人工智能技术   
摘要:本文通过研究几个最出色的电脑围棋程序,从认知科学的角度介绍了电脑围棋,并特别针对电脑围棋编程人员(或有意投身于此的程序员)揭示围棋作为一个 认知科学研究领域的日益增长的重要性。对手谈,Go4++,Many Faces of Go,Go Intellect 和Explorer几个目前最优秀的电脑围棋程序,我们概括了它们用到的人工智能技术,必须面对的关键性挑战和博弈树搜索中牵涉的问题,以此揭示为什么计算机国际象棋技术不能被很好的移植到围棋领域。   
奇境小站 (WonderLand)1998.06 -- 2000.06  Webmaster: Kerry Jia 
                           电脑围棋中的人工智能技术       作者:Jay Burmeister 和 Janet Wiles 
澳大利亚昆士兰大学心理学与信息技术学院 jay@it.uq.edu.au http://www.psy.uq.edu.au/~jay/ 翻译:Lookingfor 
 
1. 挑战围棋的程序 
    作为正规游戏之一的围棋领域,过去即便是应付一般的人类棋手计算机也难以有所作为。几个一年一度的电脑围棋赛事,如FOST杯赛为第一名提供2,000,000日元奖金,台湾的应氏基金为第一个能在分先七番棋中击败顶尖职业棋手的围棋程序许诺40万美元的奖金。 
    最早以围棋为对象把电脑围棋纳入研究工作是在1962年,尽管第一次由程序下一盘完整的棋是发生在1968年(Zobrist,1970)。随着电脑围棋 赛事的举行和第一个商业程序的发放,电脑围棋作为一个领域于80年代被正式创立,并在90年代变得兴旺起来。目前活跃在电脑围棋竞赛中的顶尖程序有 Explorer,Go Intellect,Go4++,手谈和The Many Faces of Go,它们的水平大致在4-8级之间。 
 
2. 围棋中的博弈树搜索 
二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准博弈树搜索由四部分组成: 
1.状态表示,2.候选走法产生,3.确定目标状态,以及4.一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法(比如α-β)增强了程序的表现。 
    博弈树这条途径很成功,如我们在国际象棋程序中所看到的,基于典型的完全广度α-β剪枝博弈树搜索的程序甚至击败了世界冠军。这一节我们从透视电脑围棋的角度检查博弈树搜索的四个构件。 
 
2.1 状态表示 
    从完全信息的角度看,围棋盘面有19X19的3次方格,每个交叉点要么空要么被黑子或白子占据。状态空间的大小(例如可能的位置数)是3的361次方(或 10的172次方),相比之下国际象棋大致为10的50次方而Othello棋为10的30次方(Allis,1994)。另外,博弈树的大小(例如可能 的博弈数)在10的575次方和10的620次方之间,对比国际象棋的10的123次方和Othello棋的10的55次方(Allis,1994)。  [Page]
    由于空间的组合尺寸,用19X19格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。接下来的层面的描述是把正交的邻接棋子组成串(或 链)。所有的程序把串搜集到更大的单元,然而没有通用的处理方法——即便是对专业棋手来说——把串组合到更大的单元中。依靠他们的围棋理论,程序员开发了 他们自己的启发式,当串有效的连接在一起时用做评估之用(叫做模糊组或块)。 


 

相关文章

文章评论