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

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

1、本文由qqingweihao贡献pdf文档可能在WAP端浏览体验不佳。建议您优先选择TXT，或下载源文件到本机查看。１４２０ｃｒ７中国机器博弈学术研讨会论文集‘计算机围棋博弈中模式的表示和提取李文峰，余平，刘知青（北京邮电大学北邮一九鼎计算机围棋研究所，北京１００８７６）摘要：由于围棋博弈复杂度，围棋博弈中的模式是提高计算机围棋博弈水平的关键之一。．本文结合专业围棋选手的经验，讨论了计算机围攀博弈中模式表示的基本要素，描述了一种基于Ⅻ几的系统化的围棋模式表示方法，并讨论了自动化围棋模式提取方案中的潜在问题及其潜在方法。关键词：围棋博弈；模式表示；模

2、式提取电脑围棋起步于２０世纪６０年代，ｚｏ陆ｓｔ和Ｒｖｄｅｒ在他们的博士论文中都涉及到了围棋博弈程序，前者的方法是基于模式识别采取相应的着法。后者则是基于博弈树搜索，评估不同下法的盘面结果，从而找出最佳的着法。这两种方法当棋子的真正价值则可以说是完全依赖于它所处在的位置，它周围的环境，更确切的讲，就是通过与其它棋子的配合并且处在一个整体的环境中才能发挥作用。围棋棋子间通过配合来形成各式各样的形状，来对整盘棋产生影响，这个形状称之为“模式”。故而，在围棋中与国际象棋中的棋子相对应的不应该是一个个的棋子，而应该是模式。而进一步扩展到整盘棋则是通过模式由

3、简单到复杂一层层组合而成的。时都已在国际象棋程序上得到了应用，并取得了良好的效果。现在计算机围棋博弈中采用的方法也基本没有超出这两种方法的范畴，但是单独采用某一种方法已很难达到较理想的效果，因而多是这两种方法的综合应用，只是在侧重点上各有偏颇；对模式的忽视将容易导致搜索空间的增大，而围棋棋盘上过大的搜索空间则是计算机所不能忍受的；至于只应用模式而不采用搜索则未免不现实，因为考虑到围棋的复杂程度，想搜集全可以覆盖到全部可能的模式未免不现实，而模式无法覆盖到的情况则需要搜索进行补充，并且在模式的匹配过程中也是离不开搜索的。本文结合专业围棋选手的经验，讨

4、论了计算机围棋博弈中模式表示的基本要素，描述了一种基于Ⅺ帆的系统化的围棋模式表示方法，并讨论了自动化围棋模式提取方案中的潜在问题及其潜在方法。１模式１．１模式背景假设一个人要与其他人争夺一个位置，那么他就需要使用这些关系形成一个同盟，从而拥有战胜对手的力量，因此双方增强自身并削弱对手围棋只黑白两个颜色，两种棋子，也正是这种’简单造就了其近乎无穷的复杂。既是这种简单也是这种复杂造就了围棋与国际象棋的不同。在国际象棋中各个棋子各司其职，具有很高的独立性，既作为－．个独立的个体又和其它棋子相配合在整盘棋中发挥着重要作用；而围棋则略有不同，尽管每个棋子各自

5、也都发挥着一定的作用，可是每个的手段就是，切断对方的联系并且保持自己的连接，围棋的基本原理大体如此。如果想瓦解对手的同盟，显然需要在不是很紧密的关系上着手比较容易，因为对于连接强度太高的关系，几乎是没李文峰，等：计算机围棋博弈中模式的表示和提取有可能切断的，而从另外一个角度来说ｉ连接关系越弱，往往对目标的实现帮助也越大。与象棋的线性推理相比，围棋这种交织的关系网络更加难以描述。，１５就需要把模式从棋盘上提取出来，在?个模式中，黑白子是主体，有了主体还不够ｊ还需要环境，如果放在整盘棋止的时候，这个环境就是整个棋盘，而提取出来时就需要把黑白子周围的空点

6、也包括在内。１．２．２原点制作计算机围棋程序，不使用这些连接关系来构造基本模型是不能长远发展的。国外研究者大多采用势力影响算法来模拟这个连接图，但是这种做法的效果是不稳固的，无法在此基础上架人们看事物有一定的视角，也就是以人自身为中心，视线向目标方向发散，形成看事物的视角。模式同样也需要一个视角；也就是需要一个指定的点；然后以这个点为中：心向周围以某种规构更为高级的模型。在这个系统中，围棋的模型层次如下，棋子毒（通过连接关系）构造为棋块一棋块具有的基本属性一包围和切断一局部棋块的则看去，这样就形成了模式的视角。而且；在针对模式进行一系列操作的时候，

7、也需要这样一个立足点，然后通过这个点来把模式钉在棋盘上，之后进行一些比较匹配的操作，对于这样韵点则称之为原点。在一个具体的模式中‘，究竟以哪一个点作为模式的原点为优，并没有一个绝对好的说法ｄ死活计算一全局局势判断一搜索最佳着手。模型的每个层次，都可以采用多个模式的组合来实现的。所谓的连接关系，就是文中所说的模式，使用它就能把棋盘上零散的棋子连接在一起，当输入足够多的模式就能够构成完整的棋块模型，那么这样的模式是否是无穷无尽的呢？目前我们的研究发现，职业棋手９０％的下法，使用的’连接关系模式不超过几十个。更多的形状则由这、几十个基本形状组合而成，即使

8、估算特定棋形的这个要根据具体模式的种类，看哪类点最合适≯?。在这个系统中主要采用两类点作为原点ｊ其一是当前这一手的落子位置