本文主要是介绍Game Theory In Competitive Programming|Part1 (原创),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Game Theory In Competitive Programming|Part1
在算法竞赛中,博弈论是一个经常出现的题目类型。通常是两个人在给定规则下,每个人都按照最优策略进行博弈,我们的任务是找出获胜者。这通常是贪心算法、动态规划等算法的混合。下面,将对博弈论中的一些经典问题进行讨论。
文章目录
- Game Theory In Competitive Programming|Part1
- Bash game
- Nim game
- Misère Nim game
在这里,我们讨论的是博弈游戏中的一类,即能够找到必胜策略的博弈。
并分析它的通用策略是什么?
Bash game
巴什博弈是一个简单的游戏,我们将通过分析这个游戏来引出我们分析博弈游戏的通用策略
让我们考虑这样一个游戏:
题目:
最初有一堆数量为 15 15 15的石子,选手甲、乙交替操作,每次操作需要从石子堆中拿走不超过 3 3 3个石子。
甲先手操作,取走最后一个石子的选手获胜。请问最终谁获胜?
分析:
没错,这是一个有必胜策略的游戏。
如果必胜策略不明显的话,不妨手动写出所有的状态来观察规律。
(这是一种常用的解决博弈问题的手段)。
下图为当先手操作时,面对特定的石子数量的时候,游戏最终的结果:
(L:Lose,W:Win)。
石子个数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
最终结果 | L | W | W | W | L | W | W | W | L | W | W | W | L | W | W | W |
结论:
不难观察出,当石子个数被 4 4 4整除的时候,先手必败,否则先手必胜。
这是为什么呢?
是因为,几乎所有具有必胜策略的游戏,都遵守两条关于必胜态,必败态的准则:
- 如果当前状态能转移到必败态,当前状态是必胜态。
- 如果当前状态只能转移到必胜态,当前状态是必败态。
我们能知道的是, 0 0 0是一个必败态。而先手能一次拿走 1 ∼ 3 1\sim3 1∼3个石子。
故当石子个数为 1 1 1、 2 2 2、 3 3 3的时候,
这三个状态能转移到必败态,所以它们是必胜态。
于是我们可以抽象出一张图:(黑色是必败点,粉色是必胜点)。
现在我们将题目改的更普通一点还能得到必胜策略吗?
题目:
最初有一堆数量为 N N N的石子,选手甲、乙交替操作,每次操作需要从石子堆中拿走不超过 k k k个石子。
甲先手操作,取走最后一个石子的选手获胜。请问最终谁获胜?
必胜策略:
如果石子的个数是 ( k + 1 ) (k+1) (k+1)的整数倍,说明先手必败,否则先手必胜。
我们依然能通过画图列表来得到这个结论。
这说明它们是博弈游戏中通用的观察必胜策略的手段。
现在我们考虑另一个游戏来试验这种分析手段是否可行:
题目:
最初有一堆数量为 8 8 8的石子,选手甲、乙交替操作,每次操作可以从石子堆中拿走数量为 x x x的石头,
x x x是当前石子数量的约数,且小于当前石子数量。
甲先手操作,无法取石头的人输。请问最终谁获胜?
分析:
石头数量 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
最终结果 | L | W | L | W | L | W | L | W |
通过列表的方法,我们发现了这样的结论:当石头个数为奇数,先手必败,否则先手必胜。
Nim game
Nim游戏是博弈游戏中的一个重要角色,因为它和其他很多博弈有着相同的特性。
甚至能用相同策略进行解决,我们将重点讨论Nim游戏,Nim游戏的策略推广到其他博弈。
题目:
最初有 n n n堆石子,第 i i i堆石子最初有 x i x_i xi个。
A l i c e 、 B o b Alice、Bob Alice、Bob轮流操作,每次操作可以选择拿走一堆石子中取任意数量的石子(至少为 1 1 1)。
无法取石子的玩家输掉比赛。
这也是一个具有必胜策略的游戏。
结论:
设每一堆石子最初的数量异或和为: s s s ( s = x 1 ⨁ x 2 ⨁ . . . ⨁ x n ) (s=x_1\bigoplus x_2\bigoplus...\bigoplus x_n) (s=x1⨁x2⨁...⨁xn)。
当 s = 0 s=0 s=0的时候,先手必败,否则先手必胜。
分析:
不妨设 W W W是必胜态, L L L是必败态。
根据之前说的理论:
- 如果当前状态能转移到必败态,当前状态是必胜态。
- 如果当前状态只能转移到必胜态,当前状态是必败态。
需要验证 N i m g a m e Nim \:game Nimgame的结论是否符合上述理论:
1、当 s = 0 s=0 s=0时,拿走任意一堆的任意数量的石头,都会使得 s ≠ 0 s\neq0 s=0。
2、当 s ≠ 0 s\neq0 s=0时,总有方法拿走某个堆的某个数量的石头,使得 s = 0 s=0 s=0。
验证:
设 x 1 , . . . , x n x_1,...,x_n x1,...,xn是移动前的各堆石子数, y 1 , . . . y n y_1,...y_n y1,...yn是移动后各堆石子数。
s = x 1 ⨁ . . . ⨁ x n s=x_1\bigoplus...\bigoplus x_n s=x1⨁...⨁xn, t = y 1 ⨁ . . . ⨁ y n t=y_1\bigoplus...\bigoplus y_n t=y1⨁...⨁yn
可以进行等价变换:
t = 0 ⨁ t t=0\bigoplus t t=0⨁t
= s ⨁ s ⨁ t \:\: =s\bigoplus s\bigoplus t =s⨁s⨁t
= s ⨁ ( x 1 ⨁ . . . ⨁ x i ⨁ . . . ⨁ x n ) ⨁ ( y 1 ⨁ . . . ⨁ y i ⨁ . . . ⨁ y n ) \:\:\:=s\bigoplus (x_1\bigoplus...\bigoplus x_i\bigoplus...\bigoplus x_n)\bigoplus (y_1\bigoplus...\bigoplus y_i\bigoplus...\bigoplus y_n) =s⨁(x1⨁...⨁xi⨁...⨁xn)⨁(y1⨁...⨁yi⨁...⨁yn)
= s ⨁ ( x 1 ⨁ y 1 ) . . . ( x i ⨁ y i ) . . . ( x n ⨁ y n ) \:\:\:=s\bigoplus(x_1\bigoplus y_1)...(x_i\bigoplus y_i)...(x_n\bigoplus y_n) =s⨁(x1⨁y1)...(xi⨁yi)...(xn⨁yn)
= s ⨁ x i ⨁ y i \:\:\:=s\bigoplus x_i\bigoplus y_i =s⨁xi⨁yi
= s ⨁ x i ⨁ y i \:\:\:=s\bigoplus x_i\bigoplus y_i =s⨁xi⨁yi
x i x_i xi代表的是第 i i i堆在操作前的石子数量, y i y_i yi是操作后的石子数量,因为只操作了一堆,所以其他堆的异或值是 0 0 0。
理论 1 1 1:
-
当 s = 0 s=0 s=0时,拿走任意一堆的任意数量的石头,都会使得 s ≠ 0 s\neq0 s=0。
当 s = 0 s=0 s=0时,若想要 t = 0 t=0 t=0,那么说明 x i = y i x_i=y_i xi=yi,不可能实现。
理论 2 2 2:
-
当 s ≠ 0 s\neq0 s=0时,总有方法拿走某个堆的某个数量的石头,使得 s = 0 s=0 s=0。
当 s ≠ 0 s\neq 0 s=0时,若想要 t = 0 t=0 t=0,只需要令$ y_i=s\bigoplus x_i$ 即可,也就转证为是否存在一个堆满足 x i > s ⨁ x i x_i>s\bigoplus x_i xi>s⨁xi。
这是存在的:
设 d d d为 s s s二进制中最左边 1 1 1的位置。
可以选择第 i i i堆,使得 x i x_i xi在第 d d d位是 1 1 1(这样的堆一定存在不然 s s s的第 d d d位只能是 0 0 0)。
此时 y i = x i ⨁ s y_i=x_i\bigoplus s yi=xi⨁s 。
这也代表着, y i y_i yi 在 d d d的左边的所有位都与 x i x_i xi相同,但第 d d d位为 0 0 0,所以 y i < x i y_i<x_i yi<xi
Misère Nim game
这是Nim game的相反版本,因为它规定,取走最后一个石子的人是输家。
这样的情况是比较复杂的,因为我们不能简单的取反Nim game的结论。
我们假设Misère Nim game的获胜条件是:
设每一堆石子最初的数量异或和为: s s s ( s = x 1 ⨁ x 2 ⨁ . . . ⨁ x n ) (s=x_1\bigoplus x_2\bigoplus...\bigoplus x_n) (s=x1⨁x2⨁...⨁xn)
当 s = 0 s=0 s=0的时候,先手必胜,否则先手必败。
我们需要证明这是错的:
显然能找到反例,当只有 1 1 1堆,且这一堆的石子数量为 1 1 1的时候, s ≠ 0 s\neq 0 s=0,但先手败了。
所以简单的取反Nim game的结论是无法解决这样的问题的。
给出结论:
1、如果每堆石子个数都是 1 1 1,结论与Nim game相反
2、若存在石子数量大于 1 1 1的石子堆,此时结论与Nim game相同。
证明 1 1 1是对的:
如果每一堆石子个数都是1,如果有奇数堆,显然先手必败,如果有偶数堆,显然先手必胜。
证明 2 2 2是对的:
设先手面临的局面是: s ≠ 0 s\neq 0 s=0。
先手进行一次操作使得局面变为 s = 0 s= 0 s=0。
后手不管怎么操作,都只能将这个局面变为 s ≠ 0 s\neq 0 s=0。
不断这样下去,在游戏的终态总会出现两堆不一样的石子 ( s ≠ 0 ) (s\neq 0) (s=0)。
因为我们已经假设石子数大于 1 1 1,可以证明的是,在这种情况下,先手总是能迫使后手移走最后一个棋子。
设最终剩下了两堆石子,每堆石子的数量为 x x x, y y y ( x > y ) (x>y) (x>y)。
1、如果 y = 1 y=1 y=1,那么先手直接拿走 x x x,后手只能被迫拿走最后一个石头,先手获胜。
2、如果 y ≠ 1 y\neq 1 y=1,那么先手拿走 x − y x-y x−y,后手的操作情况如下:
- 拿走一堆,此时先手只需要将另一堆拿至剩下 1 1 1,后手只能被迫拿走最后一个石子,先手获胜。
- 将一堆拿至剩下 1 1 1,此时先手只需要将另一堆拿走,后手只能被迫拿走最后一个石子,先手获胜。
- 拿走一堆中的一些,此时先手仿照后手拿走另一堆的相同数量即可。
所有情况总是先手获胜,所以证明了结论2。
这篇关于Game Theory In Competitive Programming|Part1 (原创)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!