小结博弈
參考資料：https://www.cnblogs.com/kuangbin/archive/2011/08/28/2156426.html
一、巴什博奕
只有一堆物品，兩人輪流取，每次最多m個(gè)，最少一個(gè)。最后取光者獲勝
分析：假設(shè)共n個(gè)物品，n=m+1, 那么先手必?cái) Ｋ詾榱讼仁直貏佟？梢园裯表示為
n = k(m+1) + s? ,? s <= m
只要先手取s個(gè)，把數(shù)量維持到m+1的倍數(shù)即可。對(duì)方取r個(gè)，自己就取m+1-r個(gè)
?
二、威佐夫博弈
有兩堆物品，兩人輪流取，每次可以從一堆或兩堆取相同數(shù)量物品，最少1個(gè)，最多不限，最后取光者獲勝
分析：用（ak,bk）ak<bk, k=0,1,2,3……表示兩堆的數(shù)量，也稱局勢(shì)
其中如果甲面對(duì)(0, 0)局勢(shì)，那么甲已經(jīng)輸了，稱奇異局勢(shì)
前幾個(gè)奇異局勢(shì)：（0,0） (1,2)?? (3,5)? (4, 7)? (6, 10)
其中ak就是前面未出現(xiàn)的最小數(shù)，bk = ak + k
可以看出奇異局勢(shì) 有以下三種性質(zhì)
①：任何自然數(shù)都包含在一個(gè)且僅有一個(gè)的奇異局勢(shì)中
證明：由于ak是沒出現(xiàn)的最小數(shù)，所以ak>ak-1 而bk=ak+k>ak-1+k-1=bk-1>ak-1
②：任意操作都可以把奇異局勢(shì)轉(zhuǎn)化為非奇異局勢(shì)
證明：若只改變(ak,bk)的某個(gè)分量，那么另一個(gè)分量一定不在其他奇異局勢(shì)里。所以必然是非奇異局勢(shì)。
如果使兩個(gè)分量同時(shí)減少，由于差不變，肯定也是非奇異局勢(shì)
③：適當(dāng)操作就可以把非奇異局勢(shì)轉(zhuǎn)化為奇異局勢(shì)
證明有兩個(gè)不懂。所以（證明見文頂參考資料）
?
從以上性質(zhì)可知：面對(duì)非奇異局勢(shì)，先手必勝；反之，后手必勝
現(xiàn)在問題就是 如果判斷一個(gè)局勢(shì)（a，b） 是不是奇異局勢(shì)
深?yuàn)W的看不是太懂，不過可以這樣判斷
已知 a < b, 奇異局勢(shì)：a = k*1.618
k = b - a,? 1.618=(sqrt(5)+1)/2;
?
三、尼姆博弈
有三堆物品，兩人輪流從某一堆取任意多物品，每次至少一個(gè)，最后取光者獲勝
?
分析：與二進(jìn)制有關(guān)，用(a,b,c) 表示某種局勢(shì)，首先(0,0,0) 是奇異局勢(shì)，無論誰面對(duì)必?cái) ?/span>
第二種奇異局勢(shì)(0,n,n), 只要對(duì)手拿走一樣多的物品，最后都將導(dǎo)致(0,0,0)。
仔細(xì)分析（1,2,3)也是奇異局勢(shì)，無論誰拿，都會(huì)變?yōu)?#xff08;0,ｎ,n）
這里介紹異或運(yùn)算 二進(jìn)制對(duì)應(yīng)位 不一樣為１，一樣為0
對(duì)于奇異局勢(shì) (0,n,n) 異或結(jié)果為0
對(duì)于任何奇異局勢(shì) (a,b,c) ａ^b^c = 0
?
如果我們面對(duì)非奇異(a,b,c)，要如何變?yōu)槠娈惥謩?shì)？
假設(shè)ａ<b<c 我們只虛把 ｃ 變?yōu)椤?#xff41;^b 即可
所以就把ｃ減去ｃ-a^b
?
重點(diǎn)理解：取火柴游戲：
題目1：今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，?
可將一堆全取走，但不可不取，最后取完者為勝，求必勝的方法。?
題目2：今有若干堆火柴，兩人依次從中拿取，規(guī)定每次只能從一堆中取若干根，?
可將一堆全取走，但不可不取，最后取完者為負(fù)，求必勝的方法。
?
定義：若所有火柴數(shù)異或?yàn)?，則稱為利他態(tài)，用Ｔ表示，否則就利己態(tài) 用Ｓ表示
因?yàn)檎l面對(duì)異或?yàn)?, 就輸了，所以是利他(對(duì)手)態(tài)
?
第一個(gè)題目：
定理一：對(duì)于任何一個(gè)Ｓ態(tài)，總能從一堆火柴中取出若干使之成為Ｔ態(tài)
證明：
若有ｎ堆火柴，每堆Ａ(i) 根火柴，那么既然處于Ｓ態(tài)，
ｃ＝Ａ(1)^A(2)^……^A(n) > 0
把ｃ表示成二進(jìn)制，記最高位為第ｐ位，則必然存在一個(gè)A(t), 它的第p位也是1。
那么我們把 x=A(t)^c ， 則得到x<A(t)，因?yàn)樽罡呶煌瑸?，肯定小了。所以x<A(t)
?? A(1)^A(2)^……^x^……^A(n)
= A(1)^A(2)^……^A(t)^c^……^A(n)
= A(1)^A(2)^……^A(n)^A(1)^A(2)^……^A(n)
= 0
也就是說從A(t)中取出 A(t)-x 根火柴，會(huì)從S態(tài)變?yōu)門態(tài)。證畢。
?
定理二：T態(tài)，取任何一堆的若干根，都成為S態(tài)。
證明：
反證法：c=A(1)^A(2)^……^A(i)^……^A(n)
c'=A(1)^A(2)^……^A( i' )^……^A(n)
c ^ c' = A(1)^A(1)^A(2)^A(2)^……A(i)^A(i')^……^A(n)^A(n)=A(i)^A(i')=0
推出A(i)=A(i')，與已知矛盾，所以命題得證
定理三：S態(tài)，只要方法正確，必勝
證明：
最終勝利即由S態(tài)轉(zhuǎn)化為T態(tài)，任何一個(gè)S態(tài)，只要把它變?yōu)門態(tài)(由定理一，S態(tài)可以變?yōu)門態(tài))，對(duì)于T態(tài)來說只能變?yōu)镾態(tài)(由定理 二)。所以S態(tài)向T態(tài)都可以由自己控制，對(duì)方只能被動(dòng)的實(shí)現(xiàn)T態(tài)變?yōu)镾態(tài)。故S態(tài)必勝
?
定理四：T態(tài)，只要對(duì)方方法正確，必?cái)?/span>
證明：
由定理三易得。
總結(jié)：對(duì)于先取光勝利的博弈，S態(tài)必勝，T態(tài)必?cái) ?/span>
?
第二個(gè)題目：
定義：若一堆中僅有1根火柴，稱為孤單堆。若大于1根，則稱為充裕堆。
定義：T態(tài)中，若充裕堆的堆數(shù)大于等于2，稱為完全利他態(tài)，用T2表示，若充裕堆為0，稱為部分利他態(tài)，用T0表示
不會(huì)有T1的存在：因?yàn)楣聠味旬惢蛑粫?huì)影響最后一位，一個(gè)充裕堆可以影響高位。所以異或和不會(huì)為0
?
定理五：S0態(tài)，即僅有奇數(shù)個(gè)孤單堆，必?cái) 0態(tài)必勝
證明：
S0態(tài)就是每次只能取1根，奇數(shù)堆，肯定是自己取的最后一根。必?cái) ?/span>
同理 ，T0態(tài)必勝。
?
定理六：S1態(tài)，只要方法正確，必勝
證明：
若此時(shí)孤單堆為奇數(shù)，把充裕堆取完，否則取剩1根。
?
定理七：S2態(tài)不可一次變?yōu)門0態(tài)
證明：
充裕堆不可能一次由2變?yōu)?
?
定理八：S2態(tài)可一次變?yōu)門2態(tài)
證明：
由定理一，S態(tài)可變?yōu)門態(tài)，又由定理七可知，S2態(tài)不可一次變?yōu)門0態(tài)，所以可一次變?yōu)門2態(tài)(T1不存在)
?
定理九：T2態(tài)，只能變?yōu)镾2態(tài)或S1態(tài)
證明：
由定理二，T態(tài)只能變?yōu)镾態(tài)。由于充裕堆不可能一次由2變?yōu)?，所以S態(tài)不可能為S0態(tài)。
?
定理十：S2態(tài)，只要方法正確，必勝。
證明：
1)? S2態(tài)，就變?yōu)門2態(tài)? （定理八）
2）對(duì)方只能變?yōu)镾2態(tài)或S1態(tài) （定理九）
若變?yōu)镾2態(tài)，繼續(xù)1）
若變?yōu)镾1態(tài)，S1必勝。
?
定理十一：T2態(tài)必輸。
證明：
由定理十易得。
?
總結(jié)：對(duì)于先取光失敗的博弈，必勝態(tài)：S2、S1、T0、必?cái)B(tài)：S0、T2
?
SG值內(nèi)容留
?
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/ACMerszl/p/10371521.html
總結(jié)
- 上一篇： P3796 【模板】AC自动机（加强版）
- 下一篇： 洛谷P4555 [国家集训队]最长双回文