博弈论
我们从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函数的性质,便可以解决很多复杂的游戏问题了。
同样,如果一开始两堆的石子数相 等,第二个玩家就可以完全模仿第一个玩家的操作以获得胜利。 四、结论的抽象与泛化 在前一部分,我们分析了Nim游戏在n=2时的规律...
这游戏看上去有点复杂,先从简单情况开始研究吧。如果轮到你的时候,只剩下一堆...证毕。 根据这个定理,我们可以在 O(n)的时间内判断一个 Nim 的局面的性质,...
我们以一个两堆硬币的 Nim 取子游戏作为试验。 设游戏开始时游戏处于非平衡状态。这样,游戏人 I 就能通过一种取子方式 (见下归纳)使得他取子后留给游戏人 II...
+ ei = 偶数 a0 + b0 + ….+e0 = 偶数 Nim 取子游戏才是平衡的,否则,就是不平衡的 于是我们有: 游戏人 I 能够在非平衡的 Nim 取子游戏中获胜, ...
Nim取子游戏 4页 5财富值 我们从Nim游戏开始 2页 1财富值 A game on ... The purpose of this paper is to investigate a new nim-like combinatorial...
NIM(2)“拈”游戏分析_IT/计算机_专业资料。计算机类求职常用笔试训练:编程之...还不信?那我们试试看:当 M=9,随机分堆为(1,2,6) 开始:(1,2,6) 1=...
所以我们可以随意指定第X位上的数字。 最后研究一下misere version of Moore's Nim k。misere version of Nim,即是在游戏规则不变的前提下,改变最后判断胜负的...
执行 smitty nim_bosinst,开始安装 NIM 客户端 6. 选择客户端安装类型,我们选 mksysb 7. 选择需要安装的 image 的名字,我们选'v3_mksysb' 8. 选择 SPOT 的...
客户机会重起,选择显示器,语言,硬盘等等,开始客户机安装过 程,然后客户机重起。 八 从没有操作系统的客户机上进行 nim 安装 以上我们总结了如何从 nim server ...
安装过程开始. ___25. 安装结束后系统会重启,并出现登录提示符 以 root 用户登录 Lab 3 – AIX mksysb installation NIM Server Setup ___1. 创建 JS21 的...
热门文档