前言

博弈论是 ACM 比赛中的一个考察知识点，不算特别常见，但每次区域赛总会有可能出现个一两题，在我参加的为数不多的几场比赛中，GDCPC，ICPC南昌站，ICPC香港站都有出现过这样的题目。博弈论的题目一般有个特点：一看就知道是要考博弈论，但如果没有思路就得自己玩上个大半天。为了以后遇到这样的题目不再需要和队友玩上几轮游戏，于是决定开始系统学习一下博弈论，本篇文章讲的就是三种最基本的博弈理论：巴什博弈、斐波那契博弈、威佐夫博奕。

ICG游戏

最基本的博弈论题目一般都是基于ICG游戏来进行的，即公平组合游戏，这类游戏一般具有以下几个特点：

• 竞争性：有两名玩家，且两名玩家是交替进行操作。
• 公平性：每步操作都是在有限的合法操作集合中选取一种进行，且合法操作只取决于局面本身，与操作者无关。
• 唯一性：不能再进行合法操作的玩家判负，不存在平局。

因此我们可以发现如果想入门博弈论，往往遇到的入门题目都是取石子或者跳台阶。同样，根据这个定义我们可发现，很多的日常博弈游戏并不是ICG游戏，例如象棋就不满足公平性条件，因为红方只能移动红子，黑方只能移动黑子，操作者会干涉合法操作。

巴什博弈

巴什博弈（Bash Game）是最基础的一种博弈游戏，它的规则一般如下：

有一堆数量为 n 的物品，两个人轮流从物品中取物，每次能取（1~m）个，最后取完的人获胜

很显然，如果 n=m+1 ，由于一次只能取（1~m）个物品，那么先手无论取多少个，后手都能一次拿完剩下的物品，后者取胜。因此我们可以发现取胜法则：我们令 n=k(m+1)+r ，很明显对于任意 n ，满足 0 ≤ r ＜ m+1 ，如果 r == 0 ，先手无论怎么取都会输，反之如果 r != 0 ，则先手在第一轮可以先取 r 个，在后面的轮次中，只要保证两人每次都取 m+1 ，就能保证先手赢。这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。

结论：若 n % (m+1) == 0 ，则先手必败，否则先手必胜

巴什博弈例题：HDU-2188

题目思路：
这题就是巴什博弈模板题，直接套用结论就可以解决。

AC代码：

#include <iostream>
#include <cstdio>
using namespace std;

int t,n,m;

int main()
{
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        if(n%(m+1)) printf("Grass\n");
        else printf("Rabbit\n");
    }
    return 0;
} 

斐波那契博弈

斐波那契博弈也是一种经典的博弈理论，

威佐夫博奕

参考资料

• ICG游戏
• 巴什博弈入门
• 三大博弈理论
• ACM博弈论基础

版权属于：PCsky

本文链接：http://www.hyouka.club/index.php/archives/167/

转载时须注明出处及本声明