天使問題

圖中棋盤區域中央為天使，當天使力量為 3 時，其當前可移動區域被藍色點畫線圍起

天使問題是由英國數學家約翰·何頓·康威提出的一個博弈論問題，在2006年已獲解答。

陳述

天使問題是關於一個叫天使與惡魔的雙人遊戲，其規則如下：

1. 兩名玩家分別扮演天使和惡魔
2. 遊戲開始前，指定一個正整數 K，稱之為天使的力量
3. 遊戲在一個無限大的方格棋盤上進行；開始時棋盤是空的，天使停留在棋盤上的某一個方格（稱為天使的起始點），惡魔並不存在於棋盤上
4. 每一輪中，惡魔可以在棋盤上放置一個路障，路障不可以放置在天使停留處
5. 每一輪中，天使可以向相鄰格移動至多 K 步，移動過程中可以穿過路障，但移動終點必須停留在沒有路障的格中；縱橫斜格均算作相鄰格
6. 從惡魔開始，雙方交替進行（若從天使開始，從上面的規則描述，亦可等價轉換為從惡魔開始的局面）
7. 若在一輪中，天使無法移動，則惡魔獲勝
8. 如果天使能夠無限地繼續遊戲，則天使獲勝

天使問題可以陳述為：

是否存在某個K，使得力量為K的天使擁有必勝策略？

已知的證明

二維

• K = 1 時，惡魔有必勝策略（康威, 1982）
• 如果天使不可以降低其 y 坐標，則惡魔有必勝策略（康威, 1982）
• 如果天使一直增加它到起始點的距離，則惡魔有必勝策略（康威, 1996）

在2006年，有4位數學家獨立解決了天使問題。英國數學家布萊恩·鮑迪奇（Brian Bowditch） 證明了K = 4的時候，天使有必勝策略。 挪威數學家Oddvar Kloster 和 András Máthé 各自證明了K = 2的時候，天使有必勝策略。Péter Gács 則是證明了當 K 充分大時，天使有必勝策略。

外部連結

• Oddvar Kloster 就天使問題所設的網頁