- 專欄
文章專區
2015-02-01必勝撿石頭
542 期
Author 作者
游森棚／任教臺灣師範大學數學系及空軍官校。
這學期末，「離散數學」課進行的主題是「組合對局論（combinatorial game theory）」。課堂上我設計了許多兩人對弈遊戲，要同學找出必勝的方法。兩人對弈遊戲的基本設定是，甲、乙兩人輪流下，甲先開始。比如：
1. 一開始有16顆石頭，每次可以拿走1、2、3或4顆石頭，拿光石頭的贏。請問誰有必勝策略？要怎麼玩？
2. 從「0」開始，每次可以加上2或3，先達到4、9或 12的獲勝。請問誰有必勝策略？ 要怎麼玩？
講理論之前，我挑了幾個問題，讓全班同學捉對廝殺，看能不能從嘗試中發現必勝規則。競爭求勝是生物的本能，尤其「必勝法」是密技，實在太誘人了。於是課堂陷入一片混亂，全班興致高昂，討論非常熱烈。讀者可以先停下來，找個朋友玩個幾盤，看能不能找到必勝法。
聰明的同學就發現第一個問題的必勝法了，但是第二個問題的必勝法就需要一些思考。我們來從最簡單的情形開始慢慢摸索：一開始有3顆石頭，每次可以拿走1、2顆石頭，拿光石頭的贏。誰必勝？
顯然乙必勝。因為甲拿1，乙就拿2；甲拿2， 乙就拿1。而如果一開始有4顆石頭，則甲必勝（甲需先拿1）；一開始有5顆石頭，甲也必勝（甲需先拿2）。從這裡可以看出來，留下3顆石頭是一個關鍵。
那麼一開始是6顆石頭呢？這時甲拿1、拿2都不對，所以乙必勝。依此模式思考下去，可以知道，能走到
K ＝ {0, 3, 6, 9, ⋯}
的人就是必勝者。因為對手的下一步不管怎麼走，結果一定不是3的倍數。輪到我時， 又可以讓局面變成3的倍數。所以，如果一開始有7顆石頭，就要搶先手，先拿1顆。
同理，問題1的關鍵就是K＝ {0, 5, 10, 15}，也就是這幾個點是必勝點：對手下完一定離開K，而我又一定可以回到K。既然一開始有16顆石頭，所以先手必勝，拿走1顆石頭即可。
把這個想法概念化，找必勝點就是要找一些棋局狀態，形成一個集合K，使得輪到我下時一定可以走進K，而對手時他只能走出K。
集合K（也就是必勝點）稱為這個遊戲的核（kernel），所以分析對奕遊戲就是要找核。
如何把雙人對奕遊戲的核找出來呢？有一個簡單美妙的方法，稱為Sprague-Grundy（斯普萊格–格隆第）函數。......【更多內容請閱讀科學月刊第542期】