博弈论 Game Theory

发表于 更新于 分类于 ， 阅读次数： 本文字数： 787 阅读时长 ≈ 3 分钟

经典ICG博弈算法(Impartial Combinatorial Games 公平组合游戏)

  1. 有两名选手;
  2. 两名选手交替操作，每次一步，每步都是在有限的合法集合中选取一种进行;
  3. 在任何情况下，合法操作只取决于情况本身，与选手无关;
  4. 游戏的败北条件为:当某位选手需要进行操作时，当前没有任何可以执行的合法操作，则该选手败北。

巴什博弈 Bash Game

题目：一堆n个物品，两个人轮流从中取出1~m个，最后取光者胜（不能继续取的人输）。

同余定理：n=k∗(m+1)+r，先者拿走r个，那么后者无论拿走1 m个先者只要的数目使和为m+1，那么先手必赢。反之若n=k∗(m+1)，那么先手无论怎样都会输。

1
2
if ( n % (m + 1) ) return false;
else return true;

斐波那契博弈 Fibonacci Nim Game

题目：一堆石子有n个，两人轮流取，先取者第一次可以去任意多个，但是不能取完，以后每次取的石子数不能超过上次取子数的2倍。取完者胜。

先手胜当且仅当n不是斐波那契数

1
2
3
4
5
6
7
f[0] = f[1] = 1;
for (int i = 0; f[i - 1] < n; i++)
{
    f[i] = f[i - 1] + f[i - 2];
    if (f[i] == n)  return true;
}
return false;

威佐夫博弈 Wythoff Game

题目：有两堆各若干物品，两个人轮流从任意一堆中至少取出一个或者从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜。

首先算出差值，插值*黄金分割比==最小值的话后手赢，否则先手赢。（可能涉及高精度问题）

1
2
3
4
double r = (sqrt(5) + 1) / 2;
int d = abs(a - b) * r;
if (d != min(a, b)) return true;
else return false;

尼姆博弈 Nimm Game

题目：有n堆物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜。

将n堆物品的数量全部异或后为0则结果必败，否则必胜。

1
2
3
4
5
int res = 0;
for (int i = 1; i <= n; i++)
    res ^= arr[i];
if (res)  return true;
else  return false;

SG函数 Sprague–Grundy function

  • Suppose current game state is X.

  • If X is a terminal state, SG(X) = 0.

  • 令每个局面为一个状态，SG值为X

  • 结束状态SG值为0

SG函数是将一般的ICG问题抽象为有向图模型。

MEX (Minimum EXcluded)

MEX of a set of non-negative integers is the smallest non-negative integer not in the set.

MEX 是对集合的运算，找出集合中不包含的最小非负整数值。

Example:

  • mex{0,2,4}=1;
  • mex{0,1,2,,4}=3;
  • mex{}=0.

SG function

Let y are positions which X can reach

$$
SG(X) = mex(SG(y))
$$

$$
SG(X) = mex(SG(y)|y 是 x 的后继)
$$

Build

  1. 找出必败态
  2. 找出前驱点
  3. 计算SG值

SG Theory

设G1,G2,…Gn为n个“有向图”游戏的和(Sum)，游戏G的移动规则是：任选一个子游戏Gi并移动上面的棋子

$$
sg(G)=sg(G_1)\oplus sg(G_2)\oplus …\oplus sg(G_n)
$$

参考资料

[1].浅谈博弈论-掘金

[2].博弈论基础-sjj

[3].game-theory