文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工作范文 > 演讲/主持 > 我们从Nim游戏开始
侵权投诉

我们从Nim游戏开始

博弈论

我们从Nim游戏开始:

回忆(一)最后提到的Nim游戏:

甲乙两人从N堆石子中取石子,每堆石子个数分别为ai。每人每次从一堆中至少取一个。谁不能取就算输。问什么情况下必胜,什么情况下必败。

我们的结论是给出了一个函数f(s)=a1 xor a2 xor a3 ... xor an,当f(s) = 0时,此时为必败态,否则必胜态。 这个结论的得来实际上使用了游戏的组合的一个结论。

我们先看图游戏:我们给出一个有向图作为棋盘,现在在棋盘上放一个棋子,两个选手每人每次可以沿着图中的边移动棋子。谁不能移动就算输。

如果图中不存在环,那么游戏肯定会结束:即不会出现平局。我们现在假定以下的讨论都不存在平局。

要解决图游戏,我们引入SG函数的定义。

对于棋子在图中某一个点v的局面,对应的SG函数如下:

若v出度为0,则SG(v) = 0,否则 SG(v) = min{n | n ≠ SG(u)} 边(v,u)存在。

一个最重要的结论就是若SG(v) = 0,则为v必败态,否则为必胜态。证明是十分简单的:

如果SG(v) = 0,说明此时你把棋子移动到u,则SG(u)一定不等于0。反之若SG(v) ≠0,则一定可以移动到0的状态。而最后停在SG(v)=0的无出度点为必败,所以原命题得证。

有人可能会觉得,直接用必胜态和必败态也可以解决这个问题,而且明显更简单,我们何必引入这个较复杂的函数呢?其实,这个函数具有更重要的作用。能够在更短的时间内处理更复杂的一类游戏:游戏的和。

在看游戏的和之前,我们回到Nim游戏,看看它一堆的时候会是什么情况:我们很容易把一堆石子的情况映射成一个图游戏。其中点v的编号就代表石子数,则存在边(u,v)的条件即(v<u)。

很容易推出来,在这个图中,SG(v) = v的编号;

Nim游戏就是上面这个游戏的一个和。我们有很多个游戏合起来(这里是很多个一堆的Nim游戏),每一次一个游戏者玩哪一个都是可以的(你可以在任何一堆中进行)。不能走的为输。

Nim游戏的结论就是游戏的和的一个重要的结论:对于新游戏的一个状态s = {v1, v2, v3, ... ,vn},其中vi表示在第i个图游戏的状态。有SG(s) = SG(v1) xor SG(v2) xor SG(v3) xor ... xor SG(vn)。

以上结论算是这篇文章的重点。有了这个结论和前述SG函数的性质,便可以解决很多复杂的游戏问题了。

第1页

你可能喜欢

热门文档

相关文档

  • Nim游戏-博弈论

    同样,如果一开始两堆的石子数相 等,第二个玩家就可以完全模仿第一个玩家的操作以获得胜利。 四、结论的抽象与泛化 在前一部分,我们分析了Nim游戏在n=2时的规律...

  • 浅析nim游戏与sg函数

    这游戏看上去有点复杂,先从简单情况开始研究吧。如果轮到你的时候,只剩下一堆...证毕。 根据这个定理,我们可以在 O(n)的时间内判断一个 Nim 的局面的性质,...

  • Nim取子游戏

    我们以一个两堆硬币的 Nim 取子游戏作为试验。 设游戏开始时游戏处于非平衡状态。这样,游戏人 I 就能通过一种取子方式 (见下归纳)使得他取子后留给游戏人 II...

  • Nim游戏(博弈论中的组合数学问题)

    + ei = 偶数 a0 + b0 + ….+e0 = 偶数 Nim 取子游戏才是平衡的,否则,就是不平衡的 于是我们有: 游戏人 I 能够在非平衡的 Nim 取子游戏中获胜, ...

  • A Nim-like Game on the Integers

    Nim取子游戏 4页 5财富值 我们从Nim游戏开始 2页 1财富值 A game on ... The purpose of this paper is to investigate a new nim-like combinatorial...

  • NIM(2)“拈”游戏分析

    NIM(2)“拈”游戏分析_IT/计算机_专业资料。计算机类求职常用笔试训练:编程之...还不信?那我们试试看:当 M=9,随机分堆为(1,2,6) 开始:(1,2,6) 1=...

  • NIM k问题

    所以我们可以随意指定第X位上的数字。 最后研究一下misere version of Moore's Nim k。misere version of Nim,即是在游戏规则不变的前提下,改变最后判断胜负的...

  • NIM安装流程

    执行 smitty nim_bosinst,开始安装 NIM 客户端 6. 选择客户端安装类型,我们选 mksysb 7. 选择需要安装的 image 的名字,我们选'v3_mksysb' 8. 选择 SPOT 的...

  • IBM AIX NIM 安装实例

    客户机会重起,选择显示器,语言,硬盘等等,开始客户机安装过 程,然后客户机重起。 八 从没有操作系统的客户机上进行 nim 安装 以上我们总结了如何从 nim server ...

  • NIM 快速安装手册

    安装过程开始. ___25. 安装结束后系统会重启,并出现登录提示符 以 root 用户登录 Lab 3 – AIX mksysb installation NIM Server Setup ___1. 创建 JS21 的...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email