Drawing Blanks

Premature Optimization is a Prerequisite for Success

Hunting problem

with one comment

At last Drog understood the nature of the beast he was up against. … No creature without tentacles had ever developed true intelligence. That was Etlib’s Law, and it had never been disputed. In a battle between intelligence and instinctive cunning, intelligence always won. It had to. All he had to do was figure out how.

Robert Sheckley, “Hunting Problem”.

I was planning to tell about an exciting probability game problem, but I decided to postpone that and to tell instead about a much easier game. This is one of my favorite simple problems.

We are playing a game of Battleship. The enemy Battleship is located at some integer point A on the number line. It is moving at some constant integer velocity V, meaning on each turn its position changes by V units. Both A and V are unknown. Find a strategy that allows to sink the ship in a finite number of shots.

That wasn’t a very clear formulation so let me explain. Player 1 (P1) chooses an integer number A as the initial position of the ship, and some integer number V as the velocity. On each turn, Player 2 (P2) attempts to guess the current position of the ship. If the guess is correct, the ship is sunk and P2 wins. Otherwise, P1 moves the ship by V units, and the players continue to take turns. We want to find a strategy that allows P2 to sink the ship in a finite number of turns.

Here is how to approach and solve this problem.

First let’s see what do we do if the ship is not moving, i.e. if we know that V=0. It’s trivial: we shoot at all integers one by one until we hit the target. 0, 1, –1, 2, –2, …

Now, what do we do if we know the position of the ship at some moment (let’s say on turn 0, A=A0), but we don’t know the velocity? Again, we can enumerate all values of velocity: V0=0, V1=1, V2=-1,… Then on turn n, we shoot at A0 + n * Vn. As soon as we guess the correct velocity, we sink the ship.

And finally, if both A and V are unknown, we do the same thing: we enumerate all pairs (An, Vn) and shoot at An + n * Vn.

So it doesn’t matter how many parameters define our opponent’s strategy. If the set of all possible strategies is countable, we can guess the strategy in finite time.

“Countable set” is an anagram of “Battle Us Once


Written by bbzippo

05/23/2010 at 10:47 pm

Posted in math

One Response

Subscribe to comments with RSS.

  1. […] with a deterministic random generator, the opponent will sooner or later learn to predict it. (See https://bbzippo.wordpress.com/2010/05/23/hunting-problem/ […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: