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

要让自己赢，不一定非要自己处于最佳状态，我们可以考虑置对方于死地，让对面处于必输的状态，那么剩下就是我赢了！

巴什博弈

一共n颗石头，两个人轮流拿，每次可以拿1到m颗石头，拿到最后一颗石头的人获胜。根据n和m判断谁获胜。

结论

• 当前石子的数量可以整除m+1---->> 必输态
• 当前石子的数量不可以整除m+1------->> 必胜态

制胜策略

每次将状态调整为可以被m+1整除（即平衡态），让对方无法一次性取完，从而确保自己最终能取到最后一颗石头。

质数次方取石子问题

一共n颗石头，两个人轮流拿，每一轮可以拿走p的k次方颗石头。当前选手可以随意决定p和k，但p必须是质数，k是自然数。拿到最后一棵石头获胜。

结论

• 可以被6整除的状态 ----> 必输态
• 不可以被6整除的状态 ----> 必胜态

制胜策略

利用1, 2, 3, 4, 5这五个数可以直接取走的特性，将6的倍数作为平衡态。在平衡态下，对方无法一次性取完所有石头，因为6是两个质数2和3的乘积，必须被分解。因此，问题可以转化为m=5的巴什博弈问题。

尼姆博弈

一共有n堆石头，两个人轮流进行游戏。在每个回合中，玩家需要选择任何一个非空的石头堆，并从这堆石头中移除任意数量的石头（至少一个）。谁先拿走最后的石头就获胜。

结论

所有石头堆的数量进行异或运算，结果为0则为必败态，不为0则为必胜态。

策略

将异或结果为0的状态称为平衡态。在不平衡态下，玩家应该选择一个非空的石头堆，并移除一定数量的石头，使得剩余石头堆的数量异或结果为0。这可以通过将异或结果中不为0的位对应的石头堆进行调整来实现。

例如：
策略：将异或为0的结果为平衡态，在不平衡态，我们始终可以将一个数字降低，使得所有数字异或结果为0，也就是平衡态，为了便于理解，我们将所有数字转为二进制，比如00101001，01110101，10100110，比如这三个数字代表3堆石头，异或后发现，显然不为平衡态，那么如何将其转为平衡态呢，其实不难，我们先把所有数字异或的结果拿出来==>11111010，只需要控制最大的数变成一个确定的更小的数一定可以使其变为平衡态，(实际上将最大的数和异或结果再次异或，获得的结果就是这最大石头堆应该变成的数量，实际上他的意思就是消消乐)将10100110变成11111010^10100110=01011100

• 初始状态：0010 1001（第一堆），0111 0101（第二堆），1010 0110（第三堆）
• 异或结果：1111 1010（不为0，不平衡态）
• 调整策略：选择第三堆，移除1010 0110 - 0101 1100 = 0100 1010个石头
• 调整后状态：0010 1001（第一堆），0111 0101（第二堆），0101 1100（第三堆）
• 异或结果：00000000（平衡态）

对于另外一种情况是，00110000，00110000，00001010，前两个数异或完了为0，只剩下最后一个数，我们只将最后一堆取完即可。
这样，玩家就可以通过不断调整石头堆的数量，使游戏进入平衡态，从而确保自己最终能取到最后一颗石头。

反尼姆博弈

一共有n堆石头，两人轮流进行游戏
在每个玩家的回合中，玩家需要选择任何一个非空的石头堆，并且从这堆石头移除任何正数的石头数量，谁先拿走最后的石头就失败，返回最后谁会获胜。

与尼姆博弈不同的是，反尼姆是最后取走者输。

结论： 全部异或不为0为必胜态，否则为必败态
策略：依旧是一直转让平衡态，直到只剩下一堆石头的数量是大于1的(这必定是一个失衡态，也必定会在你的手上假如一直转让平衡态的情况下)，此时根据其他剩余一颗石头的堆数决定，是将这大于1个石头的堆取完还是留下一个，比如：

• 例一1(第一堆) 1(第二堆) 5(第三堆)
• 是不是直观的看出,当我从5取出4，也就赢了呢。
• 例二1(第二堆) 5(第三堆)
• 同样直观看出，当我直接把5取完，也就赢了。
• 例三5(第三堆)
• 直观看出，当我从5中取出4，也就赢了。
  以上举得例子已经代表了所有情况

SG函数

如果在理解了巴什和尼姆博弈后，再理解这个就不难理解了

• 我们可以利用SG函数来分析ICG游戏的胜负情况。首先，我们计算出每个状态的SG值：
• SG(0)=0（终止状态，无法移动，必败）
• 对于非终止状态n（n>0），其SG值G(n)等于所有可以从n转移到的状态m（m=n-1, n-2, …, n-m，且m>0）的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),所以这里只能取1；
sg(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的规律求解