电脑围棋中的人工智能技术

来源：互联网   发布日期：2011-09-19 10:47:57   浏览：8938次  

2.3 目标状态
围棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地：建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态，因为实地的获得是靠慢慢积累起来的（不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上）。由于在接近终局前很难精确地计算实地，故启发式估计用的较多。这样的启发方式通常要归并组件和指示领地安全潜力的（例如死活组和影响）次要目标（例如国际象棋里的材料优势）。
当对局双方依次弃权时结束。棋手通常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上，要确定对局结束（即何时弃权）是相当困难的。人们下棋，计算结果时如果遇到有关死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中，如果程序出现算法不能解决的得分争执，计分就由组织比赛的人员来做。

2.4 评估函数
在判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来获得的。有意思的是，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争中是可活的（即它必须赢得打劫来使自己活下来），就必须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。
评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一个绝对的死活回答可能超出了战术或死活搜索的范围。
从复杂的类型分析看，由一个绝对位置来确定赢家是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）。
盘面（例如棋块、敌方）表示的对象属性包括它们的死活状态（也指安全性或生命力）、实地数、眼数和势。某些情况下这些属性值由战术搜索决定。
MFG的表示方式中一些组件由评估函数控制（例如块、联接、眼、实地和势）。Go4的盘面只是简单的由评估函数（例如块、眼、安全性、实地）来表示。

3.2 候选走法
通常，由模式或更常见的是由基于规则的专家系统产生候选走法。走子产生过程最后是通过（线性的或加权求和的）相加棋盘上所有点的参考值为合适的走法给出一个分值。全盘评估一般选最高得分点作为下一手的落子点。
不同程序由全局水平变量估值得出的候选走法数也有所不同：GI（陈，1997）有12手，MFG有10手，而Go4至少有50手。程序变量保持的规则数： EX大约100，MFG大约200。GI含有约20个走子算法，它们或者基于模式库，或者基于面向目标的搜索，或者基于启发式规则（可能含有大量的规则）。
模式通常既包含低级信息也包含高级信息。低级信息与黑白子的位置有关，那些点必须是空着的，已经被子占据的点不在此列。高级信息则是关于气的数量、安全性、眼位和领地的信息。模式匹配不仅与子的配置匹配，而且跟包含在子或串里的任何高级需求有关。大量的模式匹配计算是很耗时的，并且由于棋盘上的对称性而变得更复杂。这已经导致了发展特殊算法来克服与模式匹配有关的问题（比如MFG的哈希函数，EX的串匹配）。
知识以不同的方式组合到程序当中：一些程序几乎完全依据第一原则工作，另一些根据存储的模式匹配当前位置。不同的程序其模式数量相差很大：Go4约有15 个；MFG大约2000个；而EX则在3000个左右。有些程序也包含开放的走法模式数据库（定式）（例如，MFG含有约45，000个定式模式）。

3.3 目标
多数情况下，大量的实地比起少量的实地加相应的外势更合乎需要。尽管有时也存在着实地和外势间地转化（特别是在布局和中盘阶段）。然而，虽然实地的启发式评估是可能的，实地依然不总是形势优劣最好的指示明灯。在对局的早期阶段，占有大量的实地可能表明一种过于集中的形势，从实地安全的角度看，这样的形对对局的后面阶段或许是有害的。开局造就最大可能的势而不是实地通常导致局末对更多实地的追求。外势是可能用来确定形势优劣的子目标的一个例子。
用来确定形势优劣的大量子目标的相对优先度在电脑围棋中看来没有一致性可言。典型的块和实地的死活状态（安全性）被包含在目标和子目标中。在手谈中，战术手段是重点，而MFG集中在联接性、眼和块的生命力。Go4则好像完全贯注于联接性上，几乎任何东西都是从联接概率图上派生（直接或间接地）出来。

3.4 评估过程
评估围棋的形势是个很慢的过程（例如，比起国际象棋程序的每秒10,000-100,000次评估，MFG是以低于每秒10次的速度完成对整局棋不超过 10,000种全盘形势的评估）。由于比赛时间的限制，程序执行的全局评估数通常是有限的（例如，MFG在选择下一步时全局的评估数不超过100）。
Go4的50种候选走法中每一个都通过一个六步的过程来评估：1.启用一个联接概率图。对于盘面上的每一个黑子和白子，计算它与32个（实际的或假定的）友好点的联接概率（要处理大量的数据）。确定联接性还要用到战术搜索；2.棋块由联接图和战术搜索来确定；3.眼位（利用模式）由联接性和棋块数据确定； 4.眼位的数量确定了棋块的安全性；5.每个子的安全性按联接概率图的比率辐射并在所有棋子上相加；6.黑白领地由辐射值估计。黑白领地的差别作为一个给定走法的评估结果返回。
MFG的评估是个多步过程，并且在很大程度上依赖于战术搜索。战术搜索检查所有少于四口和一部分有四口气的串以确定是不是死串。战术搜索也被用来鉴别联接性和眼位。在这一环节，串组成了棋块。棋块的生命力由基于死活的考虑（例如，联接、眼位等）决定，并且用来确定黑白子在盘面每个点（在-50至+50的范围之间）行使控制的总量统计。在总和每个点的值的基础上确定领地，给出最终的估计值。多达6轮的静态搜索可以被执行，有时用一个特殊的模式集找出能使形势稳定下来的局部走法。
GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法，它就被选为要走的下一步。如果候选走法中有些走法的得分大致相等，靠评估带来方便的全局搜索决定选择走哪一步。评估时，敌子的安全性是为盘上每个点指定一个在-64到+64之间的黑白控度的基础，所有点的分值加起来返回一个评估值。全局搜索检查的步数不多于6到7步，搜索的深度不超过6层。

赞助本站