我们把机试中会考到的博弈问题分为了下面四类

1、简单博弈问题
2、巴什博奕
3、尼姆博弈
4、威佐夫博弈
博弈类的题目大多都是考察同学们推理和观察能力，大多数题目背景都是两个人做游戏，并且两个人都足够聪明，然后判断最终谁会取得胜利。

简单博弈

一眼能看出胜败关系的博弈或者存在必胜或必败的博弈。

简单博弈
题目描述：
有2*n个硬币放在桌子上围成一个圆。现在甲和乙依次轮流拿硬币，每人每次最多拿k枚硬币，并且这K枚硬币必须相邻才能拿，每次最少要拿走1枚硬币，没有硬币拿的一方输掉比赛。

假设两个人都足够聪明，甲先拿，问甲能取得最后的胜利吗？
输入描述：
多组数据输入。
输入两个正整数n和k。（k <= n，n <= 10^9）
输出描述：
如果甲一定能赢则输出“WIN”，如果甲一定会输则输出"LOSE"，如果不能确定胜负则输出"?"。
输入样例#:
1 1
输出样例#:
LOSE
题目来源：
DreamJudge 1632

题目解析：很多同学刚看的时候觉得很难推出胜负关系，那是没有找到题目的重点，显然这个题的重点是圆，圆具有从任何方向都对称的性质。使用对称原理，不论甲拿几个，乙都可以在对称的位置拿一样的数量，这样不管甲怎么拿，都是乙必胜。

参考代码

#include<stdio.h>  
  
int main() {  
    int n, k;  
    while (scanf("%d%d", &n, &k) != EOF) {  
        printf("LOSE\n");  
    }  
    return 0;  
}  

简单变种问题

两个人轮流往一张圆桌上放硬币（硬币须全部在桌面上），当一方没有位置可放的时候，另一方获胜。问是否有一种策略可以判断是先手获胜还是后手获胜？如果有，策略是什么？

提示：也是利用圆的对称性

巴什博奕

两个顶尖聪明的人在玩游戏，有n个石子，每人可以随便拿1−m个石子，不能拿的人为败者，问谁会胜利？

巴什博奕是博弈论问题中基础的问题，它是最简单的一种情形对应一种状态的博弈。
我们从最简单的情景开始分析

当石子有1−m个时，毫无疑问，先手必胜
当石子有m+1个时，先手无论拿几个，后手都可以拿干净，先手必败
当石子有m+2−2m时，先手可以拿走几个，剩下m+1个，先手必胜

我们不难发现，面临m+1个石子的人一定失败。
这样的话两个人的最优策略一定是通过拿走石子，使得对方拿石子时还有m+1个
我们考虑往一般情况推广

设当前的石子数为n=k∗(m+1)+r
先手会首先拿走r个，接下来假设后手拿走x个，先手会拿走m+1−x个，这样博弈下去后手最终一定失败

设当前的石子数为n=k∗(m+1)
假设先手拿x个，后手一定会拿m+1−x个，这样下去先手一定失败

Brave Game
题目描述：
十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏...

题目练习

DreamJudge 1633 Euclid's Game
DreamJudge 1634 A interesting game