必胜必败分析与SG函数


必胜必败分析与SG函数

必胜必败分析

概念

更明确的定义概念:

必胜点(N)

先手必胜点。

必败点(P)

先手必败点。

性质

所有终结点都是必败点;

从必胜点出发,存在一种方法能够进入必败点;

从必败点出发,无论如何都只能进入必败点。

算法

设计一种算法来分析,一个局面是先手必胜还是先手必败。

  1. 将终结点标为必败点;
  2. 将所有一步操作进入必败点的位置标为必胜点;
  3. 如果从某一个点开始,一步操作后只能进入必胜点,那么标记为必败点;
  4. 重复步骤2, 3.

记忆化搜索的过程,可以画出博弈树

例子

描述

一个 $4$ 行 $3$ 列的矩阵,有一个小球放在左上角。两个人依次移动小球,每次只能:

  • 向右移动一格;
  • 向下移动一格;
  • 向右下移动一格。

最后无路可走的人输。两人按最优策略,问谁必胜。

解析

直接用 $4$ 行 $3$ 列的矩阵表示必胜必败情况。用*表示情况不确定,P表示必败,N表示必胜。

首先标记最终的点是必败点:

***
***
***
**P

之后推第四行。第四行的所有点,只能往右走,所以:

***
***
***
PNP

再看第三行。$(3, 3)$ 可以往下走到必败,所以是必胜点。$(3, 2)$ 可以往右下走到必败,所以是必胜点,$(3, 1)$ 同理,所以:

***
***
NNN
PNP

同样的,可以算出最后两行:

NNN
PNP
NNN
PNP

所以,先手必胜。

代码实现

两个人从一堆 $n$ 个物品中轮流取物品,每次取 $1, 3, 4$ 个物品,最后没法取的人输。分析必胜必败。

bool win[1001], vis[1001];//win[i]表示剩余i个物品时的必胜必败情况
void init() {
    win[0]=false;
    vis[0]=true;
}
void dfs(int x){
    if(vis[x]){
        return;
    }
    if(x>=1){
        dfs(x-1);
    }
    if(x>=3){
        dfs(x-3);
    }
    if(x>=4){
        dfs(x-4);
    }
    win[x]=false;
    if(x>=1&&!win[x-1]){
        win[x]=true;
    }
    if(x>=3&&!win[x-3]){
        win[x]=true;
    }
    if(x>=4&&!win[x-4]){
        win[x]=true;
    }
    vis[x]=true;
    return;
}

SG函数

组合博弈游戏

组合博弈游戏是这样一种博弈游戏:

  • 有两个游戏者
  • 有一个有限的游戏状态集
  • 游戏规则规定了在每一个状态可以到达的后继状态集。如果在任意状态,双方的走步集合是相同的,那么这个游戏是公平的,否则是不公平的。比如象棋是不公平的,因为每个玩家只能移动自己的棋子。
  • 两个人轮流操作
  • 一般情况下,当一方无法操作时,无法操作者输,游戏结束。

我是真找不到别的定义了……

对于任意一个公平的组合博弈游戏(ICG),我们将每个可能的局面当成图论当中的一个点。

在这个图中的连边规则是:把局面向这个局面经过操作后可能得到的所有局面连边,构成一个有向图。如果这个游戏对于任意的局面 $A$,都不能通过一些操作,回到这个局面 $A$,那么构成的图是一个有向无环图(DAG)。

SG函数

定义一个 $mex$ 函数,表示对于一个集合,不属于该集合的最小非负整数。比如 $mex\{0, 1, 2, 4\}=3$.

还是在这个博弈游戏中:两个人从一堆 $n$ 个物品中轮流取物品,每次取 $1, 3, 4$ 个物品,最后没法取的人输。

我们对每个状态进行分级,终结态的级别是 $0$. 如果一个状态能够变为 $0$ ~ $n-1$ 级的状态,那么这个状态是 $n$ 级状态。

状态 $1$ 能够变成 $0$ 级状态,称它为 $1$ 级状态;

状态 $2$ 只能变成 $1$ 级,不能变成 $0$ 级,所以它的级别为 $0$;

状态 $3$ 可以变为 $0$ 级,级别为 $1$;

状态 $4$ 可以变为 $0,1$ 级,级别为 $2$;

状态 $5$ 可以变为 $0,1,2$ 级,级别为 $3$.

在博弈游戏当中,SG函数定义为:$\operatorname{sg}(x)=mex\{\operatorname{sg}(y)\mid y$ 是 $x$ 的后继$\}$,也就是上面所说的状态等级。

对于一个ICG来说,状态 $x$ 是必败态,当且仅当 $\operatorname{sg}(x)=0$.

例子

两个人从一堆 $n$ 个物品中轮流取物品,每次取 $1, 3, 4$ 个物品,最后没法取的人输。

$\operatorname{sg}(0)=mex(\emptyset)$,

$\operatorname{sg}(1)=mex\{\operatorname{sg}(0)\}=mex\{0\}=1$,

$\operatorname{sg}(5)=mex\{\operatorname{sg}(4), \operatorname{sg}(2), \operatorname{sg}(1)\}=3$.

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();