A fascinating Game Theory problem proposed by John Conway. Original Paper: library.msri.org/books/Book29/... 2-Angel Proof: homepages.warwick.ac.uk/~masib... Music: Bass Loop - Wooseong / wooseong012
@@fabipower1 "The angel can win, but she is a divine being of supreme power and your tiny flesh brain could never hope to understand her dazzling strategy."
I think devil can also win easily if devil just went far away (very far away long enough that angel can't come there for a while) and made a box around angel thick as amount of blocks Angel can travel then fill that box this will take time but it's simple and effective stradegy
@@TrekWarlord because it is infinite grid is what makes this possible let me explain if devil goes very far away soo far away that angel can't come close in time to escape box while devil is making it thick as x (how many boxes angel can jump) because as you said it is infinite grid devil can start far as he wants and angel has limited amount of boxes he can travel this gives devil time to box in angel when box is thick enough and angel cant escape its just matter of time for angel to fill the box and done angel is trapped it will take lot of time but its not impossible
More like a biblical angel; just a pile of floating discs and eyes that give messages but don’t really have a personality outside of being mildly unsettling
Angel can win by moving in an arc to infinity. It can lose if it only moves in one direction. From the Bowditch proof with an angel of 4K: To win, the angel must trace out a circuitous path. A circuitous path is a path semi-infinite arc (a non self-intersecting path with a starting point but no ending point).
Devil: I’ll build a wall up north where the angel is headed, they won’t want to move back so eventually I’ll win! Angel: *_simply moves to the left_* Devil: FUCKING- AAAA-
It won’t work cause the wall can always be jumped. The farther away the wall is the longer it will take to make. The angel can get to the wall and jump over it faster than the devil can make it.
I love the mental image of the devil slaving away at building an impenetrable barrier with the intent to trap the angel, only for the angel to casually walk past it mid-construction. Sounds like something straight outta Looney Tunes
I vaguely remember playing a game like this once, except it was called "Farmer and the Hog" or something like that. But instead of being the angel, you were the devil (or farmer in this case) trying to capture the hog.
*comes up to literally any important or interesting bit of information* "but that's too confusing for all of you simpletons to understand so I won't bother explaining it"
exactly why i like game/film/food theory, they actually explain the 'complicated' crap and not just gloss over it and if they DO they STILL explain it and be like "blahblahblah but basically this thing does this"
it's the duty of the teacher to explain things to people who don't understand them. "it's too complicated" is just a copout a lot of youtubers including this guy do to mass produce content with little actual substance, when they can easily put more effort in to come up with helpful explanations
@@atw8193 yes, you should research things yourself. but when watching educational videos there's an expectation that the creator explains the solution in more than just a really crappy surface level
savior139 why are you assuming that lmao?? I’m an undergrad student in my b.arch and I’m already here watching this video so I’m obviously invested in LEARNING. If you keep spouting that no one can understand the proof then maybe this video shouldn’t have been made. VSauce got famous for displaying hard to grasp concepts in easy ways, obviously the creator of this video can’t synthesize to do anything
@@omiddorrani9283 It taught you nothing? It taught me a lot, and I'm a math major. It's an interesting problem, and he presented some ways to think about the problem. That's pretty good for a 3:28 minute video.
The key issue I have with this hypothetical is that the Angel doesn’t have any goal other than avoiding the Devil. If that is the Angel’s only goal, then doubling back to a previously available square makes sense as it makes it more difficult for the Devil to box the Angel in. Perhaps I’m just not understanding the hypothetical correctly or perhaps the Angel’s goal is more explicitly laid out in the text.
No you have it right. Blockin off the Angels' previously available squares is not actually part of the problem. Furthermore, as K increases, the Devil needs to not only make a blocking row of squares, but it also has to be K deep. Even at infinite distance and time, the devil only takes 1 square, while the Angels' available space increases Somewhere between K squares and 3/4 * K^2. The Devil should never be able to mathematically win if both players have complete information. If the Angel cannot see the entire infinite board, that changes the solution dramatically.
@@ShorlanTanzo so how do you explain that for whatever K if angel only move further from the start it will always get trapped? also if any move that is going back works then directly move to the block would only move better,so it does block the previous move
@@MythicWiz Simple if we give the devil and Angel the same amount of K then the devil can't trap cause the K for the devil would be too low to matter. If the angel's K is K=10 and the devil can move 10 spaces and block a square he is on. Angel still wins cause nothing in it says that the angel can't hop OVER the square the devil went on. So technically the devil has to block off way more than just 1 space but he can only do 1 space at a time. So he would need to block off so much but in a infinite grid the angel got so many spaces that the devil can't effectly trap the angel.
@@gagecowart7157 at that point the devil is a non threat. Let's say the devil somehow made a box around the angel. Because the angel can move 10 spaces that means a 1×1×1×1 box can't EVER hold the angel. Lets say the devil is 10 squares away and makes a box the angel can get close to the edge in 1 turn then jump out of the box the next. BECAUSE WE ARE IN A INFINITE PLANE OF SQUARES THERE IS NEVER A BOARDER SO THE ANGEL CAN JUMP OUT. And after a certain point one side would be made 1 million squares long it would make 1 million moves to make for just 1 side. So even if we say the devil can technically make a box 1 million squares on a side the angel has more than enough time to get out meaning by the time 1 side is made the angel is out of the preferred space. Along with the fact there are spaces beyond this 1 million box the angel can jump out. The thought experiment is shit because the angel is always at the advantage because of movement speed. The fact that there is infinity is the issue. You can't EVER run out of space. So the devil can NEVER fill enough space.
In slightly more complicated terms, "the angel always wins, but if they play intuitively based on an initial idea of optimal play, then lose. Ignoring that they would be able to figure this out ahead of time, and that optimal play usually involves avoiding things you know will cause to lose like just giving up part way through the game when you still have valid moves to make."
@@slugintub the example he gave of the angel moving north only and the devil building a wall. The entire thing is stupid the angel would always win as long as they play optimally
@@Quatro921 the angel moving north is a demonstration and with the normal movement of the angel the devil can build a wall (all four sides of the wall) millions of kilometers away and eventually build more and more layers of the wall until eventually the angel gets trapped inside the MASSIVE MASSIVE wall the devil has built. it will take EXTREMELY long to build the wall (more time than the universe has existed) but it will eventually trap the angel
@@Quatro921He was using the “only moving north” example as a smaller, easier to understand starting point to explain how the devil could win even without that restriction Instead of building a wall only in the north, the devil can win by building a massive circular wall from far away enough that the angel can’t pass it before it closes. I may be wrong, but that’s what I understood from what he described after he removed the north restriction
“The devil theory” You play as the devil and you must trap the angel, you have infinite time, on an infinite plane. The angel moves randomly. The theory is by moving a minimal amount of times to simply fill a 10x10 grid with a space in the middle randomly, after an amount of time he angel would randomly trap herself.
The thing is, if the plane is infinite, then the odds are also infinitely low. meaning not 0 but approaching 0 ever closer... What you are thinking of, is : if the devil has infinite time to fill a finite-but-huge plane. In the case of an infinite plane, the odds of being trapped doesn't increase as the devil fills a square because there will always be more squares that are not filled
@@AnimatedStoriesWorldwide well, the devil could just go an absurd amount of spaces away and build a enclosing barrier shape with a thickness of half of the Angel's movement couldn't they? Thus making the grid finite for the angel
Mathematicians will never stop to amaze me at how they can find the most futile and impossibly useless question in the world and not get bored out of it for decades
But you didn't really say anything other than the obvious. All you done is say the angel can win by "using some maze-solving argument" which you don't even bother to explain or at least show.
That's a much better hell than the traditional one, especially since you seemingly have a way out. If you needed a break, you could just stop. Or if you just didn't want to do it anymore, you could just stop. The devil would never get another turn and you'd be safe wherever you are.
Well luckily I found a solution, so you can look for my comment if you want, but I figured out that the farther away the devil starts building, the longer it takes them to build the wall, therefore making it impossible for them to stop you
How is this fascinating? "Here's a problem, and while the answer might seem intuitive, that's because it actually is. I can't/won't explain anything about it, just take my word that something something infinity has this result because...I don't know."
You always find morr creators and influencers pretending to be experts than experts that happen to be youtubers or influencers. That's why I like finding doctors or history professors on this platform.
But couldn't the devil just encircle the angel from infinitely far away, such that by the time the angel gets there, they are bound in by a band of spaces with a width that is either equal or higher to k? From there, the devil had confined the movement of the angel, and can just fill in every single block in that area at whatever pace he wants
I was thinking the same thing but the problem with that is, the further away that the devil builds his wall the larger that wall is going to need to be and the longer it will take to build, to the point that there is mathematically no point where the devil could build a wall that the angel couldn't breach before being fully enclosed. If we're talking in infinites, the devil would then be infinitely building his wall, leaving the angel to infinitely keep moving without ever ending up trapped.
Two things, the devil would need to travel the circumstance of the square while the angel only needs to travel half the length of the square, and the circumstance of a square is defined as 4 * length. However, if we ignore the divide by 0 error because infinity, well the devil created a box that is infinitely far away from the angel on all sides. Meaning that the angel still has an infinite plane which they can travel.
for every tile the angel moves the devil would need to place 4 blocks, else it can't counter the angel moving left right or reverse. if the angel moved infinitely left one space at a time the devil would need to place one square at the side of it, one at a time. if it started ahead of the angel then they could turn left, or right or backwards, even if the devil placed four blocks (which would end the game their and then as it would surround the angel in the first move) it would have to build up each wall with the pre understanding that the angel will always move in one direction and never divert course.
@@arthurvelwest5481 I don't know, I thought it was kinda interesting and it was a short video. If people are interested, they can always research it themselves :) I think it's fine to give a brief introduction to something and then let those who are interested research more if they want to.
If I understand the video right, if the angel moves in any other direction, then it is on a square it could have been on previously, thus giving the devil a free square which is then not a perfect game theory. I.e. the 1 block distance example. If I move directly to the side after ever moving directly upwards, I wasted a turn as I could have moved diagonally that time instead of directly upwards. Limiting the movement is what allows a game theory to be developed instead of a in-game strategy. Does any of this make sense? Idk I may just be flat out wrong
@@hedgehogcuber6848 but if the devil was busy in all of those turns building a wall in the north, there shouldn't be a reason the angel can't just deviate a bit, circle the wall, and then keep going north. It would be the devil who wasted time building a wall, because the space is infinite.
@@denkerbosu3551 Because the whole point is the angel can't move fast enough to do that. The triangle shown is how far the angel can go moving up. As stated before, because this is a game theory problem, the angel would never make 2 moves 1 move would do, and the angel would never move back to a spot he could be at previously. So, if the angel moved directly sideways, then it wasted a move, as it could have gone diagonally at some point instead of straight
Not exactly. Yes, being able to move in any direction is what enables the Angel to win, but you still need a specific strategy that took mathematicians decades to prove exists. A player playing without a strategy could be trapped by a properly programmed devil, regardless of the player's ability to move in any direction.
*FOR THOSE OF YOU STILL CONFUSED, READ THIS* *1) How can the angel ever win if the game goes on forever?* The angel wins if it can find a *strategy* to always avoid capture forever no matter what the devil does. We don't need to actually play the game to infinity to determine that, we just need to prove that the strategy can work in every case. *2) How can the angel really block 100 of its own spaces?* Those spaces aren't _actually_ blocked, they just represent sub-optimal moves because it gives the devil an extra move for free. We are trying to see if the angel can win (avoid capture). If an angle can't win with optimal moves, then in definitely *cannot* win with sub-optimal ones. Therefore, for the purpose of a proof, removing those squares does not change the win/lose result of the thought experiment. So it's safe to remove them, which makes the problem easier to reason about. *3) Can't the devil win by just building a big wall ridiculously far away?* No. You can build the wall farther away, but that means it will take much longer to build. The angel can always reach the wall in less time than it takes to build it, and therefore, can jump over it before it is finished. It only works when the angel's movements are restricted as demonstrated in the video. *4) Why didn't you explain the proof at the end?* It took over 20 years for a proof to be found. It is not simple or fast to explain! I linked the proof in the description, so if you're a mathematician interested in game theory, you can read it over. But given how much confusion there was about the simpler concepts in the video, I doubt the proof would be any easier to follow, at least in a short video like this. Regardless, I'll try to explain things like that more in the future at least at a high-level.
It's simple. The way the angel gets caught is if we assume that the devil and angel are making their moves randomly. This leaves us with a chance the angel will get caught. Otherwise: *Base Game Analysis* - Infinite grid - Presume the devil cant remove the tile the angel is standing on - Angel can jump any tile at most 10 tiles away (10x10 is an area of 100) - A definitive wall must then be at most 40 tiles thick (10x4, the extreme region of the jump), assuming a perfect jump from the angel (adjacency with the wall). Otherwise the angel could hopscotch through the wall - 40 tiles is 40 turns for the devil - 40 tiles is 1 turn for the angel - So 1 definite segment of wall takes 40 turns, but it takes only a single turn for the angel to outmaneuver it *Box Method Analysis* - Former case proves Angel has 40x the turns of the devil for every definite wall piece, meaning the angel can disrupt the wall every turn - Let us assume the devil goes 6000 tiles out and starts building his wall, and we assume it is a square box - the number of tiles would be (6040^2 - 6000^2), or 481,600 tiles, a.k.a. 481,600 turns - 481,600 devil turns would need to be covered in a single turn of the angel, or else the box expands. In fact, the closest the devil can get to boxing in the angel is through starting closer, not further away. Lets take him starting just outside the angels bounds at 11 tiles away - (51^2 - 10^2), or 2501 tiles or turns. With any one turn, the angel negates any portion of built wall. - Lets build an equation for this box method to prove it doesn't work: - Devil has to cover an area of ((n+40)^2 - n^2) tiles per angel turn, or that many turns in a single angel turn, where n is the number of tiles the angel can jump to - If we include angel jumps than the area need to cover increases every turn. The minimum shared area for a single jump is 25 tiles, so a maximum of 75 tiles area must also be accounted for (or 5 tiles distance. - if n = 5, then 5+40^2 - 5^2 = 2000, or 2000 additional tiles need to be covered for every angel jump. - so if we take the original equation and add our new figure, then the number of turns needed to box the angel (at the closest adjacency) would be ((n+40)^2 - n^2) + 2000j, where j is a single maximum jump. - the minimum equation would be ((n+40)^2 - n^2) + 1680j, with a one tile jump, where j is a single minimum jump (calculated using our formula at n=1) Conclusion: Under the conditions made clear above, the devil has an impossible goal of entrapping the angel - in fact, the further away he starts building his box, the greater amount of turns he has to take in comparison to the angel, who has just as many turns to escape the box. Alternative: If we assume that both are moving randomly, in non-calculated (or poorly calculated as is the nature of programmed randomness) jumps, then it is possible for the angel to be entrapped by the devil. Such cases could be caused by moving backwards, utilizing bad jumps, etc. It would take a long time for the outcome to fruition, but it is possible. It is also possible that the angel never gets caught in this scenario. If we assume that one or the other are moving intentionally (And not both), then the intentional piece will always eventually win. *Edit:* Of course the devil cant use a circle or triangle box without risking an angel jump over the wall unless he makes the walls thicker, an equation even I don't want to think about. No matter what, my conclusion is sound.
@@whenthedustfallsaway Hey sorta that. To be clear, there's still a reason it took them many years to solve this problem. The box method is simple to disprove, but only a simple box method. As they said, it is possible if the angel only moves in a positive distance from the origin, to block him in two directions. The problem is the angel can react to the direction you are blocking and go the other direction. However, then it might be possible to trick the angel into going back and forth about which direction to run until you have enough blocks in place to force him to lock him in. Such is the reason it's unoptimal to go back to a space you've been or could have jumped to.(or maybe not depending on the devil's moves). So it's been very difficult to actually define what the angel should actually do to escape(dependent on the devil's actions) or even that it can escape until now. Edit: typo
Without going into too much detail, does this hold for all values of K>2 as well? Also, does it carry multiplicitively like if the devil can erase 2 spaces per turn the angel needs k greater than or equal to four?
Ah, but that leads into a paradox. Let me explain: If, in order to beat the devil, you need to remain still - never moving - forever, so as to prevent the devil from ever being able to block a square, then that, quite obviously, means that you are doing nothing. And so therefore the devil never has a chance to do his work. This is stated in your comment to which I am replying, so I guess I don't really need to state that. According to Thesaurus.com, synonyms for the state of doing nothing include, but are not limited to: inactive; dormant; static; sedentary; idle... Idle. In order to do nothing, and by extension, prevent the devil from doing his work, you need to be idle. Isn't that interesting? Does that make you think of anything? It makes me think of something. That something is the very something I'm going to start my next paragraph with. There is a well known adage saying, "Idle hands are the devil's workshop". This adage stems from a Bible verse found in Proverbs 16:27. It means that by being idle, we are allowing the devil to do his works. Yet this is where we get into the paradox. Prepare to be astounded by a paradox I came up with that is on par with, and is on the same level as some if the best paradoxes such as The Bootstrap Paradox, The Potato Paradox, The Dichotomy Paradox, and The Raven Paradox. By your reasoning, we can prevent the devil from doing his work, and therefore defeat him, by doing nothing. But this saying says that by doing nothing, we are enabling him to do his work. Do you see where I'm coming from? This is the paradox. Does being idle defeat the devil, or allow the devil to do his work? At this point, you might be thinking, "Come on, Christopher Dibbs, you're already been rabbiting on for four paragraphs that none of us really needed to read, are you finished yet?" And you would be right. I am finished. And I did add in a whole heap of useless nonsense in to fluff out my point into four paragraphs - my point which could have been stated in one small paragraph. And yes, I am still going. Now you might be thinking, "Hold on. There are still seven paragraphs left... What does he talk about in those?" Well, allow me to expand. And I mean that quite literally. I'm am expanding this comment with even more paragraphs that have no reason whatsoever to be here. Have you ever noticed how when someone writes a really long comment, with many, many, paragraphs, you sort of lose interest the longer it goes on? Please someone say "yes". Please don't let that only be me. Well _I_ wondered that. And I wondered if I wrote a long comment that went on for paragraphs, would people lose interest? Did it work? Are you still here? Are you still reading? Oh. You are. I guess it didn't. For you anyway. Who can say how many other people left before this point. Ok, I'm kind of running out of things to say. So I'm just going to say a few random words that are completely unrelated: Construct. Wonder. Feast. Syndrome. Coal. Knee. Physics. Member. Accurate. Feminine. Lunch. Slam. Landowner. Stream. Boot. Pill. Carve. Beef. Thinker. Are you still with me? Oh. You are. Alright. Let's try this. I'm going to make a sentence, by only pressing the middle button of the prediction bar. (I'm typing this on my phone.) Yes, I am doing this for absolutely no reason at all. But maybe there is a reason... Anyway... I don't know what you mean by that I have my phone down here and the volume is up to you and I want apology for the game and their grammar is atrocious I don't know what you mean by that I have dude that was a very standard of living in the same house as I can send that to me and my mum is a person you can put on the shelf and put it on the shelf and put it on the shelf and put... Ok. I'm sure you can see what's happening here. It's stuck in an infinite loop. Enough of that. Let's talk about something... Some stretch of warm weather we're having... Ok, that's too cliché. Let's talk about time. And how it's an unstoppable force marching us all to our inevitable deaths. Time. Time is a tool you can put on the wall, or wear it on your rizt. The past is far behind us; the future doesn't exist. Time. The amount of time I have spent slowly but surely typing out this comment is measured by time. In case you were wondering, the amount of time I have spent typing so far is approximately thirty-seven minutes. Which is exactly thirty-six minutes, thirty seconds longer than it needed to be. I really am wasting my time. Ok, this gag is getting old. I think I'm going to end it here with this final paragraph. I think I've proven my point that absurdly long comments cause drops like that meme format: "Breaking News: Attention span and interest has dropped to 0%". So if there is anyone still reading, which... Oh. There is. You. Ok, this is for you: Thank you. Thank you for reading this stupidly long comment. Thank you for wasting your time. Thank you for everything. (Also, I'm sorry.) Just kidding. This is my last paragraph. I'm going to leave you with two things: one is an inspirational quote that I live my life by, and the other is a video expanding on the actual original topic of this comment. Did you forget about that? The actual point of this comment? I have. What was it again...? _"I'm stupid, I'm ugly, I'm dumb, I smell. Did I mention I'm stupid?"_ ~Some guy no-one cares about. Here is the link: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-dQw4w9WgXcQ.html And once again, thank you, and I sincerely apologise for your decision to read this.
@@Chris_CrossImagine you're truly immortal, in space. You jack it. Eventually, you will ejaculate. That ejaculation will give you a tiny, miniscule amount of thrust. You jack it again the next day. Hell, maybe that same day, I don't judge. Same result. You shudder, a tiny amount of thrust. Then again. And again. And again, over eons. You will go faster and faster. Incredibly slowly, yes. But faster still. This is how ion engines work. Tiny amounts of thrust, but over long enough time scales you get serious results. Eventually your jacking will propel you to an appreciable fraction of the speed of light. You'll be propelled across the cosmos at the end of light years long stream of gossamer wads.
If the Angel can move 10 tiles per turn, then the devil would need to build the wall so far away that it would take an unreasonably large amount of time to reach it; and he would need to build it on all sides of the angel, making the needed distance 4 times further away than it already was. Then it also needs to be 10 layers thick to prevent movement through it, making the distance needed an extra 10 times on top of that. The Devil could never win in this scenario, because for every tile further across he makes the box, that's an extra turn he needs to spend adding a single block to it in order to get to the other side of the angel and block it in, at which point the angel has already jumped 10 spaces closer to the wall itself which wouldn't be able to hold it. Even if the wall itself was 10 layers thick and the angel couldn't pass it, the devil has no way of adding in an extra side to it which is also 10 layers thick, resulting in the angel escaping and the whole process starting over again. The only one the devil can win is if the angel only has one tile of movement, as building that box around them becomes much easier.
So unless the angel is stupid the angel always wins... but the angel can't win because they have no win state so the game never ends and a stalemate continues eternally.
The critical thing to consider is that increasing the angel's maximum movement speed necessitates a wall with greater and greater thickness, meaning that while the angel's speed scales with N, the devil's task scales with N^2
Because if you went backwards at any point you would be in the same game state as the turn before except with 2 extra bricks which clearly does not help you. If you then continue backwards the devil can just repeat that exact same strategy. You can only turn twice more because aventually you will be blocked off on all sides.
@@finn596 the idea is that if it can spend 30 years building a wall 800 miles ahead, then the angel just turns around, it can just spend another 30 years building another wall 800 miles that way. It's supposed to build the wall so far ahead that by the time it is reached it can't be passed. Ideally it would build the wall farther than necessary such that it can build walls that would be finished in any direction before it was reached. So for example spending 480 years, to start walls in 16 directions, 12,800 miles out, alternating among them rather than assuming any one direction is taken. But apparently the best it can build as an infinite maze, if the angel is careful. Though if not the angel is trapped.
@@kamikeserpentail3778 well actually it is not ideal to make it farther than it should because that takes more time to build, you can't make a cube like that in time because it would take 51,200 turns to make it and the angel will almost always be able to pass it in time, even if the angel is making some horrible decisions it could probably make it. (I could be horribly wrong though)
But there is no victory condition for the angel. What is the goal for the angel? If you would make a game like this the player would be the devil, not the angel.
It's a mathematical game with no human (a.k.a. fallible) players. The victory condition is the proof of existence of a strategy the angel can employ that the devil cannot win against.
And then the angel just moves. It doesn't care if I can move to the space it is currently on, only if there is a space within its range that it can move too.
To put it simple tho No matter what the distance is where the devil will start his wall He would require around 4x more turns to create that wall than the 2 block speed angel as the turns required to build the wall heavily out matches the advantage distance gives him If anything the further the distance the more openings the angel has Around 9x if the angel moves by 3 Heck around 100x if the angel moves by 10
its because the time to build a wall able to stop the devil, the angel could just go in a different direction. if you are thinking “just build a wall evenly all the way around” no, it would require too many turns. its not like the angel isnt going to see the trap (im assuming they can zoom out/see all devil moves) theyre moving towards anyways, so the angel will just keep going in a separate direction. by the time the devil starts attempting to build a new wall, the angel could just go up. rather then left or right.
@Noon Kelso its infinite time and space so the devil can start infinitely far away from the angel and start building a ring and spiral inwards, this will take forever but he will eventually get there
1:14 "it strictly benefits the devil". No, it does not. Changing course and going back may render the devil's move useless, then it's neutral. It even may render multiple moves of the devil useless that the devil made in anticipation of the previous direction, thus benefiting the angel.
But cant the devil just go *REALLY FAR AWAY* then make a box to trap the angel in and slowly but surely fill that box in. I'm thinking quick here but can't he? Edit Read the reply's as this has been disproven and I was a bit dumb haha
ye but devil has to get wall thick as X amount of blocks Angel can move soo Angel can't just jump over I think yes this would work but you have to start really far(depending on how far Angel can jump) but I do think it's possible
@Eric Krampitz the space is infinite and if devil can also move in any space then devil might have to go really far away but it's not impossible hard but not impossible
@@Snowclimb The further away the devil starts, the longer the sides of the box must be. As the devil starts further and further away, the time to create the box grows faster than the time the devil gains.
This also assumes the angel will go in that direction, angel can just go far enough in either direction making the devil's blocks a wasted effort. This is infinite space after all.
There seem to be a lot of people who are taking the Devil's time into consideration, but not the work he has to do. The further he moves out, the more work he has to do and the more squares he has to fill, meaning he has as much a chance of capturing the angel at the beginning as he does an infinite distance away. Yes, he's infinitely far away, but that also means the box needs an infinite amount of time to build, rendering it completely useless and the angel is able to easily escape. They are relative factors and people aren't recognising both, instead just targeting one and disregarding the other.
“The angel would never want to move to a space that she could have landed on previously. It’s impossible for that to be helpful.” Ok but at 2:08 you show a situation where it would CLEARLY be beneficial for the angel to move back to a previous square.
Except in that situation the angel would have had even more clearance by moving down from the start. Sure backtracking can be a viable solution, but it will never be an optimal solution in a given scenario: for any solution that involves back-tracking you can deduce another solution that doesn't do any back-tracking and advances even faster.
@@user-pk9qo1gd6r Here’s my problem. The title says “GAME THEORY” right? As in, you make your decisions based on the decisions of the other player. Backtracking isn’t just a loss of one move, because at that point you would have more information about what your opponent is doing than you did at the start. Sure it would have been more beneficial to go backwards at the start, but at the start you didn’t know where the devil was building a wall.
does the devil know which amount "K" is? if yes he could build a large ring far away which the angel can't travel through, and slowly spiral its way to the center. would take a long time but the angel could never win. Or am I wrong?
That's what I figured too, but if it's been proved otherwise I guess not. I'd be interested to learn more about the proof. Perhaps the amount of time needed for the devil to construct the ring grows faster than the time it takes the angel to reach it.
and this thought did not lead you to the question of how FUCKING LONG it takes to build such a ring? the FURTHER it is away from the angel, the bigger it becomes.
Exactly what Jered and Dave said: there is no distance at which you can build the ring and be faster than the angel. You could probably try building a quarter-ring in the direction the angel is going but the angel can always change direction by however much he wants.
@@buttonasas though, as the video explains, it is not EASY for the angel to avoid the blocks of the devil, since changing directions too much means giving the devil more time to build the wall.
@@nala105 as x increases, the angel gets faster and the devil slower in building the wall. For x=2, the wall would be built 4x slower than the angel can travel. Even in x=1, the devil would still need +1 turn to build every corner of the box so that the angel can't escape. So, as long as the angel is a omega player, the devil can't possibly win.
it's less about trying to win as the angel and more about mathematically proving WHY the angel always wins. It's easy to figure out that gravity will pull on a ball you drop, but it's a lot more interesting trying to figure out WHY gravity pulls a ball when you drop it.
Some things to consider: 1. When the game starts there are 2 known factors: There is an angel and there is a devil 2. The angel has omni-possible directional movement at all times within a certain distance. 3. The devil can appear anywhere and remove 1 square from being habitable each turn. With these 3 conditions we can ascertain certain things: 1. First of all, just because a line of inhabitable squares exist within a direction of the angel, does not mean the area beyond is unreachable. If the Angel has a maximum travel distance of 10 squares in any direction any given turn, so long as a wall is less than 9 (X
From what I understand here you’re assuming at least one of two things. The angel does not know what units have been removed, and/or is not employing the best possible strategy. Assuming one of these is true, then the devil does have a chance of winning with your “Door”, although very slim, as the door would have to be wide enough for the angel not to see the sides and realize it is a trap, thick enough to prevent the angel from simply jumping over, and big enough that the devil will have enough time to completely fill in the door by the time the angel realizes and goes back the other way. However, assuming the angel does know where the devil is at all times and uses the absolute best strategy, there is no hope for the devil. I’ve seen many people arguing that because the space is infinite, the devil could build a box infinitely wide. But even assuming that the devil would be able to construct this box wide enough before the angel reaches an edge and simply hops over or goes around it (which it can’t), if it is infinitely wide, the devil will never finish it. Because it’s, you know. Infinite.
I know I’m extremely late but the angel can see all of the moves the devil makes. There are no secret moves or deception involved, and the paper assumes perfect play. It’s like a game of chess, you can’t cover your side of the board with a cloth to hide your strategy. All game information must be made available to both sides.
It's expands absolutely exponentially because it's on an infinite grid, the devil could only win if the angel stayed within a confined area for long enough, but it would take too long to be realistically possible against anyone/thing playing strategically as the devil
I understand why the angel wouldn't want to go back to the exact space he was on, but what's wrong with going back to a space he could've gone to before?
The devil removes as many tiles as turns you took to get to a certain spot. If you go from A to B in one turn the devil will remove 1 tile. If you go from A to C and then back to B the devil will remove 1 extra tile for your step to C so he removes 2 tiles (or more if you take a longer path to B). But you didn't gain anything. Anything the devil would remove once you move to B from A he can also remove when you go to B from C. You just gave away a turn to the devil. It doesn't really matter where the devil puts his C tile, no matter what tile is removed it is either very bad (it was an important tile for you) or not so bad (because you didn't want to go there anyway) from you. But if the devil "wasted" the turn he got for free, he got the turn for free because you wasted a turn first. And a not so bad outcome is worse than a neutral (moving from A to B in 1 turn when B) or a good outcome (there are none, the devil can always keep chasing).
The devil gets to remove two places for the price of one if the angel takes two moves to get to a spot she could have got to in one move. For example if the angel moves 5 to the right, then 2 to the left, then 5 down, the devil takes three places away. So the angel should prefer to just move 3 to the right, then 5 down. The angel is in the same place in the second strategy, but the devil has only removed two places.
Also worth noting: This argument works when you're assuming the Devil and Angel are playing optimally, as all game theory problems do. An angel that made a mistake and moves back to a square **may** still be able to win, but we always want an optimal angel in a proof.
it is balanced, the angel has a wide range but must survive while the devil can go anywhere but has to win. and the answer to the problem proves that even given an exponential amount of time the devil is not guaranteed victory
@@Killer97 you just contradicted yourself. even if given a super duper amount of time, the devil will not even win. therefore the angel's circumstance is far better than the devil's.
@@xkilla911 no I didnt I said he isnt *guaranteed* to win meaning if they were it wouldnt be balanced, since the devil must outplay to win and the angel must outplay to survive and doing random moves could go either way, its balanced
@@Killer97 the angel does not have to outplay to survive, once the devil builds a wall in his way he can just go change his course by 90° and fuck off the devil cannot win, this entire question and its ruleset is heavily favored for the angel
The Angel would get there faster than the wall is built cause radius is always less than circumfere. Also for him to not just jump over the wall it would need to be 10 blocks thick so 10 times the radius
@@hk-ex4gw yeah but nothings stopping the devil from making it just near infinitly far away itd take ages but eventually the angel cant move out of a massive grid
Say if the wall is on the right, going 100 mil blocks up and down, the angel just needs to move downwards or upwards enough before the box can be created, so no I don’t think the devil wins that way
@@user-hv6gi9ux6z that doesn't make sense cause again no matter how far away you would need to built the circumfere of the circle times 10 while the angel only needs the radius of the same circle. Devil has no winning chance
@@user-hv6gi9ux6z you don't understand bro. No matter how far away the angel will always outrun the devil. The radius of a circle is always less than the circumfere
The simple answer to that is commonly no, but to further explain WHY its not possible most of the times: If the angel has no clue on what the devil is doing then when faced with big walls or tons of taken spots it has decisions to make that make the game way too luck based at times. It can choose to continue in that direction and hopefully find a gap and jump it if its a wall or hope that the random blocks placed around it arent forming a box and keep moving. If the devil also had a set "spawn" position and limited vision/knowledge of the area (whitch is more fair) it would badically be utter chaos on both ends as the angel tries its luck with moving and the devil making arbitrary boxes that might not even be in the right spot. Thats why the game allows for the angel and devil to both know everything.
@@maestrofeli4259 Yeah, but with mobs, textures, particles, the ability to change de world as you may desire and the fact that it´s in 3 dimensions. I don´t see any trouble for creating an almost-infinite 2d grid nowadays
@@leosamurai1910 The minecraft world has a 30 million squared blocks of space before the world border. After that, the world starts breaking down and glitching.
@@speedwagon1824 hold it! It isn't glitchy in java edition at all! If you would delete the world border and try to continue generating world, it is almost fully stable with no bugs at all! The only reason they made world border, IS BECAUSE MAYBE IT WILL LAG A LOT WITH BAD PCs!
*_EDIT_* Nevermind, I understand now. The gist of it is that the math takes advantage of the fact that for every 1 square larger the wall is made, it takes the devil _4*k_ (with _k_ being the speed of the angel) more turns to create it. *_ORIGINAL_* Wouldn't the fact that the plane is infinite and the devil is able to block a square literally _anywhere_ means that - as what was pointed out at around 2:20 - the devil simply has to create a wall far enough away that the wall would never be able to be passed? The only remaining questions are _How far away from the origin point does the wall have to be for it to be impenetrable?_ ; _What's the most efficient way for the wall to be constructed?_ ; and _How long can the angel last?_
You're falling for the 'infinite fallacy. The amount of time it takes to build the scales directly with how far away the wall is. The amount of time it takes the angel to reach and pass that wall is always going to be smaller.
I agree. From my non-proofed perspective, at a certain K the angel can travel both the radius and the circumference before the devil can fill the full circumference. I'm sure there's an equation which can describe the breaking point between the angel's speed and the one-block-per-turn speed of the devil. Maybe where angel radius+circumference travel is equal to the devil's circumference travel? This would mean that the angel is fast enough to go outwards to the wall and work its way around the interior of the wall until the very last gap where the angel slips through before the devil seals it off.
They're not restrictions. It just eliminates suboptimal moves for the angel. If you wanted to allow those squares, that would be fine, but since the angel's taking more steps to reach the same square, the devil would be able to build the wall even faster. If the devil can trap an angel making optimal moves, it can also trap an angel making suboptimal moves.
@@TheEnderLeader1 seriously the angel just need go in a straight line and change direction as needed. With 5 blocks radius applied, I tried to play with my friends, the devil may temporarily block some of the spot and eventually the angel still get out or just jump the block, no need to change direction just because the devil is there.
@@Apsolon yeah dude, you, a human, played against your friends, which are also humans. This means both of you probably didn't take the most optimal moves every round, therefore making your empirical experience useless
In an infinite board when it comes to logical game theory, it'd be impossible for the devil to beat the angel if both were on the same skill level. Only way the angel would lose is if they only moved In a predictable manner and never strayed. 10 squared has a lot of possibility and just because you could move to a stop in the past doesn't mean you cant move their again, thinking that way can give the devil an edge and understand where you'd move next.
There is no question of skill here: the question is just whether, for any given move sequence of the devil, there exists a move sequence for the angel such that it will never get stuck.
Here's my summary of the proof for those too lazy to try to read it. This is actually just the proof that if the angel has an arbitrarily large number of moves (let's denote k) per turn it can win. The proof goes on to prove this for k=2 but I can't be bothered. There's a slightly complex first part where it is explained that you can state the problem in the same way if you consider the devil to never eat a square where the angel has already been or where it could have gone. I don't feel like parsing this part out and it seems mostly seems intuitive so just assume that that's true. First, you reduce the problem. Instead of an angel with arbitrary movement, pretend the blocked squares are a 2d representation of a maze from above. Suppose the entire left side of the infinite grid has already been eaten by the devil. The angel in this case is going to follow a strategy where it runs (let's say up on the infinite grid) while keeping it's left hand on the wall (the line of blocks formed from all the blocks the devil already ate, which at turn 0 is just the line of y=0. The angel moves for t turns. Naturally, the devil has placed t blocks. This means there are 4t edges to these blocks, and since all the existing blocks face north the angel can only move south if it's on newly placed blocks, meaning it can only move south in this time at most t blocks. Thus after time t the angel must have moved at least kt - 4t -t, or in other words kt-5t blocks to the north. It's obvious the angel can't be blocked in after 2 turns (you literally can't enclose it in 2 blocks), so let's say t is at least 2. Now say k is at least 11. This is a proof for an arbitrary k, so it doesn't matter what we choose. Now, you can see that the angel will have moved at least 11*2 - 10 = 12 blocks to the north. The angel CANNOT have looped back to the origin. And if it hasn't looped back to the origin, then that means it always hasn't been trapped (assuming the devil isn't moving where it has already gone). Thus, as t grows it can be shown that the angel is never forced into a loop, meaning it can't have been trapped. The proof is obviously more thorough than this simple explanation, but I wanted to give some sort of summary rather than just saying "it's too complicated". Also, unrelated but these comments are very dumb. I know I shouldn't expect much from youtube, but come on.
i like ur comment, not because i understand the meaning (i have poor english) but because the effort u make to make people who read it understand (maybe). keep it that way. world needs a hero like u.
Then the Devil builds a large, not infinite but large enough for the Angel to not notice they enter till they hit the bottom, U shape container incredibly far away, building multiple so if the Angel gets in it can close off the U into an 0 meaning they win. Also the Angel has no win condition which ends the game, which means it goes till the devil wins which in turn means the Angel must lose. Rather then trying to build a super wall or anything complex you just need to make a basic shape far enough away and large enough. Since you have infinite time to make an infinite amount of these eventually the U trap will win.
@@Buglin_Burger7878 the simplest rebuttal to this strategy is just that the angel would then move in the opposite direction of the u shaped container. Ignoring this, and assuming you meant something like an enclosure, such as a square, rather than a U shaped container, if the angel is moving more than 2 spaces per turn, by the time the angel can reach the perimeter of that enclosure, however large, it wouldn't yet be built. This is easy to see in the case of a square, since the devil would take 4s turns to complete the square, where s is the length of any side of the square. The angel would take only s/2k turns to reach the closest point on its perimeter, where k is the angels possible move perimeter. It's easy to see 4s>(s/2k) for any non-negative integer, so the angel could always escape. As for the second point you've raised, it is also misguided. You're looking at the problem wrong. It's a game theory problem about optimal play. You don't consider the angel and the devil as human players. The question of the problem is whether there's some strategy that the devil can do that could 'checkmate' the angel, or in other words for which there is no counter-strategy. As long as the angel had a sufficiently intelligent strategy, such as the one I suggested in my original comment, it would never be 'checkmated'. So in a finite time scale it would never win, but it would equally never lose. And that is the win condition of the angel, but more importantly the answer to the question.
Assuming the angel can see what the devils moves are, the angel can just keep moving in one direction and move diagonally whenever a wall is being built, because the angel can move 10 spaces to the side for every 1 space up, if the angel is moving upwards. So for every 1 space moved to the side the devil needs to place 10 squares to counter and as the angel can move 10 spaces in 1 turn, the devil would need 100 blocks per turn to build a wall that could stop the angel from moving in a specific direction, but the devil only has 1 block per turn, so the angel has a 100x advantage over the devil if the angel decides to limit themselves to 1 direction, and I haven’t done the math, but I would imagine that number becomes way higher when the angel decides to move in all four directions
"The angel blocks 100 blocks" Not if you don't care and just go backward, you goal is not to make distance, but to avoid being trapped. There are no rules preventing you from making a u turn. While the devil is making a "wall" up north, you just change direction rendering his progress there obsolete. It would require a lot of counter planning, but it is 100% doable
I don't think you understand. Moving to a square you previously could have just lets the devil put a free tile somewhere, since he can place the tile he would've placed had you just gone there the first time, but now he also has the tile(s) that he placed during your u turn.
I thought exactly this sure it's not a "perfect strategy" but if you only play against a player expecting them to make the most logical moves, they can easily beat you cause you overestimated them
You're not trying to trick the devil here. Because you're inherently not playing a single game with the devil: instead, you're playing *every possible game* . the point of the problem is for the angel to find a winning strategy *every time* regardless of the what the devil does, and because of this you can assume without loss of generality that both move optimally and therefore the angel never goes back to a previous square - because doing so is never an optimal strategy, even if it still ends up working.
The Angel can actually exist if you charge up as Ness in Undertale so long as you are actually dead and have been killed by a force equivalent to one bullet bill but only if your adopted and a single celled organidm
I know a game that works like this, instead of an angel there is a cat and the goal of the game is to capture the cat. The map is small and instead of squares there are circles and the cat can move one circle in each turn, but the idea is similar
I mean the angel could just keep moving to the top right square or the closest nearby option, and switch directions if the devil starts setting a trap further down
tobey sherrin so turns out he couldn't, because he must keep going forward, even if leaning left or right - otherwise the devil could employ the same wall strategy for the other side, but this time he has many squares set up in the angel's path; This is why the angel can't use any points he's already been on, or could have gone to in a previous turn, because the devil could employ any strategy as many times as he wants on an infinite grid and therefore it's of no use to switch directions if you were already on that square. Remember that the devil can also just triple his distance for any given direction, in order to capture the angel in that given direction.
@@edgeisloveedgeislife5439 but for every failed trap the devil sets, the next trap takes longer to build. If the angel simply dodges a few thousand moves to one side, then the trap that took several million moves to create is utterly wasted and the devil has to start over.
That would take an eternity, literally. Because trial and error will always end up with the devil winning. Indeed, the parameters of this game only allows for _one_ victory condition: the angel has no valid moves. Only then does the game end. The game continues indefinitely until the devil has won; there is no provision in the rules for the devil losing.
To add onto this, I find this to be a very interesting question. A point in favor of the AI -- computing power has _massively_ improved over the last 20 years, and both our technology and our techniques will continue to improve. This wasn't a problem that was solved with pencil and paper; our new computers will be such a huge help. But how do we teach the AI how to go about solving the problem, without directly providing it with the solution? If we use the classic machine learning of "try things randomly, get rewarded when they work, iterate off your most successful attempts" things will take forever. We have no framework to reward the AI for making progress---what are we going to say, "Oh, blocked off 5 out of the 99 possible moves the angel had available. Good job!" That won't work, that would set the AI on pursuing a short term goal with no hope of ever grasping the bigger picture. And in this scenario, are we trying to train the Devil, or the Angel? Or are we training both at once--they're both making mistakes while they try to learn the game? When do we call the round and reset? There's just no way with your run-of-the-mill machine learning. But on the other hand, if the AI understood what its goal was and how this game worked, it would be able to solve the problem. It would take a long time if the AI tried to brute force the solution, but if the AI had even a rudimentary framework for trying strategies, it should be able to handle this relatively simple problem. And if this AI had even half of what we'd call "intelligence," I don't see it having any serious roadblocks.
Tom C. You do know we are looking for an abstract proof/disproof that the angel has a winning strategy? That is different from training someone to be „good at the game“.
He said he wouldn't go back to the place where the angel went, but the video stipulates that he can't go back to the full range of movement he's been to before. Wouldn't the situation be different if it wasn't the space where he could go before? I wonder why he said he couldn't go all the way to these spaces.
As the guy in the video didn’t want to explain it, I will. Bassically what we want to do is draw an imaginary wall on the left of our angel immidiatly after the start of the game what this will accomplish is divide the world into the left and right set(they are on the right and the left of the angel and not starting coordinates). Each time the devil blocks a square we try to make a move that will move one(or more) of these blocked squares into the left set and we will move two blocks north each time. As the devil has the power only to block one square at a time we will be able to outrun him. I might be incorrect tho because right now it almost midnight for me and I havent slept for a long time, there are also a few solutions but this is the one I chose.
the answer was literally a maze-solving algorithm. Having made one before, and seeing as there exists infinite possibilities of the game-state in the game presented, explaining the options the maze-solving algorithm can take would literally be an infinitely-long video. He could, I suppose, give a few examples of the Angel making algorithmic decisions dependent on the current board state, but the choices would be, honestly, just boring and bad video material. "There is a grey square here, here, and here, so the Angel decides to move here because of mathematical mumbo jumbo and such." Trust me, in this case, the explanation would be far beyond boring and fruitless to explain.
@BBOX 360 the problem lies when the angel can move 2 or more blocks at a time, allowing the angel to move twice as fast while requiring the devil to build a wall thicker and thicker(else the angel just jumps it). For a million blocks away, you need two million devil turns to make a two block thick wall but only 500k angel turns to get there. Thats why the angel always wins when the angel can move two or more blocks at a time.
![The Angel Problem [Game Theory]](/img/logo.svg){kind=logo}
