基础博弈论（你输则我赢，我输则你赢）

博弈巴什博弈质数次方取石子问题尼姆博弈反尼姆博弈SG函数要让自己赢不一定非要自己处于最佳状态我们可以考虑置对方于死地让对面处于必输的状态那么剩下就是我赢了巴什博弈一共n颗石头两个人轮流拿每次可以拿1到m颗石头拿到最后一颗石头的人获胜。根据n和m判断谁获胜。结论当前石子的数量可以整除m1---- 必输态当前石子的数量不可以整除m1------- 必胜态制胜策略每次将状态调整为可以被m1整除即平衡态让对方无法一次性取完从而确保自己最终能取到最后一颗石头。质数次方取石子问题一共n颗石头两个人轮流拿每一轮可以拿走p的k次方颗石头。当前选手可以随意决定p和k但p必须是质数k是自然数。拿到最后一棵石头获胜。结论可以被6整除的状态 ---- 必输态不可以被6整除的状态 ---- 必胜态制胜策略利用1, 2, 3, 4, 5这五个数可以直接取走的特性将6的倍数作为平衡态。在平衡态下对方无法一次性取完所有石头因为6是两个质数2和3的乘积必须被分解。因此问题可以转化为m5的巴什博弈问题。尼姆博弈一共有n堆石头两个人轮流进行游戏。在每个回合中玩家需要选择任何一个非空的石头堆并从这堆石头中移除任意数量的石头至少一个。谁先拿走最后的石头就获胜。结论所有石头堆的数量进行异或运算结果为0则为必败态不为0则为必胜态。策略将异或结果为0的状态称为平衡态。在不平衡态下玩家应该选择一个非空的石头堆并移除一定数量的石头使得剩余石头堆的数量异或结果为0。这可以通过将异或结果中不为0的位对应的石头堆进行调整来实现。例如策略将异或为0的结果为平衡态在不平衡态我们始终可以将一个数字降低使得所有数字异或结果为0也就是平衡态为了便于理解我们将所有数字转为二进制比如001010010111010110100110比如这三个数字代表3堆石头异或后发现显然不为平衡态那么如何将其转为平衡态呢其实不难我们先把所有数字异或的结果拿出来11111010只需要控制最大的数变成一个确定的更小的数一定可以使其变为平衡态(实际上将最大的数和异或结果再次异或获得的结果就是这最大石头堆应该变成的数量实际上他的意思就是消消乐)将10100110变成11111010^1010011001011100初始状态0010 1001第一堆0111 0101第二堆1010 0110第三堆异或结果1111 1010不为0不平衡态调整策略选择第三堆移除1010 0110 - 0101 1100 0100 1010个石头调整后状态0010 1001第一堆0111 0101第二堆0101 1100第三堆异或结果00000000平衡态对于另外一种情况是001100000011000000001010前两个数异或完了为0只剩下最后一个数我们只将最后一堆取完即可。这样玩家就可以通过不断调整石头堆的数量使游戏进入平衡态从而确保自己最终能取到最后一颗石头。反尼姆博弈一共有n堆石头两人轮流进行游戏在每个玩家的回合中玩家需要选择任何一个非空的石头堆并且从这堆石头移除任何正数的石头数量谁先拿走最后的石头就失败返回最后谁会获胜。与尼姆博弈不同的是反尼姆是最后取走者输。结论 全部异或不为0为必胜态否则为必败态策略依旧是一直转让平衡态直到只剩下一堆石头的数量是大于1的(这必定是一个失衡态也必定会在你的手上假如一直转让平衡态的情况下)此时根据其他剩余一颗石头的堆数决定是将这大于1个石头的堆取完还是留下一个比如例一1(第一堆) 1(第二堆) 5(第三堆)是不是直观的看出,当我从5取出4也就赢了呢。例二1(第二堆) 5(第三堆)同样直观看出当我直接把5取完也就赢了。例三5(第三堆)直观看出当我从5中取出4也就赢了。以上举得例子已经代表了所有情况SG函数如果在理解了巴什和尼姆博弈后再理解这个就不难理解了我们可以利用SG函数来分析ICG游戏的胜负情况。首先我们计算出每个状态的SG值SG(0)0终止状态无法移动必败对于非终止状态nn0其SG值G(n)等于所有可以从n转移到的状态mmn-1, n-2, …, n-m且m0的SG函数值集合中不包含的最小非负整数。然后我们根据SG值判断胜负如果SG(n)0则先手必败如果SG(n)≠0则先手必胜。对于多组独立的游戏分别计算各组的sg值最后异或所有sg值如果结果不为0则为必胜态否则为必败态典型例子尼姆博弈sg() 对于sg(i)的计算首先有一个之前(对于所有小于i的j,取sg(j)的值)记录的所有sg结果的表对于i状态所有可到达的状态k,取表里不是sg(k)的值且最小的那个值就是s(j)值。例现在有n堆石头轮流取石头每次不得超过2颗石头计算sg值。sg(0) 0;sg(1) 1; 由于1可以到达sg(0),所以这里只能取1sg(2) 2; 2可以到达1 和 0的状态这里取当前石头数2;sg(3) 0; 由于3只能到达2 和 1那么出现过最小的值且3不可到达的sg值为sg(0)0;sg(4) 1; 以此类推观察sg表的结果是符合巴什博弈的结论的。sg(5) 2;sg(6) 0;这类博弈问题一般要么为暴力依次求出sg值求解答案要么观察前n个数据的sg值找出sg的规律求解