组合博弈入门

简单描述

组合博弈定义
①有两个玩家
②游戏的操作状态是一个有限集合(比如:限定的总的牌的数量
③游戏双方轮流操作
④双方每次操作符合游戏规定(按规定取牌数量取牌
⑤当一方不能继续进行的时候,游戏结束,同时,对方为获胜方
⑥无论如何操作,游戏总能在有限次数操作后结束


必败点、必胜点


定义:

必败点(P点):前一个选手(Previous player)将取胜的位置称为必败点(即将要在这个点操作的玩家,一定会输)

必胜点(N点):下一个选手(Next player)将取胜的位置称为必胜点(在必胜点的玩家不一定赢,是要在不犯错误的情况下,整个游戏才会赢)

属性:

一、所有终结点是必败点(P点);(终结点有限且易标记)
(终结状态:是游戏进行不下去的点;而必败点是游戏可能还能进行下去,改变不了要输的命运)
举个例子:每次取牌规则是两张或三张;则终结点为 剩0张 或 剩1张
所以:必败点不一定是终结点,但终结点一定是必败点

二、从任何必胜点(N点)操作,至少有一种方式可以进入必败点(P点);
因为必胜点不一定怎么走都赢,一定至少一种方式进入必败点
举个例子:剩三张牌,取牌规则(1,2,3),若取了两张或一张,一定是对方赢自己输

Nim游戏

游戏简介:
①有两个玩家
②有三堆扑克牌(比如;5,7,9
③游戏双方轮流操作
④玩家每次操作是选择其中某一堆牌,然后从中取走任意张
⑤最后一次取牌的一方为获胜方

由题引入:
Nim-Sum:按位的异或运算

SG函数的含义以及实现

sg函数的定义:
X节点的sg值是除去后继点的sg值得最小非负整数。

sg函数的使用:
必败点:节点sg值等于0
必胜点:节点sg值大于0

解决的问题:组合游戏

引入定理:
如果图游戏G有若干个子图游戏Gi组成,即:G=G1+G2+···+Gn,假设gi是Gi(i=1,,,n)的SG函数值,那么,图游戏的SG值计算如下:
g(x1···xn)=g1(x1)^···gn(xn)


多个组合游戏的并
给定若干个组合游戏,可以按照下面的规则将它们并成一个新的游戏。
l 对每个游戏给定初始状态。
l 两人轮流走步,从A开始。
l 每一轮,选择一个未到达终止状态的游戏,在这个游戏中按照规则走一步,其他游戏的状态不变。
l 最后一个走步者获胜,即走完之后所有游戏都到达终止状态。
我们称这个新的游戏为“多个组合游戏的并”。我们要来看如何用每一个游戏的SG函数来求这个新的组合游戏的SG函数。
g(x1···xn)=g1(x1)^···gn(xn)

简单例题

题述

组合博弈入门_第1张图片

题目大意

有n堆苹果,每堆有mi个
两人轮流取,每次可以从一堆苹果中取任意连续个苹果
最后取光者为输
Fra先下,问是否可以获胜

输入输出

组合博弈入门_第2张图片

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
int main()
{
     
    int n,m,a,sum,i;
    while(cin>>n)
    {
     
        m=0;//判断是否是孤单堆
        sum=0;
        for(i=0;i<n;i++)
        {
     
            cin>>a;
            if(a>1)//如果a=1即是孤单堆
            m=1;
            sum^=a;
        }
        if(m==0)
        {
     
            if(n%2==0)
            cout<<"Yes"<<endl;
            else
            cout<<"No"<<endl;
        }
        else
        {
     
            if(sum==0)
            cout<<"No"<<endl;//等于0,后手必胜
            else
            cout<<"Yes"<<endl;
        }
    }
    return 0;
}

所以我们只要判断孤单堆和富裕堆然后用尼姆博弈公式(nimm game)即可

你可能感兴趣的