The Angel Problem [Game Theory]
ฝัง
- เผยแพร่เมื่อ 6 ธ.ค. 2018
- 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
![Can You Escape The Goblin? [Math Puzzle]](http://i.ytimg.com/vi/V0V3LMK40iI/mqdefault.jpg)
Of course the angel can win. She can win by not moving, thus not allowing the devil to move either. The Sans strategy.
“ A strange game. The only winning move is not to play.”
@@vestlen I understand this since somehow TH-cam recommended Tetris to me..
i mean if angel cant move mean she is traped
Ah, a fellow undertale fan.
😶
Plot twist: He only did this video so as he could have an excuse to say those Devil puns
100th like
Is it really a plot twist if we all saw it coming
Plot twist you watch owl house and i watch star vs the evil forces
Hi, King.
Never replies back
“You’d think the angel can win easily. In fact, she can.”
lol
*proceeds to not explain how she does so and ends the video*
"In fact, she can will hardily, and it took us over thirty years to make sure of that"
@@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."
@@LazarusIsBackBaby "the angel can win, but Isaac wants that fucking pentagram"
First 3 minutes: the devil will always win!
Last 30 seconds: the angel can win, with a k as low as 2!
**does not elaborate further**
Sigma male grindset
Like he said, it’s complicated. The second paper in the description is the one that has the proof, if you do actually want to see it.
This video is 3:28
@@Koiiijshut the hell up
@@Koiiij The devil removed those two seconds.
CodeParade: "You're an angel, on an infinite plane."
Me (blushing): "Heehee, I am :)"
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
Mc Diggles
hehe, i am :)
Wot
@@ploofthesheep2887 wait what
I can be your angle and yuor devil ;)
i'm more confused then i was before. "You'd think the angel can win easily. In fact, angel can win easily."
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
@@nala105 the farther he is away, the more wall he needs to make. Still can't win
@@TrekWarlord yes it will take very long but we aren't talking about time period it is possible but It will take very long
@@nala105 it's an infinite grid. It's not possible.
@@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
-States the angel can win
-Refuses to elaborate
-Leaves
Because you wouldn't understand it, illiterate nobody
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).
@@erdemmemisyazici3950your speaking a new language to me
He literally did elaborate that it’s complicated math proofs
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-
How many more settlements
pft 🤣🤣🤣🤣🤣🤣🤣🤣
Ye
Then he starts building one to the west lmao
Build a wall all around
Solution:
Build a wall and make the angel pay for it.
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.
@@BoulderInTime he was joking
@XeuNyx Cypher r/wooooshwith4os
r/ihavereddit to you all
with it's soul of course
It would be cool to see someone design an AI for the angel and devil, and have it run at an extremely fast speed. Could see this in action
Haven't you watched the video? Not even a super computer could handle those numbers
@@xicufwm doesnt have to be literally infinite, just make an ai to pick the best option and have it run for a set amount of time.
@@DuckInGameStop quack quack (translation: shut the fuck up)
@@duck_mcfuddle But you still have the infinite space. It's impossible to make a large enough simulation.
@@ILubBLOfficial it's impossible to have a infinite space on computer but it just could generate the space while playing ?
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
fr lmao
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.
I played a similar game once too, except you had to trap a black cat. Forgot what it was called though.
I remember something like that on CoolMath
also known as "Trap the Cat"
It's only possible on a limited plane when the cat or "angel" only have a K factor of 1.
Its Angel* right in the title,
@@spark1400 Chat Noir, at least thats the flash game I played with this same concept, and it was played on a hexagonal grid rather than a square grid.
*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"
Yep, at that Point you Just wasted 3 minutes of my time saying yesnoyesnoyesnoyesnoyes
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
research it yourself
@@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
He never explained the strategy of moving to a square that isn’t blocked off
This man is a genius
@@cubicallaboratory2063 not a genius at explaining things apparently
@@cubicallaboratory2063 a genius who like to add his own rules to a proven theory
@@wuskevo How could you say something so controversial yet so brave?
Oh gosh I didnt mean to type that
In simple terms, "the angel always wins, but if I imply rules I never told you that existed then the angel doesn't"
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."
what are the rules that were never implied huh?
@@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 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.
@@WhyYouMadBoi The only issue with your view is that the devil can block any space in the board regardless of the devil's current position.
@@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.
Made me watch the whole video and then just skipped the proof entirely
fr, useless video that taught me absolutely nothing
@@omiddorrani9283 that's cause you wouldn't have understood the proof, kiddo
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.
@@omiddorrani9283 You're confusing me with the person above.
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.
Eleanor Drapeaux accurate
@@HereWasDede How accurate?
The secret is that its actually the boring part, but its probably in the writeup somewhere. Probably not great video material
Thanks Eleanor
Maths at a high level is extremely abstract and is far beyond the scope of the video
“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.
Not necessarily, this really only works on a finite plain
@@TheCrashtestCZ there’s technically a chance if the angel moves truly randomly, but it’s definitely not a quick or effective method
But you would also have to leave one extra space open, to allow entrance to the trap
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
I imagine in hell you would be forced to play this game until you find a strategy to win.
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.
@@LMFAOdudeification But your in hell...
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
Yeah I got a strategy, avoid the devil.
The it restarts
Why not make it a game that *two* AI could play with each other?
My thoughts exactly,each AI would try to come up with the optimal solution to their situation,and the game can be sped up to conserve time.
Because you can't simulate an infinite grid?
Neloka yes i can
And when AI become sentient they will enclose the earth with weaponized space ships
@@neloka4313 You definitely can, with mathematics. It's just hard to graph one.
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.
Yeah this tuber is an idiot
Video got re-recommended to me and I wondered why I gave it a dislike last time. Now I remember :)!
@@business_casual_rex considering you just called him a “tuber” you’re also an idiot
That's how clickbate works. We came here to find an interesting game related problem solving and instead found a 3 minute long word diarrhea.
I love how the problem is solved if the angle just didn't move in one direction
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
Well that's not quite it. He mentioned that the devil can also start constructing a wall to all sides, just even further away.
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.
Is it just me, or did he not actually explain the solution?
"Only recently proven". 99.9% of people wouldn't even understand
@@nielsliljedahlchristensen4924 that's fair, but also why make a TH-cam video about something if you're not going to explain it?
@@arthurvelwest5481 read the description
@@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.
@@arthurvelwest5481 Probably to let people know an interesting problem exists, and a solution has been found.
damn matpat sure does sound different
Please make a roblox letsplay thanks, ,
@@tofidu ?
@@tofidu wdym
Eh
@@tofidu stop
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.
@@leotamer5 circumference is only for circles btw
Sorry for the pedantics
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.
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.
Until God intervenes and plunges the devil into the depths of Hell
the angel's win state is showing that the devil can't win so he gives up.
If the angel doesn't move, then the devils work can never continue. Thats how you stop evil >.>
If you don't move because of the fear of the devil so the devil trapped you 😈
Maybe the angel isn't trapped because of the devil. Maybe the devil is the one who is trapped, and just because some asshole didn't let him be.
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: th-cam.com/video/dQw4w9WgXcQ/w-d-xo.html
And once again, thank you, and I sincerely apologise for your decision to read this.
@Shreerang Vaidya Copy + Paste?
@@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.
*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.
Ok now sum it up in one word
@@amyvalentukonis6306 yes
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?
I've found this channel again and wow it has gotten much better since I last found it!.I love it
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.
Just build the wall further away
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.
Maybe it could be one of those games where the only goal is a high score, like temple run
What is the end game for a human
Have you ever played Pac Man?
@@finding_aether death
The devil wins. He can basically draw hentai.
:)
Lives the devil
Underrated.
Oh shoot- kid weeb away!
FUCK YEAAAAAH
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
Imagine walking upward when you don't need to. If the devil isn't harrassing you why follow your random rule that assumed he was on your trail.
What?
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.
The devil: *spends 30 years building a wall*
The angel: *turns around*
@@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 that's just a theory, a ga- *gets tackled by a cop*
An actual game theory.
@@lagg1e A game theory theory.
Angle : bro, stop following. Like, seriously.
Demon : nah man. i’m good.
"Angle" lmao you dumbass
THE1NONLY1 ever heard of mistake?
Angle : bro, stop following. Like, seriously.
Demon : nah man. i’m good.
Angle: No, you're evil. If you were good, you'd be an angle.
@@Lord_Volkner *_Angle, a mathematical terminology-_*
@@drifter2391 The best you can do is call people out on a typo. Get a life.
so i guess the angel can just move faster always to escape the "death box" no matter how far out the devil starts it?
Everyone: It's impossible for the Devil to win
Me, an intellectual: *Removes the spot the angel is standing on*
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.
lmao "the proof is pretty complicated"
WELL THATS WHY I CAME TO WATCH.
lol im sure I wouldn't understand it anyways
Using k not less than 2, the angel can just jump through the unfortunate 1 thick wall.
It would probably take at least 20 minutes to fully grasp the entire proof, and you would be bored to death.
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.
@@matthewmondilla6752 20 minutes ? youre making assumptions about peoples understanding of pure mathematics
The angel isn't actually removing squares as it moves, so if it encounters a wall, it can just turn around.
But then, the devil builds a wall in that direction too
@@Ghi102 But they can skip over that wall.
@@supermatt87
its build a wall which it cant skip
@@chongwillson972 not fast enough, unless the angels movement range is extremely small.
@@thefinestsake1660
the devil just needs to build far far away .
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.
“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.
angel
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.
I thought it would be really easy to escape the devil, but that was when I thought he also had the K square boundary.
wait what he doesn't?
@@awesomevideosonyoutube Nope. That is never stated. Each round he can block *any* square in the universe.
He said "The devil can remove a square anywhere on the infinite grid".
Yeah I went from "impossible" to "oh wait" quite quickly there.
@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
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
@@nala105 exactly
@@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.
Matpat really outdid himself with this one
I was hopping a game theory reference or at least a joke at the end, THANK YOU!
_You're an Angel_
Me: *No I'm not*
The devil, you say!
@ARTEM DORDZHIEV what's a aethiest?
@ARTEM DORDZHIEV Bruh
ARTEM DORDZHIEV it was good enough
@ARTEM DORDZHIEV that's supposed to be bruh moment but bcz of my stupid -ass- mind i just simply reply "bruh"
ah yes
*another os those videos that never stops appearing in your recommended until you click on it*
Angel: **moves up**
Devil: **blocks the path**
Angel: **moves back**
Devil: 🗿🗿🗿
i just want to say, i really love your little character dude
This channel is going to blow up.
I already know it has when I get a Justin Y. comment :P
Justin Y. fuck off dude
@@CodeParade wow you check your comments from such old videos
Day 8 part 5 of telling Justin Y. to delete his TH-cam Account
My channel is still small enough, I try to read all my comments.
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.
Well, that's why it's a hard problem and not an easy one :D
Would be interesting to see an alternative framing of the problem in which the angel can't win.
He gave it - if I understood correctly, if you force the angel to move away from the origin (not necessarily directly, but never decrease her distance to the origin) then the devil wins
cant devil just win by making a wall like 100 million away on all sides and slowly close it in
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
Describing the premise: wow seems like the angel has a big advantage.
Conclusion: yeah the angel wins
The angel loses
@@hornyfuckinturtle
If the angel is restricted to K=1, then yes, the devil wins. Otherwise, the angel wins.
winning strategy I saw not mine is that devil just makes wall thick as X(amount of blocks Angel can move) and slowly close that.
@@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.
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
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.
I feel like you just need to have the devil build walls thick enough and far enough away that the angel cannot reach them before he has completed narrowing the field, then just work inwards.
in the thought experiment where the angel can move 2 squares, the devil would need to start lets say 1,000 blocks a way and start building a wall, the angel goes north and gets tot he wall in 500 turns meaning the devil can only place 500 blocks, and needs to make the wall 2 blocks thick to prevent the angel from jumping over it. thus the wall is 250 blocks wide, the angel then turns east and runs for 500 blocks covering 1,000 squares, and the devil can expand its wall to be 250 blocks wider meaning the angel has gone 1,000 blocks east and the devil has built a 500 block wall so in the time it takes the angel to get to the wall and get around the wall the devil can only have half a wall of that size built, no matter what it takes the devil 2 turns to stop 1 turn of the angels movement meaning no matter how far away they start the angel will get past the wall in the distance away the devil started times .75 number of turns and all it has to do is go up till it hits a wall, then follow it till there is no more wall
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.
Too long didnt read
Andres179 then don’t respond
Finally, someone explaining the solution lol
"Stop running, angel, just let me tempt you to lunch at the Ritz!"
Really cool problem, though
U go too fast for me, devil
I'm kind of ashamed this comparison didn't occur to me, and I'm so happy I found this comment. :D
Entertaining overall. I was just about to complain about details but then I saw you included references.
Dawg. It’s on infinite space. Why would the devil not be able to create an infinitely large cage?
I’ll have to work this myself later.
Kinda like this game theory more then the actual game theory channel
I SwEAr wE SoLvED fnAf tHIs tImE!!!1!11!1!1!1!1!11!!!!!!!!
@@theemeraldboat9947 "remember, it's just a theory, a game theory! Thanks for watching." - the ending of every game theory by matpat
This game theory is a branch in maths. Matpat's game theory is the literal meaning; theories about video games
@@theemeraldboat9947
He technically did it's just Scott keeps pumping it more and more
@@duck3892 Except that they're not theories.
Ok I was gonna say they could go super far away but then realized the farther away they go the longer it takes them to build the wall
And Mexico will pay for it
Oh hey cool my comment got a reply and is up to 57 likes
@@buchstabensuppenfa7545 shut the fuck up idiot!
@@buchstabensuppenfa7545 shut the fuck up idiot!
I StM I Graphics Shut the fuck up (insert insult here)!
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
3:18 you waiting for the other player to make their move in every turn based game xD
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.
Ah yes I see now. Thank you both.
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.
@@earthbjornnahkaimurrao9542 it probably isnt that simple though
the question is: can the angel win without having perfect information and only sees the squares it can jump on?
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.
That seems to be the only way the angel CAN lose, other than demanding it only be allowed to travel in one direction like the only provided example.
It would still win because as long as it keeps moving as far as possible the devil can't set up anything fast enough.
@@NieroshaiTheSable rewatch video and pay attention this time
she can if she just moves randomly, in some cases a random sequence will just so happen to be a perfect solving algorithm
If he makes it big enough it doesn’t matter what the angel does.
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
Just say no, the Devil legally cannot trap you without your consent
Hey FBI we still having that 6 hour session of you monitoring me at night while I watch degenerate videos?
The circumstances are just not balanced enough.
yeah, I wished that every K amount of turns, the devil places an area of K by K. At least that way, there is some sort of challenge.
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
This suck because in order for the devil to win, the angel get put under so many restrictions in addition to the orginal rules.
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
@@guilhermemoreira4603 you can jump over block so the you need to change direction because the devil was there is kinda pointless.
@@Apsolon with enough distance the devil could make a thick enough wall so that the angel couldn't jump over
The angel can never win because there's no win condition for the angel
"You're an angel on an infinite grid."
"Aww, shucks!"
"It would be impossible due to the ENORMOUS distances"
Mojang: *[Laughs in Minecraft]*
I think minecraft worlds have a limit around 150 million blocks or something like that
@@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!
@@silly_lil_guy flatlands would like to now your location
"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.
Or just go around the wall, or go away from the get go
If you can move across an infinitely large plane, even if the devil attempts to block you, you can move around their movements and avoid defeat.
I've watched this video every time it pops up in my recommended.
So we'll say three times so far. Will update as long as I am alive
Conway always astounds from simple games creates profound results....
The Angel can win. Thats all you need to know
Oh my god!!! I found you from Hyperbolica but I didn’t realize this was also you! Keep it up you’ll become the neil cicierega of online mathematicians
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.
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.
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.
Personally, I can't even begin to understand how the Devil would ever win. The one detail of Infinite Space doesn't make this seem feasible to the Devil unless the Angel is a moron.
Otherwise, this feels more like when you try to teleport to someone who's flying at Mach 10 to try and hit them in a video game.
Let's say the angel can move 3 spaces. If the devil goes out 90 blocks, and starts blocking a block in a circle, by the time the angel gets there, he can have blocked off 30 blocks.
@@calebkirschbaum8158 But it's infinite space. You can't guarantee which direction the Angel goes unless they are playing suboptimally which defeats the purpose of the exercise
@@SomeKindaHero117 Think of it as an alien race vs Humans. We can only travel so fast in space. Let's say the aliens block off our milky way over the course of 100k years, by putting up 1 mile shields around the milky way. Each time we push in 1 direction, they put up another shield in that area. Will we escape the milky way before they put up the shield?
It doesn't matter that the space is infinite, if you can block access to that infinite space. Once the demon traps the angel, the angel will run out of spaces to go to eventually. So the question is whether or not the angel can ever be trapped.
The demon also doesn't need great amounts of information. If the first move the angel moves north, place a block in the north. If the next is to the east, place a block to the east. Going out far enough gives the devil enough time to place down the required blocks to perhaps win. The farther out you go though, the more blocks that will be needed to block them in.
@@calebkirschbaum8158 I can see how that could work but it's not changing what I think on the matter. With Infinite Space, I doubt the Devil has the capability to completely block off the Angel. Or that the Aliens can block off Humans. I'm sorry but maybe I shouldn't have watched the video or commented because this is the dumbest theory to me
@@SomeKindaHero117 Well, as long as you can see how it works, you understand it. In most citations, the angel will win. So you are right. It is just hard to prove. Unfortunately, the video does not go into detail, which may be why it is confusing.
The angel easily wins due to the fact that it's infinite, and you could just always go 10 in one direction forever
the devil could easily just build a wall in the angel's way
If the antel has 100 squares and the devil has one he's not gonna be able to block the angel, it's easy to dodge, there wont be any wall to help
@@godlyvex5543as soon as angel sees the wall he turns around
@@hunterhello5210 And once the angel turns around, the devil is at an advantage by making all those previous angel moves invalid and gaining time.
@@thethe5355 then angel goes in the third direction
But that's just a theory
A *game theory*
Janks ur 4 wtchsing
I want die
me too
and his brødda end mii
(rt game fans get the reference)
Alamkan Countryball Wife, but aight my dude.
@Random Guy too late man, too late
Dying is just like unsubscribing from Life
If it took 20 years to arrive at a mathematical solution, I wonder how long it would take an AI using trial and error.
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“.
It depends on a lot of things even if you exclude the computation speed
I love game theory shenanigans
What a lot of shower thoughts does to someone
Game theory perspective: the angel is ness/dead and in a fantasy
But that is just a theory
a THEORY THEORY!
And does crack
They're also a psychopath.
And the devil was the good guy the whole time. Muhahaha!
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
Where is matpat? Bro I was promised game theory
A long time ago, I remember a flash game based on this idea called "cat trap" or something like that. It was on a hex grid, and the cat (angel) can only move one cell at a time. But it was this exact problem: try to trap the cat by blocking all the cells around them.
Very fun little time waster, until I figured out the trick to build a diffuse wall and fill in only when the cat gets close. Then it became rather trivial. 😄
Oh, I suddenly remembered that too! I recall there was some strategy and I had fun looking the cat changing its icon to 'trapped' when left with no moves. It can be easily googled with 'cat trap game' search :D
Decided to have some fun with it again. Still as exciting as before
*_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.
just warp past the sqaures boi
warp in another parallel universe simple as
Squares
@@civotamuaz5781 D4C in a nutshell
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 see so if i just blast a shooting star at the devil then i would win.
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.
so many people pointing out that the person who made this video provided no description or proof for the solution when it's literally sitting so clearly in the description waiting to be clicked on
If the devil just removes the tiles at the boarder to infinity, the angel will loose.