论文题目 摘要
关键词：
一、问题重述
五子棋发源于中国，在中国民间流传着许多五子棋阵法, 比如以下阵法：（http://www.wuzi8.com/Article/HTML/1299.html）
一. 斜三阵：多由浦月、流星、丘月、游星、慧星演变而来。见图一。由本阵还可演变成一字长蛇阵，见图二。以及长勾阵，见图三。斜三阵的进攻多以成角或成半燕翼发起。
图一 图二
图三 图四
二. 四角阵（图四）：黑方四子呈四方形的摆布，因而得名。
三. 梅花阵：下图所示阵形因黑方四子如梅花状而被称之为梅花阵。
1. 请建立数学模型或算法讨论以上阵法中执黑方获胜的策略；
2. 你的策略的合理性及获胜的概率如何？请说明及验证。
二、基本假设
1、棋盘采用15路正方形棋盘。
2、采用无限制下棋法，无禁手限制。
三、符号说明
四、问题分析
4.1 问题一的分析
问题一要求建立数学模型或算法能对黑方获胜的情况进行预测，并得出一些比较合理的黑方获胜的策略。所建立的模型或者算法的首要要求能够充分详细的描述从下棋开始到其中一方获胜的整个过程；其次是所建立的模型或算法能够选择出下棋时棋盘中对本方有最大优势或是对对方有最大劣势的空格，从而较好的实现模拟下棋过程的较优下法，即在下棋过程中当有多个位置可以下时，优先选择对己方有最大优势或对对方有最大劣势的空格；第三是考虑到下棋过程中可能出现的情况十分繁杂，若全部考虑可能会造成算法、、或模型十分复杂，所以我们建立的模型或算法要能够根据给出的目标条件，有选择性的舍去一些没有实际意义的情况，如本问题中要求讨论执黑方获胜的策略，则可舍去白方更可能获胜的那一部分情况。
另外，因为一场完整的棋局是十分复杂多样的，各种阵型可能交错出现，而针对我们讨论某种阵法中执黑方获胜的策略这一问题，如果以一整局的输赢为研究单位，则可能会受到棋局中出现的其他阵型的影响，所以，探究某一阵型中执黑方获胜策略时，已该阵型为初始棋局，研究接下来有限步数内执黑方下棋获胜或是获胜可能性最大的最佳方案，所得结论即为该阵法中执黑方获胜的较优策略。一个新的阵法出现的最小步骤为5步，只考虑5步以内的情况可以比较合理的减少其他阵法对研究结果的影响。
对于本问题，我们用计算机程序去模仿下棋的整个过程，并参考当前应用比较广泛的五子棋游戏原理，将游戏中常见的几种基本阵型给出比较合理的分值，并设计出较为合理的运行规则（能够得出较优下棋方案），计算机程序根据所给规则运行，并能自动舍去一些没用研究意义的方案。对题中三种阵型，我们根据程序运行，可给出5步以内的较优方案，即各阵型的执黑方获胜策略。
4.2 问题二的分析
问题二要求我们说明并验证策略的合理性和获胜的概率，而合理性问题难以具体定量描述，我们希望能将该定性问题转化为定量问题来进行研究，因此问题二中的策略的合理性问题，我们认为是模糊综合评价问题。因此，本文通过以下四个步骤进行构造综合评价模型：
步骤一：根据背景以及五子棋下棋规则，对合理性问题我们进行一个定义，并确定因素集合，而综合评价模型中要求将因素集{}1, ,A n A A = 按照上述模型方案层分为s 个因素集12, , , n A A A , 且满足1s s
s n n ==∑，12S A A A U = ，对任意的
,A i j i j A φ≠= 。
步骤二：每一个因素分别作出综合判断各因素集合之间无直接关联，而步数和分数存在直接相关的因素，因此，我们需要消除两者之间的关联。那么我们采用斜率来取代分数作为直接相关的因素，当黑方斜率越陡时说明黑方已经胜利或接近胜利；而当他斜率平缓时，则说明局势焦灼，黑方可能会输；。根据上述分析，可以确定三个相关因素并确定出评判集。
步骤三：确定单因素集的评价矩阵，当评价矩阵满足检验后，则可以认为所建立的
矩阵近似满足要求
步骤四：利用层次分析法对问题一给出的所有方法结果进行分析，利用层次分析法中的各级指标确定各因素集占目标层的权重。
五、模型的建立与求解
5.1 问题一模型建立与求解
5.1.1 五子棋游戏中的部分规则及术语
（1）棋盘：采用和围棋一样的15路或19路棋盘，本文采用15 路棋盘。棋盘上纵横线交叉点叫格子，没有棋子的格子叫空格。
（2）下法：两人分别执黑白棋子，轮流在棋盘中的空格上落子。
（3） 输赢： 黑白两方有一方的5个棋子在横、竖、斜方向上连成一线即为这一方赢。
（4）在机器智能走棋设计中，首先需要了解游戏规则中涉及的几种状态。下表是五子棋游戏中涉及的常用术语，具体如图一所示
a.五连、活四图解 b.双三、活三等图解 c . 眠三图解
图一 五子棋游戏中常见的状态
5.1.2基本模型的建立
由题意知，问题一需要我们确定黑棋获胜的策略，由概率论方法我们可以明确出下棋可能会出现的阵型可达数万中之多，而计算机难以模拟出这么多具体而微的策略，因此，我们考虑该问题为NP 问题，需要我们确定一个相对最优的策略，因此该问题为优化问题：
首先需要确定目标函数，即黑方获胜的策略way ，既要考虑步数尽可能少，同时还要考虑进攻与防守的结合，在考虑这两种因素后制定并计算出相应的策略，使得黑方获胜或者黑方获胜的概率大大增加，我们就可以认为该策略为目标函数的相对最优解。
其次，我们需要确定约束条件，要使黑方获胜或是获胜几率增加，那么应该使其步数尽可能少， 而进攻分尽可能高， 当分别获得估值己方MyScore 和对方估值EnemyScore ， MyScore要比 EnemyScore大很多时，则可以认为黑方即将获胜。 那么。目标函数为：
12=+score way k k my ∙∙策略步数
其中，1k ， 2k 为常数。
5.1.3 基本算法的建立
（1）分值的引出
本文中我们用计算机算法去模仿黑方和白方的在各阵法中下棋过程，首要解决的就是判断出下棋过程中较优空位，对此，我们引用分值这一概念来衡量出下棋过程中某一空格的攻防作用的大小，一个空格一个数值。计算机先将已有棋子的格子的分值设计为0，再按照一定算法计算空格的分值，然后在分值最高的格子里随机选择一个落子。
一个空格的分值分为进攻分和防守分，是其进攻分和防守分之和。一个空格既有防守作用，又有进攻作用，分别用数值来衡量其大小，被分别称为防守分和进攻分。本文中，我们将对方棋子在该空格处的进攻分作为本方在该处的防守分。进攻分我们用SA 表示，防守分用SD 表示，则分值为：
S SA SD =+
一个空格的进攻分分为四个直线方向单独计算，再求和作为这格的进攻分。如果一个格子的四个方向的进攻分分别为SA 0，SA 1,SA 2,SA 3, ,则其进攻分为：
3
0j j SA SA ==∑
同理可得出一个格子的防守分：
3
0j j SD SD ==∑
（2）α-β剪枝搜索算法
α-β剪枝算法是指，当父节点向下搜索节点时发现某一个子节点的分值远高于其他子节点，该节点即为这一步棋的较优走法，其他节点的子节点就不需要再次搜索，该节点的值就是该层的值。即可以将父节点的的其余后继节点抛弃，这个过程就是剪枝，又因为本文中父节点所在的层一定为分值最大的层，所以这个过程即为α剪枝。另外，当某一方父节点向下搜索节点时发现到第一个子节点就赢了时，后继的子节点也可以舍去不再搜索，这个过程也称为剪枝，本文中为α剪枝。如下图所示，假定子节点B 1的分值远高于第二个节点B 2，我们所需考虑的只有B 1节点以及其子节点，而以B 2为父节点的
这一枝则舍去。
图二 剪枝法示意图
（3）估值函数的建立
为了描述下棋过程中棋局状态的优劣，并评价出较优空格，要确定一个估值函数。在 α-β搜索函数中， 当搜索的深度 Level 小于 0 的时候， 就要对所有合理范围的地方进行分数评估。不同的棋型， 其优先级不同。例如，当 4 个棋子连成一线并且端还有空位的棋型 （活四 ）显然要比只有 3 个或更少棋子连成一线更接近胜利。要使计算机能做出这种判断， 就要把这种棋型的估值设高。因此就必须对棋局出现的各种棋型设定一个估值，即建立一个全面的棋型估值表 （见表 2 ） ， 通过各种棋型估值来反映其对棋局胜负影响的权值。估值函数设计得越细越好， 这样可以加快搜索速度， 减少搜索模块调用估值函数的频率。在对棋型进行估值时， 要从该棋型 4 个方向上来考虑所下棋子对当前棋局的影响。以该棋子为基点， 4 个方向分别为水平、 竖直、45°角和 135°角。为方便形象描述棋型，本文中约定以符号 “●” 代表黑子，“○”代表白子，“×”代表棋盘上的空位，并对棋型死活作如下规定：一方落子后，对该落子连成的一条线有机会形成另外两种棋型，则该棋型是活型，否则称该棋型是死型。例如对于活三（×●●●× ） 的定义：不论对方如何落子，仍然至少有一种方法可以形成冲四棋型 （○●●●●× ）。棋型○×●●●×○中的 3 个●，不能算是活三；棋型○×●●●××○ 中的 3 个●，也不是活三，尽管它有可能成为活四。因此，在对棋型进行估值时，要考虑可能出现的所有棋型，这样计算机才不会漏判, 利用上述模型，我们对各棋型进行了估分。
本文中，为了更加合理详细的判断出最优下棋位置，我们还首先了提出实际下棋过
程中出现的其他基本状态，如冲二、活二、夹三等，并给出合理估分。如表一所示。
依据上述估分列表，就可以对棋盘里面所有合理的走法进行估分。估分要从己方和对方两个角度进行，分别获得估值己方MyScore 和对方估值 EnemyScore，然后通过计算
12K MyScore K EnemyScore ⨯⨯＋获得最终的估值结果Score 。其中12, K K 是一对关键系数， 比值
1
2
K K 反映计算机对局面的掌控程度，比值越大表示计算机的攻击性更强， 反之则表示计算机的防守性更强。
最后，棋局的胜负是根据最后一个落子的情况来判断的。此时需要查看 4 个方向， 即以该棋子为出发点的水平、 竖直和两条分别为 45°角和 135°角的线，判断在这 4 个方向上的其他棋子是否能和最后落子构成连续 5 个棋子，如果可以，则表示这盘棋局已经分出胜负。游戏算法的流程如图三所示
5.1.3 问题一结果的分析及验证
5.2 问题二模型建立与求解
5.2.1 模糊综合评价模型的建立
问题一中我们建立了优化模型并利用博弈树算法黑方策略进行了分析，我们认为黑方对棋盘全局分数进行预判，确实自己为进攻或者是防守，确定之后搜索全局中对score 影响最大的一步，在目标函数的筛选下确定一个相对最优走法。在问题二中要求我们对策略合理性进行分析，即对问题一建立模型后计算出的相对最优走法进行一个合理性分析。首先，我们对合理性进行定义：
合理性：在考虑会对黑方在五子棋各阵法中是否获胜会产生影响的相关因素后，二白方与黑方水平近似相等或只存在一定差别时，策略在利用计算机模拟1000次下棋过程后，黑方胜率远大于白方时我们可以认为我们的策略合理。
（1）影响因子的识别与筛选
对黑方是否会获胜会产生影响的相关因素而言，影响因子是一个有机整体既要涵盖影响黑方走法的诸多影响因素，同时又要全面、合理、科学与实用，具有较强的可操作性。因此，经过分析影响因子有步数、胜率、进攻分、防守分，但步数越多，防守分与进攻分也就越高，两个影响因子之间成正相关，并不符合综合评价模型中评价因子无相关性的要求，因此，我们需要消除影响因子之间的相关性，若将分数与步数之间的关系
给弱化，考虑求出每一步走之后的步数与分数之间的斜率score k =步数
。
2000
4000
6000
8000
10000
12000
14000
12345678
9
图4 步数与分数斜率图
如上图，从开始到黑方获胜时，当局势焦灼时，斜率缓和变化不大；当黑方占优时，斜率变化加剧，从而更好描述了局势的变化并且消除分数与步数之间的相关性。
（2）影响因子的度量
选定评价指标后，需进一步确定各指标的权重。本文采用层次分析法确定各评价指标的权重。
由于该问题涉及了一级指标，所以我们希望能把问题分为两个层次，在最低层通过两两对比得出各因素的权重，通过由高到低层层分析计算，最后计算出各方案对总目标的权数，根据得到的权数即可
根据判断矩阵每层每项元素进行两两比较，根据评分办法判断其优劣。而方案层是以中间层为依据来进行方案评分，建立判断矩阵()1, , k B k n = 判断方案的优劣：
矩阵所有元素的取值均靠构造比较矩阵来获得，比较矩阵通过矩阵形式来表示评价指标之间两两比较获得的相对重要的程度，由此我们引入1~9标度：
1111n k m mn b b B b b ⎛⎫ ⎪= ⎪ ⎪⎝⎭
由线性代数知识可知，判断矩阵的最大特征根所对应的特征向量即为各评价因素的重要性排序，经归一化后，就得到了各评价指标的权重分配。一般情况下，当矩阵阶数较高时，可采用以下两种近似方法求解判断矩阵的特征向量。求指标权重程序流程图如图 ：
图五 层次分析法求指标权重流程图
其中通过多次模拟后根据重要性赋予权重后，通过对判断矩阵的特征向量进行求解，检验判断的一致性；通过对一致性的检验，对各层加权排序加权值进行确定。如果检验没有通过，需要对判断矩阵进行重新调整。 其中我们定义一致性的指标：1
n CI n λ-=- ； 而CI 越大，不一致性越严重； 为了量CI 的大小，引入随机一致性指标RI ——随机模拟得到ij a , 形成A ，计算CI 即得RI 。 其中定义一致性比率CI CR RI
=
,结果允许存在一定误差，但误差控制在一定范围内时，我们可以近似认为其可以作为定量决策的依据，即当0.1CR ≤时通过一致性检验。
一致阵的任一列向量都是特征向量，一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。所以在检验我们所提出的模型时可以将所求简化为以下几个步骤：
步骤一：列向量归一化处理矩阵；
步骤二：获得新矩阵后对其求算术平均；
步骤三：利用AW W λ=，求出λ和w ，再代入一致性的公式进行检验即可。若满足，即可以作为定量决策的依据。
对每一个因素i A ，分别作出综合判断。设{}1, , m V v v = 为评判集，i A 中各因素相
对于目标层V 的权重分配是：
1, , i i i in V v v ⎡⎤=⎣⎦
而评价集的确定我们根据第一问建立的目标函数可以确定，对于初始阵型有利于黑方的起评价集如下：
当初始阵型不利于黑方时，评价集如下：
i
R 为单因素评判矩阵，则得到一级评判向量： i i i
C V R =∙ 第三步：将每个i A 看做是一个因素，即为：
{}
1, , n K u u = 这样，K 又是一个因素集，K 的单因素评价矩阵为
1111213n m mn C c c C R c c C ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢
⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦
模糊综合评价模型的流程图如下：
图六 模糊综合评价
5.2.2问题二模型的求解
5.2.4 问题二结果的分析及验证
六、模型的评价与推广
6.1 模型的评价
问题一的模型主要有：优化模型、博弈树算法、α-β剪枝搜索算法。通过这三种模型及算法，详细地刻画了黑方下棋时针对白方每一步而开展的策略，并考虑到原有阵法对黑白方的优势性、黑白方实力的差异性以及各阵型变化的随机性，这样的描述使得该模型更具有科学性。在研究双方如何下棋时，本文运用了全盘搜索的方法，对棋盘上每个空格对进攻分与防守分分别进行讨论，黑方选取分数最大的空格；在对特殊棋型的估分进行评判时，本文建立了估值函数，运用概率论以及五子棋规则常识对各特殊棋型进行讨论，得出科学、合理的估分。
用计算机模拟的方法对问题一进行求解是问题一中最大的亮点。因为用计算机模拟
的方法，可以仿真出下棋时每一过程的状态变化，这样得到的结果会更加真实可靠。 问题一的不足之处在于，在考虑五子棋的规则时，不考虑禁手等规则，导致先手的获胜的几率要更高一些。因此，我们建议可以通过增加禁手规则，让双方更为公平的来下棋，从而使黑方策略更可靠；在考虑棋子的策略时，只能考虑当前和之前的分数与阵法，没有考虑到未来多步的走法和阵型的安排。
问题二的模型主要有：模糊性综合评价模型、层次分析法。通过这两种模型并结合问题一所建立算法计算后的结果，定量地对合理性进行了讨论，并充分考虑了各个评价因子之间的相关性，最终确定了三个无直接关联的因素，这样的处理方式使得模糊综合评价模型更具有参考价值。
综上所述，本文所建立的模型与算法能够具体地描述与求解五子棋中黑方胜利的模型，故可以把该模型与算法推广到其他具有相同情况的棋类游戏中，但需更加细致考虑预测未来多步内棋盘将可能出现的情况，制定出更细致的策略。
6.2 模型的推广
七、参考文献
（参考文献按正文中的引用次序列出，主要参考文献要正文和本部分一一对应
[1] 姜启源等, 《数学模型》（第三版），北京：高等教育出版社，2003年，50-52.
[2] 匿名，中华人民共和国国家标准/碳酸饮料(汽水) ，http://www.foodmate.net/， 2006 年9月17日.
[3] 崔杰，吴昊, 误差处理的方法研究，误差理论分析，23(1):50-52,2003年. ） 1、
2、瞿锡泉, 白振兴, 包建平. 棋类博弈算法的改进[J].现代电子技术,2005.35
(1):96- 99.
八、附录
8.1 附录清单
附录1：求解问题一的LINGO 程序及命令
附录2：求解问题二的Mathematica 程序及命令
附录3：求解问题一的中间数据
附录4：问题二的完整数据结果
附录5：问题三的SPSS 过程截图
8.2 附录正文(如果附录很长，请字体尽量缩小，图片缩小，甚至采用两栏排版模式) 附录1：求解问题一的LINGO 程序
附录2：求解问题二的Mathematica 程序
附录3：求解问题一的中间数据
附录4：问题二的完整数据结果
论文题目 摘要
关键词：
一、问题重述
五子棋发源于中国，在中国民间流传着许多五子棋阵法, 比如以下阵法：（http://www.wuzi8.com/Article/HTML/1299.html）
一. 斜三阵：多由浦月、流星、丘月、游星、慧星演变而来。见图一。由本阵还可演变成一字长蛇阵，见图二。以及长勾阵，见图三。斜三阵的进攻多以成角或成半燕翼发起。
图一 图二
图三 图四
二. 四角阵（图四）：黑方四子呈四方形的摆布，因而得名。
三. 梅花阵：下图所示阵形因黑方四子如梅花状而被称之为梅花阵。
1. 请建立数学模型或算法讨论以上阵法中执黑方获胜的策略；
2. 你的策略的合理性及获胜的概率如何？请说明及验证。
二、基本假设
1、棋盘采用15路正方形棋盘。
2、采用无限制下棋法，无禁手限制。
三、符号说明
四、问题分析
4.1 问题一的分析
问题一要求建立数学模型或算法能对黑方获胜的情况进行预测，并得出一些比较合理的黑方获胜的策略。所建立的模型或者算法的首要要求能够充分详细的描述从下棋开始到其中一方获胜的整个过程；其次是所建立的模型或算法能够选择出下棋时棋盘中对本方有最大优势或是对对方有最大劣势的空格，从而较好的实现模拟下棋过程的较优下法，即在下棋过程中当有多个位置可以下时，优先选择对己方有最大优势或对对方有最大劣势的空格；第三是考虑到下棋过程中可能出现的情况十分繁杂，若全部考虑可能会造成算法、、或模型十分复杂，所以我们建立的模型或算法要能够根据给出的目标条件，有选择性的舍去一些没有实际意义的情况，如本问题中要求讨论执黑方获胜的策略，则可舍去白方更可能获胜的那一部分情况。
另外，因为一场完整的棋局是十分复杂多样的，各种阵型可能交错出现，而针对我们讨论某种阵法中执黑方获胜的策略这一问题，如果以一整局的输赢为研究单位，则可能会受到棋局中出现的其他阵型的影响，所以，探究某一阵型中执黑方获胜策略时，已该阵型为初始棋局，研究接下来有限步数内执黑方下棋获胜或是获胜可能性最大的最佳方案，所得结论即为该阵法中执黑方获胜的较优策略。一个新的阵法出现的最小步骤为5步，只考虑5步以内的情况可以比较合理的减少其他阵法对研究结果的影响。
对于本问题，我们用计算机程序去模仿下棋的整个过程，并参考当前应用比较广泛的五子棋游戏原理，将游戏中常见的几种基本阵型给出比较合理的分值，并设计出较为合理的运行规则（能够得出较优下棋方案），计算机程序根据所给规则运行，并能自动舍去一些没用研究意义的方案。对题中三种阵型，我们根据程序运行，可给出5步以内的较优方案，即各阵型的执黑方获胜策略。
4.2 问题二的分析
问题二要求我们说明并验证策略的合理性和获胜的概率，而合理性问题难以具体定量描述，我们希望能将该定性问题转化为定量问题来进行研究，因此问题二中的策略的合理性问题，我们认为是模糊综合评价问题。因此，本文通过以下四个步骤进行构造综合评价模型：
步骤一：根据背景以及五子棋下棋规则，对合理性问题我们进行一个定义，并确定因素集合，而综合评价模型中要求将因素集{}1, ,A n A A = 按照上述模型方案层分为s 个因素集12, , , n A A A , 且满足1s s
s n n ==∑，12S A A A U = ，对任意的
,A i j i j A φ≠= 。
步骤二：每一个因素分别作出综合判断各因素集合之间无直接关联，而步数和分数存在直接相关的因素，因此，我们需要消除两者之间的关联。那么我们采用斜率来取代分数作为直接相关的因素，当黑方斜率越陡时说明黑方已经胜利或接近胜利；而当他斜率平缓时，则说明局势焦灼，黑方可能会输；。根据上述分析，可以确定三个相关因素并确定出评判集。
步骤三：确定单因素集的评价矩阵，当评价矩阵满足检验后，则可以认为所建立的
矩阵近似满足要求
步骤四：利用层次分析法对问题一给出的所有方法结果进行分析，利用层次分析法中的各级指标确定各因素集占目标层的权重。
五、模型的建立与求解
5.1 问题一模型建立与求解
5.1.1 五子棋游戏中的部分规则及术语
（1）棋盘：采用和围棋一样的15路或19路棋盘，本文采用15 路棋盘。棋盘上纵横线交叉点叫格子，没有棋子的格子叫空格。
（2）下法：两人分别执黑白棋子，轮流在棋盘中的空格上落子。
（3） 输赢： 黑白两方有一方的5个棋子在横、竖、斜方向上连成一线即为这一方赢。
（4）在机器智能走棋设计中，首先需要了解游戏规则中涉及的几种状态。下表是五子棋游戏中涉及的常用术语，具体如图一所示
a.五连、活四图解 b.双三、活三等图解 c . 眠三图解
图一 五子棋游戏中常见的状态
5.1.2基本模型的建立
由题意知，问题一需要我们确定黑棋获胜的策略，由概率论方法我们可以明确出下棋可能会出现的阵型可达数万中之多，而计算机难以模拟出这么多具体而微的策略，因此，我们考虑该问题为NP 问题，需要我们确定一个相对最优的策略，因此该问题为优化问题：
首先需要确定目标函数，即黑方获胜的策略way ，既要考虑步数尽可能少，同时还要考虑进攻与防守的结合，在考虑这两种因素后制定并计算出相应的策略，使得黑方获胜或者黑方获胜的概率大大增加，我们就可以认为该策略为目标函数的相对最优解。
其次，我们需要确定约束条件，要使黑方获胜或是获胜几率增加，那么应该使其步数尽可能少， 而进攻分尽可能高， 当分别获得估值己方MyScore 和对方估值EnemyScore ， MyScore要比 EnemyScore大很多时，则可以认为黑方即将获胜。 那么。目标函数为：
12=+score way k k my ∙∙策略步数
其中，1k ， 2k 为常数。
5.1.3 基本算法的建立
（1）分值的引出
本文中我们用计算机算法去模仿黑方和白方的在各阵法中下棋过程，首要解决的就是判断出下棋过程中较优空位，对此，我们引用分值这一概念来衡量出下棋过程中某一空格的攻防作用的大小，一个空格一个数值。计算机先将已有棋子的格子的分值设计为0，再按照一定算法计算空格的分值，然后在分值最高的格子里随机选择一个落子。
一个空格的分值分为进攻分和防守分，是其进攻分和防守分之和。一个空格既有防守作用，又有进攻作用，分别用数值来衡量其大小，被分别称为防守分和进攻分。本文中，我们将对方棋子在该空格处的进攻分作为本方在该处的防守分。进攻分我们用SA 表示，防守分用SD 表示，则分值为：
S SA SD =+
一个空格的进攻分分为四个直线方向单独计算，再求和作为这格的进攻分。如果一个格子的四个方向的进攻分分别为SA 0，SA 1,SA 2,SA 3, ,则其进攻分为：
3
0j j SA SA ==∑
同理可得出一个格子的防守分：
3
0j j SD SD ==∑
（2）α-β剪枝搜索算法
α-β剪枝算法是指，当父节点向下搜索节点时发现某一个子节点的分值远高于其他子节点，该节点即为这一步棋的较优走法，其他节点的子节点就不需要再次搜索，该节点的值就是该层的值。即可以将父节点的的其余后继节点抛弃，这个过程就是剪枝，又因为本文中父节点所在的层一定为分值最大的层，所以这个过程即为α剪枝。另外，当某一方父节点向下搜索节点时发现到第一个子节点就赢了时，后继的子节点也可以舍去不再搜索，这个过程也称为剪枝，本文中为α剪枝。如下图所示，假定子节点B 1的分值远高于第二个节点B 2，我们所需考虑的只有B 1节点以及其子节点，而以B 2为父节点的
这一枝则舍去。
图二 剪枝法示意图
（3）估值函数的建立
为了描述下棋过程中棋局状态的优劣，并评价出较优空格，要确定一个估值函数。在 α-β搜索函数中， 当搜索的深度 Level 小于 0 的时候， 就要对所有合理范围的地方进行分数评估。不同的棋型， 其优先级不同。例如，当 4 个棋子连成一线并且端还有空位的棋型 （活四 ）显然要比只有 3 个或更少棋子连成一线更接近胜利。要使计算机能做出这种判断， 就要把这种棋型的估值设高。因此就必须对棋局出现的各种棋型设定一个估值，即建立一个全面的棋型估值表 （见表 2 ） ， 通过各种棋型估值来反映其对棋局胜负影响的权值。估值函数设计得越细越好， 这样可以加快搜索速度， 减少搜索模块调用估值函数的频率。在对棋型进行估值时， 要从该棋型 4 个方向上来考虑所下棋子对当前棋局的影响。以该棋子为基点， 4 个方向分别为水平、 竖直、45°角和 135°角。为方便形象描述棋型，本文中约定以符号 “●” 代表黑子，“○”代表白子，“×”代表棋盘上的空位，并对棋型死活作如下规定：一方落子后，对该落子连成的一条线有机会形成另外两种棋型，则该棋型是活型，否则称该棋型是死型。例如对于活三（×●●●× ） 的定义：不论对方如何落子，仍然至少有一种方法可以形成冲四棋型 （○●●●●× ）。棋型○×●●●×○中的 3 个●，不能算是活三；棋型○×●●●××○ 中的 3 个●，也不是活三，尽管它有可能成为活四。因此，在对棋型进行估值时，要考虑可能出现的所有棋型，这样计算机才不会漏判, 利用上述模型，我们对各棋型进行了估分。
本文中，为了更加合理详细的判断出最优下棋位置，我们还首先了提出实际下棋过
程中出现的其他基本状态，如冲二、活二、夹三等，并给出合理估分。如表一所示。
依据上述估分列表，就可以对棋盘里面所有合理的走法进行估分。估分要从己方和对方两个角度进行，分别获得估值己方MyScore 和对方估值 EnemyScore，然后通过计算
12K MyScore K EnemyScore ⨯⨯＋获得最终的估值结果Score 。其中12, K K 是一对关键系数， 比值
1
2
K K 反映计算机对局面的掌控程度，比值越大表示计算机的攻击性更强， 反之则表示计算机的防守性更强。
最后，棋局的胜负是根据最后一个落子的情况来判断的。此时需要查看 4 个方向， 即以该棋子为出发点的水平、 竖直和两条分别为 45°角和 135°角的线，判断在这 4 个方向上的其他棋子是否能和最后落子构成连续 5 个棋子，如果可以，则表示这盘棋局已经分出胜负。游戏算法的流程如图三所示
5.1.3 问题一结果的分析及验证
5.2 问题二模型建立与求解
5.2.1 模糊综合评价模型的建立
问题一中我们建立了优化模型并利用博弈树算法黑方策略进行了分析，我们认为黑方对棋盘全局分数进行预判，确实自己为进攻或者是防守，确定之后搜索全局中对score 影响最大的一步，在目标函数的筛选下确定一个相对最优走法。在问题二中要求我们对策略合理性进行分析，即对问题一建立模型后计算出的相对最优走法进行一个合理性分析。首先，我们对合理性进行定义：
合理性：在考虑会对黑方在五子棋各阵法中是否获胜会产生影响的相关因素后，二白方与黑方水平近似相等或只存在一定差别时，策略在利用计算机模拟1000次下棋过程后，黑方胜率远大于白方时我们可以认为我们的策略合理。
（1）影响因子的识别与筛选
对黑方是否会获胜会产生影响的相关因素而言，影响因子是一个有机整体既要涵盖影响黑方走法的诸多影响因素，同时又要全面、合理、科学与实用，具有较强的可操作性。因此，经过分析影响因子有步数、胜率、进攻分、防守分，但步数越多，防守分与进攻分也就越高，两个影响因子之间成正相关，并不符合综合评价模型中评价因子无相关性的要求，因此，我们需要消除影响因子之间的相关性，若将分数与步数之间的关系
给弱化，考虑求出每一步走之后的步数与分数之间的斜率score k =步数
。
2000
4000
6000
8000
10000
12000
14000
12345678
9
图4 步数与分数斜率图
如上图，从开始到黑方获胜时，当局势焦灼时，斜率缓和变化不大；当黑方占优时，斜率变化加剧，从而更好描述了局势的变化并且消除分数与步数之间的相关性。
（2）影响因子的度量
选定评价指标后，需进一步确定各指标的权重。本文采用层次分析法确定各评价指标的权重。
由于该问题涉及了一级指标，所以我们希望能把问题分为两个层次，在最低层通过两两对比得出各因素的权重，通过由高到低层层分析计算，最后计算出各方案对总目标的权数，根据得到的权数即可
根据判断矩阵每层每项元素进行两两比较，根据评分办法判断其优劣。而方案层是以中间层为依据来进行方案评分，建立判断矩阵()1, , k B k n = 判断方案的优劣：
矩阵所有元素的取值均靠构造比较矩阵来获得，比较矩阵通过矩阵形式来表示评价指标之间两两比较获得的相对重要的程度，由此我们引入1~9标度：
1111n k m mn b b B b b ⎛⎫ ⎪= ⎪ ⎪⎝⎭
由线性代数知识可知，判断矩阵的最大特征根所对应的特征向量即为各评价因素的重要性排序，经归一化后，就得到了各评价指标的权重分配。一般情况下，当矩阵阶数较高时，可采用以下两种近似方法求解判断矩阵的特征向量。求指标权重程序流程图如图 ：
图五 层次分析法求指标权重流程图
其中通过多次模拟后根据重要性赋予权重后，通过对判断矩阵的特征向量进行求解，检验判断的一致性；通过对一致性的检验，对各层加权排序加权值进行确定。如果检验没有通过，需要对判断矩阵进行重新调整。 其中我们定义一致性的指标：1
n CI n λ-=- ； 而CI 越大，不一致性越严重； 为了量CI 的大小，引入随机一致性指标RI ——随机模拟得到ij a , 形成A ，计算CI 即得RI 。 其中定义一致性比率CI CR RI
=
,结果允许存在一定误差，但误差控制在一定范围内时，我们可以近似认为其可以作为定量决策的依据，即当0.1CR ≤时通过一致性检验。
一致阵的任一列向量都是特征向量，一致性尚好的正互反阵的列向量都应近似特征向量，可取其某种意义下的平均。所以在检验我们所提出的模型时可以将所求简化为以下几个步骤：
步骤一：列向量归一化处理矩阵；
步骤二：获得新矩阵后对其求算术平均；
步骤三：利用AW W λ=，求出λ和w ，再代入一致性的公式进行检验即可。若满足，即可以作为定量决策的依据。
对每一个因素i A ，分别作出综合判断。设{}1, , m V v v = 为评判集，i A 中各因素相
对于目标层V 的权重分配是：
1, , i i i in V v v ⎡⎤=⎣⎦
而评价集的确定我们根据第一问建立的目标函数可以确定，对于初始阵型有利于黑方的起评价集如下：
当初始阵型不利于黑方时，评价集如下：
i
R 为单因素评判矩阵，则得到一级评判向量： i i i
C V R =∙ 第三步：将每个i A 看做是一个因素，即为：
{}
1, , n K u u = 这样，K 又是一个因素集，K 的单因素评价矩阵为
1111213n m mn C c c C R c c C ⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥==⎢
⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦
模糊综合评价模型的流程图如下：
图六 模糊综合评价
5.2.2问题二模型的求解
5.2.4 问题二结果的分析及验证
六、模型的评价与推广
6.1 模型的评价
问题一的模型主要有：优化模型、博弈树算法、α-β剪枝搜索算法。通过这三种模型及算法，详细地刻画了黑方下棋时针对白方每一步而开展的策略，并考虑到原有阵法对黑白方的优势性、黑白方实力的差异性以及各阵型变化的随机性，这样的描述使得该模型更具有科学性。在研究双方如何下棋时，本文运用了全盘搜索的方法，对棋盘上每个空格对进攻分与防守分分别进行讨论，黑方选取分数最大的空格；在对特殊棋型的估分进行评判时，本文建立了估值函数，运用概率论以及五子棋规则常识对各特殊棋型进行讨论，得出科学、合理的估分。
用计算机模拟的方法对问题一进行求解是问题一中最大的亮点。因为用计算机模拟
的方法，可以仿真出下棋时每一过程的状态变化，这样得到的结果会更加真实可靠。 问题一的不足之处在于，在考虑五子棋的规则时，不考虑禁手等规则，导致先手的获胜的几率要更高一些。因此，我们建议可以通过增加禁手规则，让双方更为公平的来下棋，从而使黑方策略更可靠；在考虑棋子的策略时，只能考虑当前和之前的分数与阵法，没有考虑到未来多步的走法和阵型的安排。
问题二的模型主要有：模糊性综合评价模型、层次分析法。通过这两种模型并结合问题一所建立算法计算后的结果，定量地对合理性进行了讨论，并充分考虑了各个评价因子之间的相关性，最终确定了三个无直接关联的因素，这样的处理方式使得模糊综合评价模型更具有参考价值。
综上所述，本文所建立的模型与算法能够具体地描述与求解五子棋中黑方胜利的模型，故可以把该模型与算法推广到其他具有相同情况的棋类游戏中，但需更加细致考虑预测未来多步内棋盘将可能出现的情况，制定出更细致的策略。
6.2 模型的推广
七、参考文献
（参考文献按正文中的引用次序列出，主要参考文献要正文和本部分一一对应
[1] 姜启源等, 《数学模型》（第三版），北京：高等教育出版社，2003年，50-52.
[2] 匿名，中华人民共和国国家标准/碳酸饮料(汽水) ，http://www.foodmate.net/， 2006 年9月17日.
[3] 崔杰，吴昊, 误差处理的方法研究，误差理论分析，23(1):50-52,2003年. ） 1、
2、瞿锡泉, 白振兴, 包建平. 棋类博弈算法的改进[J].现代电子技术,2005.35
(1):96- 99.
八、附录
8.1 附录清单
附录1：求解问题一的LINGO 程序及命令
附录2：求解问题二的Mathematica 程序及命令
附录3：求解问题一的中间数据
附录4：问题二的完整数据结果
附录5：问题三的SPSS 过程截图
8.2 附录正文(如果附录很长，请字体尽量缩小，图片缩小，甚至采用两栏排版模式) 附录1：求解问题一的LINGO 程序
附录2：求解问题二的Mathematica 程序
附录3：求解问题一的中间数据
附录4：问题二的完整数据结果