博弈论有关的算法知识

博弈论(Game Theory)，博弈论是指研究多个个体或团队之间在特定条件制约下的对局中利用相关方的策略，而实施对应策略的学科。

取石子游戏是典型的博弈论问题

取石子游戏分为三种：胜利方为抓走最后的石子的人

1. 巴什博弈：一堆石子，两人轮流取，每次最多m个，至少1个
2. 威佐夫博弈：两堆石子，两人轮流取，每次从任意一堆中取至少一个或者同时从两堆中取同样多的物品
3. 尼姆博弈：n堆石子（石子数量分别为 a1, a2, a3, ...），两人轮流取，每次选取一堆石子取任意多个，至少1个

巴什博弈

设定条件：1 堆石子 每次最多取m个、至少取 1 个

分析：

CASE 1：如果 n = m+1，那么由于一次最多只能取 m 个，所以，无论先取者拿走多少个，后取者都能都拿走剩余的物品，后者取胜。

CASE 2：n = (m+1)*r+s（r 为 任意自然数，s ≤ m），那么 先取者 要拿走 s 个物品，如果后者拿走 k（1 ≤ k ≤ m）个，那么先取者再拿走 m+1-k 个，结果剩下 (m+1)(r-1) 个，以后保持这样的取法，那么先取者肯定获胜。

CASE 3：n = r*(m+1) ，先手拿走 k（1 ≤ k ≤ m）个，那么后手再拿走 m+1-k 个，结果剩下(m+1)(r-1)个，以后这样保持，则后手胜。

总之，要保持给对手留下 （m+1）的倍数，就能获胜。

（m+1）的局面为 奇异局势

威佐夫博弈

设定条件：有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

对于两堆石子分别有a, b 个石子：

先手必输的奇异局面：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）

• 如果 a == (int)((b-a)*1.618) 则 先手必输，也就是后手一定能最后取完 1.618 = (sqrt(5.0) + 1) / 2
• 否则，先手有赢的可能

尼姆博弈

设定条件：有 n 堆石子，每堆石子的数量是 a1, a2, a3, ......，两人 一次从这些石子堆中的任意一个取任意的石子，至少 1 个，最后一个拿光石子的人胜利。

先手必败的奇异局势：所有石子数的异或和为零，则先手必败。

定理1：对于 的局面，一定存在某种移动使得 这时候，要将 改为 ，则 ，同时，满足这个条件的 一定也满足 ，因而这也是个合法的移动。

定理2：对于 的局面，一定不存在某种移动使得

例题：（sysu期中测试 第6题）取石子

myAI 类的实现的注意点：

• 对于 局面。这是一个奇异局面，所有只能使用随机函数 rand() 完成操作，随机选取一个非空的集合，然后随机选取一个取石子的数。
• 对于 的局面，有将其转化为后手必输的奇异局面，就是找到第一个大于xorsum的石子堆，选取 arr[i] - (arr[i]^xorsum) 个石子，则可以使得剩余石子的异或和为0。

示例代码：

class myAI{
public:
    myAI();
    bool chose_act_first(const int arr[])//选择是否先手
    {
		int xorSum = arr[0] ^ arr[1] ^ arr[2] ^ arr[3];
    	return (xorSum != 0);
	}
    void action(const int arr[],int& mission_idx,int& step)//选择动作 
    {
        int xorSum = arr[0] ^ arr[1] ^ arr[2] ^ arr[3];

        if (xorSum == 0) 
        {
            // 如果异或和为0，则使用随机策略
            int nonEmptyPiles = 0;
            for (int i = 0; i < 4; i++) 
            {
                if (arr[i] > 0) 
                {
                    nonEmptyPiles++;
                }
            }

            // 随机选择一堆非空的石子
            int randomIdx = rand() % nonEmptyPiles;
            int count = 0;
            for (int i = 0; i < 4; i++) 
            {
                if (arr[i] > 0) 
                {
                    if (count == randomIdx) 
                    {
                        mission_idx = i;
                        break;
                    }
                    count++;
                }
            }

            // 随机选择一个取石子的数量
            step = 1 + rand() % arr[mission_idx];
        } 
        else 
        {
            // 根据异或和选择最优策略
            for (int i = 0; i < 4; i++) 
            {
                int tempXor = xorSum ^ arr[i];
                if (tempXor < arr[i]) 
                {
                    mission_idx = i;
                    step = arr[i] - tempXor;
                    break;
                }
            }
        }
    }

};