奈許棋的美麗境界 - 文山國民小學.doc

中市93學年度第45屆國民中小學科學展覽會作品說明書科 別：數學科組 別：國小組作品名稱：棋樂無窮奈許棋的美麗境界關 鍵 詞：奈許棋、棋盤遊戲編 號：棋樂無窮奈許棋的美麗境界壹、 摘要生活上我們常覺得平凡的事物，在數學家的眼中可都是值得仔細研究的數學瑰寶，從利用廁所上的壁磚玩棋的這件事可看出奈許對數學的執著，也讓我們對這位偉大的數學家懷抱著興趣。從研究奈許的有趣證明開始，我們希望補足他並未完整解釋的證明，用一些在課堂上所學到的數學知識，找出和驗證奈許棋的致勝策略，並希望能將結果一般化。貳、研究動機在一次老師上課的話題中，介紹到關於數學家奈許的一生，以及描述他為數學而痴狂的傳記電影美麗的境界。我們被奈許的一句名言純粹的數學是美麗的而吸引，很希望能領略它的美。老師藉此機會向我們介紹奈許在廁所為了打發時間所想出的奈許棋，向來就喜歡下棋的我們，便要求老師教我們奈許棋。在玩棋的過程中，我們發現奈許棋不是一個公平的遊戲，裡面似乎隱藏著某些規律。自此奈許棋的魅力深深地吸引了我們，並進而探求它的奧秘。參、研究目的一、 奈許棋棋盤的探討。二、分析奈許棋，從中找出隱藏的數學規則及其是否存在規律性。三、嘗試以另一種方式分析奈許棋，是否能得到意想不到的結果。肆、研究過程及方法一、奈許棋的玩法介紹奈許棋的棋盤是由許多正六邊形的格子所組成的平行四邊形（如下圖），它的格子數目可以用nn的符號表示，每一排和每一列的格子數都是相同的，其棋盤格子數目可依下面數列的排列方式一直擴大： 4 , 9 , 16 , 25 , 36奈許棋是一種兩個人玩的遊戲，一人稱為直方，另一人稱為橫方。直方先下，橫方後下，兩人依序輪流。直方以的符號表示，橫方以一的符號表示，直方必須佔有格子，從上到下連成一條通路，橫方則須由左到右連成一條通路，先連成通路的那一方就獲勝。從圖1的棋局，直橫方佔地的狀況可以知道此盤由直方（獲勝）獲勝。圖1二、參考資料研究(一)奈許棋是否會和棋奈許棋的和棋可分為兩種情形。第一：兩方可同時各自連成一條通路。第二：兩方皆無法連成通路。值得注意的是，在第二種情形下，雙方一定是把全部的格子都下滿了仍無法達到目的而得出的結果。1.兩方可同時各自連成一條通路例如橫方已連成一條通路（如圖2所示），拿把剪刀沿著黑線經過的格子剪下來，這樣看來直方已經被橫方分隔開了，就因為被分隔開了，直方到達不了對面。所以以這個例子來看，兩方同時連成一條通路的情形是不可能發生的。圖22.兩方皆無法連成通路如果出現了兩方皆無法連成通路的狀況，那每個格子一定都被雙方下滿，才有可能出現這種狀況。現在我們拿起剪刀，把橫方的位置點剪開（如圖3所示），可以發現棋盤一定被分成上下兩半。因為如果無法成上下兩半，也就表示直方已連成通路了，這與原來的假設不符。而分開成上下部分的周界，卻剛好是橫方所佔的位置，而此周界又能左右相通，所以橫方可連成一直線。這又跟原來的說法不同，所以不可能有兩方皆無法連成一直線的情形。從上面兩種情形可得知：奈許棋不可能會和棋。奈許棋的玩法圖3(三)奈許棋是公平還是不公平首先我們定義什麼是公平的遊戲：公平的遊戲是指遊戲的玩家在玩遊戲時沒有必勝策略，而不公平的遊戲則有。奈許棋從棋盤的結構上看是個可在有限回合即可結束的遊戲，而在這種架構的遊戲下會有三種結果：先下者贏、後下者贏、和棋。而從上面的討論可知奈許棋遊戲結果只有前兩種情形，我們之後將針對奈許棋在這種狀況下，探討奈許棋是否是公平的遊戲；再來，如果它的確是不公平的遊戲，那它的必勝策略又會在誰手上。(四)奈許對奈許棋的奇妙證明奈許用了一個奇妙證明，證明後玩者有必勝棋譜的說法是錯誤的。奈許是甲，甲找了乙和丙各玩一盤奈許棋，順序是甲先和乙下一手，之後再和丙下一手，然後再回頭和乙下，之後再和丙下，輪流和兩個人一起玩，而甲都是先下者。假設甲有後玩者必勝棋譜，他給了乙和丙各一份後玩者必勝棋譜。甲先和乙下，甲隨便下了一個位置，乙照著棋譜下了一個子後，換甲跟丙下。在甲和丙的棋局，甲的第一子依照乙下的位置也下同一個位置，然後丙依照必勝棋譜下了一個子後，甲再回頭和乙下。在甲和乙的棋局裡，甲的第二子是照著丙下的位置下同一個位置，之後輪到乙下，甲就以這樣的方式一直下。先看甲和丙的棋局，丙是後下者並且有必勝棋譜，所以丙會贏，甲會輸。再看甲和乙的棋局，因為甲除了第一子之外，其他都是照著丙的棋路走，丙有必勝棋譜，如果不看甲的第一子，甲就變成了後下者，乙就變成了先下者，所以甲會贏。可是乙是後玩者並且也有必勝棋譜，所以乙也會贏。但是奈許棋是個不會和棋的遊戲，所以不可能兩個人都會贏，這也就表示後玩者會贏的說法是錯誤的。我們可由圖4來清楚了解後下者會贏的假設產生矛盾的地方，圖中紅色的英文字所表示的是甲、乙、丙的勝負狀況；而斜箭號所表示的是甲下的棋路是抄乙方或丙方的棋路所加的標示。(win and lose) 甲 乙 (win)( lose ) 甲 丙 (win)圖4雖然奈許證明出後玩者沒有必勝棋譜，也就意味證明出先玩者有必勝棋譜。但令人奇怪的是，奈許本人並沒有找出奈許棋盤必勝棋譜，證明的過程中也沒說明棋盤的長相，更沒提到奈許棋遊戲是否是公平的，所以他的證明好像瑕疵不少，於是更值得我們深入的研究奈許棋的奧秘。三、尋找、紀錄奈許棋必勝棋譜(一)奈許棋棋盤的製作首先，老師將所需的奈許棋盤從22階到55階繪製在A4大小的紙上，並且用原本是用來黏貼教具圖卡的小磁鐵片對黏，當成奈許棋棋子，再將部分磁鐵用立可白塗上白色作為直方的棋子，未塗顏色的磁鐵則為橫方棋子。如此一來，我們用磁鐵製成的棋子不僅使我們能隨時隨地攜帶研究，並且當我們有需要一起討論或對老師說明時，我們還可以在黑板上馬上繪製棋盤，自製的棋子也能吸附在黑板上方便我們對奕。(二)奈許棋盤格子位置之標示因為我們在分析奈許棋棋盤時，會常提到格子的位置，所以為了方便討論，我們將所有的格子以座標符號用來標示位置，以圖6的33階奈許棋為例子，座標符號(1,1)的第一個1代表橫列第一列，第二個1代表由左算來直排第一排，其他座標符號所代表的位置以此類推。圖5(三)奈許棋譜的紀錄方式為了使我們漫無頭緒的研究能以有條理的方式加以分析，於是我們便以的符號表示直方，以一的符號表示橫方，紀錄在棋譜上。然後將、2、3、等紅色的數字標示在棋盤的格子上，來表示直方落子的順序；將一、等藍色符號來表示橫方落子的順序。以圖3-3為例，一的記號有五個，表示當橫方第一子下這幾個位置時，直方只要在座標位置(3,3)下第二子，此局奈許棋盤直方就穩勝了。(四)奈許棋的必勝棋譜這些多達五頁的棋譜花了我們約一個月的時間整理，雖然相當耗時間，不過在錯誤的過程中也讓我們有不少意外的收穫。圖3-1所表示的是直方第一子落在的位置上時，直方必勝；落在的位置時，則直方必敗。圖3-2表示當直方下在的位置時，橫方只要下在(2,2)的位置上則直方必敗。圖3-3至圖3-14表示的是33階奈許棋直方的必勝棋譜。圖4-1所表示的是44階奈許棋，直方第一子落在的位置上時，直方必勝；落在的位置時，則直方必敗。圖4-2和圖4-3表示當直方下在的位置時，橫方只要下在一的位置上，則直方必敗。圖4-4至圖4-12表示的是44階奈許棋直方的必勝棋譜。圖5-1至圖5-60表示的是55階奈許棋直方的必勝棋譜。圖5-61表示當直方下在的位置時，橫方只要下在一的位置上，則直方必敗。四、奈許棋之轉換型為了找到必勝棋譜，經過無數次的對奕，有一次我們不經意的發現奈許棋似乎可以有不一樣的角度去分析它，因為當我們把棋盤上每個格子內畫上一個圓點，而格子與格子間相連的通路則看作是為圓點間的連線，將所有的通路以直線相連通，我們發現奈許棋盤變成菱形格子棋盤，再將菱形格子棋盤，用過去我們學習數學四邊形的單元，使用吸管製成的菱形經由拉扯可變成正方形的方法，將它拉扯成一個方格棋盤。經過這些操作，奈許棋棋盤竟會成為傳統鬼腳棋棋盤的變形。接著，當我們先簡化轉換過後的棋盤，(如圖6所示)棋局的下法與原先的下法相同，經過數次對奕，發現玩棋的雙方若是十分熟悉遊戲的玩家，則此簡化型奈許棋是會是場永遠和棋的遊戲。證明的方法很簡單：當直方佔有任一圓點時，橫方只要擋住其前進的去路，則直方便無其他直進的通路。相反的，當橫方佔有某一個圓點時，直方也可用同樣的方式阻止橫方前進，橫方亦無其他橫進的通路。圖6所以我們發現原先的奈許棋盤斜線所形成的通路是讓原本只有和棋狀況簡化型棋盤產生極大改變的重要因素，於是我們相信奈許棋經過轉換，其新的型態將有助我們對奈許棋有更深入的了解。伍、研究結果一、奈許棋盤的對偁性為了讓奈許棋的研究嚴謹，我們將直接從棋盤下手。在分析棋盤的一開始，我們馬上發現令人驚奇的現象，以下圖圖5所示，是個33階奈許棋。我們將棋盤從右下角到左上角的格子用線段AB串起來，並且以線段AB為軸將棋盤以逆時針方向旋轉180度，發現棋盤的形狀不變，而且以線段AB為對稱軸，左下角格子內三角形記號，經過旋轉後記號就挪往右上角的格子內，這表示當我們想分析棋盤右上角或左下角格子內的落子，只須分析其中一格的落子就可以了，這說明了當我們在討論奈許棋盤上的落子時，我們以線段AB為軸，只須分析整個棋盤的上半或下半格子數就可以了，而這也是奈許棋盤的對稱性質。圖7二、 奈許棋是先下者有必勝策略的遊戲我們在研究中，經過無數次的實驗，考慮了所有的可能性，一共驗證了22階到55階的奈許棋盤，所有的實驗結果都紀錄在P6P12，得到了下面三個結果：(一)奈許棋是先下者有必勝策略。(二)先下者的必勝關鍵在於所下的第一子。(三)當先下者的第一子落於(1,k),(n,k-1)：n是指奈許棋的階數,k=2,3,的位置，則後下者的第一子必落於對稱軸中心點的位置。以P6所紀錄33階棋譜為例，只要直方的第一子落於(1,1)、(2,1)、(2,2)、(2,3)、(3,3)，不管橫方的落子落在哪個位置，則這盤棋無疑是必勝的；如果落子落在(1,2)、(1,3)、(3,1)、(3,2)的位置，則這盤棋必敗無疑。所以我們將直方以紅色記號表示必勝第一子，藍色記號表示直方必敗點，將直方所有勝敗關鍵的第一子位置描繪在圖8，以利我們作進一步的觀察。圖8三、 奈許棋盤勝敗關鍵子位置具規律性首先我們先定義勝敗關鍵子：勝敗關鍵子是指直方所下的第一子，而這一子的位置影響後來勝負的關鍵。由圖8，我們發現一個令人覺得漂亮的現象，也就是奈許棋盤勝敗關鍵子的位置具規律性。偶數格棋盤的必勝子的位置都落在對稱軸的格子上，也就是在(k,k)：k=1,2,的位置上；而在奇數格棋盤上，除了在(1,k),(n,k-1)：n是指奈許棋的階數,k=2,3,的位置之外，落在其他所有位置的第一子都是必勝子。值得一提的是偶數格棋盤的必勝子數目在比例上明顯比奇數格棋盤的必勝子數目少很多。四、 奈許轉換型棋盤的新發現當我們的研究在發現了上述的結果之後遇到了瓶頸，也就是怎麼讓結果一般化，因為我們處理的棋盤都是較低階的棋盤，當較高階的棋盤出現時結果是否也是如此？這個問題令我們好奇，也讓我們頭疼。不過奈許轉換型棋盤的出現讓我們有了新發現，如圖9所示，它是55階的奈許轉換型棋盤，如果我們將第一子下在(3,3)的位置，在它的左上角及右下角，用藍線畫出一樣大的正方形，而這不就是33階的奈許轉換型棋盤，於是我們就有了一個想法，一個高階的奈許棋是不是可以用較低階的奈許棋盤來分析？圖9圖9陸、討論一、 當壁磚的形狀是正方形，奈許還會在上面下棋嗎如果壁磚如下圖所示是正方形，則依照先前的結果，將原本藍色正方形棋盤轉換成紅色棋盤，兩個熟悉遊戲的玩家一定最後是和棋收場，相信奈許應該對這種遊戲不感興趣，而且不會有現在奈許棋那麼多有趣的結果。二、 所有的不公平棋盤遊戲是否都是先下者有必勝策略在奈許的有趣證明中，我們察覺到他的證明內容沒有提到棋盤的樣子是怎樣，所以我們討論出一個結果，所有的棋盤遊戲只要符合下面的假設：(一)不管棋盤型式為何，它是個雙人遊戲。(二)它是個有限回合可結束且不會和棋的遊戲。(三)它是個不公平的遊戲。則先玩的玩家一定有必勝策略。三、奈許棋必定是先下者有必勝策略的遊戲三、奈許棋必定是先下者有必勝策略的遊戲一開始我們經由不斷的試驗，確定22階到55階奈許棋是先下者有必勝策略的，但是高階的奈許棋呢？我們藉由轉換型棋盤很快的解決了這個問題，以圖A-1為例，它是個77階奈許棋，假設直方把第一子下在(4,2)的位置，我們就以(4,4)為中心點，在它的周圍用黑筆畫出一個55階奈許棋盤。先看小棋盤，小棋盤是一個55階的奈許棋，我們知道對於這一階的奈許棋盤，直方有必勝棋譜，直方下的第一子落於小棋盤的(3,1)位置，就小棋盤而言，直方下在必勝點的位置，由之前紀錄的棋譜看，直方可上下連成通路；再看大棋盤，直方也可有效的繼續往上及往下連接。從上面的討論得知，藉由55階奈許棋的研究結果可以推出77階奈許棋直方的必勝策略，所以以同樣的方式可以推出99階奈許棋甚至更高階奈許棋直方的必勝棋譜，由此就證明出奈許棋是個不公平的遊戲，而且是先下者有必勝策略的遊戲。我們以此推出大於55階的偶數階奈許棋盤必有四個對角線上的必勝點，而奇數階棋盤則有十七個必勝點。四、先下者第一子落在(1,k+1),(n,k)：k=1,n-1上，先下者必敗由圖A-2可知，當直方第一子下在(1,4)的位置，橫方可在右下角55階棋盤變成先下者，而在此棋盤下，橫方佔有優勢，可以從右方連結通路到左方，這時直方的第一子對橫方來說是一個廢子，而橫方可輕易的贏得勝利。五、高階棋盤必勝點只能從其正中間的低階棋盤得到由圖A-3的44階奈許棋盤做例子，當直方下的第一子位置在(2,1)上，由棋譜得知直方必敗。如果我們挑選的低階棋盤是左上角的33階棋盤，直方的第一子是在其必勝點上，則直方應該會上下連成通路，但是結果不是這樣。原因出在直方往下