# Papers unpicked: Strategy on an Infinite Chessboard between an Angel and a Devil

May 30, 2024
The Angel and the Devil If you had an

### infinite

chess board in your closet, who would like to play many difficult things? The rules are super simple, one of the players is the

### angel

and on each turn the

### angel

flies to some square on the board. Before the game begins, we would agree on how far the angel can travel and we call that number of squares its power, so For example, the angel of power, one can travel only one square in any direction, essentially, the king in chess, one angel of power, two. could travel anywhere within this region 1 of power 3 to any of these squares and so on, the second character arrives, the

, every time the

### devil

lands on a square, he burns that square, making it inaccessible to the angel for the rest of the game, very similarly the angel on each turn the devil can move to another square but unlike the angel he can travel as far as he wants and those are basically the rules, the devil wins the game if he finally catches the angel and The devil has a waiting

#### strategy

If he is always able to win, a useful way to think about this is that the devil has a set of instructions such that regardless of what the angel does, the devil can look for the current layout in his great book of instructions and give the perfect answer that keeps the angel contained in a large predetermined region at all times the angel has a winning

#### strategy

if the devil doesn't mean he can always evade the devil then which character here has the advantage ?
When John Conway presented this problem and then wrote an article about it some years later, he published a collection of counterstrategies that might initially seem attractive. I'll talk briefly about the first and simplest idea I could have: I'll make my angel fly a little north on every move Conway calls this angel the fool and that's because the fool loses to the devil let's take a power fool one this This is what the devil will do: he will represent all the squares that the fool could land on in the next few terms and plans to build a wall with the rope just after the devil also takes note of the average distance between the fool and the future wall each time.

## papers unpicked strategy on an infinite chessboard between an angel and a devil...

Once the four move the devil burns one of the four squares above. When the fool reaches the halfway point the devil restricts his interest to the new smaller region now accessible to the fool and concentrates his efforts on a shorter barrier with each move the devil burns squares that half are now occupied and we repeat two more times blocking the fool of power the first example of a conway is to show that this can be scaled to be fools of any power using exactly the same tactic of progressively filling a wall of adequate width in the distance and each time the fool moves away from there the devil restricts his efforts to a wall half the size of the distance at which the fool is located. the devil builds his wall gets big extremely fast in fact, even for a fool with power also to be completely infallible the devil should start building about eight and a half billion squares north of him for 24 years the world only knew the power angel that one would lose but otherwise the question remained open and suddenly in 2006 four different independent tests came out that answered part of the central question and in this video I'm going to talk about the really clever argument that andrasmatie makes for demonstrate that the power angels have two or more a winning strategy that completely answers the question.
What I like about Mater's creative plot is that it involves introducing two new characters and one of them is the friendly devil. The friendly devil avoids all the spaces that the angel could have accessed earlier in the game. So the angel is effectively building a growing region that the devil cannot land in. It may seem like this is a disadvantage, but here is our first fact: if the devil defeats the angel so does the good devil, in other words, This restriction is not a disadvantage at all. how does the test go suppose the devil has a winning strategy and says that the angel of power 2 has flown this way so far the good devil then does the following: imagine the angel traveling backwards but selecting the oldest possible square he can reach in each step the result is a new legitimate path between the starting point and the end which we call the reduced path the sympathetic devil looks at this path evokes the level of evil and asks what move would you make if the angel had taken this reduced path if the devil responds with a square inside the forbidden region for the good devil, we'll just have the nightstand, we'll pass that turn, but otherwise America will just follow the real devil's advice.
However, there is a subtlety that must be taken into account. What if when asked? the devil can't give an answer, what if the devil says sorry, pretty devil, but I would never have let this path happen because I would have occupied one of these squares if I had seen a previous part of this path, well, if so out? In the case, there are two possibilities: if that square was outside the forbidden region at that earlier stage of the game, the good devil would have burned it too, contradicting the existence of the original path. The only other possibility is if this burnt square was inside that previous stage. region, but this would not agree with the reduction of the path we initially found, since that burned square arrives strictly after the one the angel is in, so the devil always recognizes the reduced path and if the devil has a winning strategy, this path is a losing one. path for the angel, which means that the position of the angel is kept within a large predetermined region at all times, so the good devil who has the angel in that same position also wins, so what is the mathematical motivation behind this?
Well, another way of saying if the devil wins, the good devil, if the good devil loses, so does the devil. In other words, if the angel has a winning strategy against the good devil, he has one against the evil level. Now comes the second character. the one we call the runner, the runner can. He does not fly over burnt squares, so he runs along them, always moving forward and keeping the squares to the left of him. We will color any square the runner has been in blue. The author suggests imagining the squares not as holes but as walls so that we can imagine.
The runner always keeps her left hand on a wall, in fact, we will imagine her painting that wall green with her left hand. She can also go around corners tightly and will allow you to get around a corner by joining two squares together. His companion suggests imagining the burn. The square is not so square in shape but rather octagonal, allowing the runner to slide easily. Finally, we will ask the runner to simply go as far as he can within the accessible region. Power Angel 2 would obviously have Power Angel 2 follow whatever moves the broker makes, so if the broker has a winning strategy, the angel will too.
It's worth noting later that if the runner loops like she does here, the green paint forms the boundary of a collection of squares connected by their edges, unfortunately if the runner loops she loses too, but keep in mind the idea of ​​limits, this is where the fun begins. We will have our two new characters playing against each other. The runner and the friendly devil. I'll go back to squares instead of octagons because it's a bit. It is more pleasing to the eye when there are many of them, the runner will do the following before the game begins, he offers the cute depot all the squares to his left, the cute devil happily accepts the offer since eliminating half of the board could only be an advantage, but even if it decreases, the runner can imagine that they are there, he can start moving forward by painting them green with his left hand when he finally reaches an obstacle created by the devil, follow the algorithm described above.
Now let's imagine an incredibly scary scenario where the devil has somehow built a huge barrier like this and imagine that the runner has run along it without thinking like he would. I've made the number of burned squares deliberately unrealistic to emphasize parts of the test, but any barrier would do now. Let's pause to think about how the friendly devil would win to catch the runner. He will have to close a loop, but because this is the friendly devil, it is blocked by the original blue path of the corridor, since you are not allowed to burn any of those squares.
So the only way the kind devil wins is to force the runner to return to his original path from below his initial level and before that happens, the kind devil needs to force the runner to cross that horizontal threshold first, Let's imagine that the kind devil manages. This and let's pause just before the runner is about to cross that line. Mate proves that this is impossible to do, so we keep the game paused and delete all the pre-squares except a column of width 1 that stops at the height of the northernmost square burned by the nice level in the game, let's say exactly that t twists have occurred until this pause with the pleasant devil frozen in time.
Now we imagine that the runner continues his journey and finally reaches the starting point that I would like. Emphasize that this is not part of the actual game against the good devil. The purpose is just to get a contradiction about how many squares are on the board. Let's say there are square s. We have the quantity in that column and let's call that number. n and then the ones that were burned by the nice devil in the game, let's say there are d of them. Now remember that the nice devil doesn't necessarily move every turn, so this number s is at most plus the number of turns we record. that information and count again, but this time counting the number of edges.
Now, how many edges were painted well in the race between the start and the threshold? The runner has painted at least two walls each turn, except perhaps if he was interrupted in the turn. t and I only managed to paint one edge on that turn, so a total of two ts minus one below we count one edge painted just before returning to the start, one edge painted at the top of the column and at least one edge across the horizontal threshold, which brings Let's go to two t plus two on the route over the barrier, the runner will have painted at least n edges facing north and at least two edges facing west, a very rough limit but ultimately sufficient with an additional end painted on the other side of the barrier. column, let's record this lower bound on the painted edges and start thinking about all the edges.
With square s, there are 4 edges present on the board and we can separate them into three types, the painted edges forming the boundary of a connected family. unpainted but exposed edges, for example those trapped inside the connected family or those outside of it and finally twice the number of connecting edges, since each edge connecting two squares counts as two edges, simply ignoring the middle category we get 4 as being in less as big as painted plus 2 times connecting what is the smallest possible number of connecting edges, that should simply be one less than the number of squares, which is what happens if each square exactly touches another square smaller than that and the family will no longer be connected, this updates our inequality in the same way and now we can invoke our limit on the painted edges by connecting it gives us this limit of 2 that simplifies very well and is a complete contradiction with our previous limit on the number of squares in this dark and scary barrier. which said that there could only be at most n plus t of them, so the runner will never be able to reach that horizontal line and therefore will never be able to make a loop and will therefore always escape the nicest traveling devil and further north.
I hope you enjoyed this video which is based on the article The Power to Win Angel written by Andres Mate as well as Elements of the Angel Problem written by John Conway if you would like to see more of this type of content please subscribe