天使问题

天使的许多直觉逃跑策略都可以被击败。例如，如果天使试图从附近的障碍物逃离，魔鬼可以在北边远处制作一个巨大的马蹄铁，然后反复吃掉天使南边的格子，将天使推入陷阱。如果天使试图避开设置在很远的地方的陷阱，魔鬼可以在北面做一个小马蹄铁，然后通过吃偏南的格子来让天使进入陷阱。

看起来天使应该能够以最快的速度上升，并偶尔向东或向西曲折前进，以避免任何明显的陷阱。这种策略可以通过注意到这个天使未来可能的位置在一个圆锥体中而被击败，魔鬼可以以一定的方式在远处的圆锥体表面建造一堵墙，这样当天使最终到达远处时，魔鬼就建造了一堵不可穿透的墙，由于天使坚持向北移动，天使根本就不能移动了。

这个问题首先发表在Berlekamp，Conway和Guy的《Winning Ways》[5]一书中，名为“天使和吃格子的人”。 在二维空间里，一些早期的部分结果包括:

• 如果天使有力量1，魔鬼就有力量1 获胜策略 (康威，1982)。(根据康威的说法，这个结果实际上是Berlekamp的功劳)。这可以在Kutz的论文的第1.1节中读到。
• 如果天使从不减少它的y坐标，那么魔鬼有一个获胜的策略(康威，1982)。
• 如果天使总是增加它与原点的距离，那么魔鬼有一个获胜的策略(康威，1996)。

在三维空间中，它显示为：

• 如果天使总是增加它的y坐标，而魔鬼只能在一个平面上玩，那么天使有一个获胜的策略。
• 如果天使总是增加它的y坐标，而魔鬼只能在两个平面上玩，那么天使有一个获胜的策略。
• 如果天使拥有13或更多的力量，他就有一个获胜的策略。
• 如果我们有无限多的魔鬼各自再距离d的地方进行游戏     如果力量足够强大，天使仍然可以赢。(通过“远距离游戏    “我们的意思是魔鬼必须在离起点超过d 的格子进行游戏)。

最后，在2006年（彼得温克勒的书“数学谜题”出版后不久，它帮助宣传了天使问题），出现了四个独立且几乎同时的证明，即天使在二维方面有一个成功的策略。 Brian Bowditch的证明适用于4天使，而Oddvar Kloster的证明和AndrásMáthé的证明适用于2天使。 PéterGács的证明仅适用于更大的常数。 Bowditch和Máthé的证明已发表在Combinatorics，Probability and Computing中。 Kloster的证明已发表在理论计算机科学上。

在三维空间中，假设天使总是增加它的 y坐标，魔鬼限于三个平面，魔鬼是否有获胜的策略有待证明。

4.1 “监护人”证明

证据表明，在游戏的三维版本中，高性能天使有一个获胜策略，利用“守护者”。 对于任何尺寸的每个立方体，都有一个监视该立方体的监护人。 监护人在每次移动时决定他们正在观看的立方体是否不安全，安全或几乎安全。 需要选择“安全”和“几乎安全”的定义以确保其有效。 此决定完全基于该立方体中的阻塞点密度和该立方体的大小。

如果天使没有得到命令，那么它只是向上移动。 如果天使占据的一些立方体不再安全，那么这些立方体中最大的一个的守护者被指示安排天使通过那个立方体的一个边界离开。如果监护人被指示护送天使离开魔方到一个特定的面，监护人通过绘制一条安全的子立方体路径来做到这一点。 然后这些立方体中的守护者被指示护送天使通过他们各自的子立方体。天使在给定子立方体中的路径直到天使到达该立方体才被确定。 即便如此，这条路也只能粗略地确定。 这就确保了魔鬼不能只选择一个足够远的地方来阻挡它。

这种策略可以被证明是有效的，因为魔鬼将天使路径中的安全立方体转换成不安全立方体所需的时间比天使到达该立方体所需的时间长。

这一证据是由 Imre Leader 和 Béla Bollobás 2006年提出的。^[4] 一个基本相似的证据由Martin Kutz于2005年提出。^[4][4]

4.2 Máthé的双天使证明

Máthé^[5] 介绍了 善良的的魔鬼， 永远不会摧毁一个天使本可以选择提前占领的格子。 当天使和善良的魔鬼比赛时，如果魔鬼设法把它限制在棋盘的有限区域内，天使就承认失败了(否则天使能在两个方格之间来回跳跃，永远不会输！)。Máthé的证明分为两部分:

1. 他表明，如果天使战胜了善良的魔鬼，那么天使就战胜了真正的魔鬼；
2. 他为天使对抗善良的魔鬼给出了明确的获胜策略。

粗略地说，在第二部分，天使战胜了善良的魔鬼是通过假装整个左半区域都被摧毁了(除了被善良的魔鬼实际摧毁的广场之外)，把被摧毁的格子当成迷宫的墙壁，然后通过“用手摸墙”的方法来避开它。也就是说，天使把它的左手放在迷宫的墙上沿着墙跑。然后，我们可以证明一个善良的魔鬼无法困住一个采用这种策略的天使。

第一部分的证明是矛盾的，因此Máthé'的证明不会立即产生对真正的恶魔产生明确的获胜策略。然而，Máthé说，他的证明原则上可以修改调整来给出这样一个明确的战略。

4.3 Bowditch的4天使证明

Brian Bowditch定义了[2]原始游戏的变体（游戏2），其中包含以下规则更改：

1. 天使可以回到它已经去过的任何格子，即使魔鬼后来试图阻止它。
2. 一个力量为k的恶魔在被阻挡之前必须造访一个格子k次。
3. 天使向上、向下、向左或向右移动一格(公爵移动)。
4. 为了获胜，天使必须找到一条迂回的道路(定义如下)。

迂回的道路是一条道路    在哪里    是半无限弧(有起点但没有终点的非自相交路径)，并且    是具有以下属性成对不相交循环:

•     在哪里     是ith循环的长度。

(定义明确    必须在的终点开始和结束    和    必须在的起点结束   。)

鲍迪奇考虑了游戏的一个变种(游戏1)，其中改变了2和3，有5个魔鬼。 然后他展示了在这个游戏中获胜的策略将会在我们最初的游戏中为一个4天使产生一个获胜的策略。 然后他继续展示一个天使玩5魔鬼(游戏2)可以用一个相当简单的算法获得胜利。

鲍迪奇声称，一个4天使可以通过想象一个幻影天使在游戏2中扮演一个5魔鬼来赢得游戏的原始版本。

天使沿着幽灵走的路走，但避开了环路。 因此作为路径    是一个半无限弧，天使不会回到它以前去过的任何方块，所以即使在最初的游戏中，这条路也是一条获胜的路。