公平组合游戏（ICG）ACM入门篇

组合游戏（ICG）ACM入门篇"/>

公平组合游戏（ICG）ACM入门篇

什么是公平组合游戏

        在竞赛中，像两个人轮番进行游戏，并且两个人都是最精明的人，他们会采取当前情况下最优的策略进行决策。ICG还有一个特点，就是信息的公开性，一个人做什么操作，另外一个人是知道的，并作出相应的操作。公平组合游戏不是说这个游戏就是公平的，相反的在给出已知的量的时候，游戏的胜负已知。这类题目通常会给你一些比赛的条件，再告诉你谁先手，让你输出这个人先手的情况下，到底那个人能赢。这类问题的答案通常是某个人的id或者yes/no

常见的公平组合游戏

  1.巴什博弈

          是公平组合游戏中最简单的一种，题目一般为：一共n个物品，某人先手，每次至少从n个物品中拿出一个，最多拿出k个，拿走最后一件物品的人获胜。注意：公平组合游戏一定不存在环的，上面说的例子中，每次取出物品一定是不能为0个的，不然就会形成一个死循环，两个人每次都取0个，这样游戏就无法结束。

公平组合游戏一定能在有限步内结束

   巴什博弈的解决方法依赖于一个方程，n=(k+1)*m+r,我们知道任何数都能通过其他数字表示成方程右侧的形式，对于这个方程我们不关心m的大小，只关心k+1,n,r的关系，当r=0的时候，先手不论取多少物品（在条件范围内），假设取了c个，后手都可以取k+1-c,这样一轮游戏后就会取走k+1个物品，m轮之后必定是后手去完最后一个。当r0的时候，大家可以自行推到一下，会发现，先手有必胜的策略。因此解决巴什博弈就是找到k的取值。这里给大家留几个巴什博弈的题目：hdu1846 hdu4764 hdu1847。

        其他公平组合游戏再更新。。。。

SG函数和SG定理

        说到ICG肯定离不开SG函数，ICG有很多种类型，如果一一的划分他们的求解方法就太麻烦了，有没有解决ICG问题的通用解法呢？有！那就是SG函数，说SG之前再说一个博弈。Nim博弈

题目都是这样类型的： n堆物品，每堆有ai个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。这种题目的解法不妨告诉你，就是把所有的ai取异或，如果异或和为0则后生胜，否则先手胜。至于为什么。。回头有空再写QAQ.