常用博弈

发表于 | 分类于 ，

1. 巴什博弈(Bash's Game)

1.1 问题描述

只有一堆 n 个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取 m 个.最后取光者得胜.

另一种表述:

A 和 B一块报数，每人每次报最少 1 个，最多报 m 个，看谁先报到 n

巴什博奕是博弈论问题中基础的问题，它是最简单的一种情形对应一种状态的博弈。

1.2 分析

1.2.1 模拟分析

首先我们进行简单的分析

  • 若 \(n \leqslant m\):

    那么先手必赢

  • 若 \(n = m + 1\):

    那么无论先手拿几个，剩余的数量都在[1, m]之间，因此后手必赢

  • 若 \(m+2 \leqslant n \leqslant 2m\):

    那么先手可以先拿走一部分使得剩余的数量为m+1，情况退化为第二种情况，因此先手必赢

1.2.2 推导结论

经过以上分析，可以得出结论:

  1. 结论

    若轮到A时，还剩下 \(m + 1\) 个，则 A 必输

  2. 推论

    若轮到A时，还剩下 \(k(m+1)\) 个，则 A 必输

1.3 巴什博弈的最优策略

根据以上结论可以推导出最优策略:

想方设法通过拿走石子使得留给对方剩余石子为 \(k(m+1)\) 个

1.4 结果分析

通过以上描述我们可以知道，在都采取最佳策略的情况下，谁输谁赢是和n与m有关的:

  • 若 \(n = k(m+1) + r\):

    那么先手可以先拿走 \(r\) 个，留给后手 \(k(m+1)\) 个石子

    所以先手必胜

  • 若 \(n = k(m+1)\)

    那么后手必胜

1
2
3
4
5
6
def bashGame(n, m):
    '''巴什博弈'''
    if n % (m+1) == 0:
        print('后手必胜')
    else:
        print('先手必胜')

2. 尼姆博弈(Nim's Game)

2.1 问题描述

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走至少一颗”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负

2.2 结论

Nim博弈的分析较为复杂，直接上结论:

若n堆石子的数量异或的结果为 0 则先手必胜，否则后手必胜

换而言之，要求n个数写成二进制后，相同位(列向)上的 1 的总个数都要是偶数。

1, 3, 5
0 0 1
0 1 1
1 0 1

1
2
3
4
5
6
7
8
9
def nimGame(piles):
    '''尼姆博弈'''
    res = 0
    for x in piles:
        res ^= x
    if x == 0:
        print('先手必胜')
    else:
        print('后手必胜')

3. 威佐夫博弈(Wythoff's Game)

3.1 问题描述

描述1：有两堆石子，两个人在玩游戏，每次每个人可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子(至少一个)，不能取得人输，分析谁会获得胜利

描述2：一个棋子放在棋盘右上角，有两个玩家分别移动。移动方法有且仅有三种：向左若干格、向下若干格、向左下若干格，先移到左下角的人获胜

3.2 结论

对于两堆分别为n和m的石子:

若 \(n < m \land n = \lfloor (m-n) \times \phi \rfloor\)，其中 \(\phi = \frac{\sqrt{5} + 1}{2}\) 是黄金分割比，则先手必败
且 \((m, n)\) 是第 \((m-n)\) 个必败点

1
2
3
4
5
6
7
8
9
10
def wythoffGame(n, m):
    '''威佐夫博弈'''
    from math import floor, sqrt
    if n > m:
        n, m = m, n
    k = m - n
    if n == floor(k * (sqrt(5) + 1) / 2):
        print('后手必胜')
    else:
        print('先手必胜')

4. 斐波那契尼姆(Fibonacci nim)

4.1 问题描述

有一堆石子，两个人玩游戏，先取者可以取走任意多个，但不能全取完，以后每人取的石子数不能超过上个人的两倍

4.2 结论

若石子数是斐波那契数，则先手必败

1
2
3
4
5
6
7
8
9
10
11
12
13
def fibonacciGame(n):
    if n == 1:
        print('后手必胜')
        return
    i, j, cur = 1, 1, 2
    while cur < n:
        cur = i + j
        i = j
        j = cur
    if cur == n:
        print('后手必胜')
    else:
        print('先手必胜')