The Angel Problem [Game Theory]
HTML-код
- Опубликовано: 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
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 RUclips 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"
-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
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
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.
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
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 ?
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
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
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.
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.
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
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
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
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
“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
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
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.
*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?
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 RUclips 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.
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.
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
damn matpat sure does sound different
Please make a roblox letsplay thanks, ,
@@tofidu ?
@@tofidu wdym
Eh
@@tofidu stop
The devil wins. He can basically draw hentai.
:)
Lives the devil
Underrated.
Oh shoot- kid weeb away!
FUCK YEAAAAAH
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 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
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 RUclips Account
My channel is still small enough, I try to read all my comments.
I've found this channel again and wow it has gotten much better since I last found it!.I love it
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.
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: ruclips.net/video/dQw4w9WgXcQ/видео.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.
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
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)
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.
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.
But that's just a theory, a ga- *gets tackled by a cop*
An actual game theory.
@@lagg1e A game theory theory.
Matpat really outdid himself with this one
I was hopping a game theory reference or at least a joke at the end, THANK YOU!
If the devil just removes the tiles at the boarder to infinity, the angel will loose.
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 .
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
Angel: **moves up**
Devil: **blocks the path**
Angel: **moves back**
Devil: 🗿🗿🗿
so i guess the angel can just move faster always to escape the "death box" no matter how far out the devil starts it?
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.
_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"
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.
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.
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
ah yes
*another os those videos that never stops appearing in your recommended until you click on 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.
0:59 I didn't know if CodeParade was going to be a devil, and he laughed.
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
"let's change the rules until i win"
i just want to say, i really love your little character dude
"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
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
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
I love game theory shenanigans
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!!!!!!!!
*Game theory is still relevant, Gosh darn it!*
You have your opinions though. I respect that.
@@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
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)!
Entertaining overall. I was just about to complain about details but then I saw you included references.
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
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
Conway always astounds from simple games creates profound results....
I understood that going back to a block the angel have already been is not *opitmal*, but I guess it doesn't mean it cannot do so, right ? Maybe in some case it could be more restricting to never go back than allowing the angel the went to go back, especially if we establish than the angel doesn't have a way to think and predict the devil's moves, and also if it started with the never-go-back strategy.
Maybe I'm completely wrong, but I wanna know !
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
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
"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
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.
Can you do this method in a hexagonal grid?
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
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
Solution: Create a pattern of moves so that the pseudo-randomness repeats itself.
“She can't. Why? Because i said no”
nah its cuz shes a woman/J
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 win. Thats all you need to know
"You're an angel on an infinite grid."
"Aww, shucks!"
CodeParade:Let me do a video by 10 min. or something like that
Me:Dont Underestimate THE SANS STRATEGY
1:28 This makes no sense. Just because the Angel shouldn't move back to somewhere it moved to before doesn't mean they can't. The angel can still move back to these if they have nowhere to go, but you exclude these spaces.
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.
Interesting problem, thanks for making the video
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
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.
Where is matpat? Bro I was promised game theory
can't the devil, theoretically, make 4 walls very very very far away from the angels starting point, so that by the time the angel reaches those walls it can't cross them? then it would just be a matter of slowly filling in the trapped enclosure they created?
Or would this not work since for every space away the devil goes the longer the walls need to be?
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
"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
The curves from squares. The avoidance pattern for the angel to avoid the wall.
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
2:15 can someone explain how K=3 would get you 10^65? I get 3.2*10^32. When K=1 then 1^3=1 and 4*1 = 4 and 2^4 =16. When K=2 then 2^3 = 8 and 4*8 = 32 and 2^32 = 4,294,967,296. When K = 3 then 3^3 = 27 and 4*27 = 108 and 2^108 = 3.2*10^32
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 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.
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.
It might be interesting if the angle can only view /see whats in move ( or N times movement ) range .