算法竞赛中涉及博弈论的知识并不多

公平组合游戏

Nim游戏

Nim游戏是一个很经典的博弈论模型，这类题有个通法通解：求Nim和。以下面的题目为例

题目

给定 nn 堆石子，每堆有 a[i]a[i] 个石子 ，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

分析

类似于这种题，问是否有必胜策略，计算异或和(Nim和)。
定义异或和(Nim和)为：

Nim=a1⊕a2⊕a3⊕⋯⊕anNim = a_1 \oplus a_2 \oplus a_3 \oplus \dots \oplus a_n

异或和 != 0 先手玩家有必胜策略，后手玩家输

异或和 == 0 先手玩家输，后手玩家有必胜策略

原因：

  • 异或和 ≠ 0：意味着至少有一个堆的某些位是“不平衡”的，当前玩家可以通过调整某个堆的石子数，使异或和变为0，迫使对手进入必输局面。
  • 异或和 = 0：任何移动都会破坏平衡，使得对手可以采取策略让异或和再次归零，最终当前玩家被迫面对无法移动的局面。

code：

1
2
3
4
5
6
7
8
int nim_sum = 0;
for(int i=0;i<n;i++){
    int cache;
    cin >> cache;
    nim_sum ^= cache;
}
if(num_sum) cout << "先手玩家win\n";
else cout << "后手玩家win";