数学建模论文写作B

论文题目摘要关键词：一、问题重述五子棋发源于中国，在中国民间流传着许多五子棋阵法,比如以下阵法：（）一.斜三阵：多由浦月、流星、丘月、游星、慧星演变而来。见图一。由本阵还可演变成一字长蛇阵，见图二。以及长勾阵，见图三。斜三阵的进攻多以成角或成半燕翼发起。图一图二图三图四二.四角阵（图四）：黑方四子呈四方形的摆布，因而得名。三.梅花阵：下图所示阵形因黑方四子如梅花状而被称之为梅花阵。1.请建立数学模型或算法讨论以上阵法中执黑方获胜的策略；2.你的策略的合理性及获胜的概率如何？请说明及验证。二、基本假设1、棋盘采用15路正方形棋盘。2、采用无限制下棋法，无禁手限制。三、符号说明符号意义单位备注四、问题分析4.1问题一的分析问题一要求建立数学模型或算法能对黑方获胜的情况进行预测，并得出一些比较合理的黑方获胜的策略。所建立的模型或者算法的首要要求能够充分详细的描述从下棋开始到其中一方获胜的整个过程；其次是所建立的模型或算法能够选择出下棋时棋盘中对本方有最大优势或是对对方有最大劣势的空格，从而较好的实现模拟下棋过程的较优下法，即在下棋过程中当有多个位置可以下时，优先选择对己方有最大优势或对对方有最大劣势的空格；第三是考虑到下棋过程中可能出现的情况十分繁杂，若全部考虑可能会造成算法、、或模型十分复杂，所以我们建立的模型或算法要能够根据给出的目标条件，有选择性的舍去一些没有实际意义的情况，如本问题中要求讨论执黑方获胜的策略，则可舍去白方更可能获胜的那一部分情况。另外，因为一场完整的棋局是十分复杂多样的，各种阵型可能交错出现，而针对我们讨论某种阵法中执黑方获胜的策略这一问题，如果以一整局的输赢为研究单位，则可能会受到棋局中出现的其他阵型的影响，所以，探究某一阵型中执黑方获胜策略时，已该阵型为初始棋局，研究接下来有限步数内执黑方下棋获胜或是获胜可能性最大的最佳方案，所得结论即为该阵法中执黑方获胜的较优策略。一个新的阵法出现的最小步骤为5步，只考虑5步以内的情况可以比较合理的减少其他阵法对研究结果的影响。对于本问题，我们用计算机程序去模仿下棋的整个过程，并参考当前应用比较广泛的五子棋游戏原理，将游戏中常见的几种基本阵型给出比较合理的分值，并设计出较为合理的运行规则（能够得出较优下棋方案），计算机程序根据所给规则运行，并能自动舍去一些没用研究意义的方案。对题中三种阵型，我们根据程序运行，可给出5步以内的较优方案，即各阵型的执黑方获胜策略。4.2问题二的分析问题二要求我们说明并验证策略的合理性和获胜的概率，而合理性问题难以具体定量描述，我们希望能将该定性问题转化为定量问题来进行研究，因此问题二中的策略的合理性问题，我们认为是模糊综合评价问题。因此，本文通过以下四个步骤进行构造综合评价模型：步骤一：根据背景以及五子棋下棋规则，对合理性问题我们进行一个定义，并确定因素集合，而综合评价模型中要求将因素集1,,AnAA按照上述模型方案层分为s个因素集12,,,nAAA,且满足1sssnn，12SAAAU，对任意的,AijijA。步骤二：每一个因素分别作出综合判断各因素集合之间无直接关联，而步数和分数存在直接相关的因素，因此，我们需要消除两者之间的关联。那么我们采用斜率来取代分数作为直接相关的因素，当黑方斜率越陡时说明黑方已经胜利或接近胜利；而当他斜率平缓时，则说明局势焦灼，黑方可能会输；。根据上述分析，可以确定三个相关因素并确定出评判集。步骤三：确定单因素集的评价矩阵，当评价矩阵满足检验后，则可以认为所建立的矩阵近似满足要求步骤四：利用层次分析法对问题一给出的所有方法结果进行分析，利用层次分析法中的各级指标确定各因素集占目标层的权重。五、模型的建立与求解5.1问题一模型建立与求解5.1.1五子棋游戏中的部分规则及术语（1）棋盘：采用和围棋一样的15路或19路棋盘，本文采用15路棋盘。棋盘上纵横线交叉点叫格子，没有棋子的格子叫空格。（2）下法：两人分别执黑白棋子，轮流在棋盘中的空格上落子。（3）输赢：黑白两方有一方的5个棋子在横、竖、斜方向上连成一线即为这一方赢。（4）在机器智能走棋设计中，首先需要了解游戏规则中涉及的几种状态。下表是五子棋游戏中涉及的常用术语，具体如图一所示五子棋术语五连最后取胜的那5颗或5颗以上同色棋子称之五连活四两头没有对方棋子阻挡连续的4颗同色棋子活三下一手棋能够形成活四的棋型叫“活三”冲四落下1颗子形成五连，而且只有1个五连点的棋型叫“冲四”冲四活三落下一手棋，同时形成冲四和活三的棋型叫做“冲四活三”双冲四落下一手棋同时形成两个冲四叫做“双冲四”，它有2个五连点跳冲四冲四不一定是要连着摆，有时候根据需要可以隔着一上空格来眠三下一手棋能够冲四的棋型叫做“眠三”a.五连、活四图解b.双三、活三等图解c.眠三图解图一五子棋游戏中常见的状态5.1.2基本模型的建立由题意知，问题一需要我们确定黑棋获胜的策略，由概率论方法我们可以明确出下棋可能会出现的阵型可达数万中之多，而计算机难以模拟出这么多具体而微的策略，因此，我们考虑该问题为NP问题，需要我们确定一个相对最优的策略，因此该问题为优化问题：首先需要确定目标函数，即黑方获胜的策略way，既要考虑步数尽可能少，同时还要考虑进攻与防守的结合，在考虑这两种因素后制定并计算出相应的策略，使得黑方获胜或者黑方获胜的概率大大增加，我们就可以认为该策略为目标函数的相对最优解。其次，我们需要确定约束条件，要使黑方获胜或是获胜几率增加，那么应该使其步数尽可能少，而进攻分尽可能高，当分别获得估值己方MyScore和对方估值EnemyScore，MyScore要比EnemyScore大很多时，则可以认为黑方即将获胜。那么。目标函数为：12=+scorewaykkmy策略步数其中，1k，2k为常数。5.1.3基本算法的建立（1）分值的引出本文中我们用计算机算法去模仿黑方和白方的在各阵法中下棋过程，首要解决的就是判断出下棋过程中较优空位，对此，我们引用分值这一概念来衡量出下棋过程中某一空格的攻防作用的大小，一个空格一个数值。计算机先将已有棋子的格子的分值设计为0，再按照一定算法计算空格的分值，然后在分值最高的格子里随机选择一个落子。一个空格的分值分为进攻分和防守分，是其进攻分和防守分之和。一个空格既有防守作用，又有进攻作用，分别用数值来衡量其大小，被分别称为防守分和进攻分。本文中，我们将对方棋子在该空格处的进攻分作为本方在该处的防守分。进攻分我们用SA表示，防守分用SD表示，则分值为：SSASD一个空格的进攻分分为四个直线方向单独计算，再求和作为这格的进攻分。如果一个格子的四个方向的进攻分分别为SA0，SA1,SA2,SA3,,则其进攻分为：30jjSASA同理可得出一个格子的防守分：30jjSDSD（2）α-β剪枝搜索算法α-β剪枝算法是指，当父节点向下搜索节点时发现某一个子节点的分值远高于其他子节点，该节点即为这一步棋的较优走法，其他节点的子节点就不需要再次搜索，该节点的值就是该层的值。即可以将父节点的的其余后继节点抛弃，这个过程就是剪枝，又因为本文中父节点所在的层一定为分值最大的层，所以这个过程即为α剪枝。另外，当某一方父节点向下搜索节点时发现到第一个子节点就赢了时，后继的子节点也可以舍去不再搜索，这个过程也称为剪枝，本文中为α剪枝。如下图所示，假定子节点B1的分值远高于第二个节点B2，我们所需考虑的只有B1节点以及其子节点，而以B2为父节点的这一枝则舍去。图二剪枝法示意图（3）估值函数的建立为了描述下棋过程中棋局状态的优劣，并评价出较优空格，要确定一个估值函数。在α-β搜索函数中，当搜索的深度Level小于0的时候，就要对所有合理范围的地方进行分数评估。不同的棋型，其优先级不同。例如，当4个棋子连成一线并且端还有空位的棋型（活四）显然要比只有3个或更少棋子连成一线更接近胜利。要使计算机能做出这种判断，就要把这种棋型的估值设高。因此就必须对棋局出现的各种棋型设定一个估值，即建立一个全面的棋型估值表（见表2），通过各种棋型估值来反映其对棋局胜负影响的权值。估值函数设计得越细越好，这样可以加快搜索速度，减少搜索模块调用估值函数的频率。在对棋型进行估值时，要从该棋型4个方向上来考虑所下棋子对当前棋局的影响。以该棋子为基点，4个方向分别为水平、竖直、45°角和135°角。为方便形象描述棋型，本文中约定以符号“●”代表黑子，“○”代表白子，“×”代表棋盘上的空位，并对棋型死活作如下规定：一方落子后，对该落子连成的一条线有机会形成另外两种棋型，则该棋型是活型，否则称该棋型是死型。例如对于活三（×●●●×）的定义：不论对方如何落子，仍然至少有一种方法可以形成冲四棋型（○●●●●×）。棋型○×●●●×○中的3个●，不能算是活三；棋型○×●●●××○中的3个●，也不是活三，尽管它有可能成为活四。因此，在对棋型进行估值时，要考虑可能出现的所有棋型，这样计算机才不会漏判,利用上述模型，我们对各棋型进行了估分。本文中，为了更加合理详细的判断出最优下棋位置，我们还首先了提出实际下棋过程中出现的其他基本状态，如冲二、活二、夹三等，并给出合理估分。如表一所示。表一特定棋型的估分阵型名称分值●×××●夹三5●●○冲二20○××○中二40●×●夹一50●●活二80●●●○冲三180●●○●三夹一500●●●活三800●●×●●四夹一1500●●●●活四2000●●●●●活五10000依据上述估分列表，就可以对棋盘里面所有合理的走法进行估分。估分要从己方和对方两个角度进行，分别获得估值己方MyScore和对方估值EnemyScore，然后通过计算12KMyScoreKEnemyScore＋获得最终的估值结果Score。其中12,KK是一对关键系数，比值12KK反映计算机对局面的掌控程度，比值越大表示计算机的攻击性更强，反之则表示计算机的防守性更强。最后，棋局的胜负是根据最后一个落子的情况来判断的。此时需要查看4个方向，即以该棋子为出发点的水平、竖直和两条分别为45°角和135°角的线，判断在这4个方向上的其他棋子是否能和最后落子构成连续5个棋子，如果可以，则表示这盘棋局已经分出胜负。游戏算法的流程如图三所示5.1.3问题一结果的分析及验证5.2问题二模型建立与求解5.2.1模糊综合评价模型的建立问题一中我们建立了优化模型并利用博弈树算法黑方策略进行了分析，我们认为黑方对棋盘全局分数进行预判，确实自己为进攻或者是防守，确定之后搜索全局中对score影响最大的一步，在目标函数的筛选下确定一个相对最优走法。在问题二中要求我们对策略合理性进行分析，即对问题一建立模型后计算出的相对最优走法进行一个合理性分析。首先，我们对合理性进行定义：合理性：在考虑会对黑方在五子棋各阵法中是否获胜会产生影响的相关因素后，二白方与黑方水平近似相等或只存在一定差别时，策略在利用计算机模拟1000次下棋过程后，黑方胜率远大于白方时我们可以认为我们的策略合理。（1）影响因子的识别与筛选对黑方是否会获胜会产生影响的相关因素而言，影响因子是一个有机整体既要涵盖影响黑方走法的诸多影响因素，同时又要全面、合理、科学与实用，具有较强的可操作性。因此，经过分析影响因子有步数、胜率、进攻分、防守分，但步数越多，防守分与进攻分也就越高，两个影响因子之间成正相关，并不符合综合评价模型中评价因子无相关性的要求，因此，我们需要消除影响因子之间的相关性，若将分数与步数之间的关系给弱化，考虑求出每一步走之后的步数与分数之间的斜率scorek步数。02000400060008000100001200014000123456789折线图1图4步数与分数斜率图如上图，从开始到黑方获胜时，当局势焦灼时，斜率缓和变化不大；当黑方占优时，斜率变化加剧，从而更好描述了局势的变化并且消除分数与步数之间的相关性。（2）影响因子的度量选定评价指标后，需进一步确定各指标的权重。本文