9
$\begingroup$

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)?

Improve this question
$\endgroup$
7
  • $\begingroup$ Can the piece move fewer than $n$ spaces? And how are diagonal distances handled for $n \geq 2$? $\endgroup$
    – 2012rcampion
    Dec 13, 2015 at 21:03
  • $\begingroup$ @2012rcampion Calculate distance as per king moves, so k diagonals = k moves. The piece can move 'to any square within n squares of it'. $\endgroup$
    – Dave
    Dec 13, 2015 at 21:13
  • $\begingroup$ 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$? $\endgroup$
    – 2012rcampion
    Dec 13, 2015 at 21:29
  • $\begingroup$ @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. $\endgroup$
    – Dave
    Dec 13, 2015 at 21:34
  • 7
    $\begingroup$ If anyone else wants to look it up, it appears this problem also goes by the name of "The Angel Problem." $\endgroup$
    – 2012rcampion
    Dec 13, 2015 at 22:17

2 Answers 2

Reset to default
7
$\begingroup$

This is equivalent to Conway's angel problem. It has been shown that Bob can win only if Alice has a 1- (or 0-) king, and Alice has a winning strategy otherwise. I don't know that there is any simple way to show this (it was an unsolved problem for many years). One strategy that Bob can use is described here. In the instance of the game they use, Bob plays the role of the angel while Alice is the devil.

Improve this answer
$\endgroup$
5
$\begingroup$

Here is a rough sketch of how Bob wins against a normal chess king.

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.

As Alice moves outward, she will approach a particular location on this ring. Bob's strategy is to destroy every other square in an interval surrounding the place Alice approaches. Once Alice reaches the perimeter, Bob then fills in these gaps right before Alice escapes through them. This will only occupy half of Bob's time, while the other half will be spent extending the rest of the ring. Once Bob has eaten the entire ring, he is then guaranteed to win.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What's the smallest ring size that will work? $\endgroup$
    – Dave
    Dec 14, 2015 at 16:31
  • 1
    $\begingroup$ @user17625 I've no idea... it might make a good puzzle? $\endgroup$
    – Mike Earnest
    Dec 14, 2015 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.