講義組合游戲論

1、論（1）Zhou Yuan組合by Zhou YuanOutlineCh.1 簡(jiǎn)單組合Ch.2 Nimby Zhou YuanCh.1 簡(jiǎn)單組合的組合（two-game） 兩人雙方知道所有信息（perfect information）沒(méi)有隨機(jī)事件（no chance moves） 確定的結(jié)果（a win-or-losee）by Zhou Yuan示例如下 有兩個(gè)者：I和II桌上有21個(gè)石子每個(gè)人可以從桌子上拿走1, 2, 3個(gè)石子 I開(kāi)始，兩人輪流取石子 拿走最后一個(gè)石子的者獲勝若參加后手必勝者都足夠聰明，判斷先手還是by Zhou Yuan組合稱為組合：抽象定義(Combinatorial

2、Game)如下 有兩個(gè)參與者 有一個(gè)很多可能的狀態(tài)的集合（一般是有限集） 若兩個(gè)人移動(dòng)規(guī)則都一樣，則稱為公平的（Impartial），這是的主要情況 兩個(gè)者交替移動(dòng) 某個(gè)玩家不能移動(dòng)時(shí)結(jié)束一般的：最后一個(gè)移動(dòng)的玩家是勝者相反的（最后一個(gè)移動(dòng)的玩家失敗）也是一種規(guī)則在有限回合內(nèi)一定結(jié)束by Zhou Yuan取石子的狀態(tài)：桌子上：遞推解法的石子數(shù) 0個(gè)，1個(gè)，2個(gè)，21個(gè)判斷每一個(gè)狀態(tài)先手必勝(N)/先手必?cái)?P)先手必勝iff.某個(gè)后繼狀態(tài)先手必?cái)∠仁直財(cái)ff.任何后繼狀態(tài)先手必勝?zèng)]有后繼的狀態(tài)先手必?cái)。?先手必?cái)?12345678910resultPNNNPNNNPNNby Zhou Yu

3、an構(gòu)造必勝策略對(duì)于任何一個(gè)先手必勝(N)狀態(tài)后繼狀態(tài)中，必有一個(gè)先手必?cái)?P)狀態(tài)選擇這個(gè)狀態(tài)，先手就可以保證必勝by Zhou Yuan觀察：的平衡構(gòu)造必勝策略時(shí)，始終將敗局面留給一方看來(lái)：石子數(shù)n是4的倍數(shù)就是平衡點(diǎn) 預(yù)定的勝利者總是要平衡 預(yù)定到失敗者面對(duì)平衡點(diǎn)，只能打破平衡，直平衡的主導(dǎo)權(quán)在勝利者，終止局面一定是平衡點(diǎn)問(wèn)題在于：尋找的平衡點(diǎn)by Zhou Yuan)練在取石子的石子中，雙方只能取走如下數(shù)目 1, 3, 5, 7 1, 3, 6 1, 2, 4, 8, 16, 2的整次冪那么哪些狀態(tài)是先手必勝的？by Zhou Yuan練習(xí)(2)有兩堆非空石子，一堆m個(gè)，一堆n個(gè)用(m

4、, n)表示這樣的一個(gè)狀態(tài)雙方移動(dòng)規(guī)則選擇扔掉一堆石子把另一堆石子分成兩堆（每堆非空）唯一的結(jié)束狀態(tài)(1, 1)，最后移動(dòng)這勝利求所有的先手必勝狀態(tài)by Zhou Yuan練習(xí)(3)在一個(gè)棋盤上的雙方移動(dòng)規(guī)則：棋盤就是狀態(tài)選擇一個(gè)方格（不能是左下角的）移走這個(gè)方格和其右上方的所有方格不能移動(dòng)者失敗一個(gè)先手必勝的狀態(tài)矩形棋盤：先手必勝by Zhou Yuan練習(xí)(4)一列n方格，初始都是空的雙方輪流選擇一個(gè)空方格寫(xiě)上S或者O第一個(gè)完成一個(gè)SOS的玩家勝利可能有平局證明n=4, 第一個(gè)人在第一個(gè)方格寫(xiě)下一個(gè)S, 則后者可以獲勝n=7時(shí)先手必勝，n=2000時(shí)先手必?cái)=14時(shí)結(jié)果如何？by Zho

5、u YuanCh.2 Nim規(guī)則（兩人） 桌上有很多堆石子，第i堆石子有xi個(gè)者輪流選擇一堆石子，從中拿走至少一粒（最多將這一堆取完） 所有石子取完時(shí)，最后一個(gè)移動(dòng)的玩家勝利by Zhou Yuan簡(jiǎn)要分析只有一堆非空石子：先手必勝（直接取完）有兩堆非空石子 平衡點(diǎn)：兩堆石子相同:(1,1), (2,2), (3,3) 先手從某一堆中拿走一定量石子打破平衡后手可以從另一堆中取走同樣多石子終止?fàn)顟B(tài)(0,0)也屬于平衡點(diǎn)：先手必?cái)∫虼嗽谏鲜銎胶恻c(diǎn)先手必?cái)∑渌瞧胶鉅顟B(tài)都可以到達(dá)某個(gè)平衡狀態(tài)先手必勝平衡by Zhou YuanNim和定義兩個(gè)非負(fù)整數(shù)的Nim和定義為它們二進(jìn)制形式的異或和例交換律結(jié)合

6、律by Zhou YuanNim和(contd)=求證：證明： 于是元by Zhou Yuan定理1：Boutons TheoremNim中一個(gè)局面是先手必?cái)‘?dāng)且僅當(dāng)每一堆石子的Nim和是0如4堆石子時(shí)，條件為證明思路為每一個(gè)勝局面找到一個(gè)必?cái)〉暮罄^局面證明必?cái)【置娴暮罄^都是勝局面（或無(wú)后繼）by Zhou Yuan證明為勝局面找一個(gè)必?cái)『罄^局面：構(gòu)造勝局面：Nim和大于0在Nim和的豎式中找到最高的非0位選擇一堆石子：其二進(jìn)制在該位上是1可以讓這堆石子變少使得Nim和為0：敗局面11110111000110101010100011101111by Zhou Yuan證明(contd)Nim和是0的敗局面 唯一的終止局面，每一堆石子都是0其他局面的每一個(gè)后繼局面反若在第一堆石子中取走一些，Nim和仍為0，于是后繼局面的Nim和不為0：勝局面by Zhou Yuan練習(xí)(5)一個(gè)一維棋盤，從左到右0,1,2,3,棋盤上有一些硬幣:一個(gè)方格上可以有多個(gè)雙方輪流移動(dòng) 選擇一枚硬幣，將它移至左邊的任意一個(gè)方格所有硬幣都到0號(hào)位最后移動(dòng)者勝利結(jié)束by Zhou Yuan練習(xí)(6)著名的Turning Turtles一列n個(gè)Turtles，頭朝上(H)/尾朝上(T)雙方輪流移動(dòng)，最后移動(dòng)者勝利選擇一個(gè)H改為T同時(shí)還能選擇左邊的任何一個(gè)Turtle