计算机围棋博弈中模式的表示和提取.pdf

《计算机围棋博弈中模式的表示和提取.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1420cr7中国机器博弈学术研讨会论文集‘计算机围棋博弈中模式的表示和提取李文峰，余平，刘知青(北京邮电大学北邮一九鼎计算机围棋研究所，北京100876)摘要：由于围棋博弈复杂度，围棋博弈中的模式是提高计算机围棋博弈水平的关键之一。．本文结合专业围棋选手的经验，讨论了计算机围攀博弈中模式表示的基本要素，描述了一种基于Ⅻ几的系统化的围棋模式表示方法，并讨论了自动化围棋模式提取方案中的潜在问题及其潜在方法。关键词：围棋博弈；模式表示；模式提取电脑围棋起步于20世纪60年代，zo陆st和Rvder在他们的博士论文中都涉及到了围棋博弈程序，前者的方法是

2、基于模式识别采取相应的着法。后者则是基于博弈树搜索，评估不同下法的盘面结果，从而找出最佳的着法。这两种方法当时都已在国际象棋程序上得到了应用，并取得了良好的效果。现在计算机围棋博弈中采用的方法也基本没有超出这两种方法的范畴，但是单独采用某一种方法已很难达到较理想的效果，因而多是这两种方法的综合应用，只是在侧重点上各有偏颇；对模式的忽视将容易导致搜索空间的增大，而围棋棋盘上过大的搜索空间则是计算机所不能忍受的；至于只应用模式而不采用搜索则未免不现实，因为考虑到围棋的复杂程度，想搜集全可以覆盖到全部可能的模式未免不现实，而模式无法覆盖到的情况则需要搜

3、索进行补充，并且在模式的匹配过程中也是离不开搜索的。围棋只黑白两个颜色，两种棋子，也正是这种’简单造就了其近乎无穷的复杂。既是这种简单也是这种复杂造就了围棋与国际象棋的不同。在国际象棋中各个棋子各司其职，具有很高的独立性，既作为-．个独立的个体又和其它棋子相配合在整盘棋中发挥着重要作用；而围棋则略有不同，尽管每个棋子各自也都发挥着一定的作用，可是每个棋子的真正价值则可以说是完全依赖于它所处在的位置，它周围的环境，更确切的讲，就是通过与其它棋子的配合并且处在一个整体的环境中才能发挥作用。围棋棋子间通过配合来形成各式各样的形状，来对整盘棋产生影响，这

4、个形状称之为“模式”。故而，在围棋中与国际象棋中的棋子相对应的不应该是一个个的棋子，而应该是模式。而进一步扩展到整盘棋则是通过模式由简单到复杂一层层组合而成的。本文结合专业围棋选手的经验，讨论了计算机围棋博弈中模式表示的基本要素，描述了一种基于Ⅺ帆的系统化的围棋模式表示方法，并讨论了自动化围棋模式提取方案中的潜在问题及其潜在方法。1模式1．1模式背景假设一个人要与其他人争夺一个位置，那么他就需要使用这些关系形成一个同盟，从而拥有战胜对手的力量，因此双方增强自身并削弱对手的手段就是，切断对方的联系并且保持自己的连接，围棋的基本原理大体如此。如果想瓦

5、解对手的同盟，显然需要在不是很紧密的关系上着手比较容易，因为对于连接强度太高的关系，几乎是没李文峰，等：计算机围棋博弈中模式的表示和提取15有可能切断的，而从另外一个角度来说i连接关系越弱，往往对目标的实现帮助也越大。与象棋的线性推理相比，围棋这种交织的关系网络更加难以描述。，制作计算机围棋程序，不使用这些连接关系来构造基本模型是不能长远发展的。国外研究者大多采用势力影响算法来模拟这个连接图，但是这种做法的效果是不稳固的，无法在此基础上架构更为高级的模型。在这个系统中，围棋的模型层次如下，棋子毒(通过连接关系)构造为棋块一棋块具有的基本属性一包围

6、和切断一局部棋块的死活计算一全局局势判断一搜索最佳着手。模型的每个层次，都可以采用多个模式的组合来实现的。所谓的连接关系，就是文中所说的模式，使用它就能把棋盘上零散的棋子连接在一起，当输入足够多的模式就能够构成完整的棋块模型，那么这样的模式是否是无穷无尽的呢?目前我们的研究发现，职业棋手90％的下法，使用的’连接关系模式不超过几十个。更多的形状则由这、几十个基本形状组合而成，即使估算特定棋形的数量有数十倍之多，围棋全部层次的模型也只需要几万到几十万模式就可以构成，如同人类的语言，核心词汇也许不超过几千，加上各种变形也就是几十万，这也许表明了’自然

7、语言与围棋有可能具有相同的结构。1．2模式包含的元素在系统关于模式的描述中，一个模式包含如下几个必须的要素：黑白子，模式所占据的空间，原点，锚点。1．2．1黑白子黑白子作为围棋中最基本的元素，通过其不‘断的组合，描述了棋盘上发生的一切故事，因而要描述围棋，黑白子可以说是必不可少。然后有了黑白子还远远不够。为了表示一个模式，不可能把整个棋盘全部表示出来，因为这样的话则显得多余，而且也丧失了很多灵活性。而模式本身又是一个有．一定抽象度的东西，如果把模式钉死在棋盘的某个位置上，也就使其丧失了抽象性。因而，就需要把模式从棋盘上提取出来，在·个模式中，黑白

8、子是主体，有了主体还不够j还需要环境，如果放在整盘棋止的时候，这个环境就是整个棋盘，而提取出来时就需要把黑白子周围的空点也包括在内。1．