博弈論進階之Anti-SG遊戲與SJ定理

前言

在上一節中，我們初步了解了一下SG函數與SG定理。

今天我們來分析一下SG遊戲的變式——Anti-SG遊戲以及它所對應的SG定理

首先從最基本的Anti-Nim遊戲開始

Anti-Nim遊戲是這樣的

有兩個頂尖聰明的人在玩遊戲，遊戲規則是這樣的：

有\(n\)堆石子，兩個人可以從任意一堆石子中拿任意多個石子(不能不拿)，

拿走最後一個石子的人失敗

。問誰會勝利

博弈分析

Anti-Nim遊戲與Nim遊戲唯一的不同就是兩人的勝利條件發生了改變，不過這并不影響我們對結論的推導

對于這個遊戲，先手必勝有兩種情況

• 當

  每

  堆石子都隻有一個，且遊戲的SG值

  為

  \(0\)

• 至少

  一堆石子多于一個，且遊戲的SG值

  不為

粗略的證明一下

遊戲大概可以被分為\(3\)種情況

• 每堆隻有一個石子
• 當異或值為\(0\)時，先手必勝
• 當異或值不為\(0\)時，先手必敗
• 隻有一堆石子數大于1，先手必勝

經過分析不難發現，先手可以對數量大于1的那堆石子下手腳，進而構造出後手必敗的狀态

• 存在至少兩堆石子數大于1
• 當異或和為0時，先手必敗
• 當異或和不為0時，先手必敗

這一步的結論與Nim遊戲非常相似，同時它們的證明也非常相似，大概就是從異或和為\(0\)的狀态無論怎樣都會變為異或和不為\(0\)的狀态，反過來從異或和不為\(0\)的狀态總有一步能到達異或和為\(0\)的狀态

推廣

按照我們學習SG函數的思路，我們是否可以把Anti-Nim遊戲推廣開來呢？

答案是肯定的

定義Anti-SG遊戲

• Anti-SG遊戲規定：決策集合為空的遊戲者赢
• 其餘規則與SG遊戲相同

同時我們定義SJ定理

對于Anti-SG遊戲，如果我們規定當局面中所有單一遊戲的SG值為0時，遊戲結束，則先手必勝當且僅當

• 遊戲的SG函數不為0且遊戲中某個單一遊戲的SG函數值大于1

• 遊戲的SG函數為0且沒有某個單一遊戲的SG函數大于1

證明與SG函數類似，

不追求完美的可以從DAG上歸納

追求完美的可以用模仿棋證明出該遊戲的等價性然後推出該遊戲是可數集合然後通過計算推出在模\(2\)意義下線性空間的基可以為\(nim(0),nim(1)\)最後歸納證明一個後繼是若幹Anti-nim遊戲的遊戲等價于\(mex(S)\)

例題

按照whx老師的說法

Anti-SG不怎麼重要，我至今為止就做到過一道題

那道題在這兒

題解

作者：自為風月馬前卒

個人部落格http://attack204.com//

出處：http://zwfymqz.cnblogs.com/

本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。