天使问题

天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题John H. Conway, The angel problem , in: Richard Nowakowski (editor) Games of No Chance, volume 29 of MSRI Publications, pages 3–12, 1996.，在2006年已獲解答。

 陳述 

天使问题是關於一個叫'天使與惡魔的雙人遊戲，其規則如下：
 兩名玩家分別扮演天使和惡魔
 遊戲開始前，指定一個正整數 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 就天使問題所設的網頁

Category:数学游戏
Category:组合博弈论