巴什博弈

博弈问题的特点

1.博弈模型为两人轮流决策的非合作博弈。即两人轮流进行决策，并且两人都使用最优策略来获取胜利

2.博弈是有限的。即无论两人怎样决策，都会在有限步后决出胜负

3.公平博弈。即两人进行决策所遵循的规则相同

1.巴什博弈

1、问题模型：有一个堆物品，物品数量为n个，两个人轮流从这堆物品中取物品，规定每次至少取一个，最多取m个，最后取光者得胜。

2、解决思路：当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)*r+s，（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。

关于此的题目的链接：https://ac.nowcoder.com/acm/problem/21844

在这里插入代码片#include <iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
   
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
   
        if(b%(a+1)==0)
            printf("You are loser\n");
        else
        {
   
            for(int i=1; i<=a; i++)
            {
   
                if((b-i)%(a+1)==0&&i<b)
                printf("%d ",i);
                else if(i>=b)
                    printf("%d ",i);
            }
            printf("\n");
        }
    }
}

结论:如果条件是最后取光者得胜，那么当先手面临的局势是n%(m+1)==0，先手必败
3、变形：条件不变，改为最后取光的人输。

结论：如果条件是最后取光者失败，那么当先手面临的局势是(n-1)%(m+1)==0时，先手必败。