博弈论

发布时间 2023-08-18 13:34:29作者: 匿名人士W

巴什博弈Bash

 1堆n个石子,每次最少取一个,最多取m个

例如 m = 4

判断此刻先手状态(1为胜,0为败)

n = 0, 0

n = 1, 1

n = 2, 1

n = 3, 1

n = 4, 1

n = 5, 0

n = 6, 1

n = 7, 1

n = 8, 1

n = 9, 1

n = 10, 0

当 n % (m + 1) == 0 时 先手必败

尼姆博弈Nim

Nim1

有n堆石子,每堆石子的数量分别是a1,a2,a3……,两个人依次从这些石子堆中选一堆,拿取任意的石子,至少一个,最后一个拿光石子的人胜利

面对异或结果为0的玩家必输。

Nimk

有n堆石子,每堆石子的数量分别是a1,a2,a3……,两个人依次从这些石子堆中选 [1, k ] 堆,拿取任意的石子,至少一个,最后一个拿光石子的人胜利

把所有数字(每堆石子的个数)转化成二进制后, 求每一位上1的个数numi, 如果每一位都满足  numi % (k + 1) == 0, 那就是必败态