battleship permutation

Question

Consider the following one-dimensional version of the game battleships. There is a battleship somewhere on $\mathbb N$, i.e., a interval $N,\ldots,N+k$. Your task is to find whether this battleship lies in the interval $1,\ldots,n$ using the minimal number of tests (on can ask if the battlship includes $i$ for any $1\leq i \leq n$). One does not know the value of $k$ (nor a bound on it). The battleship may not be in the test interval at all.

Intuitively I think that one choses a permutation of $\{1,\ldots,n\}$ so that after testing the first $m$, the remaining intervals of untested points in $1,\ldots,n$ are as small as possible. Example: if $n=5$ then $1,5,3,2,4$ would give an optimal strategy, as would $5,1,3,2,4$.

It is easy enough to work out an algorithm to generate such permutations

• maintain a sorted list of intervals, put $[2,n-1]$ in it
• maintain a results array and put $1$ and $n$ on it
• pop the largest interval from the sorted list, divide into two, push the division point onto the results array, push the divided intervals into the sorted list if they are not singletons

For my problem, $n<100$, so the above will probably suffice in terms of performance, but it occurs to me that such permutations might arise in other contexts, and there might be a more efficient way of generating them. Any takers?

Motivation: This arises in a non-convex global optimisation code which uses a "subdivide and reject" method. The battleship is a region around the global maximum, the tests are (rather expensive) function evaluations. If the global maximum is in the region of interest I must subdivide, if not then I can reject. Obviously I want to find whether the global maximum is in the region as soon as possible, since this saves me function evaluations.

[edit]

Thank you for the replies. I think that Douglas Zare's answer points in the right direction. After testing the end points one knows that the target is in the interior of the region (if it is there at all). Then the uniform insertion strategy seems to be the best one (possibly some chages will be needed to handle the integer location of the samples, but I don't think this is a big deal).

Incidentally, I just tested the simple strategy $1,n,2,\ldots,n-1$ on my code (i.e., test the end points, then the interior) and it gives a 2% reduction in evaluations --- well worth having. I will post the improvement with uniform insertion here when it is implemented.

Answer 1

The version of the Battleship game doesn't seem to match either the question or the motivation.

Suppose $n=15$ and $k=2$ so the Battleship has length $3$. There are $5$ disjoint positions $1-3, 4-6, 7-9, 10-12, 13-15$ so you have to make at least $5$ guesses to conclude the Battleship is not on the interval, and you can guess $3, 6, 9, 12, 15$. Each of the first $4$ guesses tests $3$ possible possitions of the Battleship, while the last checks the one remaining possibility on the interval. You can't do better than this to get the first hit on the Battleship.

If you divide the intervals evenly, then after $8, 4, 12$, you have eliminated $9$ of $13$ possible locations on the interval, but you have $4$ disjoint possibilities left which each have to be checked with a separate guess, so you take $7$ guesses. Even subdivision is not optimal.

If your goal is to have a reasonably even division from any prefix, then variations of this have been studied. I think geometric discrepancy theory includes this problem. Simply dividing the interval in half, and then dividing the largest interval in half, typically does not minimize the maximum ratio of the longest interval with the shortest interval over all prefixes.

Teramoto et al. "Inserting Points Uniformly at Every Instance" proves that the optimal ratio is $2^{m/(m+1)}$ where $m = \lfloor n/2 \rfloor$. For $n=3$, we can divide the first interval into the ratio $1 : \sqrt(2)$, and then divide the larger interval in half $1:1/\sqrt2 : 1/\sqrt2$, and then divide the larger interval in half $1/2:1/2:1/\sqrt2 : 1/\sqrt2$. I believe the last $n-m$ points divide the largest remaining interval in half, but the first $m$ points do not divide their intervals evenly. Of course, you might use a different notion to optimize than the maximum ratio between the largest and smallest interval.

Finally, the motivation was global optimization. If you know nothing of the function, then you have to try every point. However, typically the values of the function give you clues about the values at other points, even in a nonconvex setting, and you should make use of that information to slow down your sampling of locations which are unlikely to help.

Answer 2

Okay, so maybe the fastest way to do this would be to keep track of position of offset, i.e.

$x_0 = 1, y_0 = n - 1$

$\begin{cases} x_{i+1} = x_i + y_i \text{ if } x_i + y_i \leq n \newline y_{i+1} = y_i / 2, x_{i+1} = y_{i+1} / 2 \text{ else } \end{cases}$

that is to say, keep dividing the step size by half, and resetting at one half step.

If you're dealing with large enough numbers then the off-by-one error is inconsequential. For far more accurate results, only truncate the result to an integer during measurement, and otherwise keep track of fractions.

Off the top of my head I don't have the easy solution to the roundoff error, but I'm sure it's just a matter of inserting appropriate even-odd cases into your algorithm. Odd-sized intervals produce 2 even-sized intervals, and even-sized intervals produce one even, one odd.

I'm sleepy though, so I'll leave that part to you.