《围棋博弈与算法研究》由会员分享，可在线阅读，更多相关《围棋博弈与算法研究（35页珍藏版）》请在金锄头文库上搜索。
1、 / 围棋博弈与算法研究摘要下完一局棋应有无数种供选择的方案,加上每个棋手的兴趣爱好、棋风、当时的心情、状态的差异,我们称它为“千古无同局”，从古至今没有一个人下棋的手法是一模一样的，在此我们对其进行讨论并分析。文中首先讨论了围棋的起源，比如最早的围棋程序是由作为他模式识别专业博士论文的一部分提出的，之后将的程序进行了深入的研究,并得出了自己的见解.然后将定式问题对象化，将对于每一个定式的出现方式，进行统一的处理,展示出棋盘坐标系统及其映射的一种实现方案.接着分析次序问题，因为棋局中整个布局过程往往是在多个定式之间交错进行的,因此可以建立容易进行检索及匹配操作的行棋步骤表，得出行棋步骤表字符串
2、化的一种实现方式。从效果上来讲,棋子的影响模型当然是越精确越好，因此建立精细计算的影响模型，从力学模型、度量公式和棋子双方势力范围分别对其进行分析，了解到利用每个点计算得到的四个方向的力及合力的大小和方向,我们可以粗略的表示双方的势力范围，力量对比，棋势强弱等信息。因为计算各点的影响值所需的时间成为搜索总用时的最主要影响因素,要想实现计算时间可以接受的完全搜索,必须采用更简洁的影响模型,因此建立快速计算时使用的影响模型，得出了影响值与空点级别的关系.最后建立了棋盘模型，设计方形棋盘使三线围成的边部与四线围成的中腹具有相同的地位或最小的差异,利用数学知识中的三线点与四线点目效率相近的原则，得出了
3、围棋棋盘选择的网点是最佳的。关键字:行棋步骤表 定式问题对象化 精细计算的影响模型 棋盘模型一、问题重述围棋是中华民族远古的祖先们流传下来的一项宝贵文化遗产。纵向看,这项国宝历经了从春秋战国到唐宋元明清几千年的历史，有盛有衰，有褒有贬，源远流长。横向看，当中国的文化往外辐射传播时，作为有悠久历史的“琴、棋、书、画也随之传向了海外。在艺术领域中，与它的姊妹艺术“琴、书、画相比，棋文化受关注的程度要少很多，郑重其事作研究探讨的文献、文章所见也不多。时至今日，恰如许多中国文化的其他方面一样,知其然而不知其所以然.因为下完一局棋应有无数种供选择的方案（这是一个天文数字），加上每个棋手的兴趣爱好、棋风、
4、当时的心情、状态的差异，我们称之为“千古无同局”文中主要讨论什么是围棋算法？如何进行面向对象的改造，建立对象模型？请收集材料建立其相应的匹配算法。二、问题分析围棋是一项智力性很强的智力性活动,它的起源说法很多,比如最早的围棋程序是由作为他模式识别专业博士论文的一部分提出的，之后将的程序进行了深入的研究，得出了自己的见解.然后将整个定式问题看作一个对象,定义为类，对于每一个定式的种出现方式,我们进行统一的处理,展示出了棋盘坐标系统及其映射的一种实现方案.围棋定式的展开次序具有很大的不确定性，所以整个布局过程往往是在多个定式之间交错进行的,因此建立易于进行检索及匹配操作的行棋步骤表,然后得出行棋步
5、骤表字符串化的一种实现方式。接着建立精细计算的影响模型，从力学模型、度量公式和棋子双方势力范围求得结果，同时建立快速计算时使用的影响模型，得出影响值与空点级别的关系。最后建立了棋盘模型，设计方形棋盘使三线围成的边部与四线围成的中具有相同的地位或最小的差异,应用搜集到的材料和所学的数学知识，解决其问题。三、模型假设假设一:假设下棋时不受外界的影响。假设二:假设有足够多的黑白子围棋。假设三：假设下棋的两人能力一样.假设四：假设棋盘足够大能够容纳足够多的棋子。四、符号说明符号 符号说明 总控制力 平衡度 黑子的扳位 白子的扳位 空交叉点 遍历棋子 占有强度 形势评估函数 下了某子之后形势改变的度量
6、默认坐标系 各定式区坐标系五、模型的建立与求解5.1布局研究人类棋手在选择布局走法时，通常会使用定式，定式是经过几千年经验积累所得出的合理布局走法，精通定式变化是人类棋手棋力进阶的必由之路，事实上在围棋程序领域，引入了定式库的程序也会在布局阶段具有明显优势。因此，如何识别并选择定式,是布局阶段的核心问题。5.1围棋起源阶段最早的围棋程序是由作为他模式识别专业博士论文的一部分提出的。引入了影响函数的方法将棋盘分为黑方和白方地域。的影响函数计算棋盘上每一个交叉点的数值,黑子取值,白子取值而空白点为；正数效果的点要给其邻接点加，同样负数效果的点给邻点加,这样的算法递归执行次,将棋盘最终数值化，如图：
7、13 2 22 4 6 4 22 8 1 8 1 2 62 10 6 2 4 8 10 8 4 6 4 2 2 2图1。根据影响模型,一个黑子对其周围辐射的影响而的程序是研究的深入，这也是他的博士论文内容.像一样,也使用了一个影响函数,用来将每个棋子对其周围产生的影响进行量化。他的影响函数与的类似,也是黑方取正数,白方取负数，某点影响的取值由其邻点的影响传播累加形成。的影响函数较的简单,传播系数是固定的。 11 2 2 11 3 6 11 5 1 6 13 11 6 13 6 1 5 2 1图2。根据Ryder影响模型，一个黑子对其周围辐射的影响定义了两个术语:联络和强关联。某点对于某方联络，
8、对于有子点而言，是指该点上是该方的非死子;对于空白点而言，是指该点至少有一个该方邻子且没有对方邻子。完全联络的一个延伸定义为半联络，指一个空白点至少有两个某方邻子及至少一个对方邻子，有三种情况被认为是强关联的。某点由某方子占据或与某方子连接，某点与某方子对角线连接且共有至少一个空白点，尖以及某两子之间只间隔一个空白点，棋块就是由一组联络或半联络的点组成的.影响函数与联络度相结合来确定棋势.对于一组联络的点，如果其影响函数的值不小于程序预定义的一个阈值，则组成棋势。5.1。2定式问题对象化基本目标:将整个定式问题看作一个对象，并定义为类，很显然,该类必然应具备的功能是:给定一个局血，根据定式知识
9、，返回下一步应手，这一功能可以定义为类的一个方法。对称问题：围棋棋盘具有多种对称属性，首先，在以天元为原点的坐标系统中，四个象限之间具有对称关系;其次，每一象限内部还都具有以经过天元的对角线为对称轴的对称关系，如图所示,同一个定式,可以有种出现形式：图3象棋的种形式可见，我们需要把棋盘划分为个定式区，每个定式区还包含一个定式向哪个方向展开的特征,这一特征可能有两种状态：顺时针或者逆时针。对于每一个定式的种出现方式，我们进行统一的处理，所以,坐标映蔚是必然需要的。例如将左上角顺时针作为定式的默认方式，我们就需要在其他各种方式与默认方式之间建立一对转换方法，这一对方法可以定义为：、下图展示了棋盘坐
10、标系统及其映射的一种实现方案:图.棋盘坐标系统及其映射棋盘默认为以左上角为原点,的坐标系统,而各个定式区又分别属于以各自拥有的角为原点,的子坐标系统。而从各定式区坐标系到默认坐标系的转换关系为：第一象限 如图中点第二象限 如图中点第三象限 如图中点第四象限 如图中点而各定式区内逆时针与顺时针的转换关系为:。1。4次序问题围棋定式的展开次序具有很大的小确定性,首先,因为在某一定式区内的定式步骤尚未完毕之前,双方可能暂时中断而转战至另一定式区，所以整个布局过程往往是在多个定式之间交错进行的。其次，被中断的定式区在棋局的后续发展中也可能出现三种不同的情况：其一是回到该定式区时行棋次序与离开时一致，则
11、定式继续；其二是次序颠倒而导致定式终止;其三是次序颠倒后仍然符合定式步骤,这种定式属于含有脱先变化的特殊定式。由于各定式往往交错进行，所以，各定式区都必须维护一个行棋步骤表来记录本区内的定式进行过程,可以定义为： 。由于定式可能处于中断、终止或脱先等多种状态，所以各定式区还需要增设一个属性来标记自身的状态,可以定义为： 。由于各定式区处于何种状态,取决于区内的行棋步骤是否符合定式，因此,我们需要一个方法来进行判断,这一方法可以定义为：该方法进行判断的依据只能是定式区行棋步骤表,因此，行棋步骤表所采用的数据结构应该是易于进行检索及匹配操作的。显然,字符串是最佳选择，下图给出了行棋步骤表字符串化的
12、一种实现方式:图5。行棋步骤表字符串化的实现方式上图显示了在第定式区顺时针展开的一个含有脱先手的定式,如果将每一手棋用相对于定式区子坐标系的两个字母表示，则：1=DD 6=BD 1X2CF =BE 12=JC3=FC 8=B 13=EC=CC 9=CE 14=FB5=D 10=B 15=GC其中，第手黑棋脱先,无法用定式区子坐标系表示，而对于脱先手，由于其必然在其他定式区有表示并有记录,所以可以一律记作由此，图中定式即可用一个字符串表示为：。5.2定式问题对象化建立一个可供程序检索及匹配的定式库,该库应该记录各种定式及其各类变化。定式库应该指出每种定式变化对于先手方或者后手方的有利或不利程度。定式库应该指出每种定式变化所依赖的局面条件。5.21库结构定式库通常应用于教学演示日的,通常表现为森林结构：图6森林结构图森林结构的特点是冗余数据少，非常适合整体或部分加载到内存然后使用遍历算法访问,但不适合快速匹配。如果将森林中每一条从根到叶子的路径都抽取出来组成一个列表，则该列表虽然含有大量冗余数据(根及枝条多次重复储存），但非常适合于快速检索匹配：图7.快速检索匹配图52。优先级问题在同一局而下，往往具有多种定式可供选择，而这些定式之间很难判定优劣,通常只是因对手而异:对手的棋力及棋风决定着选用某一定式所能达到的最终效果.显然，最恰当的做法是主动适应对手。特别地，当对手本身也是
