知識總結 博弈論入門

2022-09-22 09:22:55 字數 3076 閱讀 2735

我要是再不好好學博弈!就當場!把!這個!電腦螢幕!吃掉!

具有以下幾個性質的遊戲是組合遊戲:

為了簡化問題,oi 中的組合遊戲通常還具有以下性質:

例如,中國象棋是組合遊戲,但不是 oi 中的組合遊戲,因為兩個玩家操作規則不同(一個只能動紅子,一個只能動黑子)。

飛行棋不是組合遊戲,因為有隨機性(擲骰子)。

石頭剪刀布不是組合遊戲,因為不是輪流操作。

取石子(有若干堆石子,兩個人輪流從一堆中取任意多個,取完者勝)是組合遊戲。這個遊戲也是組合遊戲的一個經典模型。

cs: go 不是組合遊戲,上面那一堆性質除了兩名玩家勉強滿足外全部不符合。比如沙鷹**具有隨機性,除了透視以外的玩家不知道對方在哪(遊戲資訊不完整),雙方能起的槍和勝利條件不一樣(規則不同),國服官匹可以平局,玩家的操作規則不僅與遊戲狀態有關還與有沒有開掛有關等。

以下討論的組合遊戲都是 oi 中的組合遊戲,預設無法操作**移)時算輸。

既然遊戲一定能決出勝負,且操作規則僅僅與當前狀態有關,那麼就可以把狀態分為先手必勝和先手必敗(後手必勝),簡稱必勝和必敗。如果面對某個狀態的玩家(他還沒有操作,稱為先手)一定能獲勝,那麼它就是先手必勝否則先手必敗。

以取石子游戲為例,如果一個玩家面對的是沒有石子的狀態,那麼他就失敗了,也就是說「沒有石子」是先手必敗的狀態。如果一個狀態能轉移到一個先手必敗的狀態,那麼當前的先手一定會轉移到先手必敗的狀態,讓對方(也就是下一步的先手)面對這個必敗的狀態。因此,如果一個狀態能轉移到至少一個先手必敗的狀態,那麼這個狀態就是先手必勝的。否則,轉移到的所有狀態都是先手必勝,那麼這個狀態就是先手必敗的。

根據定義,狀態和轉移組成了一個 dag 。如果狀態數和轉移數很少,就可以直接做一遍遞推就能得出每個狀態是必勝還是必敗。

說到 sg ,你有沒有想到 ……

(來自萌娘百科)

對於一個遊戲狀態 \(s\) 定義 sg 函式:

\[sg(s)=\mathrm(\)

\]其中 \(t\) 是 \(s\) 可以直接轉移到的狀態(稱為「後繼」),\(\mathrm(s)\) 表示最小的不在集合 \(s\) 中的非負整數。

如果 \(sg(s)=0\) ,那麼 \(s\) 是必敗狀態,否則是必勝狀態,歸納證明如下:

根據定義,沒有出邊的狀態(必敗)的 sg 函式值是 0 ,滿足這個性質。當 \(s\) 能到達的所有狀態都滿足這個性質(因為是 dag 所以不存在迴圈歸納),如果存在 \(s\) 的後繼 \(t\) 滿足 \(sg(t)=0\) (必敗),那麼此時根據 mex 的定義, \(sg(s)>0\) ,是必勝的,否則是必敗的。

當然現在看來這個 sg 函式好像並沒有什麼用 ,只是把必勝必敗狀態用 0 和非 0 表示了一下 ……

不要嘗試找出 sg 函式的不同非 0 值有什麼實際意義,至少我至今不知道(誰知道給我說一下謝謝)。這只是一個巧妙的構造罷了。下面會說它巧妙在哪以及有什麼用。

說到 sg …… 啪!再扯 cs: go 打死你

定義兩個集合的笛卡爾積為從這兩個集合中各選出一個元素組成的有序二元組的集合。即 \(a\) 和 \(b\) 的笛卡爾積 \(a\times b\) 為:

\[a\times b=\

\]定義兩個組合遊戲的為把這兩個組合遊戲放在一起,遊戲之間互不影響。每個人任選一個遊戲進行操作,如果所有遊戲都無法操作就輸了。例如,把一堆石子看作一個組合遊戲,取石子游戲就是若干個這種組合遊戲的和。

現在討論 \(n\) 個小遊戲的和,方便起見稱這個和為「大遊戲」。顯然,大遊戲的狀態集合就是 \(n\) 個小遊戲的狀態集合的笛卡爾積。設大遊戲的狀態 \(s=(s_1,s_2,\dots,s_n)\) ,其中 \(s_i\) 是第 \(i\) 個小遊戲的狀態。

sg 定理(其中 \(\oplus\) 表示異或):

\[sg(s)=sg(s_1)\oplus sg(s_2)\oplus\dots\oplus sg(s_n)

\]證明如下:

設等號右邊那一堆的值為 \(x\) 。現在要證明兩件事:

根據 mex 的定義, \(sg(s)=x\) 當且僅當這兩個命題成立。

接下來口胡一番證明,我也不知道對不對 qwq。

對於所有小遊戲都無法操作的狀態 \(p\),所有 \(sg(p_i)=0\) 。由於這是無法操作的必敗狀態,\(sg(p)=0\) ,這種狀態下滿足這個性質。

依然是歸納證明。假設現在所有 \(s\) 能到達的狀態都滿足這個性質。設從 \(s\) 到後繼 \(t\) 操作的遊戲為 \(i\) ,由 mex 的定義顯然 \(sg(s_i)\neq sg(t_i)\) 。其餘的小遊戲是不變的,即 \(sg(s_j)=sg(t_j),j\in[1,i)\cup(i,n]\) 。因此, \(sg(t)=sg(s)\oplus sg(s_i)\oplus sg(t_i)\) 。

假設 \(sg(t)=sg(s)=x\) ,則給兩邊同時異或 \(x\) 得到 \(sg(s_i)\oplus sg(t_i)=0\) 即 \(sg(s_i)=sg(t_i)\) ,矛盾。因此 \(sg(t)\neq x\) 。第一個命題得證。

現在,對於 \(0\leq y,要找到一個 \(t\) 使得 \(sg(t)=y\) 。

因為\[y=sg(t)=sg(s)\oplus sg(s_i)\oplus sg(t_i)

\]所以

\[sg(s_i)\oplus sg(t_i)=sg(s)\oplus y

\]設 \(sg(s)\oplus y\) 的最高二進位制位(即 \(sg(s)\) 和 \(y\) 最高的不一樣的位)是第 \(k\) 位。由於 \(y,所以一定存在這樣的位,且 \(sg(s)\) 的第 \(k\) 位一定是 1 ,由此可得至少存在一個 \(sg(s_i)\) 的第 \(k\) 位是 1 。

把這樣的 \(i\) 作為這一步操作的遊戲。它需要變成的數 \(sg(t_i)=sg(s_i)\oplus sg(s)\oplus y\) 。由於第 \(k\) 位也是 \(sg(s_i)\) 和 \(sg(t_i)\) 最高的不一樣的位,且 \(sg(s_i)\) 這一位為 1 ,所以 \(sg(t_i)。

根據 mex 的定義,\(sg(s_i)\) 可以轉移到任意一個比它小的 \(sg(t_i)\) ,因此這樣的後繼狀態 \(t\) 一定存在。第二個命題得證。