西南交大新秀杯数学建模.doc

《西南交大新秀杯数学建模.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2015年西南交通大学新秀杯数学建模竞赛题目：B（填写A或B题）组别：大二组（填写大一组或大二题）参赛队员1参赛队员2参赛队员3学号学院专业Email西南交通大学教务处西南交通大学实验室及设备管理处西南交通大学数学建模创新实践基地33五子棋部分阵法研究的数学模型摘要五子棋游戏是一种益智类的博弈游戏，其开局阵型对棋局结果往往起决定性作用。本文通过构造博弈树，结合极大极小算法、运用机理分析与计算机模拟的方法，讨论了在五种开局阵型下黑子获胜的策略，及该策略实现的概率大小问题。对于问题一，首先我们将棋盘抽象为方阵，将方阵中对于元素的描述方式引入棋盘，从而建立

2、起各棋子位置与数组之间的映射关系；其次，我们做出博弈树表示黑白双方对弈的过程，从图像上表现了这一过程中随着搜索深度增加，博弈树的子节点将成指数增长的特点，又从实际出发阐述了对弈双方在“与”和“或”节点上存在明显对立的利害关系时，两方将如何选择；在此基础上，引入极大极小化搜索思想，结合实际情况，用价值大小量化对弈过程，设计出在估值函数用来比较不同局面的对某方的价值大小；此外，考虑到在按照极大极小搜索原理，搜索理想的博弈条件下，黑棋取胜的路径时搜索空间巨大，我们又对这一算法进行了搜索空间限定及搜索方式的优化；最后利用VC6.0编程，输入四种初始界面后经过

3、一步步回溯，最终都得到了黑棋获胜的结果。可见将极大极小算法应用到这四种局面，可以寻找到取胜的路径。对于问题二，首先我们在问题二中做出了合理的假设，将问题转化为，在无初始阵型的前提下，若白棋随机性的落子，黑棋按照问题一中极大极小算法这一策略，取胜概率应如何；其次，我们首先考虑运用概率论的相关知识，通过机理分析，结合古典概型建立了在假设条件下黑棋不败的概率解析模型，但由于求解复杂，我们考虑采用蒙特卡罗模拟的方法，利用机理分析过程中的一系列结论，得到计算机模拟所需要的概率分布及随机数列，但编程结果并不理想；此外我们认为策略的合理性可以由其成功率决定，即这个

4、策略的合理性较为欠缺；最后我们通过搜集资料，在问题结果的讨论中引入了部分算法优化的方法，相信将这些方法加以应用后，能够更好的解决此类博弈问题。关键词：博弈极大极小算法概率论蒙特卡罗模拟33一、问题重述五子棋发源于中国，在中国民间流传着许多五子棋阵法,比如以下阵法：（.wuzi8./Article/HTML/1299.html）斜三阵：多由浦月、流星、丘月、游星、慧星演变而来。见图一。由本阵还可演变成一字长蛇阵，见图二。以及长勾阵，见图三。斜三阵的进攻多以成角或成半燕翼发起。四角阵（图四）：黑方四子呈四方形的摆布，因而得名。梅花阵：下图所示阵形因黑方四

5、子如梅花状而被称之为梅花阵。1.请建立数学模型或算法讨论以上阵法中执黑方获胜的策略；2.你的策略的合理性及获胜的概率如何？请说明及验证。（图片见附录）二、模型假设1.本文中不设置禁手。2.执黑者先手。3.棋盘规格为15行15列。4.开局阵法与题目中相同。5.下期过程假定为二人零和、全信息、非偶然的博弈过程。6.黑棋和白棋在对弈时都足够理智。三、符号说明符号说明黑棋白棋估值函数某局面下的估值组合种类白棋取胜的事件取胜方式集合扩展深度当前局面子节点四、问题分析33本文讨论了斜三阵、四角阵、梅花阵三种五子棋阵型中，先手必胜的策略及合理性检验。从五子棋的游戏

6、规则可知，这种黑白双方交替对抗的过程是一个博弈的过程。由假设可知，我们讨论二人零和、全信息、非偶然、无禁手的情况，是因为下棋时满足如下特征：1.对弈的双方轮流采取措施，博弈的结果只有三种情况，黑胜白负、白胜黑负及和局。2.对弈过程中，任何一方都充分了解当前格局及历史格局。3.在任何一方采取行动前都要根据当前情况分析得失，选择对自己有利而对对方不利的对策，而不存在运气因素。对于一方而言，它的行动方案有若干选择，且方案之间是“与”的关系，因为此时任何一个方案都有可能被对方选中，故需讨论每一种情况的发生。将这个“与”和“或”过程用图表示出来，就得到一棵博弈

7、树。由于五子棋的格局众多，故此博弈树很大，第一问中采用极大极小搜索原理，对一定深度的博弈树进行静态估值，通过比较找到当前最优行动方案，即黑棋所要采取的一种策略。一、问题一的模型建立与分析5.1模型准备5.1.1做出博弈树不妨设博弈的黑棋为,白棋为，为了清楚的表现博弈的过程，下面站在黑棋一方作出一定深度的博弈树，定义如下：1)将博弈的初始格局（斜三阵、四角阵、梅花阵）设为初始节点。2)所有使自己一方“获胜”的终局认为是可解节点；所有是对方“获胜”的终局认为是不可解节点。3)一方扩展的节点之间是“或”的关系；一方扩展的节点之间是“与”的关系。可见在这棵博

8、弈树中，每个格局可供选择的方案都很多，如果试图通过直到终点（一方五子相连或棋面无空位）的与或树搜索而得到最好