博弈論取石子兒問題？

01-13

石子陣列，
N行M列，可供選擇的策略，
被選中的點，其右、上的所有石子被拿走。

參與人交替進行選擇，拿到最後一個字的人輸，根據策梅洛定理，無論N、M等於多少，此博弈都有解。
問，這個博弈的解是什麼。
這道題是耶魯大學博弈論公開課，第十五集上老師出的題，沒給答案。

我想知道是不是先手必勝，以及為什麼。個人想這個題想了很長時間了，也沒想出來，急求大神幫助。

這是非常典型的一類博弈問題。先手必勝。

反證法。

假設後手必勝，則無論先手如何行動，後手都有應對策略，使得博弈樹最終走向「後手獲勝」。

此時，先手方可以將自己」假想成「後手行動，選擇第一步拿走最右上角的一枚石子。輪到後手方行動時，後手方無論如何行動，行動後都將形成右上角有一個矩形缺失的剩餘形態。

關鍵的地方到了。這時，先手方面臨的是一個後手第一步時可能面臨到的局面（後手第一步時面臨的局面只比此時先手可能面對的局面多」僅有最右上石子被拿走「這一種）。

先手方的第一步只拿走最右上方的一枚石子，其效果相當於把自己變成了後手！

那麼根據假設後手必勝，也就是說此局面下必有應對手段，使得決策樹走向」輪到在此局面下行動的一方獲勝「。即先手方在此時行動，亦有必勝之法。與假設矛盾。

這類解決博弈問題的方法，叫做」策略盜取「

Strategy-stealing argument 請見維基百科鏈接~~~~~

現在你也一定知道，在沒有禁手的情況下，五子棋為什麼先手不敗了？

------------------------------------------------------------------------------------------------------------------------------

評論中有同學問為什麼此類博弈一定是先手存在必勝策略或者後手存在必勝策略，對此請看：

http://zh.wikipedia.org/wiki/%E7%AD%96%E6%A2%85%E6%B4%9B%E5%AE%9A%E7%90%86_(%E5%8D%9A%E5%BC%88%E8%AB%96)策梅洛定理

其中需要特別說明的是，「有限」是指博弈在有限步內結束與每一步行動時有有限種策略。

樓上說的已經不錯了我就再補充一點吧

首先這類遊戲叫做progressively bounded two-person impartial game，名字叫chomp

impartial game 就是說信息完全公開雙方在同一個位置有同樣的步驟選擇（例：象棋就不是impartial game），比較常見的這類遊戲是Nim，有興趣可以去了解下。Progressively bounded就是這個遊戲在有限步之內能結束，也就是你不能走回之前的某個狀態。

然後這類遊戲有一個很重要的性質就是必定有一個人有必勝策略（不是說他一定能贏但是他可以必勝）

然後我們定義一個遊戲的N點和P點，N點就是在這個點上（Next）下一個動的人有必勝策略，P點就是（Previous）之前動的人有必勝策略

比如chomp，只剩下一顆石子的時候就是P點，因為下一個動的人必輸

然後NP點有這樣的性質，所有N點，下一步必定能動到P點，所有P點，下一步只能到N點

換言之你若處於N點，且你動，那麼必勝策略就是移到P點去，對手只能移到N點，每次都保證你移到P點，最後就能獲勝了（假設這是Normal Game，Misere的暫時不考慮）

接下來就是看M*N去掉右上角的的情況了，假如這是一個P點，那麼M*N就是N點，必勝策略就是拿走右上角。假如這是一個N點，那麼根據之前的知識，那麼他能去一個P點，這樣利用樓上說的strategy stealing，M*N是一個N點，因為他也能到那個P點……

所以綜上所述 M*N是一個N點，也就是有必勝策略

至於策略是什麼，可以逆推找出所有的N點和P點，然後你就可以知道了，但是據我所知沒有像Nim一樣的通解，我學藝不精，只會這些了