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

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

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

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

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

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

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

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

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