# Trapping pieces on an infinite chessboard

Alice and Bob are playing an unusual game of chess.

We begin with a piece on a square of an infinite chessboard.

On each of her turns, Alice moves the piece.

On each of his turns, Bob destroys a square of the chessboard.

Bob wins if he can trap Alice (i.e., create a 'moat' of destroyed squares too big for Alice to cross).

Alice wins if she can prove that Bob has no winning strategy.

Assume perfect play.

Now for the pieces: Let's make up pieces called n-kings, and say that an n-king leaps to any square within n squares of it (so can fly over destroyed squares).

Clearly Bob wins from the get-go if Alice starts with a 0-king.

What is the highest order of king for which Bob has a winning strategy?

What is the lowest order of king for which Alice has a winning strategy (if any)?

• Can the piece move fewer than $n$ spaces? And how are diagonal distances handled for $n \geq 2$? – 2012rcampion Dec 13 '15 at 21:03
• @2012rcampion Calculate distance as per king moves, so k diagonals = k moves. The piece can move 'to any square within n squares of it'. – Dave Dec 13 '15 at 21:13
• So a 2-king could move like a queen (within two spaces), but could it also move like a knight? That is, are there $4n(n+1)$ possible moves (anywhere within a $2n+1\times 2n+1$ square), or.only $8n$? – 2012rcampion Dec 13 '15 at 21:29
• @2012rcampion an n-king can move to any of (2n+1)^2 squares that are within n of it, except it can't land on squares that have been destroyed. I'm including the square it's leaving, though staying put is unlikely to be part of a winning strategy. – Dave Dec 13 '15 at 21:34
• If anyone else wants to look it up, it appears this problem also goes by the name of "The Angel Problem." – 2012rcampion Dec 13 '15 at 22:17

Choose a large number, $r$, and consider the ring of squares which are all $r$ king moves away from Alice's starting square. Bob will initially only eat squares from that ring.