bash 博弈
转载并修改自:
http://www.cnblogs.com/wulangzhou/archive/2013/03/14/2959660.html
简单的取拿游戏
一堆石子(或者其它的什么东西),下面是简单的取拿游戏规则:
两名玩家,称为 I 和 II;
有一堆石子,一共 21 个;
一次移动操作包括取走 1 个,2 个,或者 3 个石子,至少得取走 1 个,至多取走 3 个。
玩家 I 先开始,交替取,不可不取。
取走最后一个石子的获胜。
我们可以反向推导。
如果只有 1 个,2 个或者 3 个石子留下,那么下一个将要移动的玩家获胜。
如果有 4 个留下,当前这个玩家取走后留下的石子数必然是 1 个,2 个或者 3 个,这样另一个玩家必胜,因此 4 对于将要开始移动的玩家而言是必败的局面,而对前一个玩家而言是必胜的局面。
如果有 5,6,7 个留下,玩家必须得给对方留下 4 个才能保证自己获胜。
如果有 8 个留下,那么下一个玩家必须留下 5,6,7 个,这样先前那个玩家获胜。
很容易发现,0,4,8,12,16 是我们希望留下的局面,我们希望状态尽可能向这些局面转化。由于本题起初是 21 个石子,由于 21 不是 4 的倍数,因此第一个玩家必然会赢,它只要留下的石子数是 4 的倍数对方就必然输。
这便是 bash 博弈。
P 态和 N 态
在前面的游戏中,0,4,8 等对于先前的玩家(Previous)而言是胜利的局面,称为 P 态。而 1,2,3,5,6,7,9,10,11.。。等对下一个玩家(Next)是胜利的局面,称为 N 态。
在这种无偏组合游戏中,可以从结尾倒推来找出 P 态和 N 态。
步骤1:将所有终结位置标记为必败点(P点);
步骤2: 将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;
步骤4: 如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。
很容易看到向 P 态移动会获胜,从一个 P 态开始,你的对手只能移动到 N 态,然后你再移动到 P 态,最终游戏在 P 态终结。
P 态和 N 态有几个特点:
(1) 所有终结点是必败点(P点);
(2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);
(3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点).
减法游戏
和上面的取石子游戏类似,假定有一个整数 n,两个玩家轮流从整数中减去一个数 s,其中 s 的取值来自集合 S,对于上面的取石子游戏,S = {1,2,3}。让我们通过类似的倒推找出 P 态。假定 S = {1,3,4}。容易发现 P 态集合是 {0,2,7,9,14,16,。。。}。所有态势集合形成一个循环节,长度为 7。
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
position P N P N N N N P N P N N N N P ...
来自《挑战程序设计竞赛》的例题:
Alice和Bob在玩这样一个游戏。给定k个数字a1,a2,...,ak。一开始,有x枚硬币,Alice和Bob轮流取硬币。每次取的硬币数量一定要在a1,a2,...,ak当中。Alice先取,取走最后一枚硬币的一方获胜。当双方都采取最优策略的时候,谁会获胜?假定a1,a2,...,ak当中一定包含1。
代码:
int X, K, A[MAX_K];
bool win[MAX_X + ];
void solve()
{
win[] = false;
for (int j = ; j <= X; j++)
{
win[j] = false;
for (int i = ; i < K; i++)
{
win[j] |= a[i] <= j && !win[j - a[i]];
}
} if (win[X]) puts("Alice");
else puts("Bob");
}
最新文章
- strrchr 一个获取扩展名的方便的php函数
- 【Java EE 学习 75 上】【数据采集系统第七天】【二进制运算实现权限管理】【权限分析和设计】
- python实用小技巧自问自答系列(一):查看类中函数文档doc的方法
- overflow 属性
- Remove Duplicates From Sorted Array
- OpenSSL - 文件和字符MD5加密实现
- oracle中的常用函数
- ubuntu安装 scala
- antuomake 生成configure的使用
- 【译】 AWK教程指南 8处理多行数据
- ServletContext对象(每个工程只有一个此对象)
- 转://Oracle 高可用技术与云基础架构
- JavaEE正常开发怎么做
- 【转载】Linux 命令行快捷键 - 移动光标
- python系列-2 正则表达式资料
- GDC2017 把“现实的天空”在游戏内再现【Forza Horizon 3】的天空表现
- JVM总结-反射
- js-ES6学习笔记-正则的扩展
- 深度学习数据集Deep Learning Datasets
- 十分有趣的this指向题