天使問題

天使問題是英國數學家約翰·何頓·康威提出的，實質是博弈論問題，需要兩名參與者。

基本介紹

• 中文名：天使問題
• 外文名：Angel problem
• 提出者：英國數學家約翰·何頓·康威
• 實質：博弈論問題
• 人數：兩名 

基本規則

1.有兩名玩家參與遊戲， 兩名玩家分別扮演天使和惡魔。

2.遊戲開始時， 指定一個正整數 K，稱之為天使的力量 。

3.遊戲在一個無限大的方格棋盤上進行；開始時棋盤是空的，天使停留在棋盤上的某一個 (稱為天使的起始點)，惡魔並不存在於棋盤上 。

4.每一輪中， 惡魔可以在棋盤上放置一個路障，路障不可以放置在天使停留處

5.每一輪中，天使可以向相鄰格移動至多 K 步， 移動過程中可以穿過路障，但移動終點必須停留在沒有路障的格中； 縱橫斜格均算作相鄰格。

6.從惡魔開始，雙方交替進行 (若從天使開始, 從上面的規則描述，亦可等價轉換為從惡魔開始的局面)。

7.若在一輪中，天使無法移動，則惡魔獲勝。

8.如果天使能夠無限地繼續遊戲，則天使獲勝。

已知的證明

K = 1 時，惡魔有必勝策略 (康威, 1982)

如果天使不可以降低其 Y 坐標，則惡魔有必勝策略 (康威, 1982)

如果天使一直增加它到起始點的距離，則惡魔有必勝策略 (康威, 1996)

2006 年，至少有 4 位數學家獨立證明了在 K 為較小整數 (包括 K = 2) 的情況下, 天使有必勝策略。