What is the best Battleship AI?

Question

Battleship!

Back in 2003 (when I was 17), I competed in a Battleship AI coding competition. Even though I lost that tournament, I had a lot of fun and learned a lot from it.

Now, I would like to resurrect this competition, in the search of the best battleship AI.

Here is the framework, now hosted on Bitbucket.

The winner will be awarded +450 reputation! The competition will be held starting on the 17th of November, 2009. No entries or edits later than zero-hour on the 17th will be accepted. (Central Standard Time) Submit your entries early, so you don't miss your opportunity!

To keep this OBJECTIVE, please follow the spirit of the competition.

Rules of the game:

1. The game is be played on a 10x10 grid.
2. Each competitor will place each of 5 ships (of lengths 2, 3, 3, 4, 5) on their grid.
3. No ships may overlap, but they may be adjacent.
4. The competitors then take turns firing single shots at their opponent.
   • A variation on the game allows firing multiple shots per volley, one for each surviving ship.
5. The opponent will notify the competitor if the shot sinks, hits, or misses.
6. Game play ends when all of the ships of any one player are sunk.

Rules of the competition:

1. The spirit of the competition is to find the best Battleship algorithm.
2. Anything that is deemed against the spirit of the competition will be grounds for disqualification.
3. Interfering with an opponent is against the spirit of the competition.
4. Multithreading may be used under the following restrictions:
   • No more than one thread may be running while it is not your turn. (Though, any number of threads may be in a "Suspended" state).
   • No thread may run at a priority other than "Normal".
   • Given the above two restrictions, you will be guaranteed at least 3 dedicated CPU cores during your turn.
5. A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread.
6. Running out of time results in losing the current game.
7. Any unhandled exception will result in losing the current game.
8. Network access and disk access is allowed, but you may find the time restrictions fairly prohibitive. However, a few set-up and tear-down methods have been added to alleviate the time strain.
9. Code should be posted on stack overflow as an answer, or, if too large, linked.
10. Max total size (un-compressed) of an entry is 1 MB.
11. Officially, .Net 2.0 / 3.5 is the only framework requirement.
12. Your entry must implement the IBattleshipOpponent interface.

Scoring:

1. Best 51 games out of 101 games is the winner of a match.
2. All competitors will play matched against each other, round-robin style.
3. The best half of the competitors will then play a double-elimination tournament to determine the winner. (Smallest power of two that is greater than or equal to half, actually.)
4. I will be using the TournamentApi framework for the tournament.
5. The results will be posted here.
6. If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.

Good luck! Have fun!

---

EDIT 1:
Thanks to Freed, who has found an error in the Ship.IsValid function. It has been fixed. Please download the updated version of the framework.

EDIT 2:
Since there has been significant interest in persisting stats to disk and such, I have added a few non-timed set-up and tear-down events that should provide the required functionality. This is a semi-breaking change. That is to say: the interface has been modified to add functions, but no body is required for them. Please download the updated version of the framework.

EDIT 3:
Bug Fix 1: GameWon and GameLost were only getting called in the case of a time out.
Bug Fix 2: If an engine was timing out every game, the competition would never end.
Please download the updated version of the framework.

EDIT 4:
Tournament Results:

Solution 1

I second the motion to do a lot more games per match. Doing 50 games is just flipping a coin. I needed to do 1000 games to get any reasonable distinction between test algorithms.

Download Dreadnought 1.2.

Strategies:

• keep track of all possible positions for ships that have >0 hits. The list never gets bigger than ~30K so it can be kept exactly, unlike the list of all possible positions for all ships (which is very large).

• The GetShot algorithm has two parts, one which generates random shots and the other which tries to finish sinking an already hit ship. We do random shots if there is a possible position (from the list above) in which all hit ships are sunk. Otherwise, we try to finish sinking a ship by picking a location to shoot at which eliminates the most possible positions (weighted).

• For random shots, compute best location to shoot based on the likelihood of one of the unsunk ships overlapping the location.

• adaptive algorithm which places ships in locations where the opponent is statistically less likely to shoot.

• adaptive algorithm which prefers to shoot at locations where the opponent is statistically more likely to place his ships.

• place ships mostly not touching each other.

Solution 2

Here is my entry! (The most naive solution possible)

"Random 1.1"

namespace Battleship
{
    using System;
    using System.Collections.ObjectModel;
    using System.Drawing;

    public class RandomOpponent : IBattleshipOpponent
    {
        public string Name { get { return "Random"; } }
        public Version Version { get { return this.version; } }

        Random rand = new Random();
        Version version = new Version(1, 1);
        Size gameSize;

        public void NewGame(Size size, TimeSpan timeSpan)
        {
            this.gameSize = size;
        }

        public void PlaceShips(ReadOnlyCollection<Ship> ships)
        {
            foreach (Ship s in ships)
            {
                s.Place(
                    new Point(
                        rand.Next(this.gameSize.Width),
                        rand.Next(this.gameSize.Height)),
                    (ShipOrientation)rand.Next(2));
            }
        }

        public Point GetShot()
        {
            return new Point(
                rand.Next(this.gameSize.Width),
                rand.Next(this.gameSize.Height));
        }

        public void NewMatch(string opponent) { }
        public void OpponentShot(Point shot) { }
        public void ShotHit(Point shot, bool sunk) { }
        public void ShotMiss(Point shot) { }
        public void GameWon() { }
        public void GameLost() { }
        public void MatchOver() { }
    }
}

Solution 3

Here's an opponent for people to play against:

• http://natekohl.net/files/FarnsworthOpponent.cs

Instead of using a fixed geometry-inspired strategy, I thought it would be interesting to attempt to estimate the underlying probabilities that any particular unexplored space holds a ship.

To do this right, you'd explore all possible configurations of ships that fit your current view of the world, and then compute probabilities based on those configurations. You could think of it like exploring a tree:

an expansion of possible battleship states http://natekohl.net/media/battleship-tree.png

After considering all leaves of that tree that jive with what you know about the world (e.g. ships can't overlap, all hit squares must be ships, etc.) you can count how often ships occur at each unexplored position to estimate the likelihood that a ship is sitting there.

This can be visualized as a heat map, where hot spots are more likely to contain ships:

a heat map of probabilities for each unexplored position http://natekohl.net/media/battleship-probs.png

One thing I like about this Battleship competition is that the tree above is almost small enough to brute-force this kind of algorithm. If there are ~150 possible positions for each of the 5 ships, that's 150⁵ = 75 billion possibilities. And that number only gets smaller, especially if you can eliminate whole ships.

The opponent that I linked to above doesn't explore the whole tree; 75 billion is still to big to get in under a second. It does attempt to estimate these probabilities, though, with the help of a few heuristics.

Solution 4

Not a fully fledged answer but there seems little point cluttering the real answers with code that is common. I thus present some extensions/general classes in the spirit of open source. If you use these then please change the namespace or trying to compile everything into one dll isn't going to work.

BoardView lets you easily work with an annotated board.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;

namespace Battleship.ShuggyCoUk
{
    public enum Compass
    {
        North,East,South,West
    }

    class Cell<T>
    {
        private readonly BoardView<T> view;
        public readonly int X;
        public readonly int Y;
        public T Data;
        public double Bias { get; set; }

        public Cell(BoardView<T> view, int x, int y) 
        { 
            this.view = view; this.X = x; this.Y = y; this.Bias = 1.0;  
        }

        public Point Location
        {
            get { return new Point(X, Y); }
        }

        public IEnumerable<U> FoldAll<U>(U acc, Func<Cell<T>, U, U> trip)
        {
            return new[] { Compass.North, Compass.East, Compass.South, Compass.West }
                .Select(x => FoldLine(x, acc, trip));
        }

        public U FoldLine<U>(Compass direction, U acc, Func<Cell<T>, U, U> trip)
        {
            var cell = this;
            while (true)
            {
                switch (direction)
                {
                    case Compass.North:
                        cell = cell.North; break;
                    case Compass.East:
                        cell = cell.East; break;
                    case Compass.South:
                        cell = cell.South; break;
                    case Compass.West:
                        cell = cell.West; break;
                }
                if (cell == null)
                    return acc;
                acc = trip(cell, acc);
            }
        }

        public Cell<T> North
        {
            get { return view.SafeLookup(X, Y - 1); }
        }

        public Cell<T> South
        {
            get { return view.SafeLookup(X, Y + 1); }
        }

        public Cell<T> East
        {
            get { return view.SafeLookup(X+1, Y); }
        }

        public Cell<T> West
        {
            get { return view.SafeLookup(X-1, Y); }
        }

        public IEnumerable<Cell<T>> Neighbours()
        {
            if (North != null)
                yield return North;
            if (South != null)
                yield return South;
            if (East != null)
                yield return East;
            if (West != null)
                yield return West;
        }
    }

    class BoardView<T>  : IEnumerable<Cell<T>>
    {
        public readonly Size Size;
        private readonly int Columns;
        private readonly int Rows;

        private Cell<T>[] history;

        public BoardView(Size size)
        {
            this.Size = size;
            Columns = size.Width;
            Rows = size.Height;
            this.history = new Cell<T>[Columns * Rows];
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Rows; x++)
                    history[x + y * Columns] = new Cell<T>(this, x, y);
            }
        }

        public T this[int x, int y]
        {
            get { return history[x + y * Columns].Data; }
            set { history[x + y * Columns].Data = value; }
        }

        public T this[Point p]
        {
            get { return history[SafeCalc(p.X, p.Y, true)].Data; }
            set { this.history[SafeCalc(p.X, p.Y, true)].Data = value; }
        }

        private int SafeCalc(int x, int y, bool throwIfIllegal)
        {
            if (x < 0 || y < 0 || x >= Columns || y >= Rows)
            {    if (throwIfIllegal)
                    throw new ArgumentOutOfRangeException("["+x+","+y+"]");
                 else
                    return -1;
            }
            return x + y * Columns;
        }

        public void Set(T data)
        {
            foreach (var cell in this.history)
                cell.Data = data;
        }

        public Cell<T> SafeLookup(int x, int y)
        {
            int index = SafeCalc(x, y, false);
            if (index < 0)
                return null;
            return history[index];
        }

        #region IEnumerable<Cell<T>> Members

        public IEnumerator<Cell<T>> GetEnumerator()
        {
            foreach (var cell in this.history)
                yield return cell;
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public BoardView<U> Transform<U>(Func<T, U> transform)
        {
            var result = new BoardView<U>(new Size(Columns, Rows));
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Columns; x++)
                {
                    result[x,y] = transform(this[x, y]);
                }
            }
            return result;
        }

        public void WriteAsGrid(TextWriter w)
        {
            WriteAsGrid(w, "{0}");
        }

        public void WriteAsGrid(TextWriter w, string format)
        {
            WriteAsGrid(w, x => string.Format(format, x.Data));
        }

        public void WriteAsGrid(TextWriter w, Func<Cell<T>,string> perCell)
        {
            for (int y = 0; y < Rows; y++)
            {
                for (int x = 0; x < Columns; x++)
                {
                    if (x != 0)
                        w.Write(",");
                    w.Write(perCell(this.SafeLookup(x, y)));
                }
                w.WriteLine();
            }
        }

        #endregion
    }
}

Some extensions, some of this duplicates functionality in the main framework but should really be done by you.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.Collections.ObjectModel;

namespace Battleship.ShuggyCoUk
{
    public static class Extensions
    {        
        public static bool IsIn(this Point p, Size size)
        {
            return p.X >= 0 && p.Y >= 0 && p.X < size.Width && p.Y < size.Height;
        }

        public static bool IsLegal(this Ship ship,
            IEnumerable<Ship> ships, 
            Size board,
            Point location, 
            ShipOrientation direction)
        {
            var temp = new Ship(ship.Length);
            temp.Place(location, direction);
            if (!temp.GetAllLocations().All(p => p.IsIn(board)))
                return false;
            return ships.Where(s => s.IsPlaced).All(s => !s.ConflictsWith(temp));
        }

        public static bool IsTouching(this Point a, Point b)
        {
            return (a.X == b.X - 1 || a.X == b.X + 1) &&
                (a.Y == b.Y - 1 || a.Y == b.Y + 1);
        }

        public static bool IsTouching(this Ship ship,
            IEnumerable<Ship> ships,
            Point location,
            ShipOrientation direction)
        {
            var temp = new Ship(ship.Length);
            temp.Place(location, direction);
            var occupied = new HashSet<Point>(ships
                .Where(s => s.IsPlaced)
                .SelectMany(s => s.GetAllLocations()));
            if (temp.GetAllLocations().Any(p => occupied.Any(b => b.IsTouching(p))))
                return true;
            return false;
        }

        public static ReadOnlyCollection<Ship> MakeShips(params int[] lengths)
        {
            return new System.Collections.ObjectModel.ReadOnlyCollection<Ship>(
                lengths.Select(l => new Ship(l)).ToList());       
        }

        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Rand rand)
        {
            T[] elements = source.ToArray();
            // Note i > 0 to avoid final pointless iteration
            for (int i = elements.Length - 1; i > 0; i--)
            {
                // Swap element "i" with a random earlier element it (or itself)
                int swapIndex = rand.Next(i + 1);
                T tmp = elements[i];
                elements[i] = elements[swapIndex];
                elements[swapIndex] = tmp;
            }
            // Lazily yield (avoiding aliasing issues etc)
            foreach (T element in elements)
            {
                yield return element;
            }
        }

        public static T RandomOrDefault<T>(this IEnumerable<T> things, Rand rand)
        {
            int count = things.Count();
            if (count == 0)
                return default(T);
            return things.ElementAt(rand.Next(count));
        }
    }
}

Something I end up using a lot.

enum OpponentsBoardState
{
    Unknown = 0,
    Miss,
    MustBeEmpty,        
    Hit,
}

Randomization. Secure but testable, useful for testing.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Battleship.ShuggyCoUk
{
    public class Rand
    {
        Random r;

        public Rand()
        {
            var rand = System.Security.Cryptography.RandomNumberGenerator.Create();
            byte[] b = new byte[4];
            rand.GetBytes(b);
            r = new Random(BitConverter.ToInt32(b, 0));
        }

        public int Next(int maxValue)
        {
            return r.Next(maxValue);
        }

        public double NextDouble(double maxValue)
        {
            return r.NextDouble() * maxValue;
        }

        public T Pick<T>(IEnumerable<T> things)
        {
            return things.ElementAt(Next(things.Count()));
        }

        public T PickBias<T>(Func<T, double> bias, IEnumerable<T> things)
        {
            double d = NextDouble(things.Sum(x => bias(x)));
            foreach (var x in things)
            {
                if (d < bias(x))
                    return x;
                d -= bias(x);                
            }
            throw new InvalidOperationException("fell off the end!");
        }
    }
}

Solution 5

I don't have the time right now to write a full-fledged algorithm, but here's a thought: if your opponent placed ships randomly, wouldn't the placement probabilities be a simple distribution centered at (5.5,5.5)? For example, the placement possibilities for the battleship (5 units long) in the x dimension are here:

x    1 2 3 4 5  6  7 8 9 10
P(x) 2 4 6 8 10 10 8 6 4 2

The same calculations would be valid for y. The other ships would not have as steep of distributions, but your best guess is still the center. After that, the mathematical approach would be slowly radiating diagonals (perhaps with the length of the average ship, 17/5) out of the center. Ex:

...........
....x.x....
.....x.....
....x.x....
...........

Obviously some randomness would need to be added to the idea, but I think that purely mathematically that's the way to go.

View more solutions

Comments

[dicroce]

Actually, this answer is nice because it shows in a very concise form the API's you'd need to implement to compete... :)

[dhara tcrails]

I had reflection in mind when I said "Interfering". I don't want competitors to win because they bit-twiddled another engine to death.

[Nathan Taylor]

Back when I built a similar project in my college Algorithms class I used random logic interlaced with some decision making. It was good sometimes!

[Admin]

This could attempt to place overlapping ships couldn't it?

[Vilius Surblys]

I'd suggest that espionage is an important part of modern warfare, so reflecting to find the targets would be ideal -- after all, it was one of the methods used during the second world war...

[dhara tcrails]

I have a framework for isolating the engines onto different PCs, communicating over TCP/IP, rendering Reflection worthless. However, due to my estimated number of entries, This would make the competition take a prohibitively long time.

[dhara tcrails]

Potentially, yes, they could play on their own. That is not how this will be run. Great idea, though. In this competition, I want it to be possible to statistically avoid your opponent's shots.

[ziggystar]

I see. Using data from prior games against the same opponent one might be able to adapt to him?

[dhara tcrails]

Yes, but the engine will disallow this. It will then tell the AI to place them again, but this time, with a sterner voice. (Seen by pop ax \ cmp ax, 1 \ je stern)

[dhara tcrails]

Not all solutions must be in C#. I can compile and link-in a separate assembly. Also, you should be able to statistically counter your opponent.

[dhara tcrails]

The opponents have the option of using a CSPRNG.

[Triston Attridge]

Good point, although I admit that reverse engineering such a seed is beyond my expertise anyway. I guess that most vulnerable aspect would be the fire pattern selection algorithm- but even then you wouldn't necessarily gain much from breaking it, as there is no way you could move your ships once the game has started.

[darron]

So... I just need to stay away from the middle? :)

[dhara tcrails]

J#? maybe? Lol, jk. I do have a TCP framework for this, but this tournament needs to run very quickly.

[Jherico]

You also need to stay away from the edges, because an edge hit contains more information for your opponent than a non-edge hit. So you should place all your ships in a non-middle, non-edge region. Unless that's what they're expecting you to do.

[Markus Nigbur]

I didn't know they had Reflection back then!

[Jherico]

Why would you assume that TCP communication between two processes on the same machine wouldn't be blazingly fast?

[dhara tcrails]

@Jherico: If I was using TCP, I would be isolating the engines on their own PCs so that they could use any CPU resources they wanted.

[Jherico]

Even so, two machines on the same lan could easily complete a game in under a second with the network overhead being minimal

[P Shved]

When I was applying for research internship, we wrote battleship programs and competed. By setting random seed was exactly how I won X)

[dhara tcrails]

There is the "salvo" variation. Where you get to shoot as many shots per turn as you have ships remaining.

[Oddthinking]

If you start by leaving 3 or 4 spaces, you might be lucky enough to hit the sub anyway. If not, go back and try filling in the gaps. More at: somethinkodd.com/oddthinking/2009/10/29/battleship-strategy

[Jason Berkan]

Which is a battleship puzzle (en.wikipedia.org/wiki/Battleship_(puzzle)), not Battleship the game (en.wikipedia.org/wiki/Battleship_(game)).

[dhara tcrails]

Yeah, as Jason stated this is an entirely different animal.

[Glenn]

An interesting variation as well. I seem to recall playing a computer version that had a plane as well. It would randomly fire at locations on the opposing board.

[dhara tcrails]

Please post code samples if you think that the timing can be done more accurately. I don't want to change the rules too much right now.

[dhara tcrails]

Also, the ship sizes are passed in during the PlaceShips() which is run exactly once per game and can also be used as a set-up phase. Please feel free to unseal the ship for your own testing, but I plan on using the sealed one for the tournament.

[user422801]

The ship with two holes is not a goddamn sub, it's a goddamn PT boat. The sub has three holes. :)

[dhara tcrails]

Yes, indeed they would. My old engine compensated for that.

[user772401]

Where I come from, slowly radiating diagonals out of the center is considered cheating.

[Justin Ohms]

If it's considered cheating, there's a pretty easy countermeasure. Avoid (x,y) where x=y. :)

[dhara tcrails]

I think he was alluding to card counting? Which, in my opinion, is not cheating.

[abelenky]

BUG: @John Gietzen: I have determined that PlaceShips is NOT run exactly once per game (as you stated). If a player places their ships incorrectly (as the RandomOpponent often does), then PlaceShips is called repeatedly, without an intervening NewGame call.

[configurator]

I don't think that's a bug in the software, I think that's a bug in the "spec" or more correctly in his comment here.

[dhara tcrails]

@abelenky: Well, right. That is: if you screw up, it calls it untill you act right.

[Domenic]

Assuming a reasonably-simple ship placement algorithm, I would imagine one could, after getting a couple of hits on different ships, start using most of one's turn looping through all possible random seeds (probably starting with somewhere near the current time and moving forwards/backwards one step or so) and seeing which ones generate ship placements compatible with observed hits.

[Josh Smeaton]

I always considered it a strategy to place two ships in an L configuration to make my opponent think they had sunk a battleship when in fact they hadn't. I was never under the impression you had to declare which boat was sunk.

[ShuggyCoUk]

Important note foranyone who, like me, figured they could easily beat this by remembering the previously placed shots and not repeating. The framework will ignore repeats and give you another chance so long as your total time is less than the limit. This is poor in my opinion, if someone messes up their algo they should be penalized...

[dhara tcrails]

This will be run on an Intel Q9550SX quad core, 8 GB ram, Vista 64 machine. Is 1 second going to be a limiting factor?

[dhara tcrails]

You don't have to declare. Check the rules from the original pencil-and-paer game.

[DJ.]

The rules from hasbro say you do - hasbro.com/common/instruct/BattleShip_%282002%29.PDF

[Bork Blatt]

Hehehe. Next assignment I get at work I'm going to say it's NP-complete, then take a long lunch. :-)

[dhara tcrails]

@DJ: I'm going by the original pen-and-paper rules. Remember that Hasbro is a toy company and that this game predates Hasbro.

[Peter Burns]

I guess you should make your battleship AI multithreaded, then, to calculate the max # of shots per that time interval.

[TonyAbell]

the trick is how to limit the turn time interval. If I limit it 0.00005 seconds I am safe from running over the time limit, but I am significantly limiting the search space. If I increase the turn time limit, the search space is increased but I run the risk of running out of time.

[kyokley]

@TonyAbell: If it's important to have a turn based time limit, why not start with an initial value and then adjust it from round to round? After about half the rounds you will most likely have found the optimal turn length for the opponent you're facing.

[russau]

another variation: be the size of the board + number of ships.

[Jason Owen]

The strategy of waiting to sink ships until all are found depends heavily on the one-shot-per-turn variation. Under the (number of surviving ships)-shots-per-turn version, it is advantageous to sink ships as quickly as possible so as to slow your opponent.

[dhara tcrails]

So far, you are beating our only other full solution by about 67.7% to 32.3% :)

[dhara tcrails]

@Shuggy, they are penalized, in time.

[Nate Kohl]

I'm definitely curious to see how a "probability approach" compares to a "geometric approach". I've noticed that this probability opponent actually makes moves that follow the geometric patterns discussed in other answers. It could be that using geometry is just as good, and a lot faster. :)

[dhara tcrails]

You should keep track of your time left, and limit it to 1/2 of the available time left.

[ShuggyCoUk]

on my test machine (a ULV Celeron netbook) this code loses by timeout consistently. When I let it take all the time it wants it whips Simple (roughly 90% success rate). If you are relying heavily on the spec of the machine you're going to be running on to hit you timelimits you might want to give yourself some wiggle room...

[dhara tcrails]

Interesting... It runs fine on the tournament machine. However, a "perfect" engine would adapt to however much time it had already spent.

[abelenky]

And now that I've submitted my entry, some rough stats: vs. BP7 44% wins. / vs. Dreadnought 20% wins. / vs. Farnsworth 42% wins. It was a fun project.

[Thomas Ahle]

Congrats on the silver. Do you mind describing your algorithm in words? It would be interesting to know about.

[Bart]

Could you perhaps fix your answer and especially your images and link?