天使问题

维基百科,自由的百科全书
跳转至: 导航搜索
图中棋盘区域中央为天使, 当天使力量为 3 时, 其当前可移动区域被蓝色点画线围起

天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题。

规则[编辑]

  1. 有两名玩家参与游戏. 两名玩家分别扮演天使和恶魔
  2. 游戏开始时, 指定一个正整数 K, 称之为天使的力量
  3. 游戏在一个无限大的方格棋盘上进行; 开始时棋盘是空的, 天使停留在棋盘上的某一个 (称为天使的起始点), 恶魔并不存在于棋盘上
  4. 每一轮中, 恶魔可以在棋盘上放置一个路障, 路障不可以放置在天使停留处
  5. 每一轮中, 天使可以向相邻格移动至多 K 步, 移动过程中可以穿过路障, 但移动终点必须停留在没有路障的格中; 纵横斜格均算作相邻格
  6. 从恶魔开始, 双方交替进行 (若从天使开始, 从上面的规则描述, 亦可等价转换为从恶魔开始的局面)
  7. 若在一轮中, 天使无法移动, 则恶魔获胜
  8. 如果天使能够无限地继续游戏, 则天使获胜

已知的证明[编辑]

  • K = 1 时, 恶魔有必胜策略 (康威, 1982)
  • 如果天使不可以降低其 Y 坐标, 则恶魔有必胜策略 (康威, 1982)
  • 如果天使一直增加它到起始点的距离, 则恶魔有必胜策略 (康威, 1996)
  • 2006 年, 至少有 4 位数学家[谁?]独立证明了在 K 为较小整数 (包括 K = 2) 的情况下, 天使有必胜策略