OddThinking

This is a quick discussion on a puzzle, because I have an idea buzzing in my head, and I need to get rid of it so I can focus back on a task which I would prefer to finish.

Once, in spite of the jeering of my fellow students, I chose a topic for a post-graduate university assignment of “Electronic Battleships”. It used the game of Battleships as a metaphor for securing online transactions, and worked on approaches to prevent cheating. (When you are playing against an untrusted opponent with a computer, what is to stop them from moving their ships around after they find out where you fired?)

I wrote a prototype that never got finished. It was my first C++ project, and my code was awful. I threw together an essay to cover for the lack of running code. It, too, was awful, which I found out when I gave it to a friend to critique, and she ripped it to shreds. That gave me a few hours of self-pity, until I realised she was absolutely right. I rearranged my schedule, re-wrote the essay, added some actual insight into the problem, and got an A for the assignment, which I largely owe to my friend not pulling any punches.

So, Battleships holds a special place in my heart.

I have often considered writing a Battleship-playing AI, but I never have.

Now, I discover, there is a Battleship-playing AI competition, which I don’t have the time (or .NET experience) to enter.

However, I can’t focus on my real task because I am having ideas about what my AI, if such a thing existed, would do.

So here are my expectations about what you would see in a winning strategy.

Aiming

After you score a hit, you should circle around the hit find the rest of the ship and sink it. This is bloody obvious! However, I have played against another adult (on a long flight) who didn’t do this. Needless to say, she didn’t do well.

Naive statement: There is no need to bomb the even positions. You can merely bomb the odd ones (e.g. the black-squares if you were playing on a chequer-board.) That ensures that you will get even the smallest submarine, while covering the area more efficiently. (You generally gain less information from bombing a square next to a square that is already a miss, than another square.)

Of course, if you choose this algorithm, be sure to randomly swap between even and odd cells between games or the other player may learn from you and ensure most of their ships lay in even positions.

Slightly less naive statement: The submarine’s length of two, means you need to bomb every second square. Once the submarine is sunk, the distance between squares can increase to the length of the smallest remaining ship.

More intelligent approach: While still sticking to only odd squares, you should start with more distance between them (e.g. 5 cells), and reduce that the 4, 3 or 2 cells only once those positions have all been filled. If you are lucky enough to sink the submarine in the first pass, you may never need to cover the grid that closely.

A certain amount of randomness is desirable to avoid predictability in future games. Don’t simply sweep from left-to-right, top-to-bottom, or edges to centre.

A hit on an edge square (or one nearby an edge) is better than a hit in the center, because it is tells you more about the possible position of the ship – there are less directions the ship may extend. However, there are less ship positions that lie on the edge for the same reason, reducing the chance of hitting a ship on the edge.

The general rule is that the value of a cell bombing is proportional to the chance of a hit succeeding at that cell, and proportional to the value of a hit.

The chance of a hit is proportional to the number of combinations of ship that could lie on that cell. This is reduced on an edge.

The value of a hit is higher for an edge, because it takes less attempts, on average, to sink a ship discovered on an edge.

Any strategy that leads you to prefer the edge risks that the other player will know that and avoid the edge. Or know you know that, and prefer the edge! That is why randomness is key to prevent particular strategies from being easily perceived.

So, you don’t always shoot at the highest valued target, but you bomb targets randomly, with a probability distribution in proportion to their value.

Monitor the opponent’s placement strategy as the games progress. Record the number of ships on odd-cells versus even cells. Record the distribution of distances from the edge. Use that to modify your probability distribution to match.

Placement

Don’t place your ships so that they are touching (straight on, or at right angles). If the other player hits one ship, and starts circling around it to find its direction and extent, there is a good chance they will discover the second ship. (Perhaps this rule should be to only do this rarely, so the other player can’t take advantage of the fact you predictably play this way, but this is such a strong rule I suspect it isn’t worth ever breaking.)

Consider the same issues with the discoverability of ships on the edge, to determine your placement. Again, use randomness across a probability distribution to avoid detectability.

Monitor the opponent’s aiming strategy as the games progress. Record the number of attacks on odd-cells versus even cells – perhaps watching to see if it changes over time. Record the distribution of distances from the edge; again seeing if it changes over time. Use that to modify your probability distribution of placement, avoiding the areas the other player attacks first.

Conclusion

It is a shame I don’t have the time to enter this competition; writing real-time AIs is not something I have tried before. I am interested in what strategies people come up with. I expeect to see elements of everything I have suggested here to be included, and I expect a lot, lot more.