Papers unpicked: Strategy on an Infinite Chessboard between an Angel and a Devil
HTML-код
- Опубликовано: 21 авг 2021
- This video discusses András Máthé's 2006 solution to the famous Angel problem, first described by John Conway in 1982. I encourage viewers to pause if needed, as this proof makes a fair few sharp turns and mental leaps that can take time to appreciate!
The Angel problem went unsolved for 24 years till 4 independent, different proofs appeared in 2006. I gloss over certain minor details/special cases to smoothen the discussion, but the full paper is linked below for anyone who wishes to delve deeper!
Note: as Nicky Case pointed out to me, I forgot to specify something of importance. In the section which counts squares, from 9:05 onwards, we are interested in the burnt squares enclosed within the painted region, rather than all burnt squares. The amount in this connected family is what the quantity 's' refers to, and is what allows the argument to work -- indeed the 'point' of the green paint is precisely to define that region. Apologies for any confusion caused, and hats off to those who noticed!
· Máthé's paper: homepages.warwick.ac.uk/~masi...
· Conway's article, where he discusses various counterstrategies: library.msri.org/books/Book29/...
Video made using the Python package manim.
![Can You Escape The Goblin? [Math Puzzle]](http://i.ytimg.com/vi/V0V3LMK40iI/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 this solution can be used later ie imaginary numbers
Sometimes we create tools that we cant use yet
Yes, what a wankery.
@@deadbeef576 lasers were invented before we had a plan as a species on what to use them for.
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 😭
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
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
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.
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 :)
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
oh I see, the devil can't just ignore the angel and build a big square wall out at N squares, because then it has to take 8*N*P+4*P*(P-1) turns to build the wall while the angel will only take N/P turns to get there.
Yep, even if its the most efficiently built wall taken in the least amoun of turns, the angel will always win
not against the mean devil though
@@gogogo123454321 the mean devil cannot win if the angel takes optimal moves. Building a wall doesn't work. The angel can just go around it.
@@jackdonovan6533 According to the video example, if the mean devil starts far away enough the devil wins
@@gogogo123454321 That's only an angel with the power of 1, or an angel that can move only 1 square at a time. 2 or more and the Angel can always win.
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
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.
ruclips.net/video/sxiKlOK3EJY/видео.html
perhaps you were talking about this one from CodeParade
@@MeanSoybean yeah that's definitely the one. 😬
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.
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…!" ❤️
You forgot to tell me to hold on to my papers, I will never recover from this
Wow, this is a great video! I hope it blows up
Very clear and concise explanation!
I really enjoyed this video. I can only imagine how cool it would be if I understood at all what was going on.
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 can't believe you don't have more subscribers. Great video!
Nice editing ! Really satisfying
Very nice introduction. Thanks.
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.
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
Amazing video I find this stuff super entertaining and you did a great job explaining it all
wow this is some awesome math story telling! John Conway man he's a poet
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.
The graphics in this video are lovely!
Pretty sure I didn’t learn anything but I was mildly entertained so good job
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.
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.
Well that was fantastic! More please!
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
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
This is a beautiful video. Well done
grr
I was working on this exact video for a while now, but you got there first.
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 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
I was here before he had 1k subs. can't wait for you to blow up
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.
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 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.
Good to see my tuition is going to such groundbreaking work
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
Why did i think this was just going to be a chess board that stretched infinitely with pawns without end lmao
You earned a subscriber, good content!
Great video. Really enjoyed it
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.
@@user-no9st2pw3s 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.
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
that was really cool. Thank you!
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.
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.
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.
I am too stoopid to follow the video at this pace, but I still enjoyed it alot
Thanks for the video I love it
I honestly thought it said "Bagel vs the devil"
I like your funny words magic man
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".
"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.)
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! :)
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.
Awesome video. Subbed.
It seems to me that only the devil has a winning conclusion. The angel only had a continuing unresolved game.
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.
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
Very nicely done :).
This is great!
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
If you type 58008 on a calculator and flip it over it spells boobs. You’re welcome.
Wow this is a brilliant video
Man I have no idea what I am watching but I enjoyed it non the less
went searching for coal, and found gold.
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.
That was a great video
Great vid!
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.
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.
Fantastic!
- So how can an angel win with a devil?
- Well if we take a nice devil and a runner-
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.
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).
@@ComfyestofBois 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.
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.
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!
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
codeparade has a video on this game, and uses game theory to solve it, I think it's a pretty good video, basically saying that any move the angel makes to go backwards in a direction is a move made in the benefit of the devil, so it wouldn't want to make those moves. I think then however the angel plays as the fool does, and that shows that the devil always wins
Codeparade's video is garbage as it doesn't explain any point of the proof.
@@sanscipher9166 oh. We’ll I liked it
@@sanscipher9166 I don’t think he was trying to show the proof, just show his reasoning for a solvency to the problem
*I like your words magic man*
Very captivating thumbnail!
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.
This whole problem can be simplified to, “Is 1 > 2?”
I feel smart now lol, great video!
This is amazing, it's like a fandom for a game that doesn't exist
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
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.
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.
I did not understand it, but it was nice to watch :)
Follow up question, how many devils are needed to win against one angel of power n? As noted by another commenter, a devil (or group of devils) that can burn an n by n area in one turn can use the same strategy against a power n angel as one devil uses against a power 1 angel, just with a scaled up grid, so the upper bound is n^2, but can we do better?