当然，我们也有可能在游戏的基础上运行一系列类似的游戏。

添加3d飞机或能够移动一艘船而不是射击回合等内容可能会改变游戏。

“战舰”是一个经典的计算机科学np完全问题。

http://en.wikipedia.org/wiki/List_of_NP-complete_problems

(寻找战舰-它在那里，在游戏和谜题下)

我的条目。

没有什么特别的，我也没有时间把我所有的好主意都加上去。

但它似乎玩得相当不错。我们将看到它在竞争中的表现:

(将此文件放入Missouri.cs并添加到项目中。)

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

namespace Battleship
{
    // The Empire of Japan surrendered on the deck of the USS Missouri on Sept. 2, 1945
    public class USSMissouri : IBattleshipOpponent
    {
        public String  Name    { get { return name; } }
        public Version Version { get { return ver;  } }

#region IBattleship Interface
        // IBattleship::NewGame
        public void NewGame(Size gameSize, TimeSpan timeSpan)
        {
            size      = gameSize;
            shotBoard = new ShotBoard(size);
            attackVector = new Stack<Attack>();
        }

        // IBattleship::PlaceShips
        public void PlaceShips(ReadOnlyCollection<Ship> ships)
        {
            HunterBoard board;
            targetBoards = new List<HunterBoard>();
            shotBoard    = new ShotBoard(size);
            foreach (Ship s in ships)
            {
                board = new HunterBoard(this, size, s);
                targetBoards.Add(board);

                // REWRITE: to ensure valid board placement.
                s.Place(
                    new Point(
                        rand.Next(size.Width),
                        rand.Next(size.Height)),
                    (ShipOrientation)rand.Next(2));
            }
        }

        // IBattleship::GetShot
        public Point GetShot()
        {
            Point p = new Point();

            if (attackVector.Count() > 0)
            {
                p = ExtendShot();
                return p;
            }

            // Contemplate a shot at every-single point, and measure how effective it would be.
            Board potential = new Board(size);
            for(p.Y=0; p.Y<size.Height; ++p.Y)
            {
                for(p.X=0; p.X<size.Width; ++p.X)
                {
                    if (shotBoard.ShotAt(p))
                    {
                        potential[p] = 0;
                        continue;
                    }

                    foreach(HunterBoard b in targetBoards)
                    {
                        potential[p] += b.GetWeightAt(p);
                    }
                }
            }

            // Okay, we have the shot potential of the board.
            // Lets pick a weighted-random spot.
            Point shot;
            shot = potential.GetWeightedRandom(rand.NextDouble());

            shotBoard[shot] = Shot.Unresolved;

            return shot;
        }

        public Point ExtendShot()
        {
            // Lets consider North, South, East, and West of the current shot.
            // and measure the potential of each
            Attack attack = attackVector.Peek();

            Board potential = new Board(size);

            Point[] points = attack.GetNextTargets();
            foreach(Point p in points)
            {
                if (shotBoard.ShotAt(p))
                {
                    potential[p] = 0;
                    continue;
                }

                foreach(HunterBoard b in targetBoards)
                {
                    potential[p] += b.GetWeightAt(p);
                }
            }

            Point shot = potential.GetBestShot();
            shotBoard[shot] = Shot.Unresolved;
            return shot;
        }

        // IBattleship::NewMatch
        public void NewMatch(string opponent)
        {
        }
        public void OpponentShot(Point shot)
        {
        }
        public void ShotHit(Point shot, bool sunk)
        {
            shotBoard[shot] = Shot.Hit;

            if (!sunk)
            {
                if (attackVector.Count == 0) // This is a first hit, open an attackVector
                {   
                    attackVector.Push(new Attack(this, shot));
                }
                else
                {
                    attackVector.Peek().AddHit(shot);    // Add a hit to our current attack.
                }
            }

            // What if it is sunk?  Close the top attack, which we've been pursuing.
            if (sunk)
            {
                if (attackVector.Count > 0)
                {
                    attackVector.Pop();
                }
            }
        }
        public void ShotMiss(Point shot)
        {
            shotBoard[shot] = Shot.Miss;

            foreach(HunterBoard b in targetBoards)
            {
                b.ShotMiss(shot);  // Update the potential map.
            }
        }
        public void GameWon()
        {
            Trace.WriteLine  ("I won the game!");
        }
        public void GameLost()
        {
            Trace.WriteLine  ("I lost the game!");
        }
        public void MatchOver()
        {
            Trace.WriteLine("This match is over.");
        }

#endregion 

        public ShotBoard theShotBoard
        {
            get { return shotBoard; }
        }
        public Size theBoardSize
        {
            get { return size; }
        }

        private Random rand = new Random();
        private Version ver = new Version(6, 3); // USS Missouri is BB-63, hence version 6.3
        private String name = "USS Missouri (abelenky@alum.mit.edu)";
        private Size size;
        private List<HunterBoard> targetBoards;
        private ShotBoard shotBoard;
        private Stack<Attack> attackVector;
    }

    // An Attack is the data on the ship we are currently working on sinking.
    // It consists of a set of points, horizontal and vertical, from a central point.
    // And can be extended in any direction.
    public class Attack
    {
        public Attack(USSMissouri root, Point p)
        {
            Player = root;
            hit = p;
            horzExtent = new Extent(p.X, p.X);
            vertExtent = new Extent(p.Y, p.Y);
        }

        public Extent HorizontalExtent
        {
            get { return horzExtent; }
        }
        public Extent VerticalExtent
        {
            get { return vertExtent; }
        }
        public Point  FirstHit
        {
            get { return hit; }
        }

        public void AddHit(Point p)
        {
            if (hit.X == p.X) // New hit in the vertical direction
            {
                vertExtent.Min = Math.Min(vertExtent.Min, p.Y);
                vertExtent.Max = Math.Max(vertExtent.Max, p.Y);
            }
            else if (hit.Y == p.Y)
            {
                horzExtent.Min = Math.Min(horzExtent.Min, p.X);
                horzExtent.Max = Math.Max(horzExtent.Max, p.X);
            }
        }
        public Point[] GetNextTargets() 
        {
            List<Point> bors = new List<Point>();

            Point p;

            p = new Point(hit.X, vertExtent.Min-1);
            while (p.Y >= 0 && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                --p.Y;
            }
            if (p.Y >= 0 && Player.theShotBoard[p] == Shot.None) // Add next-target only if there is no shot here yet.
            {
                bors.Add(p);
            }

            //-------------------

            p = new Point(hit.X, vertExtent.Max+1);
            while (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                ++p.Y;
            }
            if (p.Y < Player.theBoardSize.Height && Player.theShotBoard[p] == Shot.None)
            {
                bors.Add(p);
            }

            //-------------------

            p = new Point(horzExtent.Min-1, hit.Y);
            while (p.X >= 0 && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                --p.X;
            }
            if (p.X >= 0 && Player.theShotBoard[p] == Shot.None)
            {
                bors.Add(p);
            }

            //-------------------

            p = new Point(horzExtent.Max+1, hit.Y);
            while (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.Hit)
            {
                if (Player.theShotBoard[p] == Shot.Miss)
                {
                    break; // Don't add p to the List 'bors.  
                }
                ++p.X;
            }
            if (p.X < Player.theBoardSize.Width && Player.theShotBoard[p] == Shot.None)
            {
                bors.Add(p);
            }

            return bors.ToArray();
        }

        private Point hit; 
        private Extent horzExtent;
        private Extent vertExtent;
        private USSMissouri Player;
    }

    public struct Extent
    {
        public Extent(Int32 min, Int32 max)
        {
            Min = min;
            Max = max;
        }
        public Int32 Min;
        public Int32 Max;
    }

    public class Board  // The potential-Board, which measures the full potential of each square.
    {
        // A Board is the status of many things.
        public Board(Size boardsize)
        {
            size = boardsize;
            grid = new int[size.Width , size.Height];
            Array.Clear(grid,0,size.Width*size.Height);
        }

        public int this[int c,int r]
        {
            get { return grid[c,r];  }
            set { grid[c,r] = value; }
        }
        public int this[Point p]
        {
            get { return grid[p.X, p.Y];  }
            set { grid[p.X, p.Y] = value; }
        }

        public Point GetWeightedRandom(double r)
        {
            Int32 sum = 0;
            foreach(Int32 i in grid)
            {
                sum += i;
            }

            Int32 index = (Int32)(r*sum);

            Int32 x=0, y=0;
            for(y=0; y<size.Height; ++y)
            {
                for(x=0; x<size.Width; ++x)
                {
                    if (grid[x,y] == 0) continue; // Skip any zero-cells
                    index -= grid[x,y];
                    if (index < 0) break;
                }
                if (index < 0) break;
            }

            if (x == 10 || y == 10)
                throw new Exception("WTF");

            return new Point(x,y);
        }

        public Point GetBestShot()
        {
            int max=grid[0,0];
            for(int y=0; y<size.Height; ++y)
            {
                for (int x=0; x<size.Width; ++x)
                {
                    max = (grid[x,y] > max)? grid[x,y] : max;
                }
            }

            for(int y=0; y<size.Height; ++y)
            {
                for (int x=0; x<size.Width; ++x)
                {
                    if (grid[x,y] == max)
                    {
                        return new Point(x,y);
                    }
                }
            }
            return new Point(0,0);
        }

        public bool IsZero()
        {
            foreach(Int32 p in grid)
            {
                if (p > 0)
                {
                    return false;
                }
            }
            return true;
        }

        public override String ToString()
        {
            String output = "";
            String horzDiv = "   +----+----+----+----+----+----+----+----+----+----+\n";
            String disp;
            int x,y;

            output += "      A    B    C    D    E    F    G    H    I    J    \n" + horzDiv;

            for(y=0; y<size.Height; ++y)
            {
                output += String.Format("{0} ", y+1).PadLeft(3);
                for(x=0; x<size.Width; ++x)
                {
                    switch(grid[x,y])
                    {
                        case (int)Shot.None:       disp = "";  break;
                        case (int)Shot.Hit:        disp = "#"; break;
                        case (int)Shot.Miss:       disp = "."; break;
                        case (int)Shot.Unresolved: disp = "?"; break;
                        default:                   disp = "!"; break;
                    }

                    output += String.Format("| {0} ", disp.PadLeft(2));
                }
                output += "|\n" + horzDiv;
            }

            return output;
        }

        protected Int32[,] grid;
        protected Size     size;
    }

    public class HunterBoard
    {
        public HunterBoard(USSMissouri root, Size boardsize, Ship target)
        {
            size = boardsize;
            grid = new int[size.Width , size.Height];
            Array.Clear(grid,0,size.Width*size.Height);

            Player = root;
            Target = target;
            Initialize();
        }

        public void Initialize()
        {
            int x, y, i;

            for(y=0; y<size.Height; ++y)
            {
                for(x=0; x<size.Width - Target.Length+1; ++x)
                {
                    for(i=0; i<Target.Length; ++i)
                    {
                        grid[x+i,y]++;
                    }
                }
            }

            for(y=0; y<size.Height-Target.Length+1; ++y)
            {
                for(x=0; x<size.Width; ++x)
                {
                    for(i=0; i<Target.Length; ++i)
                    {
                        grid[x,y+i]++;
                    }
                }
            }
        }

        public int this[int c,int r]
        {
            get { return grid[c,r];  }
            set { grid[c,r] = value; }
        }
        public int this[Point p]
        {
            get { return grid[p.X, p.Y];  }
            set { grid[p.X, p.Y] = value; }
        }

        public void ShotMiss(Point p)
        {
            int x,y;
            int min, max;

            min = Math.Max(p.X-Target.Length+1, 0);
            max = Math.Min(p.X, size.Width-Target.Length);
            for(x=min; x<=max; ++x)
            {
                DecrementRow(p.Y, x, x+Target.Length-1);
            }

            min = Math.Max(p.Y-Target.Length+1, 0);
            max = Math.Min(p.Y, size.Height-Target.Length);
            for(y=min; y<=max; ++y)
            {
                DecrementColumn(p.X, y, y+Target.Length-1);
            } 

            grid[p.X, p.Y] = 0;
        }

        public void ShotHit(Point p)
        {
        }

        public override String ToString()
        {
            String output = String.Format("Target size is {0}\n", Target.Length);
            String horzDiv = "   +----+----+----+----+----+----+----+----+----+----+\n";
            int x,y;

            output += "      A    B    C    D    E    F    G    H    I    J    \n" + horzDiv;
            for(y=0; y<size.Height; ++y)
            {
                output += String.Format("{0} ", y+1).PadLeft(3);
                for(x=0; x<size.Width; ++x)
                {
                    output += String.Format("| {0} ", grid[x,y].ToString().PadLeft(2));
                }
                output += "|\n" + horzDiv;
            }
            return output;
        }

        // If we shoot at point P, how does that affect the potential of the board?
        public Int32 GetWeightAt(Point p)
        {
            int x,y;
            int potential = 0;
            int min, max;

            min = Math.Max(p.X-Target.Length+1, 0);
            max = Math.Min(p.X, size.Width-Target.Length);
            for(x=min; x<=max; ++x)
            {
                if (Player.theShotBoard.isMissInRow(p.Y, x, x+Target.Length-1) == false)
                {
                    ++potential;
                }
            }

            min = Math.Max(p.Y-Target.Length+1, 0);
            max = Math.Min(p.Y, size.Height-Target.Length);
            for(y=min; y<=max; ++y)
            {
                if (Player.theShotBoard.isMissInColumn(p.X, y, y+Target.Length-1) == false)
                {
                    ++potential;
                }
            } 

            return potential;
        }

        public void DecrementRow(int row, int rangeA, int rangeB)
        {
            int x;
            for(x=rangeA; x<=rangeB; ++x)
            {
                grid[x,row] = (grid[x,row]==0)? 0 : grid[x,row]-1;
            }
        }
        public void DecrementColumn(int col, int rangeA, int rangeB)
        {
            int y;
            for(y=rangeA; y<=rangeB; ++y)
            {
                grid[col,y] = (grid[col,y]==0)? 0 : grid[col,y]-1;
            }
        }

        private Ship Target = null;
        private USSMissouri Player;
        private Int32[,] grid;
        private Size     size;
    }

    public enum Shot
    {
        None = 0,
        Hit = 1,
        Miss = 2,
        Unresolved = 3
    };

    public class ShotBoard
    {
        public ShotBoard(Size boardsize)
        {
            size = boardsize;
            grid = new Shot[size.Width , size.Height];

            for(int y=0; y<size.Height; ++y)
            {
                for(int x=0; x<size.Width; ++x)
                {
                    grid[x,y] = Shot.None;
                }
            }
        }

        public Shot this[int c,int r]
        {
            get { return grid[c,r];  }
            set { grid[c,r] = value; }
        }
        public Shot this[Point p]
        {
            get { return grid[p.X, p.Y];  }
            set { grid[p.X, p.Y] = value; }
        }

        public override String ToString()
        {
            String output = "";
            String horzDiv = "   +----+----+----+----+----+----+----+----+----+----+\n";
            String disp;
            int x,y;

            output += "      A    B    C    D    E    F    G    H    I    J    \n" + horzDiv;

            for(y=0; y<size.Height; ++y)
            {
                output += String.Format("{0} ", y+1).PadLeft(3);
                for(x=0; x<size.Width; ++x)
                {
                    switch(grid[x,y])
                    {
                        case Shot.None:       disp = "";  break;
                        case Shot.Hit:        disp = "#"; break;
                        case Shot.Miss:       disp = "."; break;
                        case Shot.Unresolved: disp = "?"; break;
                        default:              disp = "!"; break;
                    }

                    output += String.Format("| {0} ", disp.PadLeft(2));
                }
                output += "|\n" + horzDiv;
            }
            return output;
        }

        // Functions to find shots on the board, at a specific point, or in a row or column, within a range
        public bool ShotAt(Point p)
        {
            return !(this[p]==Shot.None);
        }
        public bool isMissInColumn(int col, int rangeA, int rangeB)
        {
            for(int y=rangeA; y<=rangeB; ++y)
            {
                if (grid[col,y] == Shot.Miss)
                {
                    return true;
                }
            }
            return false;
        }
        public bool isMissInRow(int row, int rangeA, int rangeB)
        {
            for(int x=rangeA; x<=rangeB; ++x)
            {
                if (grid[x,row] == Shot.Miss)
                {
                    return true;
                }
            }
            return false;
        }
        protected Shot[,] grid;
        protected Size     size;
    }
}

萨里大学的詹姆斯·希瑟博士代表英国计算机学会举办了一次类似的比赛。

对资源的限制——即每回合的最大处理器时间，移动之间不能存储状态，最大堆大小。为了限制时间，AI可以在时间段内的任何时间点提交移动，并在回合结束时被要求移动。

非常有趣，更多信息请访问:http://www.bcsstudentcontest.com/

也许能给你更多的建议。

我不能参与，但如果我有时间，我将实现以下算法:

首先，当我发现被击中时，我不会立即追击剩下的船只——我会建立一个船的位置表，并在开始完全击沉它们之前确定我是否至少一次击中了所有五艘船。(注意，这是一个糟糕的策略多镜头变体-见评论)

Hit the center (see final note below - 'center' is just a convenience for description) Hit the spot 4 to the right of the center Hit the spot 1 down and one to the right of the center Hit the spot four to the right of the previous hit Continue in that pattern (should end up with diagonal lines separated by 3 spaces filling the board) This should hit all 4 and 5 length boats, and a statistically large number of 3 and 2 boats. Start randomly hitting spots inbetween the diagonals, this will catch the 2 and 3 length boats that haven't already been noticed.

一旦我检测到5个命中，我将确定这5个命中是否在不同的船上。这是相对容易的，只要在两个命中点在同一水平或垂直线上，并且彼此之间有5个位置(可能是同一条船上的两个命中点)的位置附近多拍几次就可以了。如果他们是分开的船，那么继续击沉所有的船。如果发现它们是同一艘船，继续上面的填充模式，直到所有5艘船都被定位。

该算法是一种简单的填充算法。关键的特点是，它不会浪费时间去击沉它知道的船只，当仍然有它不知道的船只时，它不会使用低效的填充模式(即，完全随机的模式将是浪费的)。

最后指出:

一)“中心”是棋盘上的一个随机起点。这消除了该算法的主要弱点。 B)虽然描述表明从一开始就立即绘制对角线，但理想情况下，算法只是在这些对角线上的“随机”位置射击。这有助于防止竞争对手计算他们的船只被可预测的模式击中的时间。

这描述了一个“完美”的算法，因为它可以让所有船只在(9x9)/2+10次射击之内。

但是，它可以显著改善:

一旦一艘船被击中，在做“内部”对角线之前确定它的大小。你可能已经找到了2号船，在这种情况下，内部对角线可以简化以更快地找到3号船。

确定游戏的各个阶段并采取相应的行动。这种算法可能在游戏的某一点上很好，但其他算法可能会在游戏的最后产生更好的收益。此外，如果其他玩家非常接近击败你，另一个算法可能会更好-例如，一个高风险的算法可能更容易失败，但当它起作用时，它会很快起作用，你可能会击败比你更接近胜利的对手。

识别竞争对手的打法——这可能会给你一些线索，让你知道他们是如何规划船只位置的(比如，他们自己的算法很有可能最快速地识别出他们如何放置自己的船只——如果你唯一的工具是锤子，那么所有的东西看起来都像钉子)

亚当

事实上，这个解决方案在ubuntu 9.10 linux的monodevelop中无需修改就可以打开和运行