Hello! Thanks for watching this video. Since there seems to be some amount of disagreement in the comments, I thought I’d try to briefly clear up some of the common ones! - the extra characters the author introduces are a creative way of talking about certain tweaks one can make on the initial problem without actually affecting the end goal. This is very common in mathematics: in order to prove something, sometimes it is sufficient to prove something else, and that something else might be easier to argue! - some people are not happy with the Nice Devil losing implying the real Devil loses. It is first important to realise that this is completely equivalent to the real Devil winning implying the Nice Devil winning (which it seems people were more okay with); indeed if this were true, the Nice Devil cannot possibly lose should the Devil win. Note also that this part of the proof is set up against the Angel in its full form; what might happen between the Runner and the original Devil is never a part of it. Whilst it might feel as though the Devil should be ‘stronger’ against the Angel, the first part of this proof is precisely arguing that this notion of ‘strength’ is not useful in this particular game, because the Devil’s extra moves are essentially wasted (hence the notion of a reduced path). Perhaps a better name for the Nice Devil is the Smart Devil: fewer unnecessary moves, assuming the Devil had a good strategy in the first place. - there is confusion around the 5:12 mark for two understandable reasons I think: one is that I went through it very fast (I will avoid this in future videos), the other is that proofs by contradiction can turn out to be more confusing visually in cases like these than they are in written form, as they require displaying something that ‘can’t have happened’ (in particular, the new reduced path seemingly appearing out of nowhere). If you were lost at this point I would urge you to check out the original paper which is linked in the description! - several people are suggesting the Devil should simply start very very far away, akin to facing the Fool. Unfortunately, the further away the Devil starts, the longer the wall is needed to trap the Angel. This does win against an Angel of power 1, but once the Angel has a power of 2 or more, it will always be fast and agile enough to outdo the Devil if it plays perfectly. If the Angel can put off being trapped indefinitely, it wins (by definition). Also to be clear, whilst the board itself is infinite, there are no infinite distances. You can think of the squares of the board as all pairs (a,b) with a,b integers, if that helps. The game is then a sequence of such pairs. - finally, if you feel as though there is a flaw, please first visit the original paper, and remember that this is the work of a professional mathematician whose proof was published, peer reviewed by other mathematicians, and that Conway himself enjoyed seeing this undoubtedly correct and remarkably clever argument! Stay tuned for the next video on something very different but equally fun :)
One small correction: At 10:00 you say "N edges facing north and at the very least 2 edges facing west"; I think you mean "N edges facing east and at the very least 2 edges facing north" respectively here?
If I win with my arm tied behind my back, I can win without my arm tied behind my back. This does not mean if I lose with my arm tied behind my back, I would inherently lose without my arm tied behind my back. Crows being black does not imply all things that are black are crows. This is not to say that the notion of the nice devil loses, the devil loses, mind. Just simply to say that the argument of the inverse is not sufficient as proof alone. Outside of mathematics, perhaps. I suspect that's the source of people's issue.
@@theriveracis5172 you’ve misread. The analogue to ‘if D wins ND wins = if ND loses D loses’ would be ‘if win with arm tied, win without arm tied = if lose without arm tied then lose with arm tied’. This is known as the contrapositive, and is what the proof is using. The (common) misinterpretation is known as denying the antecedent.
@@localmeadows9387 So the confusion is whether or not ND is a disadvantage or an advantage, then, I take it? Perhaps that's what most missed, then. For myself, I don't see the advantage ND has over D, as it just sounded a negative to me.
I spent the entire time thinking “what is he talking about, closing the runner in would be trivial” because I totally forgot the runner could move 2 at a time
Nah, it only needs to be boxed in, so making an open-ended box that has more than three walls on the inside while making corners is all you need, so a 4x4 box, leaving the south-west corner open, and then closing that as soon as the "runner" is inside. Thirteen walls, moves two at a time, meaning you build a box that's 25 squares away from the start
@@CheffBryan they use the rule of the nice devil meaning he cant close a box behind the runner as it is a square previously occupied by the runner, contradicting the ruleset of the nice devil
@@tibodeclerck3331 Doesn't that betray one of our assumptions, though? Before, we were told that if a nice devil can't win against an angel, then a normal devil can't. But it seems like a normal devil can win against this angel, where a nice devil can't.
@@c0i9z my thoughts as well, though i'm not sure if it's just some part of the explanation i missed or misunderstood. The video was very fast with its explanations afterall. I feel that the theory proposed was more to make an exaple that there is a possible winning strategy for the angel, even if not 100% reliable. I may be incorrect however
i think the Monster Group is much more interesting, because it's more than just a definition. The GoL and the Angel Problem are problems that were created, and aren't necessarily something fundamental. but the Monster Group was more-so discovered; it's a necessary consequence of Group Theory and just makes no sense at all but it's there and it's important; you can't have the axioms of group theory without the Monster Group; it represents something fundamental about mathematics in general and symmetry in particular and we just don't know what that is (something about modular forms ??)
Dearest friend, my simplicity could not understand a word past three minutes forty five seconds, but I enjoyed every second of my confusion. This was very fun. You math-people are a special breed.
A simplified version i thought up. If the angel has a power of one, the devil can do the math trick to restrict it's options with the closing wall, capturing it. However, with simply a power of 2, the angel can always outrun the devil that can only burn one tile at a time, simply by heading in the perfect direction, that the devil will not have the resources to account for. No matter what wall it makes, the angel will be past it by the time the trap is set. The nice devil and the runner are simply a mathematical proof to this answer.(showing your work is always the hardest part of math)
@@Ed-1749 And it shows how well mathematics deals in spiritual truths. The power of two is like finding your genius/guardian angel that gives you the power to resist the Red Devil with your green left hand (made sinister by continuous contact with the black mirror/wall/screen = riding the edge, blade running). The runner is key/Chi and is imaged as a key hole, making me think of a door in between. The magnetic north is virtue
What if I introduce a devil that when it moves it burns literally all of the squares on the board, lets call it the "I make up rules as I go along and defeat the intended purpose of the thought experiment" devil.
a 2x2 square has a very unique advantage in that the angel of power 2 can no longer jump over it. a devil of power 2 also has the ability to seal a diagonal in a single move while also extending its territory in a way that the devil p1 could not
An interesting question: does messing with the board geometry affect the result? I.E. Put them on a hex tilemap or a triangular tiling or stop the angel from going diagonally in one move.
Great question! Something I can ponder about. In fact the hexagonal version of this problem reminds me of the coolmath game "Block the Pig". You can check it out if you want to.
Now that I think of it, what if you use a {4,5} tiling (order 5 square tiling)? Will an angel of power one be able to win in this case? For a bit more context, order 5 square tiling is a tiling of the hyperbolic plane with five squares meeting at each vertex.
For a hex version google circle the cat, each turn you burn one square and the cat moves one space, it's not quite the same since it always starts with a random assortment of random burnt squares, which makes sense since I'm pretty sure otherwise it's impossible to catch the cat within the board size.
I’ve been trying to work my brain around these proofs to the Angel Problem for a long time now, so I was kind of surprised to see this show up in my feed all of a sudden because of how niche of a topic it is. Thank you for the video, I think you do a wonderful job visualizing Mathe’s proof in a very insightful way! Look forward to learning more :)
I feel like the "Nice devil vs runner" problem has a much more intuitive solution: Since the runner is moving two squares for every one square the devil burns, even if the devil burns two tiles out form the side of the wall, then the best he will be able to do is to get the runner almost back to the starting line. He can build a "trap" of length N in N+2 moves (2 moves for the 'end', then 1 move for every tile 'captured' in the trap), while the runner can navigate from her starting position, to the 'dead end', and back to her starting position in N moves. Because she's following the wall, though, the last move(s) will take her out of the trap with room to spare. Even if the devil decides to make the gap wider to facilitate filling it with 'teeth' to slow down the runner, the diagonal movement means that it takes only a single move to get around the ends of each 'tooth', and again they begin passing two squares for every one square placed by the devil.
The authors proof is basically a formalisation of what you’re saying, which is what a proof needs to be if you want to publish it and convince the community. Your intuition is the basis of the proof rather than a fundamentally simpler solution. I agree that the video should’ve talked about the intuition before diving in though.
@@serendipitydoctorxqy6122 And that is false. As a CS and math major, these types of intuitive reasonings can compose well over half of a real solution. If you compare the OP's comment and the solution, you can see that they are almost the same, with one just way more formal and thought out than another. No mathematician would come up with a solution like the one in the video in this form. First, you come up with the idea(that the nice devil can't intuitively win against the runner, because intuitively the runner just runs faster than the devil can build), and then you formulate and refine your idea
@@AbradeVenom He didn't say that intuitive answers aren't part of the proving. He's saying that these intuitions are bastardly hard to prove, which is true, since it took years for someone to finally come up with a proof that the angel wins with power of 2. You may be a math major, but you should probably try to properly understand someone's words before going on your own tangent.
I love this video, and others of your channel! But one thing I gotta say: they are very fast-paced, it‘s difficult to follow them with so little pauses in between speaking (for me at least, and I study mathematics). I think this is one thing you need to adress before this channel will experience blow-up as the differential equation people say ;)
Personally I find it strikes a nice balance between being difficult to follow and being boring. If I don't understand I can rewind certain bits without getting bogged down in endless explanations of things I already get.
Not sure how this got recommended to me at 2022 views but I believe the algorithm is being nice on this video. Wishing you well, subbed for more like this.
Since I couldn't see it in comments: The proof you can actually fully trap a one move angel can be reached using the 'fool' angel idea but requires a little extra setup. Initially the devil chooses a sufficiently large square around the angel's starting position that he will use to make the trap, say 100*100 square would be plenty. The devil blocks off all four corners of that square by building an 'L' shaped wall into the large square. For the top left of the trap area he would start say 5 squares below the top corner, build in 5 squares then up 4 squares to get back to the top edge of his 'trap' square. This takes 9 turns for each corner blocked, 36 turns in total. Wherever the angel has gone it is still well inside the 100*100 square we set as the devil's trap at this point. It is now facing a partially constructed trap which has corner walls but a big gap between them in each direction. However the problem now is that whichever gap it moves towards to try and escape the trap we can build a wall along the edge of our 100*100 square to stop it escaping that direction, as demonstrated in the video. Because of the corners we already put in place the angel can't threaten to escape in two directions at once, it has to commit to one gap at a time to go for, if it switches so can the devil, and we can always build a one dimensional wall fast enough to stop the angel escaping in whatever direction it is trying to go.
This is wonderful! I remember seeing a basic explanation of the angel vs devil problem a while ago that *totally* hand waved the actual solution and it was very unsatisfying. It's nice to actually have some closure on the topic.
Oversimplification: In order to trap the angel, the devil can only let the angel move in a circle. But because the angel that moves twice can move around walls so easily, the devil cannot build walls fast enough to trap the angel.
I love this problem, and I love Máthé's proof even though I don't fully understand it. When you said you were talking about this problem, I thought "Please talk about Máthé's proof…!" ❤️
I get that it's a mathematical proof thing, but, I think there's a more intuitive answer to the runner vs the nice devil. Consider if the Nice Devil built the wall backwards. This effectively means the runner and the Nice Devil are now in an infinite race, in which the runner can move a distance of 2 every turn, and the devil can move a distance of 1 every turn. Sure, the devil can go make roadblocks, but to do so is to give the runner more distance on the wall you need to construct
This isn't enough for a proof because in this situation, the nice devil must complete the wall before the runner reaches its base; whereas in the actual situation, the nice devil can still be completing the wall at that time.
@@lzllzzl It's definitely not a proof, but for those who might be confused by the mathematics going on within these calculations, it serves as a good visualization of why the proof makes sense.
That's the intuitive basis of an answer, but does not have the math for a proof. We know it's correct, but mathematicians are finicky and want a very specific and descriptive formula that will always work. This proof is complicated for the sole purpose of proving that the angel could do no better than the runner.
It'd be cool if the logic was put into an neural simulation. I know people can work out the maths, but to see it intelligently play itself out would be neat.
the devil has an infinite number of options, so you would need to prove some spatial bounds on optimal moves. Even then the devil would have billions of options each turn, so searching for the optimal strategy, like in tic-tac-toe or checkers, would be completely intractable.
@@ictogon Well, you wouldn't represent the options linearly, then. You'd use a slow-growing function for relative distance and just limit the AI's search algorithm to cut off before it makes it far enough to be a problem.
@@plasmakitten4261 It still sounds intractable. Consider that to defeat even the "fool" version of the angel of power 2 required placing the wall billions of squares away from the starting location. The full-powered angel or an angel of higher power makes the distances grow astronomically to the point it's intractable to even record which squares the devil has burned on a computer.
The nice devil vs. runner had me confused at first I had to rewatch to the point where the runner started with the preburrned line, this eliminated my first thought of just don't burn any connecting squares. For proving the runner wins Any easier way for me to think about this problem is to work backwards. In this you have the devil trying to start at where the runner did and get in front to block the runner. You instantly see it is impossible as the runner is moving twice as fast. Having the tron rule of the devil not being able to go where the angel has been keeps you from building a trap farther down the line
My tldr is as such; The basic devil can't beat any OPTIMAL angels with power 2 or greater simply due to the fact they'll outspeed any trap that'd ever be made. Any boxes built to enclose would take too long due to the angel being able to take atleast twice as many moves, essentially. If the devil had equal power, the chance to win is MASSIVELY boosted, however that isnt an option
@@ilusions4on an intuitive level I think it’s because that even if the devil starts building his wall infinitely far away, it takes infinitely long to close it, since it’s so damn big, so the angel of power 2 will always manage to find a way past
@@ilusions4its a case of greater infinities - the devil has access to an infinite board, and therefore can construct a path an infinite number of tiles away. BUT, the issue is, the angel has an infinity factor of x2. The devil can only do 'one action' per turn, while the angel has two (two tiles moved for very every one burned.)
The angel would in fact lose every game, and theres nothing it can do to possibly win. Since the devil has infinite movement and the Angel's is limited, the devil can always create a box with the nessecarily thickness and size required to trap the angel. It simply doesnt matter how many more 'turns' the angel gets as opposed to the devil, because on an infinite board there will always be an optimal distance that would allow the Devil to trap the Angel before it could get there.
I really enjoyed this, but I can't wrap my head around the proof explaining the "Nice Devil losing means the Devil loses" thing. Gonna check out the paper to try and figure it out. Thanks for introducing this topic though, I find it very interesting.
The proof explained in the video shows that the devil doesn't have a winning strategy; and combined with the fact this is a closed game, this implies that the angel does have a winning strategy. But is there an explicit algorithm known to compute a winning strategy?
Yes! One of the other papers mentioned, written by O. Kloster, gives an explicit strategy (link in description). It exhibits similarities with the Runner vs ND section. One can also reverse-engineer a strategy from the argument used in Máthé's proof, and in fact the author makes a note of this and writes that it would be non-trivial. I would not be surprised if doing so resulted in something that looked quite a bit like Kloster's strategy.
I think the next question is "for an angel of a given power, how many squares does the devil need to be able to burn each turn in order to keep up" Also at some point in this video I started thinking of it as the coyote-and-roadrunner and it's going to be a struggle to say angel and devil again now
"Why not just build a box really far away?" The devil simply does not have enough time. To make it even clearer, let's restrict the angel to only move in the first quadrant of the grid - as if it started in the bottom-left corner of a chessboard that extended north and east indefinitely. Let's say you start building your wall at a distance R from the starting point. A completed box with length R will have 2 walls of length R that are 2 tiles thick, so this wall will take 4R turns to build. It is very important to notice that this minimum requirement is the same regardless of what R you choose. Because this box has side length R, the angel can follow this strategy to escape: Go north R tiles, then east R tiles, then south R tiles. If you ever find an opportunity to get further than R tiles away from your starting point, take it. Notice that this strategy can walk the entire length of the wall in 3R/2 turns. Because the wall cannot be completed by then, it will ALWAYS find a gap that it can use to escape. (The scenario also works if you use a wall shaped like a quarter-circle. Even if you assume that you don't need extra squares to close off diagonals, this wall is still length pi*R/2 and 2 tiles thick, so would take pi*R turns to build. The angel walks this wall in R(pi+2)/4 turns. (pi+2)/4 is less than half of pi, so still plenty of time.)
Wait , I’m not sure if I understand how the runner can’t be caught. Wouldn’t it be possible for the devil to make a trap for the runner by extending two tiles out of the wall and then moving back toward the runner, and then enclosing the runner when she walks into the area partially enclosed by the trap?
The runner is playing against a nice devil, who can't burn off squares that the runner was on or could have reached earlier. This means that the nice devil can't just enclose the runner because the runner's path is in the way. The argument is that if a runner can win against a nice devil, so can an angel, just by following the runners moves. And if the angle can win against the nice devil, it can also win against a normal devil, as was proved in the earlier part of the video.
@@dani-rybe Yes, but the evil devil can win without any issues against the runner. In fact, the runner ends up being even easier to trap than the fool for the evil devil and only the evil devil. I get that the runner isn't intended to be compared to the evil devil, but something about the proof just isn't sitting right with me.
@@abderianagelast7868 Máthé's proof is not a 'direct' argument, which might be what you feel uneasy about. They show several things: (a) if A wins against the ND, then A wins against D (b) R wins against ND (c) and trivially, A can do whatever R does. Combined, these prove that A wins against D, without ever offering a strategy for A against D.
@@abderianagelast7868 I think something to consider, which may quell your uneasiness, is that you cannot reintroduce the evil devil without also reintroducing the angel, and the angel has exponentially more movement options over the runner than the evil devil has over the nice devil. The runner is handicapped much more heavily than the nice devil is, yet still wins against the nice devil, so the fact that the evil devil can lure the runner into a box doesn't matter, because the angel could sidestep the trap in fewer turns than it takes for the devil to construct it.
With Runner vs Nice Devil, the runner runs into the trap and out again because the Nice Devil can't block him. When you convert this to the real Angel, he takes the "reduced path" which never goes into the trap.
I think that a much simpler way to out this is simply that, because the angel can move more than one space, the devil is always outpaced when only allowed to burn one square at a time
the problem with that thinking is that the devil doesnt technically only burn 1 square, he burns every square the angel could have moved to and didnt. You can think of this as the angel moving to a square in 2 moves it couldve reached in 1 does nothing but give the devil an extra turn, meaning that moving to a space it couldve moved to previously can only hurt the angel.
@@orange_famta3956 the question isn’t whether or not the devil can trap the angel if it just moves back and fourth constantly, the question is if the devil wins or loses even if both have the best/perfect strategies
this about covers why i was confused that other videos stated the devil has a winning strategy i didnt realize it would be as simple as reducing it to a one direction and one half wall to prove it mathematically though
This isn't a proof of the one move strategy here they just show how you might build a wall to block off one direction. It is illustrative of how the one move angel can be controlled but how much more powerful the two move angel is to even try and control in the same way. The proof you can actually fully trap a one move angel can be reached in a similar way but requires a little extra setup. Initially the devil chooses a sufficiently large square around the angel's starting position that he will use to make the trap, say 100*100 square would be plenty. The devil blocks off all four corners of that square by building a wall into the large square. For the top left square he would start say 5 squares below the top corner, build in 5 squares then up 4 squares to get back to the top edge of his 'trap' square. This takes 9 turns for each corner blocked, 36 turns in total. Wherever the angel has gone it is still well inside the 100*100 square we set as the devil's trap at this point. It is now facing a partially complete trap which has corner walls but a big gap between them in each direction. However the problem now is that whichever gap it moves towards to try and escape the 100*100 square we can build a wall along the edge of our 100*100 square to stop it escaping that direction, as demonstrated in the video. Because of the corners we already put in place the angel can't threaten to escape in two directions at once, it has to commit to one gap at a time to go for, and we can always build a one dimensional wall fast enough to stop the angel escaping in whatever direction it is trying to go.
so the angel can always win if it makes a perimeter, because every time the devil puts down 1 square, it's putting down 4 edges, giving the angel >1 spaces to move for every 1 turn the devil plays...? I dunno, that's my best shot.
Just realised the final examples are actually pretty simple. Nice devil is just to prevent trapping the runner in burnt box so the only way for the runner to lose is to loop back to the start. Assuming the left wall is already there, you would need to build the right wall + 2 squares at the top, n+2. Runner has to go the left and right wall + 2 walls to escape, 2n+2. The devil wins in n+2 turns The runner wins in (2n+2)/2 turns = n+1 turns So even if the devil moves first, the runner always wins first.
I'm not sure what I missed in the video, but I missed something that caused me a lot of confusion. So now I'm looking at the paper itself, and it's making more sense, but I still don't get what was causing me issues. I think what's helped me understand it is trying to construct smaller walls such that a runner allowed to move diagonally would be forced to take more turns than the number of tiles it takes to make the walls. This is impossible, assuming you allow the runner to take diagonals. Which is a very fair assumption to make. Being able to visualize it through Tabletop Simulator helps a ton. However, I believe that a devil of power equal to or greater than the power of a given angel can win every time against said angel. EDIT: It occurred to me that a devil with power V against an angel with power P would basically be the same as a devil with power 1 against an angel with power P/V, so basically as long as P/V is less than 2, the devil can win. That's pretty much what was already discovered, so...yeah.
@@tudornaconecinii3609 The original game is that the devil can move anywhere he wants on the infinite chessboard, but can only burn one square per move. He and the Angel take turns one after the other, so if the angel can move at least 2 spaces for every move the Devil makes, the Angel can always come up with a strategy to win. Conversely, if the Angel:Devil ratio is reducible to anything less than 2:1, I'm pretty sure the Devil can always come up with a strategy to win.
@@tudornaconecinii3609 Oh, yeah, that's what I meant! Sorry, I didn't realize that was the question lol. I definitely should have explained that better.
nice devil vs runner is really clear to me when you try to imagine what the devil would have to do to construct a staircase going from north to east. to trap the runner in a giant triangle and force it back to it's starting height. that is to say, the diagonal from satandard x,y coordinate (0,200) and (200,0) 200 space up should be plenty of time to get started on construction vs the runner, right? but for each space you want to go down and to the right, you need to burn out 1 additional square to close off the diagonal. in the 200 turns it takes the runner to get to the top, youre only halfway done with the stairs. and in the 100 turns it takes the runner to get halfway down the stairs to were you were, youve only gotten 50 spaces. the runner is closing the gap
My favorite part of this video is the comments section filled with mathematical geniuses and intellectual giants who apparently dwarf András Máthé but for some reason or other wont publish their findings. Instead they grace us mere mortals by posting their galaxy-brain ideas in the comments section.
@@thomas.thomas It's a mathematical proof about an infinitely large chess board, and an angel and a devil, two mythical creatures, I don't think "squares can't be unburnt" is really an argument
Then every turn the devil would burn a square, which would then see that it has no living neighbors, and then die and become unburnt. The devil would have no way to progress at all.
Okay, for everyone who isn't understanding the half assed math explanation: There is a "mathematical" game/problem of an escaper and a trapper. The question for that problem is ¿Does the trapper always trap? And the short answer is "yes, as long as the trapper has the same level as the escaper, else the runner wins". The whole thing with the nice trapper is there to prove that by backtracking the escaper always wastes moves, so there's no point in covering spaces that may be used for backtracking. Then there's an odd tangent against a runner variant that never explains why that's important: Runner is just a non-backtracking fool that changes directions once it can't move. The way the trapper wins against a runner is by making a bigger wall to the point where runner is going in the time it takes the runner to run across one. This is simple for the trapper to do (you can just simulate it in your head), but once the runner has a higher level it becomes impossible (again, just simulate the same but the wall thickness is doubled and escaper moves twice as fast). And that's it, the whole video is spent to say in a roundabout way that the trapper only wins while in the same level as the runner... Gotta love complicating stuff with math I guess... Oh, and stuff holds even if the runner is constantly using diagonals and decides to change paths prematurely, but it's harder to simulate in the head. If you want to give it a go, you need the devil to 'know' the wall beforehand, and pick the most extreme end that the runner can go to when it changes directions, working from there "inwards" on each step taken to said wall. If there's ever a point where you are lacking walls to trap, you can just move the first one further "back", making the whole perimeter bigger and giving you more time overall.
Imagine a character named Ghost. They appear in a random square every turn. This means that the chance of them existing at any one squere is one in infinity. Do they exist?
Hey man, great video with awesome premice and visuals. However, you lost me precisely at 5:13. The explanation would have benefited from being clearer. Do note, I’m no genius at all, but I’m not an idiot either. You may want to dumb it down for us simpletons next time ;)
The dumb explanation is that the only reason to burn a square is to prevent the angel from moving there, and if the angel wanted to move to that square, then it should have moved there back when it could have. However, this explanation isn't fully rigorous because the angel might have wanted to intentionally visit that square later as an attempt to evade the devil for as long as possible.
I think, essentially if the square that gets burnt was to going to become part of the path later on then it would have to be part of the reduced path (as it is within 2 spaces of a lower number). But it isn't part of the reduced path since that would cause the square the angel is currently on to not be part of the reduced path (as the burnt square is closer to a square with a lower number). But we've assumed the angel is travelling on the reduced path. This contradiction means that the devil will never burn a square in the earlier region.
What if the devil could step on a cell the runner has stepped on. He could simply make a wall millions of cells away and close it to a box with a 1x1 cell entrance while the runner comes. As she has to touch a wall, and there's already a big one she has to follow, whenever she gets to the wall, the devil could simply close the box and trap her.
At that point the angel is disappointed in you for not having perfect game theory, so he stops acting as the runner and avoids the trap. Congratulations, you had the disadvantage if you played a perfect game and now you've deviated from the perfect moves. But that's not the point, the runner and the nice devil are just ideal instructions where both play perfectly. And whoever wins the perfect game wins the regular game with stratagems and gambits, because while the devil can trick the runner, it can't trick the angel. Basically devil=nice devil
I found this problem and proof very interesting. I found your explanation of the proof Fully frustratingly terrible. You did not bring me on the journey of understanding how and why the optimal strategy is optimal. you only communicated to me some of what the optimal strategy was. and as this is not a real game that real people play, that information is more than useless. and not what I want from a video like this. Its taken me 20 minutes to get to this level of articulation of how this video made me feel. I guess i've been fortunate to never have had a bad teacher for something I care about, as I imagine that is what I'm feeling now.
Essentially, the nice devil needs to make a wall a certain distance away and loop back to the start. The runner can run twice that length in that amount of time. The exact moment the nice devil is about to finish the loop, the runner has made it to the end and back since they moved twice as fast as the devil. 2 trips for the angel = 1 trip for the devil. The devil will always lose.
I feel like something is off with the proof the angel can win... If the devil does the same strategy to block off the fool, but acts as if the angel has 4 times more power, it can alternate building walls on each side and trap the angel, why would a version of the angel with less movement be able to escape that?
This is a good thought! Something along the lines of "if A heads North at any point in time, continue building a North barrier, if A heads West at any point in time, continue building a West barrier" and so on. If so, this does indeed lose against the Devil if you require the Angel to increase its distance from the origin at every step, and in fact this is one of the other tempting "false strategies" addressed by Conway in his paper. However, without that promise from the Angel, the Devil loses a 'reference point' around which to build the barriers, and the Angel can essentially meander enough that it is perpetually free of being completely stuck.
Because that strategy specifically depends on the angel being a Fool. The Runner is not limited in its direction, and the way it plays out, it just runs faster than the Devil can place walls to block it in.
@@inconspicuoususername The strategy about building the wall to block in the angel doesn't rely on her being the fool. Specifically, the wall is built as if her power was 4 times larger, giving the devil time to construct 4 walls completely blocking off the angel's movement in every direction. If that strategy is able to block off the angel who can move to any square she want's, why would it not work on the runner, who's movement option is even more restricted? The 4 walls strategy gets around relying on the angel being the fool because it builds the wall in each of the 4 directions, any path the angel takes would move it closer to one of the four walls, which for that specific wall would have it's own half steps. No matter which direction the angel moves, a wall is being built to block off the path entirely. With no way out, the angel becomes restricted to a finite playing field in which case the devil will always win.
@@localmeadows9387 It's not that the devil builds the wall based on which direction the angel moves. The devil builds the walls regardless of which direction the angel moves. If the angel has power N then the devil builds the wall thick enough to block N but at a distance required to build the 4N sized wall. That means the devil has 4 times longer to build the wall, so with that extra time he builds 4 walls instead of 1. Every turn he alternates between walls. North, East, South, West, in that order. The only time he cares about the angel's move is when she reaches the half step towards a ny wall. in which case he shortens that wall to fill in the gaps he left whenever it's the right turn to build it. The wall is always far enough away because the devil acts as if the angel had more power than she really did, building the walls as if the angel were a fool 4 times stronger, but instead of building just a single wall, he builds a square around the angel to prevent movement in any direction (because the angel is not the fool). But because the distance the wall was built was extremely conservative, the angel won't reach any of the walls in time to get past them before they are built. And if the angel isn't strictly increasing in distance away from the origin, she's giving the devil more moves to build the walls. Taking 2 turns to reach a space she could've gotten to in 1 turn doesn't change anything except the number of spaces the devil has removed.
@@anthonycannet1305 in which case the answer is simply: the devil will never have enough time to trap her. The further away the devil builds, the more squares need to be burnt to create a loop of sufficient width. You will see that this is the case if you try to formalise your idea! :)
I don't really get the thing at 5:12 isn't that just an example of a way the normal devil is actually different to the Nice devil? why's it invalidate the other path
If the evil devil had already been there, then the angel couldn't have gone there later. When we were talking about how the nice devil picks its route, we picked in order going backwards and then made the nice devil take shortcuts. The angel can't go to a square that the evil devil burned. So if the evil devil had been there, then the angel couldn't have been, and so the nice devil wouldn't have decided its route in that way. This doesn't mean the nice devil and the evil devil are different, it means that the particular scenario where they would end up being different can't happen. If the evil devil would have gone there without the nice devil, then it would have burned the square before the angel ever got there, meaning the angel would have to go somewhere other than where it did, which is false. So the evil devil has to be nice. All of the evil devil's winning strategies, if it even has any, are proven to be nice. That means we can just use the nice devil from the start, which makes the problem easier to solve because the nice devil acts in a very specific way we know about, instead of possibly being able to flutter around the entire board like a jackass with no rhyme or reason and no way for us to know if his plan is working or not. Since he has to be nice, and act in nice ways, to even have a chance of winning, it's much much easier for us to know if his plan is working.
@@williambarnes5023 I'm not sure that explained it. The situation we're given is effectively taking a game played between the angel and the nice devil, then looking to see if there are moves that are optimal for the normal devil that the nice devil couldn't have made. Supposedly this will never happen because of the path reduction thing (the "work backwards from end tile" method), but there's no explanation as to why those two things are related. Or even why the path reduction is important at all.
@@Graknorke A better way to explain it that the angel if playing perfectly would never want to go to a square that it could have gone to before, and with this knowledge the devil also won't ever suggest a move that the angel could have gone to before and therefore the nice devil and the devil would play the same against the angel.
I remember being introduced to this "game" via Destiny 2. The traveler is the angel and the pyramids are the devil. Currently, the traveler has stopped due to damage from Rasputin, so perhaps we're doomed.
I am entirely confused by everything from 6:00 onward. Does this runner somehow relate to the angel and devil problem or is it an entirely different thing? Then when it comes to actually solving this problem, I can not follow the logic. Why're we using an intentionally large amount of burnt squares? Why're they already built before the runner even starts? Why isn't the good runner devil always moving? Why're we using a movement by the runner that doesn't follow the game's rules to prove a contradiction? Why does that contradiction mean the runner can never reach that line? The speed of the presentation I can deal with by slowing down and pausing, that's easy. I feel like there're a ton of logical leaps that're not explained, though, especially in the particulars of the math.
Imagine you were playing as the Devil and your opponent said "I'm going to use the Runner instead of the Angel, and also I'm going to start with the left half of the board burnt --- and I'm still going to win." You have no reason to object to this --- it doesn't limit your choices, only theirs. They're saying they can beat you with one hand tied behind their back --- and they do, so you know they could have done it using both hands too.
@@unwono The devil would need to take two turns for every one unit of perimeter around such a square. The angel only needs to travel half the length of one side, and can move two units per turn. It doesn't matter how big of a square you try to make, the devil will never have the time to finish any more than a quarter of it.
@@Endominateur remember , he proved that since the runner wins against the nice devil, the angel wins against the nice devil (since the angel is a better runner) But if the nice devil loses against the Angel , then the devil does (since if the devil wins , then the nice devil HAS to win ) so therefore angel wins against devil
It seems like if the runner loops around an island, she loses for reasons that have nothing to do with the original problem. Also, if she offers the Nice Devil half the squares, the Nice Devil could just start building a trap 1,000 squares out, and the regular Devil could just close the loop. In that scenario, the Nice Devil's inability to trap the runner has nothing to do with the nature of the problem, and everything to do with the weird, self-imposed "no burning squares the runner has been on" rule.
The thing is - against the Angel, the ND is not weaker than the Devil. The Angel has no reason to ever return to a previously available square - in optimal strategy it would've gone to that square the first chance it got and thus on a board with less total burnt squares. So there is effectively no difference between Devil and ND for the ANGEL. It's also proved as you concede that a strictly inferior Angel, the Runner, will always beat the ND. Because a crippled Angel can always beat the ND, an un-crippled Angel can always beat the ND, and because for the ANGEL the ND and the Devil are the same, the Angel can always beat the Devil.
I just realized something that makes this problem a bit melancholy: The Devil's work is done when it wins. It can stop once it's trapped the Angel. But the Angel's work is only done when it loses. If the Devil can't win, the Angel has to keep running forever.
One interesting tidbit: given an angel which always moves randomly, the devil can always win. Whilst the angel busies itself moving about, the devil will construct spaces which are sealed in all but one spot. Whenever the angel enters such a space, the devil can simply seal off the cube or circle or whatever and therefore contain the angel within a finite, exhaustible space. Given an infinite span of time and the nonzero chance of the angel blundering in this way, the devil will eventually win. The proof would go something like this: If the devil always starts building its cube right where the angel is, the angel will never be farther than [the number of steps it takes to build a box with one entrance that can contain the angel] * [the number of squares the angel can move per step] * 2 (because a worst-case scenario sees the angel moving in a straight line away, and half-finished boxes do not count). This allows us to calculate the probability of the angel making it into the box before the devil builds the next one, from every possible square it could be in, which gives us a minimum to work from. Having a nonzero but hard minimum means that as the amount of time spent approaches infinity, the probability of the angel being boxed in at some point approaches 1. Obviously, this only works because we assume that the angel is moving randomly. If its movements are not random but are instead designed then, however stupid its movements are, the proof falls apart because we cannot guarantee a nonzero probability of the angel entering the box.
I imagine, though I'd love to see a proof of it, that to win against an angel, the devil would need to burn squares each turn equal to her power. Since they're only burning one square, the runner can always sneak by, but two would match them evenly.
I'm no mathematician, but I know that to disprove something you only need one example that contradicts it, so here's my example contradiction in the assumption that if the devil wins, the nice devil wins also: Suppose the angel behaves like the aforementioned runner and the devil realises it (*). The devil decides to prepare a trap for the angel, somewhere far enough away in the direction of the angel's movement, as to be able to complete the trap. Since the angel behaves like a runner and the board is infinite, the devil can always go far enough to prepare the trap, no matter the angel's power. The devil creates a box with walls wide enough to prohibit the angel from jumping over them, leaving only one opening for the angel to get through. The devil waits, and once the angel gets in the box, the devil swiftly closes it off. I think it's pretty clear that this is a winning strategy for dealing with a runner-type angel of any power, yet the nice devil could never use it, since he cannot close the box off, the angel had to be able to go through it after all. What I think this proves is that whereas the nice devil cannot beat the runner, as proved in the video, the normal devil can, regardless of the runner's power, which in turn contradicts the assumption that if the devil wins, the nice devil wins also. Please do tell me where I went wrong with my reasoning! I am pretty certain that whoever wrote the paper thought about it more than me, so I am inclined to believe they got it right. What I marked by (*) seems like a pretty big assumption to me, but aside from that I'm not really able to find where I erred.
You are right, the asterisk is where you are going wrong. :) When we say “the angel wins”, this is shorthand for “the angel has a winning strategy”. It is actually, non-ideal terminology. You can picture a winning strategy for one of the players as being a very large book, where chapter N refers to the Nth turn of that player. Inside that chapter is a list of instructions that look like: “if the other player has made the sequence of moves X_1, X_2, … X _N, move to square Y”. This chapter will contain every possible sequence the other player could have made till the Nth game, so our player is always able to find an instruction. This book is called a winning strategy if it is such that, at each turn, if our player looks into the book for which move to play, and follows the instructions very diligently, they will win the game. In the case of the angel, this book allows the angel never to get caught, no matter what the devil does. This is why the question of “if the angel doesn’t obey the strategy” falls outside the problem being dealt with. Indeed otherwise we could suppose the angel is even sillier, and just alternates between the same two squares for the entire game. Surely then the devil could capture it! But the point is, if there exists a winning strategy, it will not contain any sequence of instructions that will lead to the angel being captured. Finally, to be clear, Máthé’s proof does not offer a winning strategy explicitly. It uses lots of clever detours to prove that this book exists.
I sorta understand where this is coming from but, in an infinite setting, wouldn't there be a point so far that the Level 2 Angel could never reach in convenient time to not be boxed in by the devil? And after he was boxed in wouldn't it be enough for the devil to just do a second lap around this structure as to not let the angel move past the burnt squares?
It was a little rough to understand in the video, but the creator's pinned comment goes over it a little better. Basically, yes that will work against any power 1 angel (it can move 1). However, any angel with a higher power than 1 will always win. Why is that? Because when a devil starts out a thousand blocks, the devil must now build a wall that is big enough to block an angel that could move two thousand blocks in the time it takes the devil to build a thousand blocks. The problem get worse for devils with higher powered angels, because even starting out an infinite amount, the angel will get that infinite amount times its power. That's why the first strategy shown to win as the devil only works on power 1 angels. It really just boils down to action economy, 2 is always bigger than 1. Hence angels past power 1 will always win (assuming both side play it perfectly).
@@Comfyest This video says no, that does not exist. There's a special calculus formula to answer where that optimized sweetspot in this scenario, and when you plug in 2 for the angel, there will be no real answer.
God I looked away for 2 minutes and come back to some complete insanity mathematics 😂 great video though after watching all the way through everything was explained perfectly!
a lot of people in the comments are very confused, as am I, but I think I've made the second proof make sense in more layman's terms. tl;dr: the work needed for the devil to trap the angel inside a massive box made out of burnt squares will always be much higher than the work needed for the angel to get outside of that box. the angle can always escape an attempt at being boxed in, no matter how far away the box starts, because the devil will never have enough time to complete the box before the angel can potentially escape it, so the devil will never have any time to contain the angel in any circumstance - there are several people saying that the mean devil can win by building an infinitely-far away box that can contain the angel before it reaches any edge. what those people don't realize is that THIS IS WHAT IS being attempted in the second scenario, with the runner and the nice devil. See, the nice devil isn't actually nice: it's forward-thinking. it doesn't want to eliminate a bunch of squares just to be courteous. Rather, it wants to create a wall of burnt squares that the angel never, ever could have broken through, no matter what additional moves were taken. That's how you build a consistent winning strategy, by accounting for deviations. the runner starts out exactly the same as the fool, just running as fast as possible in one direction. The nice devil does its best to build a wall that will be able to contain it regardless of what moves it may take. However, the amount of work that the angel has to do to survive is drastically less than the amount of work the devil has to do to win, and they both have the exact same amount of moves to do it. Let's say i'm a devil, and i'm dealing with an angel with a power of one. if i try to build a wall five blocks out from the angel in every direction, i have to make 40 moves to complete the box on all sides. however, it will only take the angel five moves to get to that edge, which won't give me enough time to fill in the box. so, i change the strategy and push the wall one block further, so the wall now surrounds the angel from 6 blocks away. however, this only adds one extra move needed for the angel to reach that edge, whereas i now need to fill in 48 squares instead of 40. The farther you go, the additional work for the devil is exponential, whereas the work for the angel is simple, just one additional move. so, you could not build an infinitely far wall that gives you enough time to complete the square wall around the start, since the work necessary would be exponentially larger than the work for the angel to reach any potential edge, even with just a power of one. By using the second example, where the runner knocks out half the board to begin and sticks to a firmly predictable strategy, still neither the nice or the mean devil would be able to build a wall to contain the runner at any distance. If the angel still wins, even with those handicaps, it can't lose in any scenario
Thank you, I was having trouble trying to figure out wtf the nice devil or the runner had to do with the first problem at all and this explanation makes sense.
So this makes sense exept for the statement that if the nice devil loses the normal devil loses. For instance the runner will lose to the normal devil no matter what by the devil creating a box to trap them. This same thing will occur when an angel can move however many squares the devil needs to go out an insane distance and create a barrier of 2 thickness or whatever the jump distance of the angel is and he will win every time
It's more "if there's a way to win against the nice devil there's also a way to win against the normal devil", meaning it might not be the exact same, but there's a way to turn a winning strategy for one into a winning strategy for the other.
The “good devil” is the devil playing optimally against the angel. The runner is a weakened angel. Evil devil > runner > good devil But Angel > runner > good devil (> evil devil only for angel) For angel: good devil > evil devil For runner: evil devil > good devil
This is an amazing video! That said, would have been nice to have a few seconds of respite between ideas, had to watch some parts thrice or so before getting them.
As a layman, I see the answer as follows. The devil can only block one square per turn. The angel of power >=2 can access more than that one removed square per turn, and therefore will always be able to out-maneuver the devil.
i know this might well be impossible (or even addressed in the paper, i am also not a mathematician), but i wonder about a variation of this game: imagine that for every turn the angel makes, the devil gets to burn a number of squares, n. for an angel of power x, it has (2x+1)² - 1 different squares it can go the next turn, before considering burnt squares, so it is self-evident that a devil that performs at least that many burns (8 for power 1, 24 for power 2 etc) per turn has an instant win available to it. what im wondering though, is whether one can construct a way to prove the *minimum* n for the devil to beat an angel of power x! im gonna think on it. thanks for the video!
My first intuition would be that a devil would only need as many squares n as the angle has power x (n+x). Because then it seems like the angle of power 1 scenario.
![The Angel Problem [Game Theory]](http://i.ytimg.com/vi/sxiKlOK3EJY/mqdefault.jpg)
Hello! Thanks for watching this video. Since there seems to be some amount of disagreement in the comments, I thought I’d try to briefly clear up some of the common ones!
- the extra characters the author introduces are a creative way of talking about certain tweaks one can make on the initial problem without actually affecting the end goal. This is very common in mathematics: in order to prove something, sometimes it is sufficient to prove something else, and that something else might be easier to argue!
- some people are not happy with the Nice Devil losing implying the real Devil loses. It is first important to realise that this is completely equivalent to the real Devil winning implying the Nice Devil winning (which it seems people were more okay with); indeed if this were true, the Nice Devil cannot possibly lose should the Devil win. Note also that this part of the proof is set up against the Angel in its full form; what might happen between the Runner and the original Devil is never a part of it. Whilst it might feel as though the Devil should be ‘stronger’ against the Angel, the first part of this proof is precisely arguing that this notion of ‘strength’ is not useful in this particular game, because the Devil’s extra moves are essentially wasted (hence the notion of a reduced path). Perhaps a better name for the Nice Devil is the Smart Devil: fewer unnecessary moves, assuming the Devil had a good strategy in the first place.
- there is confusion around the 5:12 mark for two understandable reasons I think: one is that I went through it very fast (I will avoid this in future videos), the other is that proofs by contradiction can turn out to be more confusing visually in cases like these than they are in written form, as they require displaying something that ‘can’t have happened’ (in particular, the new reduced path seemingly appearing out of nowhere). If you were lost at this point I would urge you to check out the original paper which is linked in the description!
- several people are suggesting the Devil should simply start very very far away, akin to facing the Fool. Unfortunately, the further away the Devil starts, the longer the wall is needed to trap the Angel. This does win against an Angel of power 1, but once the Angel has a power of 2 or more, it will always be fast and agile enough to outdo the Devil if it plays perfectly. If the Angel can put off being trapped indefinitely, it wins (by definition). Also to be clear, whilst the board itself is infinite, there are no infinite distances. You can think of the squares of the board as all pairs (a,b) with a,b integers, if that helps. The game is then a sequence of such pairs.
- finally, if you feel as though there is a flaw, please first visit the original paper, and remember that this is the work of a professional mathematician whose proof was published, peer reviewed by other mathematicians, and that Conway himself enjoyed seeing this undoubtedly correct and remarkably clever argument!
Stay tuned for the next video on something very different but equally fun :)
One small correction: At 10:00 you say "N edges facing north and at the very least 2 edges facing west"; I think you mean "N edges facing east and at the very least 2 edges facing north" respectively here?
@@edderiofer excellent catch, you are absolutely right! Will add that to the description. Thank you!
If I win with my arm tied behind my back, I can win without my arm tied behind my back.
This does not mean if I lose with my arm tied behind my back, I would inherently lose without my arm tied behind my back.
Crows being black does not imply all things that are black are crows.
This is not to say that the notion of the nice devil loses, the devil loses, mind.
Just simply to say that the argument of the inverse is not sufficient as proof alone. Outside of mathematics, perhaps.
I suspect that's the source of people's issue.
@@theriveracis5172 you’ve misread. The analogue to ‘if D wins ND wins = if ND loses D loses’ would be ‘if win with arm tied, win without arm tied = if lose without arm tied then lose with arm tied’. This is known as the contrapositive, and is what the proof is using. The (common) misinterpretation is known as denying the antecedent.
@@localmeadows9387
So the confusion is whether or not ND is a disadvantage or an advantage, then, I take it?
Perhaps that's what most missed, then. For myself, I don't see the advantage ND has over D, as it just sounded a negative to me.
This is the best example of 'creating a problem just so you can solve it' I've ever seen
Don't ya just love it?
Sometimes we create tools that we cant use yet
@@deadbeef576 lasers were invented before we had a plan as a species on what to use them for.
Lasers were famously called "a solution looking for a problem" when they were invented and now they're one of the most important technology we have.
I agree. To me this feels very pointless. Like, what is the point of creating a nice devil here?
I spent the entire time thinking “what is he talking about, closing the runner in would be trivial” because I totally forgot the runner could move 2 at a time
Nah, it only needs to be boxed in, so making an open-ended box that has more than three walls on the inside while making corners is all you need, so a 4x4 box, leaving the south-west corner open, and then closing that as soon as the "runner" is inside. Thirteen walls, moves two at a time, meaning you build a box that's 25 squares away from the start
@@CheffBryan they use the rule of the nice devil meaning he cant close a box behind the runner as it is a square previously occupied by the runner, contradicting the ruleset of the nice devil
@@tibodeclerck3331 Doesn't that betray one of our assumptions, though? Before, we were told that if a nice devil can't win against an angel, then a normal devil can't. But it seems like a normal devil can win against this angel, where a nice devil can't.
@@c0i9z my thoughts as well, though i'm not sure if it's just some part of the explanation i missed or misunderstood. The video was very fast with its explanations afterall. I feel that the theory proposed was more to make an exaple that there is a possible winning strategy for the angel, even if not 100% reliable. I may be incorrect however
@@c0i9z The normal devil beats the runner. But the normal cannot beat the power of 2. The proof was the contest between the nice and runner.
Conway was known for defining very complicated things with simple rules. The Game of Life, the Angel problem, and the Monster group.
i think the Monster Group is much more interesting, because it's more than just a definition. The GoL and the Angel Problem are problems that were created, and aren't necessarily something fundamental. but the Monster Group was more-so discovered; it's a necessary consequence of Group Theory and just makes no sense at all but it's there and it's important; you can't have the axioms of group theory without the Monster Group; it represents something fundamental about mathematics in general and symmetry in particular and we just don't know what that is (something about modular forms ??)
RIP 😭
Dearest friend, my simplicity could not understand a word past three minutes forty five seconds, but I enjoyed every second of my confusion. This was very fun. You math-people are a special breed.
A simplified version i thought up. If the angel has a power of one, the devil can do the math trick to restrict it's options with the closing wall, capturing it. However, with simply a power of 2, the angel can always outrun the devil that can only burn one tile at a time, simply by heading in the perfect direction, that the devil will not have the resources to account for. No matter what wall it makes, the angel will be past it by the time the trap is set. The nice devil and the runner are simply a mathematical proof to this answer.(showing your work is always the hardest part of math)
@@Ed-1749 And it shows how well mathematics deals in spiritual truths. The power of two is like finding your genius/guardian angel that gives you the power to resist the Red Devil with your green left hand (made sinister by continuous contact with the black mirror/wall/screen = riding the edge, blade running). The runner is key/Chi and is imaged as a key hole, making me think of a door in between. The magnetic north is virtue
what delightful insight we share bossman
@@mongolianqwerty123 What in the flying fuck?
This doesn't have anything to do with the proof but I like aesthetically how the burnt squares during the contradiction form a scythe
What if I introduce a devil that when it moves it burns literally all of the squares on the board, lets call it the "I make up rules as I go along and defeat the intended purpose of the thought experiment" devil.
It wins in three moves.
The devil's advocate
aka "The screw you devil"
Lmao
the "just get this bloody thing over with" devil
Wow, this was a nice video!
woah, carykh, hi
the mathemagic man himself
Fancy seeing the programming ai guy watching abstract math videos! Hi!
exquisite
Hi Cary
What if you introduced a demon with the power of two? I.e. it burns a 2x2 square instead of just 1 square
This is a great question! Will think about it.
I think a devil like that closes the Runner's Loophole.
These types of alterations typically just increase or decrease the scale of the algorithm to catch the angel.
But if it’s an angel of power 2 I think you can reduce this to the 1-angel case, and the 1-angel can’t win.
a 2x2 square has a very unique advantage in that the angel of power 2 can no longer jump over it. a devil of power 2 also has the ability to seal a diagonal in a single move while also extending its territory in a way that the devil p1 could not
An interesting question: does messing with the board geometry affect the result? I.E. Put them on a hex tilemap or a triangular tiling or stop the angel from going diagonally in one move.
Great question! Something I can ponder about. In fact the hexagonal version of this problem reminds me of the coolmath game "Block the Pig". You can check it out if you want to.
Now that I think of it, what if you use a {4,5} tiling (order 5 square tiling)? Will an angel of power one be able to win in this case? For a bit more context, order 5 square tiling is a tiling of the hyperbolic plane with five squares meeting at each vertex.
For a hex version google circle the cat, each turn you burn one square and the cat moves one space, it's not quite the same since it always starts with a random assortment of random burnt squares, which makes sense since I'm pretty sure otherwise it's impossible to catch the cat within the board size.
Nvm me, i misread some things.
My guess is that Mathe's proof should work on an octagonal board for power greater than or equal to 4 but I haven't worked it through to check!
I’ve been trying to work my brain around these proofs to the Angel Problem for a long time now, so I was kind of surprised to see this show up in my feed all of a sudden because of how niche of a topic it is. Thank you for the video, I think you do a wonderful job visualizing Mathe’s proof in a very insightful way! Look forward to learning more :)
I feel like the "Nice devil vs runner" problem has a much more intuitive solution: Since the runner is moving two squares for every one square the devil burns, even if the devil burns two tiles out form the side of the wall, then the best he will be able to do is to get the runner almost back to the starting line. He can build a "trap" of length N in N+2 moves (2 moves for the 'end', then 1 move for every tile 'captured' in the trap), while the runner can navigate from her starting position, to the 'dead end', and back to her starting position in N moves. Because she's following the wall, though, the last move(s) will take her out of the trap with room to spare.
Even if the devil decides to make the gap wider to facilitate filling it with 'teeth' to slow down the runner, the diagonal movement means that it takes only a single move to get around the ends of each 'tooth', and again they begin passing two squares for every one square placed by the devil.
The interesting thing about math like this is that intuitive solutions are often difficult or impossible to prove.
I agree. I'd bet that this is exactly the intuition that led Mathe into investigating the runner vs nice devil and discovering this proof.
The authors proof is basically a formalisation of what you’re saying, which is what a proof needs to be if you want to publish it and convince the community. Your intuition is the basis of the proof rather than a fundamentally simpler solution. I agree that the video should’ve talked about the intuition before diving in though.
@@serendipitydoctorxqy6122 And that is false.
As a CS and math major, these types of intuitive reasonings can compose well over half of a real solution. If you compare the OP's comment and the solution, you can see that they are almost the same, with one just way more formal and thought out than another.
No mathematician would come up with a solution like the one in the video in this form. First, you come up with the idea(that the nice devil can't intuitively win against the runner, because intuitively the runner just runs faster than the devil can build), and then you formulate and refine your idea
@@AbradeVenom He didn't say that intuitive answers aren't part of the proving. He's saying that these intuitions are bastardly hard to prove, which is true, since it took years for someone to finally come up with a proof that the angel wins with power of 2. You may be a math major, but you should probably try to properly understand someone's words before going on your own tangent.
I love this video, and others of your channel! But one thing I gotta say: they are very fast-paced, it‘s difficult to follow them with so little pauses in between speaking (for me at least, and I study mathematics). I think this is one thing you need to adress before this channel will experience blow-up as the differential equation people say ;)
Thank you so much! You are not the first to comment on the pace so I will be sure to allow more space in between scenes/sentences in next videos. :)
Personally I find it strikes a nice balance between being difficult to follow and being boring. If I don't understand I can rewind certain bits without getting bogged down in endless explanations of things I already get.
I agree. I’m still not clear why there couldn’t be some arbitrary distance that could work. Not that he didn’t say, I just didn’t pick up on it.
yeah I really got lost when it started explaining the contradiction with the inequalities of s
I second this. For example, the nice devil = devil and runner = angel proof parts went to fast for me to understand why those are true.
Not sure how this got recommended to me at 2022 views but I believe the algorithm is being nice on this video. Wishing you well, subbed for more like this.
128k now
That proof is smart! I almost thought I had devised a method of trapping the runner, but I realized upon further examination that it was faulty.
You forgot to tell me to hold on to my papers, I will never recover from this
This is like math problems that I think of a simple answer for but the real answer is the most complicated thing I've seen in my life
Since I couldn't see it in comments:
The proof you can actually fully trap a one move angel can be reached using the 'fool' angel idea but requires a little extra setup. Initially the devil chooses a sufficiently large square around the angel's starting position that he will use to make the trap, say 100*100 square would be plenty. The devil blocks off all four corners of that square by building an 'L' shaped wall into the large square. For the top left of the trap area he would start say 5 squares below the top corner, build in 5 squares then up 4 squares to get back to the top edge of his 'trap' square. This takes 9 turns for each corner blocked, 36 turns in total. Wherever the angel has gone it is still well inside the 100*100 square we set as the devil's trap at this point. It is now facing a partially constructed trap which has corner walls but a big gap between them in each direction.
However the problem now is that whichever gap it moves towards to try and escape the trap we can build a wall along the edge of our 100*100 square to stop it escaping that direction, as demonstrated in the video. Because of the corners we already put in place the angel can't threaten to escape in two directions at once, it has to commit to one gap at a time to go for, if it switches so can the devil, and we can always build a one dimensional wall fast enough to stop the angel escaping in whatever direction it is trying to go.
This is wonderful! I remember seeing a basic explanation of the angel vs devil problem a while ago that *totally* hand waved the actual solution and it was very unsatisfying. It's nice to actually have some closure on the topic.
ua-cam.com/video/sxiKlOK3EJY/v-deo.html
perhaps you were talking about this one from CodeParade
@@MeanSoybean yeah that's definitely the one. 😬
Oversimplification: In order to trap the angel, the devil can only let the angel move in a circle. But because the angel that moves twice can move around walls so easily, the devil cannot build walls fast enough to trap the angel.
I really enjoyed this video. I can only imagine how cool it would be if I understood at all what was going on.
I love this problem, and I love Máthé's proof even though I don't fully understand it. When you said you were talking about this problem, I thought "Please talk about Máthé's proof…!" ❤️
I get that it's a mathematical proof thing, but, I think there's a more intuitive answer to the runner vs the nice devil. Consider if the Nice Devil built the wall backwards. This effectively means the runner and the Nice Devil are now in an infinite race, in which the runner can move a distance of 2 every turn, and the devil can move a distance of 1 every turn. Sure, the devil can go make roadblocks, but to do so is to give the runner more distance on the wall you need to construct
Yeah this makes a lot more sense to me.
This isn't enough for a proof because in this situation, the nice devil must complete the wall before the runner reaches its base; whereas in the actual situation, the nice devil can still be completing the wall at that time.
@@lzllzzl It's definitely not a proof, but for those who might be confused by the mathematics going on within these calculations, it serves as a good visualization of why the proof makes sense.
That's the intuitive basis of an answer, but does not have the math for a proof. We know it's correct, but mathematicians are finicky and want a very specific and descriptive formula that will always work. This proof is complicated for the sole purpose of proving that the angel could do no better than the runner.
It'd be cool if the logic was put into an neural simulation. I know people can work out the maths, but to see it intelligently play itself out would be neat.
I think the solutions would just be too big ever to leave the paper past power of 2
the devil has an infinite number of options, so you would need to prove some spatial bounds on optimal moves. Even then the devil would have billions of options each turn, so searching for the optimal strategy, like in tic-tac-toe or checkers, would be completely intractable.
yeah but i think the mathematical approach has more merit considering we are dealing with infinite time and space
@@ictogon Well, you wouldn't represent the options linearly, then. You'd use a slow-growing function for relative distance and just limit the AI's search algorithm to cut off before it makes it far enough to be a problem.
@@plasmakitten4261 It still sounds intractable. Consider that to defeat even the "fool" version of the angel of power 2 required placing the wall billions of squares away from the starting location. The full-powered angel or an angel of higher power makes the distances grow astronomically to the point it's intractable to even record which squares the devil has burned on a computer.
I can't believe you don't have more subscribers. Great video!
The nice devil vs. runner had me confused at first I had to rewatch to the point where the runner started with the preburrned line, this eliminated my first thought of just don't burn any connecting squares. For proving the runner wins Any easier way for me to think about this problem is to work backwards. In this you have the devil trying to start at where the runner did and get in front to block the runner. You instantly see it is impossible as the runner is moving twice as fast.
Having the tron rule of the devil not being able to go where the angel has been keeps you from building a trap farther down the line
The graphics in this video are lovely!
Pretty sure I didn’t learn anything but I was mildly entertained so good job
My brain is on fire with how much math I ingested in such a short amount of time. which of course we represent here as "t".
My tldr is as such;
The basic devil can't beat any OPTIMAL angels with power 2 or greater simply due to the fact they'll outspeed any trap that'd ever be made. Any boxes built to enclose would take too long due to the angel being able to take atleast twice as many moves, essentially. If the devil had equal power, the chance to win is MASSIVELY boosted, however that isnt an option
the devil already has infinite power in this case, since it can move any number of squares
@@ilusions4on an intuitive level I think it’s because that even if the devil starts building his wall infinitely far away, it takes infinitely long to close it, since it’s so damn big, so the angel of power 2 will always manage to find a way past
@@ilusions4 because the angel of power 2 essentially has twice as many turns as the devil, since he can only burn 1 square at a time
@@ilusions4its a case of greater infinities - the devil has access to an infinite board, and therefore can construct a path an infinite number of tiles away. BUT, the issue is, the angel has an infinity factor of x2. The devil can only do 'one action' per turn, while the angel has two (two tiles moved for very every one burned.)
The angel would in fact lose every game, and theres nothing it can do to possibly win.
Since the devil has infinite movement and the Angel's is limited, the devil can always create a box with the nessecarily thickness and size required to trap the angel. It simply doesnt matter how many more 'turns' the angel gets as opposed to the devil, because on an infinite board there will always be an optimal distance that would allow the Devil to trap the Angel before it could get there.
I really enjoyed this, but I can't wrap my head around the proof explaining the "Nice Devil losing means the Devil loses" thing. Gonna check out the paper to try and figure it out. Thanks for introducing this topic though, I find it very interesting.
The proof explained in the video shows that the devil doesn't have a winning strategy; and combined with the fact this is a closed game, this implies that the angel does have a winning strategy. But is there an explicit algorithm known to compute a winning strategy?
Yes! One of the other papers mentioned, written by O. Kloster, gives an explicit strategy (link in description). It exhibits similarities with the Runner vs ND section. One can also reverse-engineer a strategy from the argument used in Máthé's proof, and in fact the author makes a note of this and writes that it would be non-trivial. I would not be surprised if doing so resulted in something that looked quite a bit like Kloster's strategy.
Great video! I think I was introduced to this problem prior to 2006, but I may he mistaken. Fun to dig this memory back up.
wow this is some awesome math story telling! John Conway man he's a poet
I am too stoopid to follow the video at this pace, but I still enjoyed it alot
I think the next question is "for an angel of a given power, how many squares does the devil need to be able to burn each turn in order to keep up"
Also at some point in this video I started thinking of it as the coyote-and-roadrunner and it's going to be a struggle to say angel and devil again now
"Why not just build a box really far away?"
The devil simply does not have enough time. To make it even clearer, let's restrict the angel to only move in the first quadrant of the grid - as if it started in the bottom-left corner of a chessboard that extended north and east indefinitely.
Let's say you start building your wall at a distance R from the starting point. A completed box with length R will have 2 walls of length R that are 2 tiles thick, so this wall will take 4R turns to build.
It is very important to notice that this minimum requirement is the same regardless of what R you choose.
Because this box has side length R, the angel can follow this strategy to escape: Go north R tiles, then east R tiles, then south R tiles. If you ever find an opportunity to get further than R tiles away from your starting point, take it.
Notice that this strategy can walk the entire length of the wall in 3R/2 turns. Because the wall cannot be completed by then, it will ALWAYS find a gap that it can use to escape.
(The scenario also works if you use a wall shaped like a quarter-circle. Even if you assume that you don't need extra squares to close off diagonals, this wall is still length pi*R/2 and 2 tiles thick, so would take pi*R turns to build. The angel walks this wall in R(pi+2)/4 turns. (pi+2)/4 is less than half of pi, so still plenty of time.)
Very nice introduction. Thanks.
Wow, this is a great video! I hope it blows up
Very clear and concise explanation!
Even after reading the explanation in the comments I have absolutely no understanding of what I just watched.
I honestly thought it said "Bagel vs the devil"
This is amazing, it's like a fandom for a game that doesn't exist
grr
I was working on this exact video for a while now, but you got there first.
Wait , I’m not sure if I understand how the runner can’t be caught. Wouldn’t it be possible for the devil to make a trap for the runner by extending two tiles out of the wall and then moving back toward the runner, and then enclosing the runner when she walks into the area partially enclosed by the trap?
The runner is playing against a nice devil, who can't burn off squares that the runner was on or could have reached earlier. This means that the nice devil can't just enclose the runner because the runner's path is in the way. The argument is that if a runner can win against a nice devil, so can an angel, just by following the runners moves. And if the angle can win against the nice devil, it can also win against a normal devil, as was proved in the earlier part of the video.
@@dani-rybe Yes, but the evil devil can win without any issues against the runner. In fact, the runner ends up being even easier to trap than the fool for the evil devil and only the evil devil. I get that the runner isn't intended to be compared to the evil devil, but something about the proof just isn't sitting right with me.
@@abderianagelast7868 Máthé's proof is not a 'direct' argument, which might be what you feel uneasy about. They show several things: (a) if A wins against the ND, then A wins against D (b) R wins against ND (c) and trivially, A can do whatever R does. Combined, these prove that A wins against D, without ever offering a strategy for A against D.
@@abderianagelast7868 I think something to consider, which may quell your uneasiness, is that you cannot reintroduce the evil devil without also reintroducing the angel, and the angel has exponentially more movement options over the runner than the evil devil has over the nice devil.
The runner is handicapped much more heavily than the nice devil is, yet still wins against the nice devil, so the fact that the evil devil can lure the runner into a box doesn't matter, because the angel could sidestep the trap in fewer turns than it takes for the devil to construct it.
With Runner vs Nice Devil, the runner runs into the trap and out again because the Nice Devil can't block him. When you convert this to the real Angel, he takes the "reduced path" which never goes into the trap.
It seems to me that only the devil has a winning conclusion. The angel only had a continuing unresolved game.
One must imagine the angel happy.
I think that a much simpler way to out this is simply that, because the angel can move more than one space, the devil is always outpaced when only allowed to burn one square at a time
If it was that easy, it would have been proven by Conway himself
the problem with that thinking is that the devil doesnt technically only burn 1 square, he burns every square the angel could have moved to and didnt. You can think of this as the angel moving to a square in 2 moves it couldve reached in 1 does nothing but give the devil an extra turn, meaning that moving to a space it couldve moved to previously can only hurt the angel.
@@orange_famta3956 the question isn’t whether or not the devil can trap the angel if it just moves back and fourth constantly, the question is if the devil wins or loses even if both have the best/perfect strategies
Good to see my tuition is going to such groundbreaking work
Apparently this is the same Conway as Game of Life Conway
And apparently he’s also done a crazy amount of other shit too, smart fuckin guy
he’s a genius man, one of the smartest thinkers of our tine
Why did i think this was just going to be a chess board that stretched infinitely with pawns without end lmao
this about covers why i was confused that other videos stated the devil has a winning strategy
i didnt realize it would be as simple as reducing it to a one direction and one half wall to prove it mathematically though
This isn't a proof of the one move strategy here they just show how you might build a wall to block off one direction. It is illustrative of how the one move angel can be controlled but how much more powerful the two move angel is to even try and control in the same way.
The proof you can actually fully trap a one move angel can be reached in a similar way but requires a little extra setup. Initially the devil chooses a sufficiently large square around the angel's starting position that he will use to make the trap, say 100*100 square would be plenty. The devil blocks off all four corners of that square by building a wall into the large square. For the top left square he would start say 5 squares below the top corner, build in 5 squares then up 4 squares to get back to the top edge of his 'trap' square. This takes 9 turns for each corner blocked, 36 turns in total. Wherever the angel has gone it is still well inside the 100*100 square we set as the devil's trap at this point. It is now facing a partially complete trap which has corner walls but a big gap between them in each direction.
However the problem now is that whichever gap it moves towards to try and escape the 100*100 square we can build a wall along the edge of our 100*100 square to stop it escaping that direction, as demonstrated in the video. Because of the corners we already put in place the angel can't threaten to escape in two directions at once, it has to commit to one gap at a time to go for, and we can always build a one dimensional wall fast enough to stop the angel escaping in whatever direction it is trying to go.
Nice editing ! Really satisfying
so the angel can always win if it makes a perimeter, because every time the devil puts down 1 square, it's putting down 4 edges, giving the angel >1 spaces to move for every 1 turn the devil plays...? I dunno, that's my best shot.
Just realised the final examples are actually pretty simple.
Nice devil is just to prevent trapping the runner in burnt box so the only way for the runner to lose is to loop back to the start.
Assuming the left wall is already there, you would need to build the right wall + 2 squares at the top, n+2. Runner has to go the left and right wall + 2 walls to escape, 2n+2.
The devil wins in n+2 turns
The runner wins in (2n+2)/2 turns = n+1 turns
So even if the devil moves first, the runner always wins first.
I'm not sure what I missed in the video, but I missed something that caused me a lot of confusion. So now I'm looking at the paper itself, and it's making more sense, but I still don't get what was causing me issues. I think what's helped me understand it is trying to construct smaller walls such that a runner allowed to move diagonally would be forced to take more turns than the number of tiles it takes to make the walls. This is impossible, assuming you allow the runner to take diagonals. Which is a very fair assumption to make. Being able to visualize it through Tabletop Simulator helps a ton. However, I believe that a devil of power equal to or greater than the power of a given angel can win every time against said angel.
EDIT: It occurred to me that a devil with power V against an angel with power P would basically be the same as a devil with power 1 against an angel with power P/V, so basically as long as P/V is less than 2, the devil can win. That's pretty much what was already discovered, so...yeah.
Wait, I'm not sure if I'm missing something about this devil power thing. Isn't the devil supposed to have infinite power as a given in this question?
@@tudornaconecinii3609 The original game is that the devil can move anywhere he wants on the infinite chessboard, but can only burn one square per move. He and the Angel take turns one after the other, so if the angel can move at least 2 spaces for every move the Devil makes, the Angel can always come up with a strategy to win. Conversely, if the Angel:Devil ratio is reducible to anything less than 2:1, I'm pretty sure the Devil can always come up with a strategy to win.
@@abderianagelast7868 Oh, by "devil power" you mean the number of squares the devil can burn, not move. Okay now I understand your original post.
@@tudornaconecinii3609 Oh, yeah, that's what I meant! Sorry, I didn't realize that was the question lol. I definitely should have explained that better.
nice devil vs runner is really clear to me when you try to imagine what the devil would have to do to construct a staircase going from north to east. to trap the runner in a giant triangle and force it back to it's starting height.
that is to say, the diagonal from satandard x,y coordinate (0,200) and (200,0)
200 space up should be plenty of time to get started on construction vs the runner, right? but for each space you want to go down and to the right, you need to burn out 1 additional square to close off the diagonal. in the 200 turns it takes the runner to get to the top, youre only halfway done with the stairs. and in the 100 turns it takes the runner to get halfway down the stairs to were you were, youve only gotten 50 spaces. the runner is closing the gap
My favorite part of this video is the comments section filled with mathematical geniuses and intellectual giants who apparently dwarf András Máthé but for some reason or other wont publish their findings. Instead they grace us mere mortals by posting their galaxy-brain ideas in the comments section.
Crazy idea: What if the squares that the devil burns start following the rules of Conway's game of life?
that doesnt make any sense, burnt squares cant be unburnt
@@thomas.thomas It's a mathematical proof about an infinitely large chess board, and an angel and a devil, two mythical creatures, I don't think "squares can't be unburnt" is really an argument
Then every turn the devil would burn a square, which would then see that it has no living neighbors, and then die and become unburnt. The devil would have no way to progress at all.
@@AnarchistEaglethe starting square is burnt
I was here before he had 1k subs. can't wait for you to blow up
Okay, for everyone who isn't understanding the half assed math explanation:
There is a "mathematical" game/problem of an escaper and a trapper. The question for that problem is ¿Does the trapper always trap?
And the short answer is "yes, as long as the trapper has the same level as the escaper, else the runner wins".
The whole thing with the nice trapper is there to prove that by backtracking the escaper always wastes moves, so there's no point in covering spaces that may be used for backtracking.
Then there's an odd tangent against a runner variant that never explains why that's important:
Runner is just a non-backtracking fool that changes directions once it can't move.
The way the trapper wins against a runner is by making a bigger wall to the point where runner is going in the time it takes the runner to run across one.
This is simple for the trapper to do (you can just simulate it in your head), but once the runner has a higher level it becomes impossible (again, just simulate the same but the wall thickness is doubled and escaper moves twice as fast).
And that's it, the whole video is spent to say in a roundabout way that the trapper only wins while in the same level as the runner...
Gotta love complicating stuff with math I guess...
Oh, and stuff holds even if the runner is constantly using diagonals and decides to change paths prematurely, but it's harder to simulate in the head.
If you want to give it a go, you need the devil to 'know' the wall beforehand, and pick the most extreme end that the runner can go to when it changes directions, working from there "inwards" on each step taken to said wall. If there's ever a point where you are lacking walls to trap, you can just move the first one further "back", making the whole perimeter bigger and giving you more time overall.
I watched the nice angel part of the video twice and still didn't get it, but explaining it in terms of backtracking makes so much sense.
Man I have no idea what I am watching but I enjoyed it non the less
Imagine a character named Ghost. They appear in a random square every turn. This means that the chance of them existing at any one squere is one in infinity. Do they exist?
No. The Ghost is only part of my imagination.
Very captivating thumbnail!
Hey man, great video with awesome premice and visuals. However, you lost me precisely at 5:13. The explanation would have benefited from being clearer. Do note, I’m no genius at all, but I’m not an idiot either. You may want to dumb it down for us simpletons next time ;)
Same here. Watched that part like 5 times now and i don't get it
The dumb explanation is that the only reason to burn a square is to prevent the angel from moving there, and if the angel wanted to move to that square, then it should have moved there back when it could have.
However, this explanation isn't fully rigorous because the angel might have wanted to intentionally visit that square later as an attempt to evade the devil for as long as possible.
I think, essentially if the square that gets burnt was to going to become part of the path later on then it would have to be part of the reduced path (as it is within 2 spaces of a lower number). But it isn't part of the reduced path since that would cause the square the angel is currently on to not be part of the reduced path (as the burnt square is closer to a square with a lower number). But we've assumed the angel is travelling on the reduced path. This contradiction means that the devil will never burn a square in the earlier region.
This is a beautiful video. Well done
What if the devil could step on a cell the runner has stepped on.
He could simply make a wall millions of cells away and close it to a box with a 1x1 cell entrance while the runner comes.
As she has to touch a wall, and there's already a big one she has to follow, whenever she gets to the wall, the devil could simply close the box and trap her.
Evil devil wins against the runner. But since nice devil loses to runner, that means that evil devil loses to angel.
At that point the angel is disappointed in you for not having perfect game theory, so he stops acting as the runner and avoids the trap. Congratulations, you had the disadvantage if you played a perfect game and now you've deviated from the perfect moves. But that's not the point, the runner and the nice devil are just ideal instructions where both play perfectly. And whoever wins the perfect game wins the regular game with stratagems and gambits, because while the devil can trick the runner, it can't trick the angel. Basically devil=nice devil
I found this problem and proof very interesting. I found your explanation of the proof Fully frustratingly terrible. You did not bring me on the journey of understanding how and why the optimal strategy is optimal. you only communicated to me some of what the optimal strategy was. and as this is not a real game that real people play, that information is more than useless. and not what I want from a video like this. Its taken me 20 minutes to get to this level of articulation of how this video made me feel. I guess i've been fortunate to never have had a bad teacher for something I care about, as I imagine that is what I'm feeling now.
Essentially, the nice devil needs to make a wall a certain distance away and loop back to the start. The runner can run twice that length in that amount of time.
The exact moment the nice devil is about to finish the loop, the runner has made it to the end and back since they moved twice as fast as the devil. 2 trips for the angel = 1 trip for the devil. The devil will always lose.
- So how can an angel win with a devil?
- Well if we take a nice devil and a runner-
I feel like something is off with the proof the angel can win... If the devil does the same strategy to block off the fool, but acts as if the angel has 4 times more power, it can alternate building walls on each side and trap the angel, why would a version of the angel with less movement be able to escape that?
This is a good thought! Something along the lines of "if A heads North at any point in time, continue building a North barrier, if A heads West at any point in time, continue building a West barrier" and so on. If so, this does indeed lose against the Devil if you require the Angel to increase its distance from the origin at every step, and in fact this is one of the other tempting "false strategies" addressed by Conway in his paper. However, without that promise from the Angel, the Devil loses a 'reference point' around which to build the barriers, and the Angel can essentially meander enough that it is perpetually free of being completely stuck.
Because that strategy specifically depends on the angel being a Fool. The Runner is not limited in its direction, and the way it plays out, it just runs faster than the Devil can place walls to block it in.
@@inconspicuoususername The strategy about building the wall to block in the angel doesn't rely on her being the fool. Specifically, the wall is built as if her power was 4 times larger, giving the devil time to construct 4 walls completely blocking off the angel's movement in every direction.
If that strategy is able to block off the angel who can move to any square she want's, why would it not work on the runner, who's movement option is even more restricted?
The 4 walls strategy gets around relying on the angel being the fool because it builds the wall in each of the 4 directions, any path the angel takes would move it closer to one of the four walls, which for that specific wall would have it's own half steps. No matter which direction the angel moves, a wall is being built to block off the path entirely. With no way out, the angel becomes restricted to a finite playing field in which case the devil will always win.
@@localmeadows9387 It's not that the devil builds the wall based on which direction the angel moves. The devil builds the walls regardless of which direction the angel moves. If the angel has power N then the devil builds the wall thick enough to block N but at a distance required to build the 4N sized wall. That means the devil has 4 times longer to build the wall, so with that extra time he builds 4 walls instead of 1. Every turn he alternates between walls. North, East, South, West, in that order. The only time he cares about the angel's move is when she reaches the half step towards a ny wall. in which case he shortens that wall to fill in the gaps he left whenever it's the right turn to build it.
The wall is always far enough away because the devil acts as if the angel had more power than she really did, building the walls as if the angel were a fool 4 times stronger, but instead of building just a single wall, he builds a square around the angel to prevent movement in any direction (because the angel is not the fool). But because the distance the wall was built was extremely conservative, the angel won't reach any of the walls in time to get past them before they are built. And if the angel isn't strictly increasing in distance away from the origin, she's giving the devil more moves to build the walls. Taking 2 turns to reach a space she could've gotten to in 1 turn doesn't change anything except the number of spaces the devil has removed.
@@anthonycannet1305 in which case the answer is simply: the devil will never have enough time to trap her. The further away the devil builds, the more squares need to be burnt to create a loop of sufficient width. You will see that this is the case if you try to formalise your idea! :)
‘once upon a time, a gardener and a winnower worked in a garden’
I don't really get the thing at 5:12
isn't that just an example of a way the normal devil is actually different to the Nice devil? why's it invalidate the other path
If the evil devil had already been there, then the angel couldn't have gone there later. When we were talking about how the nice devil picks its route, we picked in order going backwards and then made the nice devil take shortcuts. The angel can't go to a square that the evil devil burned. So if the evil devil had been there, then the angel couldn't have been, and so the nice devil wouldn't have decided its route in that way. This doesn't mean the nice devil and the evil devil are different, it means that the particular scenario where they would end up being different can't happen. If the evil devil would have gone there without the nice devil, then it would have burned the square before the angel ever got there, meaning the angel would have to go somewhere other than where it did, which is false. So the evil devil has to be nice. All of the evil devil's winning strategies, if it even has any, are proven to be nice. That means we can just use the nice devil from the start, which makes the problem easier to solve because the nice devil acts in a very specific way we know about, instead of possibly being able to flutter around the entire board like a jackass with no rhyme or reason and no way for us to know if his plan is working or not. Since he has to be nice, and act in nice ways, to even have a chance of winning, it's much much easier for us to know if his plan is working.
@@williambarnes5023
I'm not sure that explained it. The situation we're given is effectively taking a game played between the angel and the nice devil, then looking to see if there are moves that are optimal for the normal devil that the nice devil couldn't have made. Supposedly this will never happen because of the path reduction thing (the "work backwards from end tile" method), but there's no explanation as to why those two things are related. Or even why the path reduction is important at all.
@@Graknorke A better way to explain it that the angel if playing perfectly would never want to go to a square that it could have gone to before, and with this knowledge the devil also won't ever suggest a move that the angel could have gone to before and therefore the nice devil and the devil would play the same against the angel.
This problem: when you let your little brother make the rules at Christmas board game time.
If you type 58008 on a calculator and flip it over it spells boobs. You’re welcome.
I remember being introduced to this "game" via Destiny 2. The traveler is the angel and the pyramids are the devil. Currently, the traveler has stopped due to damage from Rasputin, so perhaps we're doomed.
I am entirely confused by everything from 6:00 onward. Does this runner somehow relate to the angel and devil problem or is it an entirely different thing? Then when it comes to actually solving this problem, I can not follow the logic. Why're we using an intentionally large amount of burnt squares? Why're they already built before the runner even starts? Why isn't the good runner devil always moving? Why're we using a movement by the runner that doesn't follow the game's rules to prove a contradiction? Why does that contradiction mean the runner can never reach that line?
The speed of the presentation I can deal with by slowing down and pausing, that's easy. I feel like there're a ton of logical leaps that're not explained, though, especially in the particulars of the math.
And I don't get how the devil can't just go a trillion blocks out and make a 2 wide square then close it in on the angel
Imagine you were playing as the Devil and your opponent said "I'm going to use the Runner instead of the Angel, and also I'm going to start with the left half of the board burnt --- and I'm still going to win." You have no reason to object to this --- it doesn't limit your choices, only theirs. They're saying they can beat you with one hand tied behind their back --- and they do, so you know they could have done it using both hands too.
@@LukeSciarappa but that only works vs the nice devil. there is no winning strategy in the proof. no matter how many concessions the angel gives.
@@unwono The devil would need to take two turns for every one unit of perimeter around such a square. The angel only needs to travel half the length of one side, and can move two units per turn. It doesn't matter how big of a square you try to make, the devil will never have the time to finish any more than a quarter of it.
@@Endominateur remember , he proved that since the runner wins against the nice devil, the angel wins against the nice devil (since the angel is a better runner)
But if the nice devil loses against the Angel , then the devil does (since if the devil wins , then the nice devil HAS to win ) so therefore angel wins against devil
I did not understand it, but it was nice to watch :)
I like your funny words magic man
It seems like if the runner loops around an island, she loses for reasons that have nothing to do with the original problem.
Also, if she offers the Nice Devil half the squares, the Nice Devil could just start building a trap 1,000 squares out, and the regular Devil could just close the loop. In that scenario, the Nice Devil's inability to trap the runner has nothing to do with the nature of the problem, and everything to do with the weird, self-imposed "no burning squares the runner has been on" rule.
The thing is - against the Angel, the ND is not weaker than the Devil. The Angel has no reason to ever return to a previously available square - in optimal strategy it would've gone to that square the first chance it got and thus on a board with less total burnt squares. So there is effectively no difference between Devil and ND for the ANGEL.
It's also proved as you concede that a strictly inferior Angel, the Runner, will always beat the ND.
Because a crippled Angel can always beat the ND, an un-crippled Angel can always beat the ND, and because for the ANGEL the ND and the Devil are the same, the Angel can always beat the Devil.
I just realized something that makes this problem a bit melancholy: The Devil's work is done when it wins. It can stop once it's trapped the Angel. But the Angel's work is only done when it loses. If the Devil can't win, the Angel has to keep running forever.
you did what codeparade couldn't. bravo
One interesting tidbit: given an angel which always moves randomly, the devil can always win. Whilst the angel busies itself moving about, the devil will construct spaces which are sealed in all but one spot. Whenever the angel enters such a space, the devil can simply seal off the cube or circle or whatever and therefore contain the angel within a finite, exhaustible space. Given an infinite span of time and the nonzero chance of the angel blundering in this way, the devil will eventually win.
The proof would go something like this: If the devil always starts building its cube right where the angel is, the angel will never be farther than [the number of steps it takes to build a box with one entrance that can contain the angel] * [the number of squares the angel can move per step] * 2 (because a worst-case scenario sees the angel moving in a straight line away, and half-finished boxes do not count). This allows us to calculate the probability of the angel making it into the box before the devil builds the next one, from every possible square it could be in, which gives us a minimum to work from. Having a nonzero but hard minimum means that as the amount of time spent approaches infinity, the probability of the angel being boxed in at some point approaches 1.
Obviously, this only works because we assume that the angel is moving randomly. If its movements are not random but are instead designed then, however stupid its movements are, the proof falls apart because we cannot guarantee a nonzero probability of the angel entering the box.
I have no idea what he's saying, but I love it any way
Ignore the guy who said you're moving too fast. Your tempo is perfect. Keep making videos like this and your channel will succeed.
This is cool, it will be cooler when I watch it again later cause I haven’t slept yet and it’s 6am and I have no idea what you’re saying
I imagine, though I'd love to see a proof of it, that to win against an angel, the devil would need to burn squares each turn equal to her power. Since they're only burning one square, the runner can always sneak by, but two would match them evenly.
I'm no mathematician, but I know that to disprove something you only need one example that contradicts it, so here's my example contradiction in the assumption that if the devil wins, the nice devil wins also:
Suppose the angel behaves like the aforementioned runner and the devil realises it (*). The devil decides to prepare a trap for the angel, somewhere far enough away in the direction of the angel's movement, as to be able to complete the trap. Since the angel behaves like a runner and the board is infinite, the devil can always go far enough to prepare the trap, no matter the angel's power. The devil creates a box with walls wide enough to prohibit the angel from jumping over them, leaving only one opening for the angel to get through. The devil waits, and once the angel gets in the box, the devil swiftly closes it off. I think it's pretty clear that this is a winning strategy for dealing with a runner-type angel of any power, yet the nice devil could never use it, since he cannot close the box off, the angel had to be able to go through it after all. What I think this proves is that whereas the nice devil cannot beat the runner, as proved in the video, the normal devil can, regardless of the runner's power, which in turn contradicts the assumption that if the devil wins, the nice devil wins also.
Please do tell me where I went wrong with my reasoning! I am pretty certain that whoever wrote the paper thought about it more than me, so I am inclined to believe they got it right. What I marked by (*) seems like a pretty big assumption to me, but aside from that I'm not really able to find where I erred.
You are right, the asterisk is where you are going wrong. :) When we say “the angel wins”, this is shorthand for “the angel has a winning strategy”. It is actually, non-ideal terminology. You can picture a winning strategy for one of the players as being a very large book, where chapter N refers to the Nth turn of that player. Inside that chapter is a list of instructions that look like: “if the other player has made the sequence of moves X_1, X_2, … X _N, move to square Y”. This chapter will contain every possible sequence the other player could have made till the Nth game, so our player is always able to find an instruction. This book is called a winning strategy if it is such that, at each turn, if our player looks into the book for which move to play, and follows the instructions very diligently, they will win the game.
In the case of the angel, this book allows the angel never to get caught, no matter what the devil does. This is why the question of “if the angel doesn’t obey the strategy” falls outside the problem being dealt with. Indeed otherwise we could suppose the angel is even sillier, and just alternates between the same two squares for the entire game. Surely then the devil could capture it! But the point is, if there exists a winning strategy, it will not contain any sequence of instructions that will lead to the angel being captured.
Finally, to be clear, Máthé’s proof does not offer a winning strategy explicitly. It uses lots of clever detours to prove that this book exists.
I sorta understand where this is coming from but, in an infinite setting, wouldn't there be a point so far that the Level 2 Angel could never reach in convenient time to not be boxed in by the devil?
And after he was boxed in wouldn't it be enough for the devil to just do a second lap around this structure as to not let the angel move past the burnt squares?
The farther away the devil builds the wall, the more turnd the devil will need to actually build it, thus the angel always has time to escape.
@@alvedonaren What I'm proposing is that there might be a "sweetspot" in which the devil can always box the angel in
It was a little rough to understand in the video, but the creator's pinned comment goes over it a little better. Basically, yes that will work against any power 1 angel (it can move 1). However, any angel with a higher power than 1 will always win. Why is that? Because when a devil starts out a thousand blocks, the devil must now build a wall that is big enough to block an angel that could move two thousand blocks in the time it takes the devil to build a thousand blocks. The problem get worse for devils with higher powered angels, because even starting out an infinite amount, the angel will get that infinite amount times its power. That's why the first strategy shown to win as the devil only works on power 1 angels. It really just boils down to action economy, 2 is always bigger than 1. Hence angels past power 1 will always win (assuming both side play it perfectly).
@@Comfyest This video says no, that does not exist. There's a special calculus formula to answer where that optimized sweetspot in this scenario, and when you plug in 2 for the angel, there will be no real answer.
Bro, where did you go? It has been 9 months
went searching for coal, and found gold.
God I looked away for 2 minutes and come back to some complete insanity mathematics 😂 great video though after watching all the way through everything was explained perfectly!
a lot of people in the comments are very confused, as am I, but I think I've made the second proof make sense in more layman's terms.
tl;dr: the work needed for the devil to trap the angel inside a massive box made out of burnt squares will always be much higher than the work needed for the angel to get outside of that box. the angle can always escape an attempt at being boxed in, no matter how far away the box starts, because the devil will never have enough time to complete the box before the angel can potentially escape it, so the devil will never have any time to contain the angel in any circumstance
-
there are several people saying that the mean devil can win by building an infinitely-far away box that can contain the angel before it reaches any edge. what those people don't realize is that THIS IS WHAT IS being attempted in the second scenario, with the runner and the nice devil.
See, the nice devil isn't actually nice: it's forward-thinking. it doesn't want to eliminate a bunch of squares just to be courteous. Rather, it wants to create a wall of burnt squares that the angel never, ever could have broken through, no matter what additional moves were taken. That's how you build a consistent winning strategy, by accounting for deviations.
the runner starts out exactly the same as the fool, just running as fast as possible in one direction. The nice devil does its best to build a wall that will be able to contain it regardless of what moves it may take. However, the amount of work that the angel has to do to survive is drastically less than the amount of work the devil has to do to win, and they both have the exact same amount of moves to do it.
Let's say i'm a devil, and i'm dealing with an angel with a power of one. if i try to build a wall five blocks out from the angel in every direction, i have to make 40 moves to complete the box on all sides. however, it will only take the angel five moves to get to that edge, which won't give me enough time to fill in the box. so, i change the strategy and push the wall one block further, so the wall now surrounds the angel from 6 blocks away. however, this only adds one extra move needed for the angel to reach that edge, whereas i now need to fill in 48 squares instead of 40. The farther you go, the additional work for the devil is exponential, whereas the work for the angel is simple, just one additional move.
so, you could not build an infinitely far wall that gives you enough time to complete the square wall around the start, since the work necessary would be exponentially larger than the work for the angel to reach any potential edge, even with just a power of one.
By using the second example, where the runner knocks out half the board to begin and sticks to a firmly predictable strategy, still neither the nice or the mean devil would be able to build a wall to contain the runner at any distance. If the angel still wins, even with those handicaps, it can't lose in any scenario
Thank you, I was having trouble trying to figure out wtf the nice devil or the runner had to do with the first problem at all and this explanation makes sense.
So this makes sense exept for the statement that if the nice devil loses the normal devil loses. For instance the runner will lose to the normal devil no matter what by the devil creating a box to trap them. This same thing will occur when an angel can move however many squares the devil needs to go out an insane distance and create a barrier of 2 thickness or whatever the jump distance of the angel is and he will win every time
It's more "if there's a way to win against the nice devil there's also a way to win against the normal devil", meaning it might not be the exact same, but there's a way to turn a winning strategy for one into a winning strategy for the other.
The “good devil” is the devil playing optimally against the angel.
The runner is a weakened angel.
Evil devil > runner > good devil
But Angel > runner > good devil (> evil devil only for angel)
For angel: good devil > evil devil
For runner: evil devil > good devil
This is an amazing video! That said, would have been nice to have a few seconds of respite between ideas, had to watch some parts thrice or so before getting them.
This whole problem can be simplified to, “Is 1 > 2?”
Great video. Really enjoyed it
how about we just introduce the precondition that the angel has a gun and just shoots the devil... there. i solved it for you. your welcome
As a layman, I see the answer as follows. The devil can only block one square per turn. The angel of power >=2 can access more than that one removed square per turn, and therefore will always be able to out-maneuver the devil.
i know this might well be impossible (or even addressed in the paper, i am also not a mathematician), but i wonder about a variation of this game:
imagine that for every turn the angel makes, the devil gets to burn a number of squares, n. for an angel of power x, it has (2x+1)² - 1 different squares it can go the next turn, before considering burnt squares, so it is self-evident that a devil that performs at least that many burns (8 for power 1, 24 for power 2 etc) per turn has an instant win available to it. what im wondering though, is whether one can construct a way to prove the *minimum* n for the devil to beat an angel of power x! im gonna think on it.
thanks for the video!
My first intuition would be that a devil would only need as many squares n as the angle has power x (n+x). Because then it seems like the angle of power 1 scenario.
Amazing video I find this stuff super entertaining and you did a great job explaining it all