天使问题，一个2006年才被证明的博弈难题！

南琴御依:
搜了下k=1的必胜策略 为方便展示，这里将格点化为方格。如图2所示是一个33*33的棋盘，天使起始位于红色方格。无论天使开局怎么走，恶魔前8步只需将棋盘四周的8个黑格填上障碍物，这时天使必然位于中间的蓝色区域内，距离接触包围圈还有7步。

【回复】回复 @不是故意不小心的 : 这是最佳解，围更大应该也是可以的
【回复】回复 @正常的球 :这是k=1的情况，天使只能走周围的8个
【回复】有个问题，这是不是k=1的唯一解法，再围大一点行吗
三界游:
这类问题最不缺的就是形而上学的讨论，最缺的就是严密的论证。大胆假设是很多人都喜欢干的事情，这样让他们很有“科研感”和“参与感”。但是真正要小心求证的时候，因为或许枯燥，过于焦虑，大部分人就不感兴趣了。只有一小撮人愿意去做，留下论文。

【回复】说得对[支持][支持][支持]但是“形而上学”这个词用错了，“形而上学”的“形而上”一词来源于“形而上者谓之道，形而下者谓之器”，“形而上学”最早出现在古希腊，意思是“比具体科学更加根本、更加深层的科学”，换句话说，数学、逻辑学、哲学等等都属于“形而上学”。认为“形而上学”是“片面、孤立、静止”的代名词，只是一部分“辩证法”支持者(事实上，这一部分支持者中甚至有相当一部分对“辩证法”的含义并不清楚)对于“形而上学”一词的曲解，并不是“形而上学”的本义。形而上学的研究方法本身是全面的、联系的、严密的、科学的研究方法。或者说，如果一种研究方法不能做到全面、联系、严密、科学，它就不能被归为形而上学，因为它并不“上”于“形”。
【回复】看了下后面的评论，都被你说中了。这个问题要严谨地论证真的挺难的，本数学白痴已经晕了[笑哭]
【回复】回复 @地卒幼子 : 所谓形而上的“片面、孤立、静止”，是指遵循亚里士多德以来的经典逻辑的无矛盾律以及爆炸原理（ECQ）传统。正式背离这点始于黑格尔，但因为没有严格的逻辑基础，形式上能指派任意的正题和反题而流于诡辩，因此传统形而上学也排斥传统的辩证法。从现代观点来看，用次协调逻辑替代弱化的ECQ（而不是完全扬弃ECQ的使用）是可能的，所以辩证法在这个意义上不是诡辩，而是形而上学的一部分非传统形式的补充（因为研究的对象的一致）。现代普遍认为，关于形而上学的辩论普遍会落入形而上学的传统之内。至于科学就是另一回事了——因为如果能算科学就直接赶到科学里去了，形而上学是剩下的科学解决不了的疑难杂症的合集；只不过原则上形而上学会和科学之间保持无矛盾。
燚燚阳阳:
问个不合时宜的问题 困住有cg吗[星星眼]

【回复】确实挺不合时宜的，答案也自然是没有的[doge]
【回复】就你小子油盐不进是吧[doge]
花徒めと:
[doge]我已经发现了一种绝妙的天使必赢的证明方法，奈何这里太小，写不下。

【回复】那你发视频证明啊，十个小时我们也看[傲娇]
低调的小恶魔:
感觉天使能不能赢取决于天使的这个k格有多远，如果只是k＝1的话，那恶魔完全可以天使封锁起来，但如果k＞1，就算恶魔造好了墙，天使也可以跨过去，除非恶魔造的墙有k格厚，k越大，天使越活跃，恶魔所需造墙的厚度也越大，然而恶魔只能一次造一格子的墙。至于这个k的最大可以为多少以至刚好够恶魔造墙困住天使，我就算不来了[藏狐]

【回复】地图是无限大的，且恶魔不限制移动距离。就是说恶魔可以在距离天使“无限”远的地方围一堵天使移动距离厚度的墙，让这个地图变成有限大小，有限的天使输掉就是迟早的事情。
【回复】回复 @插座叔 :能不能成功还是要证明的吧，因为砌这墙的速度是跟不上天使变化的速度，因为你要成功就必须建个圆来困住天使，但问题是你一次只能动一格，而天使能动10格，也就是说天使每动一次就会大大的增加你的工作量，那到底你能不能在天使到达墙壁前每次都完成工作这个是要证明的吧[doge]
【回复】回复 @插座叔 :那你也得无限时间才能造出来墙
灵の语:
还有一点，如果魔鬼采取的是提前堵的策略，那么天使所谓的不会回到原来的区域的设想就将不复存在 而且一个比较简单的验证方法是限定天使只能向一个方向直线行驶最大的距离，魔鬼是否能够在一个足够远的距离建造以天使的起始点为中心的正方形的一条边的隔离带，这条隔离带的厚度必须等于天使移动的最大半径

【回复】这是一个信息对称的博弈，天使回到原来的区域后，与上一次相比只是地图上多了几个禁止区域，没有任何好处。
【回复】你这句“如果魔鬼采取提前堵的策略，那么天使所谓不会回到原来的区域的设想将不复存在”有问题。就假设你一开始往北走，我在你北边一定距离外堵你，那么你此时掉头往南走，我照样在你南边同样距离外堵你。这和你一开始就往南走没区别，我反而多在北边堵了一下，显然就算我在远处堵你还是不应该走到你曾经能到的地方
【回复】怎么说呢，如果所有天使不回到原先能走位置的情形都是魔鬼赢，那么所有天使能回到原先能走位置的情形也是魔鬼赢
秋天无落叶:
这视频好有意思，这么多人说在无穷远的地方开始建墙就行了，[辣眼睛]你在无穷远的地方建墙，等于我需要无穷的时间才能抵达墙，但是恶魔的胜利条件是天使不能移动啊，天使在无穷的时间内一直在移动，这算什么，恶魔的自暴自弃吗

【回复】不是无穷远，而是足够远。一旦k值确定，天使的最大移动速度即确定。只要足够远，即可保证在天使到达之前建成宽度超过k值的墙，天使无法跨越。如天使反向或转向移动，按照公式提前在对应方向筑墙。最终可得一个有限面积的牢笼，剩下的就是逐步缩小面积。
【回复】回复 @lance1ight :足够远这个描述基本上是错误的，你墙越远，墙的长度越长，你永远只有一块砖，是来不及建好墙的
【回复】回复 @bili_77684889263 :[笑哭]无限的距离能收缩到有限吗？
爸比说:
只要数学家从数学上已经论证过了，学历最多到大学高数的人也就不需要再参与进抬杠了

【回复】水平在本科的数学系大学生一眼确定这不是我能讨论的，在我学历之下的很多人却急着发表观点甚至理直气壮的挣理论据[doge]
【回复】大学高数的人想验算一遍都不够格
【回复】回复 @Pro47 :别，这个问题验证证明的难度没那么难，难的是把证明方法想出来
doubledxm:
这是个哲学问题，其实恶魔只要把个小范围围起来就行了，那么天使就在“另一侧”被围起来了

【回复】把自己围起来然后说“我在外面”是吧😂
【回复】如果是一个无限大的球面 那么理论上可行 但条件只说了网格
【回复】不是，困住的意思是“无法移动”，天使的所有够得到的地方全都被移除才算。
土文小朋友:
如果你发现了一个非常有趣的问题，那么要么他的提出者是John Conway，要么是John Conway把它解决了。如果以上两种情况都不是，那么就是这个问题还不够有趣

【回复】这是高斯笑话哦[doge]原笑话都是讲述高斯在数学上的离谱成就，我套个皮发的（下为更多高斯笑话： 很多数学家们相信上帝有一本记录数学中所有绝妙证明的书，而上帝相信这本书在Conway手里 Conway可以一个数位不漏的默写圆周率——倒着写 Conway可以不重复的一次走遍哥尼斯堡的七座桥 Conway通过列举了全部的素数证明了素数有无穷多个 当你在证明某些命题时企图假设一些东西——诸如设x为正整数——时，你是在请求Conway允许你这样做
【回复】回复 @bili_22624687028 :这些笑话我能讲一晚上（ 当Conway给一个正整数加一时，那个正整数并没有增加，而是其他全部正整数都减少了一 Conway从来不了解什么是随机过程，因为他能预测出随机数 发散级数之所以存在，是因为Conway认为它们不值得被加起来 Conway可以用三种颜色染满任何一张地图 Conway可以把任何数除以零 Conway掰断了一块磁铁，然后他就能得到两个单极磁铁 Conway为了证明一个难题在50年前发明了量子计算机，但当Conway使用它时，这使他的证明工作减慢了 Conway是这样证明庞加莱猜想的：他验证了全部的三维流形，没有找到反例 空集的定义是Conway无法证明的定理所构成的集合 上帝从不掷色子，除非Conway允许他赢一小会儿 高斯是Conway发表未公开的成果时使用的假名
【回复】John Conway有一次遇到一个有趣的问题，但是他发现这道题的解非常不美观，于是他就把这个问题证明成了非有趣的
随身听ing:
这个问题还可以再拓展一下：如果恶魔一次建N个墙（N＞1）那么天使每次至少走的步数是多少才能不被困住？[doge]

【回复】通过瞪眼法，我只能告诉你，当n足够大的时候，天使可以直接考虑怎么在cg里出场了[doge]
【回复】那再扩展一下，假设规则改为恶魔建造的墙数N和天使步数K成正比例关系，是否存在天使必胜策略？
【回复】回复 @你先憋急 :虽然但是，k＞1时题上天使是能穿墙的
BlackR:
一个简单的思考方式，没啥严谨性，发出来一乐： 谜题里效率最高的建墙方式应该就是正方形墙了，因为所有有效的斜墙都可以通过把内侧格子移动到外侧的方式来扩展面积，而不增加需要的格子数，所有格子移动完成后自然会变成方形。 然后是移动与建墙的格子数关系，在k=2的时候，天使从中心走到墙边，然后巡着边长n（考虑n→无限大）的正方形墙一圈，需要2.25n回合，这期间魔鬼无论如何都只能砌出28.125%的墙，所以天使总是能找到无法完全封堵的突破口？如果是k=1，走到墙边巡墙一周需要4.5n回合，这个时长在纸面上足够把4n格的墙建好了，剩下的编排格子分布策略就能够解决。 当然，这属于是瞪眼法给结论（以及看到结论再顺杆爬），严谨的证明要是有这么简单哪还要到2006年才有结果[思考]

【回复】回复 @就会说的话vksuhk :斜墙需要K+1排才能围住，直墙只需要K排
【回复】回复 @Sourhyme :不一样，举个很简单的例子，假如K为1，以3*3的格子为例。假设你斜着围(1，1)(2，2)(3，3)这三个格子，那么是可以从(2，1)到(1，2)的。而如果围(1，2)(2，2)(3，2)这三个，那么是无法从(1，1)到(1，3)的。
【回复】4个格子的斜墙可以控制5个格子，直的只能4个。。。
白井黑加仑:
咱们现在才搞明白，这个视频的逻辑，这个视频主要是探讨在k=1的情况下，天使可不可以走出去？然后得出来的结论是出不去，因为我可以根据天使的方向上在足够的距离上建墙。但是后面会说在k=2或者k更大的情况下，天使会获得胜利。

【回复】回复 @lx554999 :k更大了肯定更加能跑出去啊
【回复】回复 @lx554999 :K指的是天使所能一次移动的距离，原文说的是K=1时，天使能够被围堵，但是，K越大所需要围堵的范围，即墙体厚度宽度需要增加，所以K≥2时天使可以逃出
【回复】回复 @kekebili :不管啥策略，k只要大于等于2时恶魔都没有可能会赢，堵的速度只有在k等于1时能追上跑的速度
头像背叛了你:
我个人的理解是K≥2时天使必胜 首先前提，魔鬼已经在一个方向上布置好了一个圆环的一部分，天使已经装上这堵墙了，即视频里提到的“魔鬼必胜”套路的一部分 此时天使选择绕着这个环开始走，一直走到一个环宽未达到天使的跳跃距离K的位置并跳出去。 反证法，假设魔鬼第S（step）步，成功形成了一个半径为R且环宽不小于K的环困住天使（简化成圆环），这意味着天使在第（S-1）步时，她必须要未处于此环最薄弱的位置边缘否则其可以直接跳出这个环 但我已经提到了，天使是贴着环走的，也就是说魔鬼需要让这一整个环的边缘都大于K，而造这么一个环，也就是说S≥2πRK，而天使绕完整个环的步伐一共需要S'=1+（R+2πR）/K步（中心到边缘距离+绕一圈的距离/天使的跳跃格子数+1步出圈），显然在R非常大的时候，若K为正整数，当且仅当K=1时，S'＞S，否则S'＜S 反证法证明矛盾，说明K≥2时天使必胜 ————补充分割——— 1.反证法只能证明K≥2时即使恶魔采取最佳策略也困不住天使，不能证明K=1时必定困住 2.我知道这是正方形，你取π=4就是正方形了，这不会影响最后的结果 3.钝角

【回复】拿思路说的就不用反驳了，原证明就是证明天使绕着恶魔框出的圈走一圈花的时间少于恶魔把天使围起来的时间，不过因为正方形，人家用的单位方框数不是半径，由于K不小于二时天使走一步至少为会经过二条边，而恶魔需要连框在一起，每走一步至多出现二边，最后和恶魔的步数相比天使能出去，你可以说我把这个复杂问题简化成最简圆环了，但整体思路没问题
【回复】总体思路是对的，但是你的第一条回复“天使知不知道没有任何所谓”毫无疑问是错的。棋盘必须是公开信息这个问题才有意义。否则恶魔大可以在某个地方做个笼子碰运气等天使来送。只有是公开信息，才有“必胜”的结论。
【回复】回复 @头像背叛了你 : 我感觉在某种程度上接近围棋啊，就是所谓“气”，一颗棋子有四口气，四口气被堵满了这颗子死掉，但在这四口气被堵完之前这颗子总有能力可以提前走一步，假设这个棋盘无限大，那无论如何封堵，这颗子只需要多走出一步就能继续拥有至少两口气，所以天使必赢。当然这个情况是建立在双方都是执棋者，即双方都有对整个局势的无限视野的情况下。假如将视角放到棋盘上落子的交叉点所在的平面上的话，那就更像是博弈问题了，天使和恶魔都需要在双方完全不知道对方位置的情况下移动，则天使只需要不停的向某个方向移动，除非恶魔恰在此处构建了一堵墙来围堵天使，否则天使一定能够逃离，且恶魔在信息完全未知的情况下也无法确认天使是否在自己的封锁圈内，那么他需要构筑的是一个直径无限大的圆，而天使接近于走一条直线就能走出这个包围圈了。在无限大的平面内直线与圆相交的概率极低，且在此情况下直线上的点落在圆内只有相交区域的一部分线段，这条线段在无限大的平面中可以近似于一个点，即概率接近于零。那么天使获胜的概率接近于无限大 我是这么个想法，不知道对不对
kg62580:
奇怪，为什么恶魔的建墙速度恒定为1，而天使速度动态为K？这不是欺负人吗。只要k大于1，天使就能从增长的“口”字形墙体尚未完成的缺口中走出。简化来看，天使终究会抵达城墙边上，随后问题就变成了天使绕围墙移动的速度和围墙增长速度的比拼，显然，天使更快，总能超过围墙。

【回复】回复 @研究员-- :k=2天使就必赢了
【回复】那么你可以试一下恶魔一次挖掉K个格子
【回复】回复 @研究员-- :距离越远，封锁所需格子越多
往生堂七七:
[doge]我一看到这题目的想法是恶魔一开始就在一个正方形边界开始造围墙让天使出不去不就赢了吗

【回复】有个问题就是，比如你造个100x100的正方形，那你需要移动396次，天使直走的话可以走3960 早就走出你造的正方形了
【回复】回复 @令和唯一峰哥孙一峰 :数学家证明的，不会有啥大问题，恶魔先看天使的期望路径，在极其远的位置建虚线墙，天使离墙越近就把天使离最近的那墙建越密集，天使换向会导致自己白走很多路白给恶魔好几回合，综合下来恶魔会赢，但是棋盘会极其大
【回复】回复 @棍状闪电 :事实上这个问题2006年就被证明过了。当天使一次只能移动一格时，恶魔有必胜策略。当天使一次能移动2格以上时，天使有必胜策略。[doge]所以你理想中的虚线墙不存在
油布裹身涵洞睡觉:
这就跟围棋一样 长龙经常拐不出去就被堵死了

【回复】回复 @击退八的末地烛 :基本上到不了边就被堵死了 新手才会去拐长龙
【回复】不一样，围棋是完全围死，而现在就好比你黑棋下一手，白旗可以有白旗周围下10手，你怎么堵? 好比K=1时，你下一手，对面下一手， 视频也说了，K≥2时，你下一手，对面能下多收手，你怎么打 所以说K≥2天使就能赢
【回复】但是围棋格子有限[脱单doge]
草莓战宝变身:
在数学中，k＞2时，天使是必赢 在一个无限大的网格中，天使每回合可以在至多k的k值格子中移动。 那么，假如恶魔在天使无限距离外的格子内地方外建立起一堵围墙，而天使移动无限次后，正好抵达这一面墙，发现这一面墙正好是k格远，无法跳过去，这面墙一直向两旁衍生，距离是无限远。 而天使此时原路返回也是不现实的，假如这么墙的轴在平面上为X，而天使的原初出发点是O，那么天使原路返回的那一刻，恶魔会在X距离O的长度上，在对称的平面Y轴上，建立起另一面无限长的墙。 而天使原路返回到O点时，这一面墙就会完成。 也就是说，如果天使在碰到这一面墙之后，选择原路返回，在到达O点之后，可以移动的范围从无限远的四个方向，变成了只有两个远的无限方向。 看起来是这样吗？ 事实上，恶魔不但要建立这一面墙，还需要建立对角值的k×k平方根的k值的墙，防止天使在抵达墙边后，从斜角方向跳出去。 这个差值，会导致恶魔在无限的远的距离堵天使，而天使用迷宫法贴墙移动时，会使恶魔的工作量增大K×K的平方根的K值工作量，从而导致恶魔堵天使的效率跟不上天使逃脱的效率。 在无限长的时间内，恶魔建立了这一面无限长的墙，而天使在向某一方向移动的时候，恶魔只需要在对应方向的无限远的N轴，去除掉一个方块即可。即O至X的距离÷2÷K，K值越高，这一面墙的距离越短。也就是说，无论恶魔在多远的距离建立围墙，只要天使在抵达墙边后，无限的贴着墙移动，那么只要K＞2，恶魔建墙的速度就无法赶上天使的移动速度

【回复】回复 @雅败 :还是一样的，假设恶魔能看到天使的移动轨迹，而天使只能看到以自己为中心10×10的范围，天使只要随机跳跃（不走回头路），恶魔的陷阱就不可能砌好（因为恶魔速度慢）。 比如说恶魔在很远的地方（比如一亿格外）砌了一个长宽1000的陷阱，那么代表天使必须笔直的钻进陷阱，恶魔才能赢。 而只要天使在前进的时候方向和恶魔预估的差一步，到一亿格的时候就已经远离了陷阱（手拿激光笔只要动一点，终点就会偏离很多）。 恶魔天使偏一点，恶魔就得再比砌陷阱，游戏又回到了开始。 至于说恶魔在无限远的砌了无限大的陷阱，那就又回到之前的讨论了，无限大意味着无限久，所以恶魔必输。 如果硬要说恶魔能绝对计算出天使的移动轨迹，而天使看不到恶魔，那这就不是数学问题了，因为这这等于从题目上直接说天使一定会钻进陷阱，恶魔必赢，就不用讨论了。
【回复】回复 @逼展会倒闭但不会变质 : 可以啊，不是是概率的。比如你想想，如果k=10，恶魔建了了长宽各1000的正方形，边宽10，然后一边开了一个10x10的口子（这个口子的宽度和正方形的边长有关，边长越长，口子可以越大）。概率上如果天使进去了(如果天使不能看到10x10之外的地方，那就是有概率进去的)，并且一直往前走，直到看到另一面的边之后才意识到问题找出口。这个时候她至少要差不多100次移动才可以出去。恶魔只要在这100次移动的时间里面把10x10的口子堵住就行了。被关在1000x1000的正方形里面后，抓住就只是时间问题了。
【回复】很有趣的论点，但假设恶魔建的不是无限长的墙，而是弧线呢？或者有角度呢？
岳伞:
可能我脑子出了点问题，有以下想法： 只要恶魔在足够远的地方造一个厚度为5格厚的墙（保证自己在建完之前天使无法赶到）用这个围住，之后天使的可移动范围就有了上限，恶魔只需要把墙以内的空间慢慢填满不就行了[思考]

【回复】越远的地方需要修的墙也越长，花的时间越多，天使就也有可能在修好墙前逃出去。
【回复】就不说厚度为5，就算厚度是1的话，假设你距离天使为x的地方开始建墙，需要的时间是8x，而天使逃走的时间是x÷10，但是没有正数满足x÷10＞8x
【回复】回复 @保持微㗛 :地图是无限的，天使的速度是有限的。但天使对抗的并不是地图，而是速度远比天使更有限的恶魔。 现实是修填墙速度远没有天使脱困的速度快，结果上恶魔才是毫无机会的那个
Hwoke:
老实说，我感觉视频里天使的移动距离出了点问题，假如它有严格的移动距离限制（K格），那么它的移动范围就不该是一个正方形，视频里这个天使的K为10，但如果它要去左上角，那就走了横10格+纵10格，这下K等于20了，很明显是不对的[藏狐]

【回复】你说的那叫曼哈顿距离，视频里说的这个距离应该是切比雪夫距离，你们俩说的不是同一个玩意
【回复】规则定义一回合可以朝左右走最多K格，同时可以朝上下走K格，这样说可以了吧
【回复】用无穷范数诱导的距离[脱单doge]