博弈論

oi中的博弈論

oi中的博弈論主要研究博弈游戲，本質(zhì)上是平等組合游戲

什么是“平等組合游戲”

兩人游戲

有一個狀態(tài)集，通常是有限的

規(guī)定哪些狀態(tài)的轉(zhuǎn)移是允許的

所有的規(guī)定對兩個人來說是一樣的

兩個人輪流走步

有一個終止狀態(tài)，到達終止狀態(tài)后游戲即告終止

游戲可以在有限的步內(nèi)終止

開頭及一些基本的性質(zhì)

一.必勝點與必敗點

P點：必敗點，在雙方都聰明無比的情況下（比如zsyzsy和pplppl在玩游戲），當前先手的人必敗的情況。
N點：必勝點，在雙方操作都正確的情況下先手必勝的位置。

幾個性質(zhì)

所有的終止位置都是必敗點P（我們認為這個是公理，即所有推導都在這個性質(zhì)成立的基礎上進行）。
從任何一個必勝點N操作，至少有一種方法可以達到一個必敗點P。
從一個必敗點P出發(fā)，只能夠到達一個必勝點N。

我們要明白這樣一件事，所有的選擇都是為了最大化自己的利益，所以，當有讓對方失敗的機會時，自己肯定會選擇這樣做

二.無偏博弈

無偏博弈是一類任意局勢對于游戲雙方都是平等的回合制雙人游戲。平等的含義是當前的所有可行的走法僅僅只依賴與當前的局勢，而與當前誰移動無關。換而言之，兩個人除了先后手的區(qū)別之外就不存在任何區(qū)別。除此之外，還需要滿足一下性質(zhì)：

完全信息，任何一個游戲者都能夠知曉整個游戲狀態(tài)。
無隨機行動，所有的行動都會轉(zhuǎn)移到一個唯一確定的狀態(tài)。
在有限步內(nèi)游戲會終止，此時有唯一的勝者。

常見的模型

巴什博奕(Bash GameBash Game)
威佐夫博弈(Wythoff GameWythoff Game)
尼姆游戲(Nim GameNim Game)
Anti?SGAnti?SG游戲
Multi?SGMulti?SG游戲
Every?SGEvery?SG游戲
翻硬幣游戲
樹上刪邊游戲

巴什博弈

基本問題

有一堆石子，總個數(shù)是nn，兩名玩家輪流在石子堆中拿石子，每次至少取11個，至多取mm個。取走最后一個石子的玩家為勝者。判定先手和后手誰勝。

解決辦法

如果((m+1)|n)則先手必敗，否則先手必勝

證明

假設(m+1)|n，那么假設先手拿走了x個，那么后手必定可以拿走(m+1)?x個，這樣子無論怎么拿，剩下的石頭個數(shù)都將是m+1的倍數(shù)。那么最后一次取的時候石頭個數(shù)必定還剩m+1個，無論先手拿多少個，都會剩下石頭，此時后手必定可以將剩下的所有石頭取光從而獲勝。

威佐夫博弈(Wythoff GameWythoff Game)

基本問題

有兩堆石子，石子數(shù)可以不同。兩人輪流取石子，每次可以在一堆中取，或者從兩堆中取走相同個數(shù)的石子，數(shù)量不限，取走最后一個石頭的人獲勝。判定先手是否必勝。

解決辦法

這個東西意義不是很大，打表找規(guī)律之后可以發(fā)現(xiàn)先手必敗的狀態(tài)一定形如(([i×?],[i×?2])中?=√{5+1}/2)，表示不大于x的最大整數(shù)。一些證明可以參考

尼姆博弈(Nim GameNim Game)

基本問題

有三堆石子，兩人輪流取，每次可以從一堆中取走任意數(shù)量個石子，至少取走一個，問先后手誰勝。一般推廣：有nn堆石子x1,x2,x3,...,xnx1,x2,x3,...,xn，兩人輪流取，每次可以從任意一堆石子中取走至少一個石子，問先后手誰勝。

解決方法

方法很簡單，直接求所有xixi的異或和，如果異或和為00則先手必敗，否則先手必勝。形式化的表達即當且僅當x1⊕x2⊕x3⊕...⊕xn=0時，先手必敗。同理，也就是所以異或和為0的狀態(tài)是P狀態(tài)，所有異或和非0的是N狀態(tài)。

證明

首先當沒有石子的時候，先手必敗，此時所有石子的異或和為0，這個是P狀態(tài)。(必敗點)

接下來我們證明任意一個N狀態(tài)至少能夠達到一個P狀態(tài)。

假設當前所有石子個數(shù)的異或和為k，即(⊕_{i=1}^n)xi=k，那么，必定存在一個xi滿足xi二進制位上存在kk的最高位，并且不難證明xi⊕k<xi，那么，將xi異或上k之后，剩下所有的數(shù)的異或和恰好為0，又回到了一個P狀態(tài)。

而一個P狀態(tài)的異或和為0，任何一個數(shù)減小之后異或和一定不為0，所以可以證明任何一個P狀態(tài)的后繼狀態(tài)都是N狀態(tài)。

綜上，異或和為0的狀態(tài)先手必敗，其他情況先手必勝。

拓展模式

每次取的石子數(shù)存在上界m

這個是Bash Game+Nim Game，只需要把所有石子按照m+1取模再考慮Nim游戲就好了。

每次允許從k堆石子中取((Nim_k))

我們一般考慮的情況是(Nim_1)，我們的解法是考慮2進制下的異或和是否為0，而異或和是不進位的加法，同理，對于(Nim_k)的情況，我們考慮k+1進制下每一位不進位加法的結果，如果每一位都是0的話就是P局面，否則是N局面。

階梯博弈：博弈在階梯上進行，每次可以將一堆的若干式子移動到上一階去，不可操作者輸。

忽略所有的偶數(shù)階梯，只留下奇數(shù)階梯，轉(zhuǎn)化為普通的Nim游戲。大致的思路是這樣的：首先終止狀態(tài)一定是所有石子都在0號階梯，即一個偶數(shù)階梯。那么如果對方移動了一個偶數(shù)階梯上的石子，那么你可以在移動結束的那個奇數(shù)階梯，直接把等數(shù)量的石子繼續(xù)向前移動，這樣子可以保證偶數(shù)階梯上的石子對于結果沒有任何影響。那么如果移動的是一個奇數(shù)階梯，因為偶數(shù)階梯是沒有影響的，所以你可以認為移動奇數(shù)階梯就是直接被移走了，那么這就是一個普通的Nim游戲了。

階梯博弈的例題洛谷p2575

AKN玩游戲玩累了，于是他開始和同伴下棋了，玩的是跳棋！對手是wwx！這兩位上古神遇在一起下棋，使得棋局變得玄幻莫測，高手過招，必有一贏，他們都將用最佳策略下棋，現(xiàn)在給你一個n*20的棋盤，以及棋盤上有若干個棋子，問誰贏？akn先手！

游戲規(guī)則是這樣的：

對于一個棋子，能將它向右移動一格，如果右邊有棋子，則向右跳到第一個空格，如果右邊沒有空格，則不能移動這個棋子，如果所有棋子都不能移動，那么將輸?shù)暨@場比賽。

題目及模版

洛谷2197 Nim游戲裸題

BZOJ1299 Nim游戲變形

POJ1704 階梯博弈變形

SG定理及SG函數(shù)

Sprague?GrundySprague?Grundy定理：所有一般勝利下的無偏博弈（定義在上面）都能夠轉(zhuǎn)化成尼姆數(shù)表達的尼姆堆博弈，一個無偏博弈的尼姆值定義為這個博弈的等價尼姆數(shù)。(抄自YMDYMD課件)
SGSG函數(shù)：對于每一個狀態(tài)的一個尼姆數(shù)的函數(shù)又被稱作Sprague?GrundySprague?Grundy函數(shù)。

翻譯成人話就是：對于當前游戲X，它可以拆分成若干個子游戲x1,x2,x3,...,xn那么(SG(X)=SG(x1)⊕SG(x2)⊕...⊕SG(xn))。

接下來定義mex運算，mex運算是對于一個集合S而言的，mex(S)表示的是最小的、不屬于集合S的非負整數(shù)。例如mex{1,2,3}=0,mex{?}=0。那么我們有運算SG(x)=mex{SG(y),<x,y>∈E}，其中E是邊集。即對于當前狀態(tài)x的SG函數(shù)，它的值定義為所有的后繼狀態(tài)的mex值。對于SG函數(shù)為0的位置一定是P位置，SG函數(shù)非0的位置是N位置。

這里直接空說很不好，我們舉個例子。

HDU1848 Fibonacci again and again，為了節(jié)約篇幅，直接戳鏈接看題目&題解&代碼。

事實上，注意"后繼"這個詞語，我們不難發(fā)現(xiàn)上述的東西可以理解為一個DAG上的問題。

(Anti?SG)游戲&(SJ)定理

基本問題

決策集合為空者的操作者勝利。翻譯成Nim一點的問題就是，給定n堆式子，每次每個人可以從任意一堆石子中拿走不少于一個的石子，拿走最后一個石子的人輸。

解決辦法

SJ定理：對于一個Anti?SG游戲，如果我們規(guī)定當前局面中所有單一游戲的SG為0時，游戲結束，則先手必勝的條件為：

游戲的SG值不為0，且存在一個單一游戲的SG值大于1
游戲的SG值為0，且不存在一個單一游戲的SG值大于1

題目及模版

BZOJ1022 Anti?SGAnti?SG模板題

(Multi?SG)游戲

基本模型

決策集合為空的操作者輸。一個單一游戲的后繼可以是多個單一游戲。還是寫成Nim一點的式子，給定你n堆石子，每次可以取走任意數(shù)量個，或者將一堆式子拆分成兩堆（事實上更多也是可行的）非空石子，不能操作者輸，判定勝負。

解決辦法

還是可以使用SGSG函數(shù)解決，舉個例子，比如當前存在一堆33個石子，那么可以直接走0,1,2,3個石子，也可以拆分成(1,2)兩堆，因此(SG(3)=mex{SG(0),SG(1),SG(2),SG(3),SG((1,2))=SG(1)⊕SG(2)})

那么這個問題本質(zhì)上還是一個Nim游戲，可以直接用SG函數(shù)解決。

同時，對于這樣每次可以拆分兩堆的Multi?SG游戲，打表后發(fā)現(xiàn)有這樣一個性質(zhì)：

[SG(x)=left{ egin{aligned} x-1 & = & (x mod 4=0) \ x & = & (xmod 4=1&2) \ x+1 & = & (x mod 4=3) end{aligned} ight.
]

題目&模板

HDU3032 Multi?SGMulti?SG模板題

BZOJ2940 簡單的Multi?SGMulti?SG題目

BZOJ1188 有些困難的Multi?SGMulti?SG模型

BZOJ3576 有點難度的Multi?SGMulti?SG變形

Every--SG游戲

基本模型

對于沒有結束的任何一個單一游戲，操作者必須對其進行一步操作，無法操作者輸。

解決辦法

所有游戲都是獨立的，并且我們發(fā)現(xiàn)無法操作者輸，而同時又在進行多個游戲。因此，我們知道勝負情況只與最后結束的游戲的勝負情況相關。既然只與最后結束的游戲相關，那么我們這樣分析：首先對于一個能夠取得勝利的游戲，我們必定會取得勝利，這樣一定不會讓結果更差，因為只要贏了，這局游戲就一定不會讓自己輸。那么對于所有單個游戲的勝負情況，我們一定可以判定，但是對于整個Every?SG的情況，我們只能夠通過最后結束的游戲判定。所以，對于一個我們必勝的游戲，我們一定會想辦法將其盡可能的向后拖，即我們期望它盡可能完的結束；反過來，對于一個必敗的游戲，我們一定會讓他盡可能早的結束。這幾句推論正確的理由都是所有游戲都是互相獨立的。

那么，我們首先可以判定出所有位置是N點還是P點，然后根據(jù)必勝和必敗的關系，我們必定要決策步數(shù)最小還是步數(shù)最大，那么這個就非常類似于一個min?max搜索。至于NN點和PP點的判定我們可以很容易的用SGSG函數(shù)表示出來。我們定義step(x)為狀態(tài)xx時(在滿足N/P的條件下)的步數(shù)，我們可以得到這樣一個轉(zhuǎn)移:

翻硬幣游戲

題目

有n枚硬幣排成一排，依次編號1到N，有的正面朝上，有的反面朝上。現(xiàn)在按照一定的規(guī)則翻硬幣（比如每次只能翻一枚或者兩枚，或者每次只能翻動連續(xù)的幾枚），但是強制要求最靠右的硬幣必須從正面被翻到了反面。操作集合為空者負。

解決辦法

結論是這樣的：當前局面的SG值是所有正面朝上的硬幣單獨存在時的SG值的異或和。

證明？我也不會啊。可以感性理解一下，無論如何最右邊的硬幣都要翻，它翻了之后必定改變前面的狀態(tài)，但是前面的狀態(tài)是什么似乎和之前的狀態(tài)無關(假裝能夠說服我自己)，之和之前的狀態(tài)和現(xiàn)在狀態(tài)的差別(也就是看成01串后的異或和)相關，所以你可以把游戲拆分成所有正面朝上的硬幣的子游戲。

鏈接中給出這么多游戲的主要目的是因為直接使用SG函數(shù)求解效率太低，很多時候利用SG函數(shù)打表找規(guī)律才是最好的方法。

總結

以上是生活随笔為你收集整理的博弈论的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。