西南交大新秀杯数学建模

2015年西南交通大学 新秀杯数学建模竞赛

题目： B （填写A或B题）

组别： 大二组 （填写大一组或大二题）

姓名 学号 学院 专业 参赛队员1 参赛队员2 参赛队员3 电话 Email

西南交通大学教务处

西南交通大学实验室及设备管理处 西南交通大学数学建模创新实践基地

五子棋部分阵法研究的数学模型

摘要

五子棋游戏是一种益智类的博弈游戏，其开局阵型对棋局结果往往起决定性作用。本文通过构造博弈树，结合极大极小算法、运用机理分析与计算机模拟的方法，讨论了在五种开局阵型下黑子获胜的策略，及该策略实现的概率大小问题。

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

对于问题二，首先我们在问题二中做出了合理的假设，将问题转化为，在无初始阵型的前提下，若白棋随机性的落子，黑棋按照问题一中极大极小算法这一策略，取胜概率应如何；其次，我们首先考虑运用概率论的相关知识，通过机理分析，结合古典概型建立了在假设条件下黑棋不败的概率解析模型，但由于求解复杂，我们考虑采用蒙特卡罗模拟的方法，利用机理分析过程中的一系列结论，得到计算机模拟所需要的概率分布及随机数列，但编程结果并不理想；此外我们认为策略的合理性可以由其成功率决定，即这个策略的合理性较为欠缺；最后我们通过搜集资料，在问题结果的讨论中引入了部分算法优化的方法，相信将这些方法加以应用后，能够更好的解决此类博弈问题。

关键词：博弈 极大极小算法 概率论 蒙特卡罗模拟

1

一、问题重述

五子棋发源于中国，在中国民间流传着许多五子棋阵法,比如以下阵法：（http://www.wuzi8.com/Article/HTML/1299.html）

斜三阵：多由浦月、流星、丘月、游星、慧星演变而来。见图一。由本阵还可演变成一字长蛇阵，见图二。以及长勾阵，见图三。斜三阵的进攻多以成角或成半燕翼发起。

四角阵（图四）：黑方四子呈四方形的摆布，因而得名。

梅花阵：下图所示阵形因黑方四子如梅花状而被称之为梅花阵。

1.请建立数学模型或算法讨论以上阵法中执黑方获胜的策略；

2.你的策略的合理性及获胜的概率如何？请说明及验证。（图片见附录）

二、模型假设

1. 2. 3. 4. 5. 6.

本文中不设置禁手。 执黑者先手。

棋盘规格为15行15列。 开局阵法与题目中相同。

下期过程假定为二人零和、全信息、非偶然的博弈过程。 黑棋和白棋在对弈时都足够理智。

三、符号说明

符号 Max Min 说明 黑棋 白棋 估值函数 某局面下的估值 组合种类 白棋取胜的事件 取胜方式集合 扩展深度 当前局面子节点 Evaluate cijk nij A N MaxD Childset 四、问题分析

2

本文讨论了斜三阵、四角阵、梅花阵三种五子棋阵型中，先手必胜的策略及合理性检验。从五子棋的游戏规则可知，这种黑白双方交替对抗的过程是一个博弈的过程。由假设可知，我们讨论二人零和、全信息、非偶然、无禁手的情况，是因为下棋时满足如下特征：

1. 对弈的双方轮流采取措施，博弈的结果只有三种情况，黑胜白负、白胜黑负及和局。

2. 对弈过程中，任何一方都充分了解当前格局及历史格局。

3. 在任何一方采取行动前都要根据当前情况分析得失，选择对自己有利而对对方不利的对策，而不存在运气因素。

对于一方而言，它的行动方案有若干选择，且方案之间是“与”的关系，因为此时任何一个方案都有可能被对方选中，故需讨论每一种情况的发生。将这个“与”和“或”过程用图表示出来，就得到一棵博弈树。由于五子棋的格局众多，故此博弈树很大，第一问中采用极大极小搜索原理，对一定深度的博弈树进行静态估值，通过比较找到当前最优行动方案，即黑棋所要采取的一种策略。

五、问题一的模型建立与分析

5.1 模型准备 5.1.1 做出博弈树

不妨设博弈的黑棋为Max,白棋为Min，为了清楚的表现博弈的过程，下面站在黑棋一方作出一定深度的博弈树，定义如下：

1) 将博弈的初始格局（斜三阵、四角阵、梅花阵）设为初始节点。

2) 所有使自己一方“获胜”的终局认为是可解节点；所有是对方“获胜”的终局认为是不可解节点。

Min一方扩展的节点之间是3) Max一方扩展的节点之间是“或”的关系；“与”

的关系。

可见在这棵博弈树中，每个格局可供选择的方案都很多，如果试图通过直到终点（一方五子相连或棋面无空位）的与或树搜索而得到最好的一步是难以实现的，考虑到计算机存储空间的限制，我们只生成一定深度为20的博弈树，即在棋面一共落子20个时停止扩展节点。为了找到当前最优策略，需要对每个可能方案产生的后果进行比较，并将这一后果量化为得分。

3

图 1

5.1.2 构造估值函数

五子棋算法的评价函数需要考虑棋色，分别计算出它们各种组合（“眠三”、“眠四”、“活三”、“活四”等）的个数，根据经验及相关论文的结论[1]定义出各估价值，将个数乘以相应的估价值再求和，这样就得到了在某局面k下某种颜色棋子的估价Evaluate:

Evaluate(k)???cijk?nijk,

j?1i?162其中，i为棋色；j为组合种类；nij为各组合个数；cij为相应的估价值（见表1）

构造估价值时，根据假设，对于同一组合，黑棋的估价与白棋之和为0，即白棋各估价为黑棋的相反数。

表格 1

黑棋 五连 估价值 正无穷大 白棋 五连 估价值 负无穷大 5.2 模型建立

活四 1000 活四 -1000 眠四 300 眠四 -300 活三 300 活三 -300 眠三 120 眠三 -120 活二 30 活二 -30 易知，当Evaluate(k)<0时，值越小局面对白棋越有利；大于0则反之。故在每一个“或”节点，选取其子节点中一个最大的得分作为父节点的得分，使黑棋在可供选择的方案中选择对自己最有利的方案；对“与”节点，选取子节点中一个最小的得分作为父节点的得分，即白棋选择对黑棋最不利的方案。即：

Evaluate(kMax)?Max{Evaluate(kMax1),Evaluate(kMax2)....Evaluate(kMaxn)}

4

本文来源：https://www.bwwdw.com/article/5fyf.html