围棋博弈与算法研究

围棋博弈与算法研究摘要下完一局棋应有无数种供选择的方案，加上每个棋手的兴趣爱好、棋风、当时的心情、状态的差异，我们称它为“千古无同局”，从古至今没有一个人下棋的手法是一模一样的，在此我们对其进行讨论并分析。文中首先讨论了围棋的起源，比如最早的围棋程序是由 AZobrist作为他模式识别专业博士论文的一部分提出的，之后JonRyder将Zobrist的程序进行了深入的研究，并得出了自己的见解。然后将定式问题对象化，将对于每一个定式的出现方式，进行统一的处理，展示出棋盘坐标系统及其映射的一种实现方案。 接着分析次序问题，因为棋局中整个布局过程往往是在多个定式之间交错进行的，因此可以建立容易进行检索及匹配操作的行棋步骤表，得出行棋步骤表字符串化的一种实现方式。从效果上来讲，棋子的影响模型当然是越精确越好，因此建立精细计算的影响模型，从力学模型、度量公式和棋子双方势力范围分别对其进行分析，了解到利用每个点计算得到的四个方向的力及合力的大小和方向， 我们可以粗略的表示双方的势力范围，力量对比，棋势强弱等信息。因为计算各点的影响值所需的时间成为搜索总用时的最主要影响因素， 要想实现计算时间可以接受的完全搜索，必须采用更简洁的影响模型，因此建立快速计算时使用的影响模型，得出了影响值与空点级别的关系。最后建立了棋盘模型，设计方形棋盘使三线围成的边部与四线围成的中腹具有相同的地位或最小的差异， 利用数学知识中的三线点与四线点目效率相近的原则，得出了围棋棋盘选择19/19的网点是最佳的。关键字：行棋步骤表 定式问题对象化 精细计算的影响模型 棋盘模型#一、问题重述围棋是中华民族远古的祖先们流传下来的一项宝贵文化遗产。纵向看，这项国宝历经了从春秋战国到唐宋元明清几千年的历史，有盛有衰，有褒有贬，源远流长。横向看，当中国的文化往外辐射传播时，作为有悠久历史的“琴、棋、书、画”也随之传向了海外。在艺术领域中，与它的姊妹艺术“琴、书、画”相比，棋文化受关注的程度要少很多，郑重其事作研究探讨的文献、文章所见也不多。时至今日，恰如许多中国文化的其他方面一样，知其然而不知其所以然。因为下完一局棋应有无数种供选择的方案 （这是一个天文数字 ）,加上每个棋手的兴趣爱好、棋风、当时的心情、状态的差异 ,我们称之为“千古无同局”文中主要讨论什么是围棋算法？如何进行面向对象的改造，建立对象模型？请收集材料建立其相应的匹配算法。二、问题分析围棋是一项智力性很强的智力性活动，它的起源说法很多，比如最早的围棋程序是由A.Zob门琳为他模式识别专业博士论文的一部分提出的，之后JonRyder将Zobrist的程序进行了深入的研究，得出了自己的见解。然后将整个定式问题看作一个对象 ,定义为CGoFormulary类，对于每一个定式的8种出现方式,我们进行统一的处理，展示出了棋盘坐标系统及其映射的一种实现方案。围棋定式的展开次序具有很大的不确定性 ,所以整个布局过程往往是在多个定式之间交错进行的，因此建立易于进行检索及匹配操作的行棋步骤表，然后得出行棋步骤表字符串化的一种实现方式。接着建立精细计算的影响模型，从力学模型、度量公式和棋子双方势力范围求得结果，同时建立快速计算时使用的影响模型，得出影响值与空点级别的关系。最后建立了棋盘模型，设计方形棋盘使三线围成的边部与四线围成的中具有相同的地位或最小的差异，应用搜集到的材料和所学的数学知识，解决其问题。三、模型假设假设一：假设下棋时不受外界的影响。假设二：假设有足够多的黑白子围棋。假设三：假设下棋的两人能力一样。

假设四：假设棋盘足够大能够容纳足够多的棋子四、符号说明符号符号说明总控制力平衡度黑子的扳位白子的扳位空交叉点遍历棋子FB占有强度SFB形势评估函数卜了某子之后形势改变的度量x,y默认坐标系x,,y,符号符号说明总控制力平衡度黑子的扳位白子的扳位空交叉点遍历棋子FB占有强度SFB形势评估函数卜了某子之后形势改变的度量x,y默认坐标系x,,y,各定式区坐标系五、模型的建立与求解布局研究人类棋手在选择布局走法时，通常会使用定式，定式是经过几千年经验积累所得出的合理布局走法，精通定式变化是人类棋手棋力进阶的必由之路 ，事实上在围棋程序领域,引入了定式库的程序也会在布局阶段具有明显优势。因此，如何识别并选择定式，是布局阶段的核心问题。围棋起源阶段最早的围棋程序是由A.Zobrist作为他模式识别专业博士论文的一部分提出的。Zobrist引入了影响函数的方法将棋盘分为黑方和白方地域。Zobrist的影响函数计算棋盘上每一个交叉点的数值，黑子取值+50,白子取值-50而空白点为0;正数效果的点要给其邻接点加+1,同样负数效果的点给邻点加-1,这样的算法递归执行4次，将棋盘最终数值化，如图：32 42 4 81 2 6 102 4 832 42 4 81 2 6 102 4 82 421.根据Zobrist影响模型，一个黑子对其周围辐射的影响6 4 210 8 4 262 10 6 2 110 8 4 26 4 22 2一个黑子对其周围辐射的影响而JonRyder的程序是Zobrist研究的深入，这也是他的博士论文内容。像Zobrist一样，Ryder也使用了一个影响函数，用来将每个棋子对其周围产也是黑方取正数，白方取负数，某点影响的取值由其邻点的影响传播累加形成。Ryder的影响函数较Zobrist的简单，传播系数是固定的。1313601313生的影响进行量化。他的影响函数与 也是黑方取正数，白方取负数，某点影响的取值由其邻点的影响传播累加形成。Ryder的影响函数较Zobrist的简单，传播系数是固定的。1313601313.根据 Ryder影响模型，一个黑子对其周围辐射的影响Ryder定义了两个术语：联络和强关联。某点对于某方联络 ,对于有子点而言，是指该点上是该方的非死子；对于空白点而言，是指该点至少有一个该方邻子且没有对方邻子。完全联络的一个延伸定义为半联络，指一个空白点至少有两个某方邻子及至少一个对方邻子，有三种情况被认为是强关联的。某点由某方子占据或与某方子连接，某点与某方子对角线连接且共有至少一个空白点，尖以及某两子之间只间隔一个空白点，棋块就是由一组联络或半联络的点组成的。影响函数与联络度相结合来确定棋势。对于一组联络的点，如果其影响函数的值不小于程序预定义的一个阈值，则组成棋势。5.1.2定式问题对象化基本目标：将整个定式问题看作一个对象，并定义为CGoFormulary类，很显然，该类必然应具备的功能是：给定一个局血，根据定式知识，返回下一步应手，这一功能可以定义为CGoFormulary类的一个方法CGoFormulary::GetNextStep()。对称问题：围棋棋盘具有多种对称属性，首先，在以天元为原点的坐标系统中四个象限之间具有对称关系；其次,每一象限内部还都具有以经过天元的对角线为对称轴的对称关系，如图所示，同一个定式，可以有8种出现形式：图3.象棋的8种形式可见，我们需要把棋盘划分为4个定式区，每个定式区还包含一个定式向哪个方向展开的特征，这一特征可能有两种状态：顺时针或者逆时针。对于每一个定式的8种出现方式，我们进行统一的处理，所以，坐标映蔚是必然需要的。例如将左上角顺时针作为定式的默认方式，我们就需要在其他各种方式与默认方式之间建立一对转换方法，这一对方法可以定义为：CGoFormulary::MapToDefault()、CGoFormulary::MapToFactual()下图展示了棋盘坐标系统及其映射的一种实现方案 ：：

012340123456789101112131415T61718图4.棋盘坐标系统及其映射棋盘默认为以左上角为原点，19*19的坐标系统,而各个定式区又分别属于以各自拥有的角为原点，10*10的子坐标系统。而从各定式区坐标系（x，,y，）到默认坐标系（x,y）的转换关系为：第一象限 x，=x y第一象限 x，=x y，=y如图中a点第二象限x，=18-y y，=x如图中B点第三象限x，=y y，=18—x如图中C点第四象限 x第四象限 x，=18-xy，=18-y 如图中D点而各定式区内逆时针（x，，y，）与顺时针（x，y）的转换关系为：x，=y，y，=x5.1.4次序问题围棋定式的展开次序具有很大的小确定性，首先，因为在某一定式区内的定式步骤尚未完毕之前，双方可能暂时中断而转战至另一定式区，所以整个布局过程往往是在多个定式之间交错进行的。其次，被中断的定式区在棋局的后续发展中也可能出现三种不同的情况 ：其一是回到该定式区时行棋次序与离开时一致，则定式继续；其二是次序颠倒而导致定式终止;其三是次序颠倒后仍然符合定式步骤，这种定式属于含有脱先变化的特殊定由于各定式往往交错进行，所以，各定式区都必须维护一个行棋步骤表来记录本区内的定式进行过程，可以定义为：Areali].StepsI]0由于定式可能处于中断、终止或脱先等多种状态 ，所以各定式区还需要增设一个属性来标记自身的状态，可以定义为：ArealiI.State。由于各定式区处于何种状态，取决于区内的行棋步骤是否符合定式，因此，我们需要一个方法来进行判断，这一方法可以定义为：CGoFormulary::IsFormulary()该方法进行判断的依据只能是定式区行棋步骤表 Area【1.Steps因此，行棋步骤表所采用的数据结构应该是易于进行检索及匹配操作的。显然 ，字符串是最佳选择，下图给出了行棋步骤表字符串化的一种实现方式上图显示了在第2定式区顺时针展开的一个含有脱先手的定式，如果将每手棋用相对于定式区子坐标系的两个字母表示，则：TOC\o"1-5"\h\z1=DD 6=BD 11=XX2=CF 7=BE 12=JC3=FC 8=BC 13=EC

4=CC9=CE14=FB4=CC9=CE14=FB5=CD10=EB 15=GC其中，第11手黑棋脱先，无法用定式区子坐标系表示，而对于脱先手，由于其必然在其他定式区有表示并有记录，所以可以一律记作XX由此，图中定式即可用一个字符串表示为:DDCFFCCCCDBDBEBCCEEBXXJCECFBGC。定式问题对象化建立一个可供程序检索及匹配的定式库，该库应该记录各种定式及其各类变化。定式库应该指出每种定式变化对于先手方或者后手方的有利或不利程度。 定式库应该指出每种定式变化所依赖的局面条件。库结构定式库通常应用于教学演示日的，通常表现为森林结构：图6.森林结构图图6.森林结构图森林结构的特点是冗余数据少，非常适合整体或部分加载到内存然后使用遍历算法访问，但不适合快速匹配。如果将森林中每一条从根到叶子的路径都抽取出来组成一个列表，则该列表虽然含有大量冗余数据（根及枝条多次重复储存）,但非常适合于快速检索匹配：

图7图7.快速检索匹配图优先级问题在同一局而下，往往具有多种定式可供选择，而这些定式之间很难判定优劣，通常只是因对手而异：对手的棋力及棋风决定着选用某一定式所能达到的最终效果。显然，最恰当的做法是主动适应对手。特别地，当对手本身也是程序时，由于可以进行大量的自动对局来积累经验，所以对定式设定优先级，并针过实际对局结果修正该优先级，就可能大大提高对特定程序对手的对抗能力。因此，在定式库设计及定式匹配算法设计中引入自适应的优先级设置，是当然之选。精细计算的影响模型从效果上来讲，棋子的影响模型当然是越精确越好。需要以此为基础建立分块模型，用来作为战斗单位的是棋块而不是单独的棋子。棋局中计算实地外势，或者简单计算棋块的活力，强弱都会与棋子的影响模型有关。步着手时都要计算上百次或更多,义与计算简便之间找到平衡点。而另一方面，由于影响模型在计算评估函数时要用到，评估函数在计算每一所以影响模型又不能过于复杂，必须在精确定步着手时都要计算上百次或更多,义与计算简便之间找到平衡点。力学模型棋盘上的每一个棋子，都向周围四个方向发出影响。通过这种影响实现对空点的占领和棋子之间的相互作用，这种影响可以被视为一种控制力沿四个方向大小相等，而黑白棋子产生的控制力符号相反。控制力产生后，沿它的方向向前传播，其传播方式遵守如下定律：递减定律：控制力遇到一个点后，力的大小被减弱，符号方向不变的继续向前传播。如果遇到空点，减弱后的控制力变为原来的一个常数倍，该常数被称为传播率；如果遇到有子点，沿原方向的控制力消失。折射定律：控制力遇到一个点后，产生与控制力方向相垂直的两个新的控制力，这两个力符号与原控制力相同，方向相反，大小相等，为原控制力的一个常数倍，该常数被称为折射率。反射定律：控制力到达棋盘边缘后，会被反射回来，该反射力与原控制力方向相反，符号相同，大小为原控制力的一个常数倍该常数被称为反射率。每一个点都受到四个方向的控制力的作用，任一方向的控制力的大小是这个点所受这个方向所有控制力的代数和。由于这种叠加类似于力的叠加原理，所以这种模型被称为“力学模型”。在实际计算时，我们取：任意棋子产生的初始控制力的大小为 32；黑子的影响为正、白子的影响为负；传播率为1/2;折射率为1/4；反射率为1;初始控制力的大小取为2的幕，而传播率取为1/2,折射率取为1/4,就使各级影响值均为整数，避免了小数运算。围棋程序因要计算很多问题，宜尽量节省计算时间，因此此处只用整数运算。度量公式在得到任一棋盘状态下各空点影响的分布图后，可以由这些影响值经过计算得到一些棋盘状况的深层信息，一些常用的度量公式如下：设一个点受到的四个控制力大小为：向上F0;向右F1;向下F2;向左F3。总力：A=F0F1F2F3 (1)表示一个点受到某一方影响的度量。A>0受黑的影响强一些。

A<0受白的影响强一些。A=0受双方的影响基本平衡。模：F),F),F02F12F22F32(2)表示一个空点受到棋子影响的强度。F很大，表示这一点受子的影响已经很强，常常是官子价值较小的位置。F很小，表示这一点受子的影响还很弱，常常是大场。平衡度：B=12 2F0-F2F1-F32FB=12 2F0-F2F1-F32FF1+F3—F0-F2F0+F1+F2+F3表示在一个点上四个方向的力互相平衡的程度，变化范围 0~1。B很大，表示在某方的控制范围内。B很小，表示在双方控制范围的交界线上。占有强度：FB=FB (4)表示一点作为某方实空的现实程度。FB很大，已是某方的实空了，这样的位置双方一般是不下子的。FB很小，有几种情况：F很小，表示这一点是大场； F很大，B很小，表示这一点是双方的分界线。形势评估函数：SFB=£F(sign(A,F*B)十£g(color,状态) (5)空点 有子点其中，F函数的作用是对FB值进行圆滑处理，尤其对于FB值很大的点,当FB值超过一定数值，该点已经被某方占有了，FB值再大已失去其数值意义,应当进行规格化。g函数的作用是对盘面上的死子进行处理， g函数的一个例子如下:(6)1

gx,p=(6)-1g函数还可以更加细化的处理处于安全，死亡之间的状态。SFBa0,表示盘面黑棋优势；SFB<=0,表示盘面白棋优势。一手棋的价值：△SFB=下子之后的SFB—下子之前的SFB(7)表示下了某子之后形势改变的度量，也就是这一手的价值。在无急场的情况下，选择价值大的点落子。5.3.3判定双方势力范围对每一空点，它受到的总控制力A=F0+F1+F2+F3,当A大于某一数值n时，将其规格化为n(T)。当A>0时受黑的影响强一些，该点能否被黑方所控制，能否算作黑方实地，按照以下规则判定：.如果该点所受四个方向的力均大于1,则该点为黑方势力范围；.如果该点所受四个方向的力均大于0,且A大于10,则该点为黑方势力范围；.如果该点的A值大于规格化最大值n的2/3,则该点为黑方势力范围；.如果该点为黑方势力范围，且所受四个方向的力均大于 1,其中3个方向的力大于2,则该点为黑方实地；.如果该点为黑方势力范围，且所受四个方向的力均大1,A值大于34则该点为黑方实地。对于白方的势力范围与实地有类似的判断规则。利用力学模型，建立多层块结构，以FB的值为基础，根据FB值的范围，建立起多级的块，过程如下：.每个棋子建立一个零层(最底层块)；.如果相邻，两个零层块属于同一个一层块；.如果两个i层块之间可以找到这样一个路径相通：路径上的任一点的FB值大于某一与i相关的设定值(在实现时根据经验选取)，则两个i层块同属于一个i+1层块；.如果i+1层块只有一个则结束，否则重复3o利用这个力学模型，分析一些简单的常用走法，利用每个点计算得到的四个方向的力及合力的大小和方向，可以粗略的表示双方的势力范围，力量对比，棋势强弱等信息。棋子产生的影响用控制力的形式来表示，多个棋子的作用被看作是单个棋子作用的简单叠加，当棋子有一定的距离时，这种叠加是有道理的。但是当棋子相近或相连时，单纯的叠加已经不能近似实际情况。5.3.4快速计算时使用的影响模型在搜索棋块的死活状态时，需要确定一些与眼位有关的空点处于哪方的控制之下，此时，计算各点的影响值所需的时间成为搜索总用时的最主要影响因素，要想实现计算时间可以接受的完全搜索，必须采用更简洁的影响模型。应用于快速计算的影响模型，首先按照空点对棋子的位置关系定义了以下的级别划分：邻位A的级别为1;关位B的级别为2;斜邻位C的级别为1.5;小飞位D的级别为2.5o若双方棋子相连，F是黑子的扳位，对于黑子级别为2;E是白子的扳位，对于白子级别为2。某色棋子对某空点的影响仅决定于离该点最近（即具最小级别数）的该色棋子，影响值如下表所示：表1.影响值与空点级别的关系空点级别11.522.5黑子影响6532白子影响-6-5-3-2黑白影响可以互消，所有点计算完毕，再根据以下规则进行圆滑处理某点影响值的代数和为1或-1,则取为0;与0或负影响相邻的点，其影响值不得超过3；与1或2相邻的点，其影响值不得超过5;负值（白子影响）有类似的规则。在实际计算时，遍历所有的空交叉点（个数为m）而不是像前面的影响模型计算时遍历棋子（个数为n）。如果遍历棋子，一个棋子影响的空点有4+4+4+8=20个，需计算nx20次，每次都要判断该棋子对此空点的影响值是否最大；而遍历空点则只需计算mwx（x<20）次，从空点出发由近及远，遇到第一个棋子（黑白各一次）就可以停止计算。5.4棋盘模型的建立为了对围棋问题建立数学模型，需首先对围棋棋子价值有个数学描述，为此我们给出如下定义：对于一块成活型棋块，用它的棋子数去除这些棋子所包含的目数，得到的商值称为此棋块的目效率，记为PE。可以看出，目效率表示单位棋子所占的目数，即表示此棋块平均占有目数的能力下面利用此概念对围棋棋盘问题建立模型。围棋的棋盘由古时的每边11道增至现在的每边19道，其间历经数千年。这种进化的过程也显示着人们的认识逐渐接近真理。 古人在不贴子的情形下仍可公平对弈,说明先下的一方占的便宜不会太大可以推测，围棋内部一定存在两种抗衡的力量，使先手即使先落子也无法取得多少优势。一般的棋类（如象棋），往往有攻有守，攻守之间有一种平衡，而且随时可以转换，因此，先手一方即使先进行攻击也未必得胜。由此可以说，一般棋类之所以变化无穷，根本原因在其包含了攻与守这既对立又统一的两个方面。它们在胜负的天平上地位相同，相互抑制，一切取胜的走法或定式不过是围绕着攻与守， 以攻为守，或以守为攻来进行罢了。围棋亦如此，但围棋的攻守（攻为欲杀死对方，守为不被对方杀死）却显然不同于其它棋类，由于弈棋双方轮换落子，因此，单纯为杀死对方而进行攻击要比防守来得困难。就是说，围棋里的攻与守无法取得相同的地位，因此，绝不能把围棋也认为是攻与守的对立统一体。但围棋那样富于变化从根本上讲，其内部一定存在着两种力量的抗衡。这两种力量既可以对抗，又可随时转换。象棋的两个对立面之所以是攻与守，无非是缘于其取胜规则为吃掉对方的将（帅），不进攻当然不行。因此，在确定围棋中对抗的两种力量时必须意识到：这两种力量抗争的最终目的与围棋的目的应是统一的，即多占地盘。首先，我们把围棋棋盘按区域特点笼统地分为边部和中腹。从做活和占地两个角度看，边部因空间受阻而易受攻击，但可利用边部成目快的特点迅速做活，有根据地后再图发展，中腹则由于四方皆可发展，不容易受到攻击，做活便退居其次，而先去抢占空间。由此可见，边部和中腹将成为围棋中的两种对抗的势力，除此之外，还应保证两种势力所具有的价值相同，从而使二者能够真正地进行抗衡，这是必要的，否则，无论偏重哪一方，围棋都会成为单一净夺边部或中腹的乏味游戏,而且使先手棋获益颇大。前面在讨论三线的作用时，曾经指出三线控制边部的优势。显然，控制中腹的重任无疑落到了紧邻的四线上。这样，问题最终可化为：怎样设计方形棋盘（即每边选取多少道）使三线围成的边部与四线围成的中腹具有相同的地位或最小的差异？图9.方形棋盘每边19道时的情形三线点、四线点设置如图9（此时棋盘每边道数为19）,设三线点、四线点组成的棋块的目效率分别为PE3,PE,。根据三线与四线目效率相近的原则，我们提出本节的数学问题：方形围棋棋盘每边设置多少道数,将使E=PE4-PE3的绝对值最小？5.4.1模型的求解假设棋盘每边为x道，x为自然数。为了实用的需要，围棋棋盘不宜太大，也不宜太小，设11Wx^23。参照图9（此时x=19）,由于对x的限制，三线围成的边及四线围成的中腹已成为实空，对方无法在其中做活这样。所有三线围成的目数为：8x-16其目效率为：四线围成中腹的目数为:PE38x-164x—20四线围成中腹的目数为:PE38x-164x—20(8)2，,一，、-(x—8)其目效率为:PE_Zz814-4x-28两目效率之差为:Ex=PE4-PE3Ex=PE4-PE3(x-8f4x-288x-164x-20(10)对于PE3,如果把x看做连续变量，可以看出它是关于x的单调下降函数，因为这是PE3可改写成:PE38x-16PE38x-168x-5 24c62

4x-20 4x-5x-5(11)同理，对PE4有:2 2x-8x-7-2x-7 1pe42 2x-8x-7-2x-7 1pe4= = 4x-7 4x-7x-714 21+ 4x-7(12)将PE4关于x求导得:TOC\o"1-5"\h\z1 1PE4x=4-K (13)由x-7>1,从而(PE4x>0,即PE4关于x单调上升，这将导致E(x)也关于x单调上升，因而，对于方程E(x)=PE4-PE3=0,若有解，其解也只能有一个，又由于；E18=-0.1888,E19=0.092 (14)故由连续函数介值定理，E(x)=0的解在开区间(18,19)中，显然其解非整数，而我们寻求的是使|E(x)最小的整数解，由E(x)的单调性及同19卜忙(18),即知x=19将使E(x|最小。因此，我们用三线点与四线点目效率相近的原则证明了围棋棋盘选择 19M19的网点是最佳的。六、模型的评价与推广围棋在生活中随处可见，平时的家庭生活又或者国际比赛中，它经常被广泛的应用于各种比赛。我们也可以根据建立的围棋模型，结合生活中的实际情况，学习相应的数学知识与技能。优点：本文建立的模型能够与实际精密联系，结合实际情况对问题进行了求解，使得模型具有很好的通用性和推广性。本文模型的计算采用了专业的数学软件，可信度较高。本文应用了正确的数据处理方法，很好的解决了小数取整的问题。缺点：本文没有很好的把握重心，让人感觉文章有点散。本文在模型建立的过程中引入的变量较多，不利于编程处理。七、参考文献.马净，经久不衰的魅力，文化艺术出版社，1989年.姜启源，数学模型，高等教育出版社，北京，1987年.杜维新，围棋布局基础，《成都棋苑》编辑委员会，1985年.吴清源，围棋高级死活，1991.曹文君，知识库系统原理及其应用，1995.程慧霞，用C+碇造专家系统，1995八、附录附录一：/*************************************************/TOC\o"1-5"\h\z//文件名：Go.h //////用途：围棋 程序对弈类库头文件。////版本：V0.1 ////版权:伍白杨 ////日期：2014年11月 ///*************************************************/#pragmaonce#defineHUMAN0#defineCOMPUTER#defineCLOSEDdefineBLACK0defineWHITE1defineBLANK2defineFRAME3defineUP0defineDOWN1defineLEFT2defineRIGHT3defineLTOP4defineRTOP5#defineLBOT6#defineRBOT7#definePROLOG0#defineMIDRUN1#defineFINALE2template<classT>classCGoNodepublic;CGoNode();CGoNode<Tvalue,CGoNode*next=NULL>;tTvALUE;CGoNode*pNext;};classCGoStringpublic;CGoString(intnintc);~CGoString();intnColor;intnDots;intnPeps;intnEyes;CGoNode<int>*pDotHead;CGoNode<int>*pPepHead;voidTakePep(intn);voidLosePep(intn);voidLink(CGoString*str);};classCGoLonk{public;CGoLink();~CGoLink();intnType;CGoString*pBegin;CGoString*pEnd;intnBegin;intnEnd;}classCGoDragon{public;CGoDragon();'CGoDragon();intnFields;intnViablility;CGoString*pBase;CGoNode<CGoString*>*pStringHead;CGoNode<CGoLink*>*pLinkHead;CGoNode<int>*pFieldHead;intLiveExam();intExpand();intDefend();};classCGoFormularypublic;CGoFormulary();'CGoFormulary();_ConnectionPtrpConnect;_RecordsetPtrpRecordest;intnStste[4];CStringsSteps[4];CStringMapToFormulary(intn,intarea);intMapToStep(CStrings,intarea);CStringSyometrical(CStrings);intIsFormulary(CStrings);CStringGetNextStep(CStrings,CStringterm);voidUpdateState(intn;intcolor);intChoseStep(intcolor,intarea);};classCGoPoint{public;CGoPoint();CGoString*pString;intnForce[2];intnHolder;};classCGo{public;CGo();~CGo();CGoPointDots[361];intnSteps;intStepList[1000];intnFields[2];intnSeesawPoint;intnStage;CGoFormulary*pForm;voidReset();intCheck(intn,intdir);voidUpdateForce(intn,intc,intkill=0);intKillString(intn);intCanGo(intn);intTryGo(intn);voidGo(intn);voidReGo();intComputerChoice();voidEstimateFields();};#include"stdafx.h"#include"Sieger.h"#include"GoDlg.h"#include"Go.h"staticUINTWM_COMPUTER_DONE=RegisterWindowMessage("User");HANDLEhComputerInvolve;HANDLEhComputerDo;CGo*pBoard;UINTComputerThink(LPVOIDparam){while(WaitForSingleObject(hComputerInvolve,0)==WAIT_OBJECT_0){WaitForSingleObject(hComputerDo,INFINITE);if(WaitForSingleObject(hComputerInvovle,0)!=WAIT_OBJECT_0)return0;intn=pBoard->ComputerChoice();ResetEvent(hComputerDo);::PostMessage((HWND)param,WM_COMPUTER_DONE,n,0);}return0;}IMPLEMENT_DYNAMIC(CGoDlg,CDialog)BEGIN_MESSAGE_MAP(CGoDlg,CDialog)ON_WM_PAINT()ON_WM_LBUTTONDOWN()ON_BN_CLICKED(IDC_BUTTON_Black,OnBnClickedButtonBlack)ON_BN_CLICKED(IDC_BUTTON_White,OnBnClickedButtonWhite)ON_BN_CLICKED(IDC_Start,OnBnClickeedStaet)ON_BN_CLICKED(IDC_ReStart,OnBnClickedRestart)ON_BN_CLICKED(IDC_BUTTON_UNDO,OnBnClickedButtonUndo)ON_BN_CLICKED(IDC_BUTTON_SAVE,OnBnClickedButtonSave)ON_BN_CLICKED(IDC_BITTON_LOAD,OnBnClickedButtonLoad)ON_REGISTERED_MESSAGE(WM_COMPUTER_DONE,OnComputerDone)ON_BN_CLICKED(IDC_BUTTON_FORCE,OnBnClickedButtonForce)END_MESSAGE_MAP()BOOLCGoDlg::OnInitDialog(){CDialog::OnInialog();m_pBlackBrush=newCBrush;m_pWhiteBrush=newCBrush;m_pBlackBrus->CreateSolidBrush(0);m_pWhiteBrush->CreatesolidBrush(0xffffff);m_nRoles[BLACK]=HUMAN;m_nRoles[WHITE]=HUMAN;m_nStart=0;m_nState=0;m_LoadFile="";m_Button_Blick.SetWindowText(_T("人"));m_Button_White.SetWindowText(_T("人"));m_Button_Start.SetWindowText(_T("开始"));m_Button_Force.SetWindowText(_t("形式(关)"));hComputerInvolve=CreateEvent(NULL,TRUE,FALSE,NULL);hComputerDo=CreateEvent(NULL,TRUE,FALSE,NULL);EesetEvent(hComputerInvolve);ResetEvent(hComputerDo);retureTRUE;}voidCGoDLG::DoDataExchange(CGataExchange*pDX){CDialog::DoDataExchange(pDX);DDX_Control(pDX,IDC_BUTTON_Black,m_Button_Black);DDX_Control(pDX,IDC_BUTTON_White,m_Button_White);DDX_Control(pDX,IDC_Start,m_Button_Start);DDX_Control(pDX,IDC_ReStart,m_Button_ReStart);DDX_Control(pDX,IDC_BUTTON_UNDO,m_Button_Undo);DDX_Control(pDX,IDC_BUTTON_SAVE,m_Button_Save);DDX_Control(pDX,IDC_BUTTON_LOAD,m_Button_Load);DDX_Control(pDX,IDC_BUTTON_FORCE,m_Button_Force);}CGoDlg::'CGoDlg(){deletem_pBlackBrush;deletem_pWhiteBrush;CloseHandle(hComputerInvolve);CloseHandle(hComputerDo);}intCGoDlg::GetTurn(){if(!m_nStart)rturnCLOSED;inti=Board.nSteps%2;if(m_nRoles[i])returnCOMPUTER;elsereturnHUMAN;}voidCGoDlg::OnPaint(){CPaintDCdc(this);CDCMemDC;MemDC.CreateCompatibleDC(NULL);MemBitmap.CreateCompatibleBitmap(&dc,400,400);MemDC.SelectObject(&MemBitmap);MemDC.FillSolidRect(0,0,400,400,0xff9999);CRectrect(19,19,382,382);MemDC.FrameRect(&rect,m_pBlackBrush);for(inti=1;i<20;i++){MemDC.MoveTo(20,I*20);MemDC.LineTo(380,i*20);MemDC.MoveTo(i*20,20);MemDC.LineTo(i*20,380);}MemDC.SelectObject(m_pBlackBrush);for(i=0;i<9;i++){MemDC.Ellipse(i%3*120+77,i/3*120+77,i%3*120+83,i/3*120+83);}for(i=0;i<361;i++){if(Board.Dots[i].pString){if(Board.Dots[i].pString->nColor==BLACK)MemDC.SelectObject(m_pBlackBrush);elseMemDC.SelectObject(m_pWhiteBrush);MemDC.Ellipse(i%19*20+10,i/19*20+10,i%19*20+30,i/19*20+30);}elseif(m_nState){if(Board.Dots[i].nHolder==BLACK){MemDC.SelectObject(m_pBlackBrush);MemDC,Ellipse(i%19*20+15,i/19*20+15,i%19*20+25,i/19*20+25);}elseif(Board.Dots[i].nHolder==WHITE)MemDC.SelectObject(m_pWhiteBrush);MemDC.Ellipse(i%19*20+15,i/19*20+15,i%19*20+25,i/19*20+25);}}}if(Board.nSteps){intn=Board.nSteps-1;i=Board.StepList[n];if(n%2)MemDC.SelectObject(m_pBlackBrush);elseMemDC.SelectObject(m_pWhiteBrush);MemDC.Ellipse(i%19*20+15,i/19*20+15,i%19*20+25,i/19*20+25);}dc.BitBlt(0,0,400,400,&MemDC,0,0,SRCCOPY);MemBitmap.DeleteObject();MemDC.DeleteDC();}voidCGoDlg::OnLButtonDown(UINTNflags,CPointpoint){if(GetTurn()!=HUMAN)return;if((point.x<10)||()point.x>=390)||(point.y<10)||(point.y>=390))return;intx=(point.x-20)/20;inty=(point.y-20)/20;if((point.x>20)&&(point.x%20>10))x++;if((point.y>20)&&(point.y%20>10))y++;intn=y*19+x;if(!Board.CanGo(n))return;Board.Go(n);Inva;idate(FALSE);if(GetTurn()==COMPUTER)SetEvent(hComputerDO);elseResetEvent(hComputerDO);CDialog::OnLButtonDown(nFlags,point);}voidCGoDlg::OnBnClickedButtonBlanck(){if(m_nRoles[BLACK]==HUMAN){m_Button_Black.SetWindowText(_T("机"));m_nRoles[BLACK]=COMPUTER;}else{m_Button_Black.SetWindowText(_T("人"));m_nRoles[BLACK]=HUMAN;}Invalidate(FALSE);}voidCGoDlg::OnBnClickedButtonWhite(){if(m_nRoles[WHITE]==HUMAN)m_Button_White.SetWindowText(_T("机"));m_nRoles[WHITE]=COMPUTER;}else{m_Button_White.SetWindowText(_T("人"));m_nRoles[WHITE]=HUMAN;}Invalidate(FALSE);}voidCGoDlg::OnBnClickedStart(){m_nStart=1-m_nStart;if(m_nStart){m_Button_Start.SetWindowText(_T("暂停"));m_Button_Black.EnableWindow(FALSE);m_Button_White.EnableWindow(FALSE);m_Button_ReStart.EnableWindow(FALSE);m_Button_Undo.EnableWindow(FALSE);m_Button_Force.EnableWindow(FALSE);m_Button_Save.EnableWindow(FALSE);m_Button_Load.EnableWindow(FALSE);if(m_nRoles[BLACK]||m_nRoles[WHITE]){PbOARD=&Board;SetEvent(hComputerInvolve);HWNDhWnd=GetSafaeHwnd();AfxBeginThread(ComputerThink,hWnd);if(GetTurn()==COMPUTER)SetEvent(hComputerDo);elseResetEvent(hComputerDo);}}else{pBoard=NULL;m_Button_Start.SetWindowText(_T("开始"));m_Button_Black.EnableWindow(TRUE);m_Button_White.EnableWindow(TRUE);m_Button_ReStart.EnableWindow(TRUE);m_Button_Undo.EnableWindow(TRUE);m_Button_Force.EnableWindow(TRUE);m_Button_Save.EnableWindow(TRUE);m_Button_Load.EnableWindow(TRUE);ResetEvent(hComputerInvolve);SetEvent(hComputerDo);}Invalidate(FALSE);}voidCGoDlg::OnBnClickedRestart(){Board.Reset();Invalidate(FALSE);voidCGoDlg::OnBnClickedButtonUndo(){intn=Board.nSteps-2;Boerd.Reset();for(inti=0;i<n;i++){Board.Go(Board.StepList[i]);}Invalidate(FALSE);}voidCGoDlg::OnBnClickedButtonForce(){m_nState=1-m_nState;if(m_nState)m_Button_Force.SetWindowText(_T("形式(开)"));elsem_Button_Force.SetWindowText(_T("形式(关)"));Invalidate(FALSE);}voidCGoDlg::OnBnClickedButtonSave(){CStringoutfile;CFileDialog*pFileDlg=newCFileDialog(FALSE,"go",m_LoadFile,OFN_OVREWRITEPROMPT,"Go",Files|*.go||",this|);INT_PTRnResp=pFileDlg->DoModal();if(nResp==IDOK)outfile=pFileDlg->GetPathName();else{deletepFileDlg;return;}deletepFileDlg;CFile*pOoutFile=newCFile();if(!pOutFile->Open(outfile,CFile::modeCreate,CFile::modeWnite)){AfxMessageBox("文件无法打开")；deletepOutFile;return;}pOutFile->SetLength(0);pOutFile->SeekToBegin();charch[2];for(inti=0;i<Board.nSteps;i++){ch[0]=Board.StepList[i]%19+'A';ch[1]=Board.StepList[i]/19+'A';pOutFile->Write(ch.2);}pOutFile->Close();deletepOutFile;}voidCGoDlg::OnBnClickedButtonLoad(){CFileDialog*pFileDlg=newCFileDialog(TRUE,"go",NULL,OFN_HIDERE