毕业设计-拈游戏的设计

《毕业设计-拈游戏的设计》由会员分享，可在线阅读，更多相关《毕业设计-拈游戏的设计（34页珍藏版）》请在金锄头文库上搜索。

1、中 北 大 学 2011 届 毕 业 设 计 说 明 书第 1 页 共 34 页 1 引言1.1 开发背景据说，拈游戏起源于中国，英文名字叫做“NIM” ，是由广东话“拈” （取物之意）音译而来，经由当年到美洲打工的华人流传出去，这个游戏一个常见的变种是将十二枚硬币分三列排成3,4,5再开始玩，我们这里讨论的是一般意义上的“拈”游戏。另外一种形式也称为取石子游戏，取石子问题是个家喻户晓的游戏。它的问题是这样的：“有一堆小石子共 100 颗，甲乙两人轮流取，每次可取 1 至 10 颗，取完的人为胜者,若甲先取乙后取，谁能获胜？”天下的游戏五花八门，必胜策略成为人们眼中的救星。而对必胜策略是否存在

2、的具体阐述是在博弈论当中。博弈论是研究竞争中参加者为争取最大利益应当如何做出决策的数学方法 1。 。博弈论又被称为对策论,是研究具有斗争或竞争性质现象的理论和方法，它既是现代数学的一个新分支，也是运筹学的一个重要学科。博弈要素：(1) 局中人：在一场竞赛或博弈中，每一个有决策权的参与者成为一个局中人。只有两个局中人的博弈现象称为“两人博弈”,而多于两个局中人的博弈称为“多人博弈”；(2) 策略：一局博弈中，每个局中人都有选择实际可行的完整的行动方案，即方案不是某阶段的行动方案，而是指导整个行动的一个方案，一个局中人的一个可行的自始至终全局筹划的一个行动方案，称为这个局中人的一个策略。如果在一个

3、博弈中局中人都总共有有限个策略，则称为“有限博弈”，否则称为“无限博弈”；(3) 得失：一局博弈结局时的结果称为得失。每个局中人在一局博弈结束时的得失，不仅与该局中人自身所选择的策略有关，而且与全局中人所取定的一组策略有关。所以，一局博弈结束时每个局中人的“得失”是全体局中人所取定的一组策略的函数，通常称为支付函数；中 北 大 学 2011 届 毕 业 设 计 说 明 书第 2 页 共 34 页 (4) 博弈涉及到均衡：均衡是平衡的意思，在经济学中，均衡意即相关量处于稳定值。在供求关系中，某一商品市场如果在某一价格下，想以此价格买此商品的人均能买到，而想卖的人均能卖出，此时我们就说，该商品的供

4、求达到了均衡。所谓纳什均衡，它是一个稳定的博弈结果 2。该课题主要是通过“拈游戏”的各种成功策略来对博弈论进行研究，针对“拈游戏”来研究几种博弈论的方法。1.2 国内外发展状况在所有双人对局游戏中，拈游戏是极其古老且饶富兴趣的一个课题。据说，拈游戏源自中国，经由被贩卖到美洲的奴工们外传。辛苦的工人们，在工作闲暇之余，用石头玩游戏以排遣寂寞。流传到高级人士，则用便士 (Pennils)，在酒吧柜台上玩。直到本世纪初，哈佛大学的数学教授 Chales Leonard Bouton 提出一篇极详尽的分析和证明，利用数的二进位表示法，在理论上解答了这个古老游戏的一般法则：对任意列数的铜板，每列有任意枚

5、数，如何取得致胜之道 3。二进制异或运算是不进位的加法运算：00=0,01=1,10=1,11=0。现定义：二进制数做不进位加法，和为 0 时，称为偶式；和不为 0 时，称为奇式。容易发现，偶式各个加数相同位上 1 的个数都是偶数，奇式各个加数相同位上 1 的个数至少还有一个数奇数。任意一个二进制数的不进位加法有两个重要的性质:(1) 和为偶式时，在这些数中任取一个数，减去一个小于等于这个数的数，所得的差和其他各个数的不进位加法的和一定为奇式。(2) 和为奇式时，总可以在这些数中找到一个数，将它减去一个适当的数后，使所得的差与其他各个数的不进位加法的和一定为偶式。利用这两个性质，在游戏中能获胜

6、时就必定能胜。原理是：石子取完后，各堆石子数都是 0，不进位加法是偶式。甲要取胜，在每次取石子前，各堆石子数的不进位加法和应为奇式。取石子时，要选择堆和取的个数，使剩下的石子数的不进位加法和为偶式。随后不管乙怎么取，取后剩下的石子数的不进位加法总是奇式。所以，取胜的诀窍就是：把偶式留给对方 4。中 北 大 学 2011 届 毕 业 设 计 说 明 书第 3 页 共 34 页 1.3 本课题的研究内容本课题研究的题目是：拈游戏的设计。Nim 游戏是组合游戏(Combinatorial Games)的一种，准确来说，属于“Impartial Combinatorial Games”（以下简称 IC

7、G） 。满足以下条件的游戏是ICG：(1) 有两名选手；(2) 两名选手交替对游戏进行移动(move)，每次一步，选手可以在有限的合法移动集合中任选一种进行移动；(3) 对于游戏的任何一种可能的局面，合法的移动集合只取决于这个局面本身，不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它什么因素；(4) 如果轮到某名选手移动，且这个局面的合法的移动集合为空（也就是说此时无法进行移动） ，则这名选手负。根据这个定义，很多日常的游戏并非 ICG。例如象棋就不满足条件(3)，因为红方只能移动红子，黑方只能移动黑子，合法的移动集合取决于轮到哪名选手操作 5。通常的 Nim 游戏的定义是这样的：

8、有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿） ”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动） 。本文主要的研究内容包括：(1) 完成人-机拈游戏的设计；(2) 游戏开始前设计必要参数：每堆石子个数，堆的数目，人人方式，还是人机方式；(3) 生成石子堆；(4) 移动石子；(5) 判断结果。2 开发工具C+ Builder 优化的 32 位原码（Native Code）编译器建立在 Borland 公司久经考验的编译技术基础之上，提供了高度安全性、可靠性、快速性的编译优化中 北 大 学 2011 届 毕 业 设

9、计 说 明 书第 4 页 共 34 页 方法，完全编译出原始机器码而非中间码，软件执行速度大大提高。在编译和连接过程中，C+ Builder 自动忽略未被修改的原代码和没有使用的函数，从而大大提高了编译和连接速度。C+ Builder 的 CPU 透视工具包括五个独立的小面板，可以对正在运行程序从内部进行深层次的了解。另外 C+ Builder 还提供了一个专业开发环境所必需的命令行工具，以帮助建立 C+程序或者准备编译和连接的程序进行更精细的控制。 C+ Builder 可以编译所有符合 ANSI/ISO 标准的原代码，支持最新 ANSI C+/C 语言特征：模板（Templates） 、例

10、外（Exceptions） 、运行类型信息（Runtime Type Information） 、Namespaces 等，另外它还可以使用标准 C+库且支持标准模板库（STL） ，以前的所有 C+/C 原代码可以不经过修改，直接移植到C+ Builder 环境下来。C+ Builder 完全支持 32 位长文件名、多线程程序设计，且允许程序员直接调用任何 Win95 和 NT API 函数。 C+ Builder 的集成开发环境（IDE）提供了可视化窗体设计器、对象观察器、控件板、工程管理器、集成编辑器和调试器等一系列可视化快速应用程序开发（RAD）工具，让程序员可以很轻松地建立和管理自己的

11、程序和资源 6-8。C+ Builder 提供了方便的代码编辑功能。尽管你可以使用记事本、Word 或其它任何文本编辑器来写代码，但除非特殊需要，否则那将是极为低效的方法。相反，现在的编程集成环境，都相当的智能，例如：代码自动功能，可以在很多情况下自动完成我们所需的代码，既准确又迅速。可视化的程序界面设计功能。你所要产生的窗口，在设计期间就真实地出现，包括字体、颜色和定位。比如：你不仅可以插入 falsh 的动画，而且无需运行，就直接可以在你的界面上看到该动画的演播，这是别的编程环境不能做到的。3 系统分析3.1 需求描述3.1.1 系统需求本系统硬件环境：CPUAMD2800+，内存 512

12、M 以上，硬盘 80G 以上。本系统软件环境：操作系统 Windows XP，Borland C+Builder 5。中 北 大 学 2011 届 毕 业 设 计 说 明 书第 5 页 共 34 页 3.1.2 系统设计思想及功能设置系统需求分析的目标就是明确系统开发的目标和用户的使用需求，提出新系统的逻辑方案。(1) 总体需求根据系统开发的要求，确定系统功能模块，并对其进行模块划分工作。如图3.1 所示为系统模块设计图。拈游戏的设计游戏入口系统操作游戏配置堆数的选择每堆石子数对弈的方式演示区设置操作区设置结果的判定图 3.1 系统模块设计图(2) 功能设计分析1）参数配置界面需求参数配置界面

13、需求分析，定制配置界面内容。配置界面主要是开始游戏前对游戏相关的参数配置，包括：拈游戏中堆的数目，每堆石子的数目以及对弈模式地选择等。2) 游戏操作界面需求游戏操作界面需求分析，定制演示界面内容。演示界面即游戏运行界面，中 北 大 学 2011 届 毕 业 设 计 说 明 书第 6 页 共 34 页 该界面是游戏运行的动态界面，界面包括：演示区、操作区、状态显示区、结果的判定等。演示区是游戏动态运行的表现形式；操作区控制游戏进行演示；状态显示区即游戏运行时对弈双方的操作状态的显示，用于提示用户目前属于何种对弈状态；通过对次数和结果的判断掌握游戏规律。 3.2 可行性分析可行性分析包括两层含义：

14、一是可能性，二是必要性。通过可行性研究，可避免盲目投资，减少损失。下面从三方面来讨论 9：（1）经济可行性：主要是只指估算一个新的游戏系统开发所需要的投资费用和运算费用。本系统所需的软硬件成本比较低、投资小、在经济上是可行的。（2）操作可行性：系统能够正常运行，并能执行相应的操作，按照相关的操作正常输出，合理的提供给用户使用。（3）技术可行性：系统设计一定要考虑到业务未来发展的需要，尽可能设计得简明，降低个功能模块的耦合度，并能够充分的考虑其兼容性，系统能够支持硬件、软件等多层面的可扩展性。4 系统设计本章主要详细说明系统设计方法以及开发过程。内容主要包括算法设计、游戏界面设计、功能模块的实现

15、等。4.1 算法设计如果石头的数目是偶数，就把它们分为两堆，每堆有同样多的数目。这样无论对手如何取，你只要保证你取石子之后是安全局面，你就能赢。如果石头数目是奇数个呢？我们做如下分析：当 M=3 的时候，有两种情况， （2, 1） 、 （1, 1, 1） ，这两种情况都会是先拿者赢。当 M=5 的时候，和 M=3 类似。无论你怎么摆，都会是先拿者赢。若 M=7 呢？情况多起来了，也是先拿者赢。在对拈游戏进行设计时，用到了很重要的一个运算就是二进制异或运算（XOR） ，这个运算是解决拈游戏设计关键。异或运算规则如下 10-11：XOR（0, 0）= 0；中 北 大 学 2011 届 毕 业 设

16、计 说 明 书第 7 页 共 34 页 XOR（1, 0）= 1；XOR（0, 1）= 1；XOR（1, 1）= 0。首先看整个游戏过程，从 N 堆石头（M1, M2, , Mn）开始，双方斗智斗勇，石头一直递减到全部为零（0, 0, 0） 。当 M 为偶数的时候，取胜策略是把 M 分成相同的两份，这样就能取胜。开始：（M1, M1）,它们异或的结果是 XOR（M1, M1）= 0。中途：（M1, M2） ，对手无论怎样从这堆石头中取，XOR（M1, M2）!= 0。己方：（M2, M2） ，己方还是把两堆变相等。XOR（M2, M2）= 0。最后：（M2, M2） ，己方取胜。类似的，若 M 为奇数，把石头分成（1, 1, ,1）奇数堆的时候，XOR（1, 1,1）奇数个 !=0。而这时候，对方可以取走一整堆，XOR（1, 1, 1）偶数个=0，如此下去，己方必输。推广到