Angel vs Demon

There is an infinite chess board, and on it is an angel. At noon each day, the angel moves up, down, left or right one square, and must do so every day. At midnight each day, the demon burns any square on the chess board, except it can't burn the square the angel is currently on. If the angel steps on a burnt square, it dies. Can the demon kill the angel after a finite number of moves?

Alternative question? What if every day the angel can move diagonally as well as orthogonally?

Originally posted by Dejection
There is an infinite chess board, and on it is an angel. At noon each day, the angel moves up, down, left or right one square, and must do so every day. At midnight each day, the demon burns any square on the chess board, except it can't burn the square the angel is currently on. If the angel steps on a burnt square, it dies. Can the demon kill the angel a ...[text shortened]...
Alternative question? What if every day the angel can move diagonally as well as orthogonally?

Yes, The demon has to burn squares far away from the angel first, on the same line as the angel in the direction the angel moves, to create a "fence", and then starts burning squares once the fence is sealed. i.e. Angel is on (0,0) and moves to (1,0), demon burns (10,0), angel moves to (1,1), demon burns (1,10) and so forth... if the angel moves in the same direction again, burn the squares evenly next to the burnt square, i.e. angel moves to (1,2), demon burns (2,10) or (0,10)

I suppose the same would hold true for diagonal moves as well, but the burnt squares would have to be further away. i.e. angel moves from (0,0) to (1,1), burn (20,20)

Originally posted by Dejection
There is an infinite chess board, and on it is an angel. At noon each day, the angel moves up, down, left or right one square, and must do so every day. At midnight each day, the demon burns any square on the chess board, except it can't burn the square the angel is currently on. If the angel steps on a burnt square, it dies. Can the demon kill the angel a ...[text shortened]...
Alternative question? What if every day the angel can move diagonally as well as orthogonally?

As I inderstand it, it takes the demon at most 63 burnings.

The first night he burns any of the squares adjacent to the angel.
Every next time he can burn the square he saw the angel on the previous night.

Eventually the board is used up and the angel must step onto one of the burnt tiles.

Originally posted by TheMaster37
As I inderstand it, it takes the demon at most 63 burnings.

The first night he burns any of the squares adjacent to the angel.
Every next time he can burn the square he saw the angel on the previous night.

Eventually the board is used up and the angel must step onto one of the burnt tiles.

The board is infinite, so there is no "eventually".

Originally posted by brobluto
The board is infinite, so there is no "eventually".

Ah, that's what I missed, thank you. My method is the same as yours, only not that far away 🙂

I'm assuming the demon cannot see the angel during the first day, so he doesn't know where the angel starts out.

Second try:

If the angel only moves horizontally or vertically;

The demon burns a square 3 paces away from the angel.
The next night, the demon can see in what direction the angel moved. The demon will try to make a square around the area the angel is in.

Two possibilities;

1) The angel moved towards the recently burned square.

Demon expands the wall on that side by burning a square above or below the existing wall. The demon must alternate between above and below.

2) The angel does not move towards the recently burned square.

Demon burns the square 3 paces ahead of the angel.

The third rule the demon must follow is when the angel moves north, he will expand the north side of the square by burning a square in front of the angel, in line with other burned squares already in the north wall of the square.

The fourth rule is that the demon will prevent the angel from moving in a space where a piece of wall would normally come. Rule 1 ensures that the angel will not escape by moving along a wall.

I hope that I made this clear. It works for me on paper.

For the angels that also moves diagonally:

I'm thinking that the same rules apply, but the demon needs to burn 4 paces away from the angel to determine the distance to the wall.

Originally posted by brobluto
I suppose the same would hold true for diagonal moves as well, but the burnt squares would have to be further away. i.e. angel moves from (0,0) to (1,1), burn (20,20)

I'm not sure about this. A diagonal is two basic directions at the same time and a diagonal fence needs at least to be at least two squares thick to stop it. If you build a fence he can shift one of the directions and continue on the other one. (I hope it's clear what I'm trying to say here...)

Originally posted by Palynka
I'm not sure about this. A diagonal is two basic directions at the same time and a diagonal fence needs at least to be at least two squares thick to stop it. If you build a fence he can shift one of the directions and continue on the other one. (I hope it's clear what I'm trying to say here...)

The board is infinite- no fence, the demon just has to burn away a square a few miles away and close in... assuming the demon can block- I think it can.

Originally posted by Palynka
I'm not sure about this. A diagonal is two basic directions at the same time and a diagonal fence needs at least to be at least two squares thick to stop it. If you build a fence he can shift one of the directions and continue on the other one. (I hope it's clear what I'm trying to say here...)

I think I understand because I was going through the same logic in my head. That's why I said twice as far away as the basic directional fence. But then again, better make it 4 times the distance just to be on the safe side.

I guess what I'm saying is that, we all agree that in a finite space, the demon will eventually win. All he has to do is make the infinite space finite, but fencing in the angel. The fence will be a lot larger if the angel is allowed to move diagonally, but still doable.

Originally posted by TheMaster37
Ah, that's what I missed, thank you. My method is the same as yours, only not that far away 🙂

I'm assuming the demon cannot see the angel during the first day, so he doesn't know where the angel starts out.

Second try:

If the angel only moves horizontally or vertically;

The demon burns a square 3 paces away from the angel.
The next night, t ...[text shortened]... t the demon needs to burn 4 paces away from the angel to determine the distance to the wall.

Following these directions didn't work for me. I took an alternating N and E route with the angle, and was able to get into an infinite tunnel.

Dang! Though it wouldn't create an infinite tunnel, you are right about it going wrong in the corner (I'd make an illegal move 🙂)

Still I tihnk it's possible. Instead of just extending the wall, I would try extending it with every other square, while only filling up the gaps when needed. This would ensure a wall is made and that the corners are closed in time.

Originally posted by TheMaster37
Dang! Though it wouldn't create an infinite tunnel, you are right about it going wrong in the corner (I'd make an illegal move 🙂)

Still I tihnk it's possible. Instead of just extending the wall, I would try extending it with every other square, while only filling up the gaps when needed. This would ensure a wall is made and that the corners are closed in time.

I think 10 spaces for 4-direction and 40 spaces for diagonal work. They may not be the most efficient, but it get's the job done.

Yes, it is definitly not the most efficient way, but is probably the easiest way to prove it. The most efficient way is obvious to anyone who plays Go or Wei-Chi, but very difficult to explain.

I can't describe an exact best algorithm, but I suspect if the angel was placed in the middle of a 9x9 grid, the devil could prevent him from exiting the grid.

The main trick would be to set up a "virtual wall" where the devil can close the openings faster than the angel can get through them, usually by dividing escape areas into half, then closing off the half the angel attempts to take.

The angel could attempt to go back, but doing so means he has lost ground and is worse off than when he was first there.

Burning the square diagonally outward of a chosen "center" (usually the angel starting square), and/or burning two squares ahead are both powerful effective moves, especially if you avoid tunnel scenarios.

I think I have a 14 move algorithm, although it is a bit complex to describe.

It essentially centers on trapping him within the following pattern..

~X~X~
X~~~X
~~x~~
X~~~X
~X~X~

After that, you then force him into a thin channel and remove the longer end each time.

The angel also is incapable of penetrating a gate with a gap of 2, and can be turned back from it.

What if the Angel can move only orthoganally, but makes two moves for every one move by the demon?