基礎博弈論 博弈論，又稱對策論，是現代數學的一個分支，強調一個對策，看起來十分深奧，好像古代那些軍師的計謀。的確，博弈論是一門非常深奧的學科，在生活中也有不少運用，但作為信息學奧賽選手，我們沒有必要去專業的學習博弈論，只需要知道一些常見的博弈論以及它的結論和證明即可。 1、 巴什博弈 ： 這是一個最 ...
基礎博弈論
博弈論，又稱對策論，是現代數學的一個分支，強調一個對策，看起來十分深奧，好像古代那些軍師的計謀。的確，博弈論是一門非常深奧的學科，在生活中也有不少運用，但作為信息學奧賽選手，我們沒有必要去專業的學習博弈論，只需要知道一些常見的博弈論以及它的結論和證明即可。
1、巴什博弈：
這是一個最常見的博弈論，我們小學都玩過。這個博弈講的是有n個石子，兩個人輪流取，每次至少要取一個，最多取m個，誰先取完誰勝，判斷誰有必勝策略。
我們假設希望後手贏，那麼最理想的狀態就是，輪到後手取了，而剩下的石子數不超過m。記石子數為x，不難得出，這時候x的取值範圍在1~m。那麼，我們再往前推一步，先手還沒取時x的取值範圍應該在2~2m之間。但是，這裡面並不是所有情況下我們都能保證後手必勝，這時候我們分別討論它的兩個邊界：
①∵先手取完後剩下的石子數量必須大於0，得x-m>=1，即x>=m+1；
②∵先手取完後剩下的石子數量還不能大於m，得x-1<=m，即x<=m+1.
∴綜上所述：x=m+1。也就是說，在一輪內後手必勝的情況當且僅當x=m+1。說明一下討論的過程：我們的目的是想讓後手在先手->後手這一輪內必勝，所以先手肯定不能把石子取完，換句話說就是先手取完後剩下的石子數必須不小於1；但是，既然要保證在一輪內結束，先手->後手以後不能再有剩下的石子，換句話說就是先手取完後剩下的石子數不能超過m，於是就得出了我們的結論。
既然這樣，那這個問題就變得很簡單了：我們已經知道一輪內後手必勝的條件，那我們如果能使整個局面劃分成很多這樣的“一輪”，結果不就很明顯了嗎？如果n可以被m+1整除，那麼後手就可以控制整個局面，只要每一輪取得石子與先手取的石子的和都保持在m+1，就相當於玩了很多輪，每輪都勝，最後必勝；反之，如果無法整除，那麼先手的人就可以把n取到可以被m+1整除，然後，原來的後手就處於先手的位置上了，原來的先手扮演的角色就變成了後手，誰勝誰負不言而喻。
所以，巴什博弈的結論就是：如果n除以m+1餘數為0，則後手必勝；否則先手必勝。
2、尼姆游戲：
尼姆游戲是一種兩個人玩的回合制數學戰略游戲。游戲者輪流從一堆棋子（一共有好幾堆，一次只能從其中一堆拿）中取走一個或者多個，最後不能再取的就是輸家。當然，這是最基本的尼姆游戲，在這個規則上可以加上五花八門的規則，使這個游戲更有趣味，思維也更加複雜。所以，我們會拿具體的例子來分析，也會隨時拿新的規則來試玩。
（1）給出n堆石子，從1到n標號，每堆若幹個。兩個人輪流取石子，每次只能從有石子的，且標號最小的那一堆取石子，不能不取，取的數量不限，取走最後一個石子的玩家獲勝。
什麼意思呢？假如說我有n堆石子，那我們兩個人必須先把第一堆石子取完，才能取第二堆，取完第二堆才能取第三堆，取完第三堆才能取第四堆......這樣的話，我想要取勝，就要保證最後取完n-1堆後輪到我，這樣我就可以直接取完。那麼，我肯定要找到一種能讓我在小範圍必勝的策略，而且要能夠將整個局面劃分成很多個這樣的小範圍。所以，不妨先考慮對於兩堆石子我們的策略，一堆就是先手必勝了，不必考慮。假設我是先手，那麼兩堆石子，我想要讓這堆石子由後手取完，我該怎麼做？實際上，讓後手取完這堆石子，實際上就是讓我在開始取新的一堆石子時保持先手，這要如何實現呢？
不要著急，我們縮小規模，從兩堆石頭開始討論，註意是兩堆，一堆的話沒啥好說的。現在要讓先手贏，先手有這兩種操作：取完，不取完。取完的話，先手就輸了。那麼我們肯定不能取完。來到後手，根據上面的推導，同樣可以得出後手不能取完，於是就這樣僵持著......會不會有個盡頭呢？會！因為題目有說，每一次不能不取，也就是最少取一個，那如果取到只剩下一個石子，你不想取也得取，這就是我們的突破口：
如果石子的數量為1，那麼下一堆石子的先手權就到了另一個人手上。因此，如果我們想要讓先手得到下一輪的先手權，我們的做法就是將這堆石子取到只剩一個，那後手只好取完這堆石子，我們拿到了下一堆石子的先手權，可以用同樣的方法，獲得再下一堆的先手權......這樣，最後一堆石子必然是由我們取完。
但是，如果中間原先就有數量為1的石子堆，怎麼辦？1的作用是讓先手權轉移，假如下一堆只有1個石子，那這時候我就不會再想要下一輪的先手權了，因為再下一輪我就沒有先手權了，那麼我們可以把當前這堆石子取完，讓另一個人拿到下一堆石子的先手權，那再下一堆石子先手權又回到我們手上了。如果有連續的1呢？實際上，連續的1是可以抵消的，偶數個1其實就相當於沒有1，奇數個1就相當於一個1，因為你的先手權轉移兩次相當於沒轉。所以，我們採取必勝策略的情況下，當有奇數個1的時候，我們就把當前這堆石子取完；否則就按照正常的情況，取到剩下一個。綜上所述，只要我們當前的石子數量不為1，我們總有方法掌控全局，讓先手必勝。
但是！如果我們開頭就是1呢？那這樣的話，先手就沒有任何策略可以使用了，只能乖乖地將先手權讓出去，這是先手唯一可能失敗的情況。如果開頭就是1，我們就要判斷連續1的個數是奇數還是偶數，如果是奇數那先手必敗，這時候的先手的處境就像我們上文的後手。如果是偶數，那麼先手又贏了。說了半天，我們最終得到一個結論：對於這道題，判斷勝負的依據就是開頭連續1的個數。所以我們只需記錄開頭1的個數即可，但值得一提的是，我們對於這些石子堆的討論終止於第n-1堆石子，什麼意思？我們不需要考慮第n堆石子，因為第n-1堆石子就可以決出勝負了，所以，在記錄連續1的個數是，最多只能記錄到第n-1堆，也就是說如果用i來表示當前堆的編號，那麼i<n。
來源於YZOJ 1698（作者爭取儘快弄到洛谷上）
