網(wǎng)上找的一些數(shù)學(xué)基礎(chǔ)博弈sg函數(shù)

1、SG 函數(shù)給定一個(gè)有向無(wú)環(huán)圖和一個(gè)起始頂點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動(dòng)，無(wú)法移 動(dòng)者判負(fù)。事實(shí)上，這個(gè)可以認(rèn)為是所有 Impartial Combinatorial Games 的抽象模型。也就是說(shuō)，任何一個(gè) ICG 都可以通過(guò)把每個(gè)局面看成一個(gè)頂點(diǎn)，對(duì)每個(gè)局面和它的子局面連一條有向邊來(lái)抽象成這個(gè)“有向圖”。下 面就在有向無(wú)環(huán)圖的頂點(diǎn)上定義 Sprague-Garundy 函數(shù)。首先定義 mex(minimal excludant)運(yùn)算，這是施加于一個(gè)集合的運(yùn)算，表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)。例 如 mex0,1,2,4=3、mex2,3,5=0、mex=0。對(duì)

2、于一個(gè)給定的有向無(wú)環(huán)圖，定義關(guān)于圖的每個(gè)頂點(diǎn)的 Sprague-Garundy 函數(shù) g 如下：g(x)=mex g(y) | y 是 x 的后繼 。來(lái)看一下 SG 函數(shù)的性質(zhì)。首先，所有的 terminalition(終端態(tài))所對(duì)應(yīng)的頂點(diǎn)，也就是沒(méi)有出邊的頂點(diǎn)，其 SG 值為 0，因?yàn)樗暮罄^集合是空集。然后對(duì)于一個(gè) g(x)=0 的頂點(diǎn) x，它的所有后繼 y 都滿(mǎn)足 g(y)!=0。對(duì)于一個(gè) g(x)!=0 的頂點(diǎn)，必定存在一個(gè)后繼 y 滿(mǎn)足 g(y)=0。以上這三句話(huà)表明，頂點(diǎn) x 所代表的tion 是 P-ition 當(dāng)且僅當(dāng) g(x)=0（跟 P-itioin/N-ition 的 定

3、義的那三句話(huà)是完全對(duì)應(yīng)的）。通過(guò)計(jì)算有向無(wú)環(huán)圖的每個(gè)頂點(diǎn)的 SG 值，就可以對(duì)每種局面找到必勝策略了。但 SG 函數(shù)的用途遠(yuǎn)沒(méi)有這樣簡(jiǎn)單。如果將有 向圖變復(fù)雜一點(diǎn)，比如說(shuō)，有向圖上并不是只有一枚棋子，而是有 n 枚棋子，每次可以任選一顆進(jìn)行移動(dòng)，這時(shí)，怎樣找到必勝策略呢？再來(lái)考慮一下頂點(diǎn)的 SG 值的意義。當(dāng) g(x)=k 時(shí)，表明對(duì)于任讓意一個(gè) 0=ik，都存在 x 的一個(gè)后繼 y 滿(mǎn)足 g(y)=i。也 就是說(shuō)，當(dāng)某枚棋子的 SG 值是 k 時(shí)，可以把它變成 0、變成 1、變成 k-1，但絕對(duì)不能保持 k 不變。不知道你能不能根據(jù)這個(gè)聯(lián)想到 Nim， Nim的規(guī)則就是：每次選擇一堆數(shù)量為

4、k 的石子，可以把它變成 0、變成 1、變成 k-1，但絕對(duì)不能保持 k 不變。這表明，如果將 n 枚棋子所在的頂 點(diǎn)的 SG 值看作 n 堆相應(yīng)數(shù)量的石子，那么這個(gè) Nim對(duì)應(yīng)于原來(lái)這 n 枚棋子的必勝策略！對(duì)于 n 個(gè)棋子，設(shè)它們對(duì)應(yīng)的頂點(diǎn)的 SG 值分別為(a1,a2,an)，再設(shè)的每個(gè)必勝策略都局面(a1,a2,an)時(shí)的 Nim的一種必勝策略是把 ai 變成 k，那么原游戲的一種必勝策略就是把第 i 枚棋子移動(dòng)到一個(gè) SG 值為 k 的頂點(diǎn)。這聽(tīng)上去有點(diǎn)過(guò)于神奇怎么繞了一圈又回到 Nim上了。的局面是 P-ition其實(shí)還是只要證明這種多棋子的有向圖當(dāng)且僅當(dāng)所有棋子所在的位置的 SG

5、 函數(shù)的異或?yàn)?0。這個(gè)證明與上節(jié)的 B outons Theorem 幾乎是完全相同的，只需要適當(dāng)?shù)母膸讉€(gè)名詞就行了。剛才，我為了使問(wèn)題看上去更容易一些，認(rèn)為 n 枚棋子是在一個(gè)有向圖上移動(dòng)。但如果不是在一個(gè)有向圖上，而是每個(gè)棋子在一個(gè)有向圖上，每次可以任選一個(gè)棋子（也就是任選一個(gè)有向圖）進(jìn)行移動(dòng)，這樣也不會(huì)給結(jié)論帶來(lái)任何變化。所以可以定義有向圖的和(Sum of Graph Games)：設(shè) G1、G2、Gn 是 n 個(gè)有向圖，定義G 是 G1、G2、Gn 的Gi 并移動(dòng)上面的棋子。和(Sum)，G 的移動(dòng)規(guī)則是：任選一個(gè)子Sprague-Grundy Theorem 就是：g(G)=g(

6、G1)g(G2)g(Gn)。也就是說(shuō)，的和的 SG 函數(shù)值是它的所有子的 SG 函數(shù)值的異或。再考慮在本文一開(kāi)頭的一句話(huà)：任何一個(gè) ICG 都可以抽象成一個(gè)有向圖。所以“SG 函數(shù)”和“的和”的概念就不是局限于有向圖。我們給每 個(gè) ICG 的每個(gè)ition 定義 SG 值，也可以定義 n 個(gè) ICG 的和。所以說(shuō)當(dāng)面對(duì)由 n 個(gè)組的一個(gè)時(shí)，只需對(duì)于每個(gè)找出求它的每個(gè) 局面的 SG 值的方法，就可以把這些 SG 值全部看成 Nim 的石子堆，然后依照找 Nim 的必勝策略的方法來(lái)找這個(gè)的必勝策略了！。有 n 堆石子，每次可以從第 1 堆石子里取 1 顆、回到本文開(kāi)頭2 顆或 3 顆，可以從第 2

7、 堆石子里取奇數(shù)顆，可以從第 3 堆及以后石子里取任意顆可以把它看作 3 個(gè)子，第 1 個(gè)子只有一堆石子，每次可以取 1、2、3 顆，很容易看出 x 顆石子的局面的 SG 值是 x%4。第2 個(gè)子 知道這個(gè)就是一個(gè) Nim也是只有一堆 石子，每次可以取奇數(shù)顆，經(jīng)過(guò)簡(jiǎn)單的畫(huà)圖可以有 x 顆石子時(shí)的 SG 值是 x%2。第 3 個(gè)有 n-2 堆石子，的 SG 值異或。對(duì)于原的每 個(gè)局面，把三個(gè)子的 SG 值，然后就可以根據(jù)這個(gè) SG 值判斷是否有必一下就得到了整個(gè)勝策略以及做出決策了。其實(shí)看作 3 個(gè)子還是保 守了些，干脆看作 n，其中第 1、2 個(gè)子如上所述，第 3 個(gè)及以后的子都是“1有個(gè)子堆

8、石子，每次取幾顆都可以”，稱(chēng)為“任取石子”，這個(gè)超簡(jiǎn) 單的x 顆石子的 SG 值顯然就是 x。其實(shí)，n 堆石子的 Nim本身不就是 n 個(gè)“任取石子”的和嗎？來(lái)說(shuō)，SG 函數(shù)與“的和”的概念不是讓所以，對(duì)于制造稀奇古怪的去組合、，而是把遇到的看上去有些復(fù)雜的試圖分成若干找出它的 SG 函數(shù)，然后個(gè)子，對(duì)于每個(gè)比原簡(jiǎn)化很多的子的 SG 函數(shù)，就可以解決原全部異或起來(lái)就得到了原了。P-N-ition:先手必?cái)B(tài) ition:后手必?cái)B(tài)terminalition:終端態(tài)以 Nim為例，對(duì)于當(dāng)前的局面，遞歸計(jì)算它的所有子局面的性質(zhì)，如果存在某個(gè)子局面是P-ition，那么向這個(gè)子局面的移動(dòng)就是必勝策略【 Boutons Theorem對(duì)于一個(gè) Nim的局面(a1,a2,a3an),它是 P-ition當(dāng)切僅當(dāng)a1a2a3an=0 】根據(jù)定義,只需要證明三個(gè)命題:1.2.3.這個(gè)判斷將所有terminal根據(jù)這個(gè)判斷被判為N-根據(jù)這個(gè)判斷被判為P-ition 判為N-itionition 的局面一定可以移動(dòng)到某個(gè)P- ition 的局面一定無(wú)法移動(dòng)到某個(gè)P-ition ition當(dāng)一個(gè)較