博弈论之威佐夫博弈

忘是亡心i 2022-05-27 11:26 176阅读 0赞

**威佐夫博弈**（Wythoff's game）是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

我们用(a\[k\]，b\[k\]) (a\[k\] ≤ b\[k\] ,k=0，1，2，......n)来表示两堆物品的数量，并且称这个为局势。

首先我们来从最简单的情况开始分析：

如果现在的局势是(0，0)，很明显此时已经没有办法再取了，所以肯定是之前的人在上一局中取完了。

假设现在的局势是(1，2)，那么先手只有四种取法。

（1） 如果先手取走“1”中的1个，那么后手就从“2”中取出2个，此时取完，所以后手胜利。

（2）如果先手取走“2”中的2个，那么后手取走“1”中的1个，此时取完，后手胜利。

（3）如果先手取走“2”中的1个，那么后手就在两堆中各取走1个，此时取完，后手胜利。

（4）如果先手在“1”和“2”各取走了1个，那么后手取走“2”中的1个，此时取完，后手胜利。

由此可得，先手必输。

是不是觉得这个后手好厉害，无论先手怎么取，后手都会胜利。

在学习威佐夫博弈之前，我也是这样认为的。不过，当你继续看完这篇博客，你也会轻松获得胜利。

为了让大家更好地理解威佐夫博弈，我们继续来进行具体分析。

假设现在的局势是（3，5），**首先根据上面分析的经验，我们知道先手肯定不能把任意一堆物品取完，这是因为每次可以从任意一堆取走任意个物品，那么后手就可以直接把另一堆取完，所以后手获胜。**

所以我们这里就不分析那些情况，来分析其他的情况。

先看在一堆中取的情况：

（1） 假设先手在“3”中取1个，后手就可以在“5”中取走4个，这样就变成了（1，2）的局势，根据上面的分析，我们知道是先手输，后手获胜。

（2） 假设先手在“3”中取2个，后手就可以在 “5” 中取走3个，这样也变成了（1,2）的局势了，还是先手输，后手获胜。

（3）假设先手在“5”中取1个，后手就在 “3”和“5” 中各取走2个，这样又成了（1，2）的局势了，先手输，后手赢。

（4）假设先手在“5”中取2个，后手就在 “3”和“5” 中各取走3个，这样变成了（0，0）的局势，先手输，后手赢。

（5）假设先手在“5”中取3个，后手就在 “3”和“5” 中各取走1个，也变成了（1，2）的局势，先手输，后手胜利。

（6）假设先手在“5”中取4个，后手在“3”中取走1个，还是（1，2）的局势，先手输，后手赢。

我们发现上面列举的这几种局势，无论先手怎么取都是后手赢。

我们可以来找找那些先手必输局势的规律

第一种（0，0）

第二种（1，2）

第三种（3，5）

第四种 (4 ，7）

第五种（6，10）

第六种 (8，13）

第七种 (9 ， 15）

第八种 (11 ，18）

第n种 （a\[k\]，b\[k\]）

我们把这些局势称为“**奇异局势**”

**我们会发现他们的差值是递增的，分别是0,1,2,3,4,5,6,7......n**

有兴趣的读者可以自己模拟一下过程进行验证

**我们用数学方法分析发现这些局势的第一个值是未在前面出现过的最小的自然数。**

继续分析我们会发现，每种奇异局势的第一个值(**这里假设第一堆数目小于第二堆的数目**)总是等于当前局势的差值乘上1.618

我们都知道0.618是黄金分割率。而威佐夫博弈正好是1.618，这就是博弈的奇妙之处！

即 a\[k\] = (int) （(b\[k\] - a\[k\])\*1.618） 注：这里的int是强制类型转换，注意这不是简单的四舍五入，假如后面的值是3.9，转换以后得到的不是4而是3，也就是说强制int类型转换得到的是不大于这个数值的最大整数。

在编程题中，有些题目要求精度较高，我们可以用下述式子来表示这个值

1.618 = (sqrt(5.0) + 1) / 2

下面我们来看一道威佐夫博弈的入门题

[点击打开链接][Link 1]

![20180417221816809][]

看了上面的推导，这个问题也就迎刃而解了。

由此我们给出代码：

![2018041722193355][]

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1527
[20180417221816809]: /images/20220527/9c15761d6d77460691c2b7294938fe65.png
[2018041722193355]: /images/20220527/925abe82dce24b93bd216b235e47692f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关 1072 威佐夫游戏(威佐夫博弈模板)

/ Wythoff Game:黄金分割先取完者赢威佐夫博弈：每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取一个局面

怼烎@/ 2024年02月17日 23:59/ 0 赞/ 38 阅读

相关威佐夫博弈

( d o u b l e ) a b s ( b − a ) ∗ ( 1.0 + s q r t ( 5.0 ) ) / 2.0 = = m i n ( a , b ) (

墨蓝/ 2022年08月30日 01:54/ 0 赞/ 130 阅读

相关博弈论--巴什博弈——HDU1846

/\巴什博弈：HDU--1846\/ \ include<iostream> using namespace std; int main() \{ int

以你之姓@/ 2022年08月27日 09:52/ 0 赞/ 168 阅读

相关博弈之威佐夫博弈详解

威佐夫博弈是博弈中的另一个经典模型。问题：首先有两堆石子，博弈双方每次可以取一堆石子中的任意个，不能不取，或者取两堆石子中的相同个。先取完者赢。分析：首

柔光的暖阳◎/ 2022年08月26日 01:15/ 0 赞/ 157 阅读

相关 51nod 1072 博弈威佐夫游戏

有2堆石子。A B两个人轮流拿，A先拿。每次可以从一堆中取任意个或从2堆中取相同数量的石子，但不可不取。拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失

怼烎@/ 2022年08月21日 13:56/ 0 赞/ 151 阅读

相关博弈论之Nim 博弈

写在前面：此类问题一般有如下特点： > 1、博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利。 > > 2、博弈是有限的。即无论

Myth丶恋晨/ 2022年07月28日 09:46/ 0 赞/ 166 阅读

相关 HDU 5973-Game of Taking Stones（威佐夫博弈-JAVA BigDecimal）

Game of Taking Stones Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/6553

左手的ㄟ右手/ 2022年06月16日 01:43/ 0 赞/ 136 阅读

相关 51nod 1185 威佐夫游戏 V2 （博弈+大数乘法模拟）

题目链接： [点击打开题目链接][Link 1] 题解：如果数据在106左右，可以直接用(b−a)∗5√\+12。但是这道题数据是1018，那么直接乘的话，肯定会有

ゝ一纸荒年。/ 2022年06月15日 02:13/ 0 赞/ 139 阅读

相关博弈论之威佐夫博弈

威佐夫博弈（Wythoff's game）是指的这样一个问题：有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不

忘是亡心i/ 2022年05月27日 11:26/ 0 赞/ 177 阅读

相关威佐夫博弈

首先威佐夫博弈的内容是：有两堆石子，两个顶尖聪明的人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取得人输，分析谁会获得胜利。第

た入场券/ 2022年03月22日 04:18/ 0 赞/ 179 阅读