战舰!
早在2003年(当时我17岁)，我参加了一场《战舰》AI编码比赛。尽管我输了那场比赛，但我从中获得了很多乐趣，也学到了很多东西。
现在，我想恢复这个比赛，在搜索最好的战舰AI。
下面是这个框架，现在托管在Bitbucket上。
获胜者将获得+450声望奖励!比赛将于2009年11月17日开始。17号零时之前的投稿和编辑将不被接受。(中央标准时间)
尽早提交你的作品，这样你就不会错过机会!
为了保持这个目标，请遵循比赛的精神。
游戏规则:
游戏在10x10的网格上进行。
每个参赛者将5艘船(长度为2、3、3、4、5)中的每一艘放在他们的网格上。
没有船只可以重叠，但它们可以相邻。
然后选手们轮流向对手射击。
游戏的一个变体允许每次齐射多次，每艘幸存的船一次。
如果击球沉、命中或未命中，对手将通知选手。
当任何一名玩家的所有船只都沉没时，游戏就结束了。
比赛规则:
The spirit of the competition is to find the best Battleship algorithm.
Anything that is deemed against the spirit of the competition will be grounds for disqualification.
Interfering with an opponent is against the spirit of the competition.
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.
A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread.
Running out of time results in losing the current game.
Any unhandled exception will result in losing the current game.
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.
Code should be posted on stack overflow as an answer, or, if too large, linked.
Max total size (un-compressed) of an entry is 1 MB.
Officially, .Net 2.0 / 3.5 is the only framework requirement.
Your entry must implement the IBattleshipOpponent interface.
得分:
Best 51 games out of 101 games is the winner of a match.
All competitors will play matched against each other, round-robin style.
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.)
I will be using the TournamentApi framework for the tournament.
The results will be posted here.
If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.
好运！玩得开心!
编辑1:
多亏弗里德，他在飞船上发现了一个错误。是否是可用的函数。问题已经解决了。请下载框架的更新版本。
编辑2:
由于人们对将统计数据持久化到磁盘等非常感兴趣，所以我添加了一些非计时设置和删除事件，它们应该能够提供所需的功能。这是一个半突破性的变化。也就是说:修改了接口，添加了功能，但不需要body。请下载框架的更新版本。
编辑3:
错误修复1:GameWon和GameLost只在超时的情况下被调用。
错误修复2:如果引擎在每一款游戏中都暂停计时，那么竞争将永远不会结束。
请下载框架的更新版本。
编辑4:
比赛结果:
我的电脑现在正在戴尔维修，但这是我上周在哪里:
namespace Battleship
{
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
public class BSKiller4 : OpponentExtended, IBattleshipOpponent
{
public string Name { get { return "BSKiller4"; } }
public Version Version { get { return this.version; } }
public bool showBoard = false;
Random rand = new Random();
Version version = new Version(0, 4);
Size gameSize;
List<Point> nextShots;
Queue<Point> scanShots;
char[,] board;
private void printBoard()
{
Console.WriteLine();
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
Console.Write(this.board[x, y]);
}
Console.WriteLine();
}
Console.ReadKey();
}
public void NewGame(Size size, TimeSpan timeSpan)
{
this.gameSize = size;
board = new char[size.Width, size.Height];
this.nextShots = new List<Point>();
this.scanShots = new Queue<Point>();
fillScanShots();
initializeBoard();
}
private void initializeBoard()
{
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
this.board[x, y] = 'O';
}
}
}
private void fillScanShots()
{
int x, y;
int num = gameSize.Width * gameSize.Height;
for (int j = 0; j < 3; j++)
{
for (int i = j; i < num; i += 3)
{
x = i % gameSize.Width;
y = i / gameSize.Height;
scanShots.Enqueue(new Point(x, y));
}
}
}
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()
{
if (showBoard) printBoard();
Point shot;
shot = findShotRun();
if (shot.X != -1)
{
return shot;
}
if (this.nextShots.Count > 0)
{
shot = this.nextShots[0];
this.nextShots.RemoveAt(0);
}
else
{
shot = this.scanShots.Dequeue();
}
return shot;
}
public void ShotHit(Point shot, bool sunk)
{
this.board[shot.X, shot.Y] = 'H';
if (!sunk)
{
addToNextShots(new Point(shot.X - 1, shot.Y));
addToNextShots(new Point(shot.X, shot.Y + 1));
addToNextShots(new Point(shot.X + 1, shot.Y));
addToNextShots(new Point(shot.X, shot.Y - 1));
}
else
{
this.nextShots.Clear();
}
}
private Point findShotRun()
{
int run_forward_horizontal = 0;
int run_backward_horizontal = 0;
int run_forward_vertical = 0;
int run_backward_vertical = 0;
List<shotPossibilities> possible = new List<shotPossibilities>(5);
// this only works if width = height for the board;
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
// forward horiz
if (this.board[x, y] == 'M')
{
run_forward_horizontal = 0;
}
else if (this.board[x, y] == 'O')
{
if (run_forward_horizontal >= 2)
{
possible.Add(
new shotPossibilities(
run_forward_horizontal,
new Point(x, y),
true));
}
else
{
run_forward_horizontal = 0;
}
}
else
{
run_forward_horizontal++;
}
// forward vertical
if (this.board[y, x] == 'M')
{
run_forward_vertical = 0;
}
else if (this.board[y, x] == 'O')
{
if (run_forward_vertical >= 2)
{
possible.Add(
new shotPossibilities(
run_forward_vertical,
new Point(y, x),
false));
}
else
{
run_forward_vertical = 0;
}
}
else
{
run_forward_vertical++;
}
// backward horiz
if (this.board[this.gameSize.Width - x - 1, y] == 'M')
{
run_backward_horizontal = 0;
}
else if (this.board[this.gameSize.Width - x - 1, y] == 'O')
{
if (run_backward_horizontal >= 2)
{
possible.Add(
new shotPossibilities(
run_backward_horizontal,
new Point(this.gameSize.Width - x - 1, y),
true));
}
else
{
run_backward_horizontal = 0;
}
}
else
{
run_backward_horizontal++;
}
// backward vertical
if (this.board[y, this.gameSize.Height - x - 1] == 'M')
{
run_backward_vertical = 0;
}
else if (this.board[y, this.gameSize.Height - x - 1] == 'O')
{
if (run_backward_vertical >= 2)
{
possible.Add(
new shotPossibilities(
run_backward_vertical,
new Point(y, this.gameSize.Height - x - 1),
false));
}
else
{
run_backward_vertical = 0;
}
}
else
{
run_backward_vertical++;
}
}
run_forward_horizontal = 0;
run_backward_horizontal = 0;
run_forward_vertical = 0;
run_backward_vertical = 0;
}
Point shot;
if (possible.Count > 0)
{
shotPossibilities shotp = possible.OrderByDescending(a => a.run).First();
//this.nextShots.Clear();
shot = shotp.shot;
//if (shotp.isHorizontal)
//{
// this.nextShots.RemoveAll(p => p.X != shot.X);
//}
//else
//{
// this.nextShots.RemoveAll(p => p.Y != shot.Y);
//}
}
else
{
shot = new Point(-1, -1);
}
return shot;
}
private void addToNextShots(Point p)
{
if (!this.nextShots.Contains(p) &&
p.X >= 0 &&
p.X < this.gameSize.Width &&
p.Y >= 0 &&
p.Y < this.gameSize.Height)
{
if (this.board[p.X, p.Y] == 'O')
{
this.nextShots.Add(p);
}
}
}
public void GameWon()
{
this.GameWins++;
}
public void NewMatch(string opponent)
{
System.Threading.Thread.Sleep(5);
this.rand = new Random(System.Environment.TickCount);
}
public void OpponentShot(Point shot) { }
public void ShotMiss(Point shot)
{
this.board[shot.X, shot.Y] = 'M';
}
public void GameLost()
{
if (showBoard) Console.WriteLine("-----Game Over-----");
}
public void MatchOver() { }
}
public class OpponentExtended
{
public int GameWins { get; set; }
public int MatchWins { get; set; }
public OpponentExtended() { }
}
public class shotPossibilities
{
public shotPossibilities(int r, Point s, bool h)
{
this.run = r;
this.shot = s;
this.isHorizontal = h;
}
public int run { get; set; }
public Point shot { get; set; }
public bool isHorizontal { get; set; }
}
}
没有那么复杂，但这是我想到的。它有99.9%的几率击败随机对手。如果有人有其他类似的小挑战，我会感兴趣的，这很有趣。
namespace Battleship
{
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
public class AgentSmith : IBattleshipOpponent
{
public string Name { get { return "Agent Smith"; } }
public Version Version { get { return this.version; } }
private Random rand = new Random();
private Version version = new Version(2, 1);
private Size gameSize;
private enum Direction { Up, Down, Left, Right }
private int MissCount;
private Point?[] EndPoints = new Point?[2];
private LinkedList<Point> HitShots = new LinkedList<Point>();
private LinkedList<Point> Shots = new LinkedList<Point>();
private List<Point> PatternShots = new List<Point>();
private Direction ShotDirection = Direction.Up;
private void NullOutTarget()
{
EndPoints = new Point?[2];
MissCount = 0;
}
private void SetupPattern()
{
for (int y = 0; y < gameSize.Height; y++)
for (int x = 0; x < gameSize.Width; x++)
if ((x + y) % 2 == 0) PatternShots.Add(new Point(x, y));
}
private bool InvalidShot(Point p)
{
bool InvalidShot = (Shots.Where(s => s.X == p.X && s.Y == p.Y).Any());
if (p.X < 0 | p.Y<0) InvalidShot = true;
if (p.X >= gameSize.Width | p.Y >= gameSize.Height) InvalidShot = true;
return InvalidShot;
}
private Point FireDirectedShot(Direction? direction, Point p)
{
ShotDirection = (Direction)direction;
switch (ShotDirection)
{
case Direction.Up: p.Y--; break;
case Direction.Down: p.Y++; break;
case Direction.Left: p.X--; break;
case Direction.Right: p.X++; break;
}
return p;
}
private Point FireAroundPoint(Point p)
{
if (!InvalidShot(FireDirectedShot(ShotDirection,p)))
return FireDirectedShot(ShotDirection, p);
Point testShot = FireDirectedShot(Direction.Left, p);
if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Right, p); }
if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Up, p); }
if (InvalidShot(testShot)) { testShot = FireDirectedShot(Direction.Down, p); }
return testShot;
}
private Point FireRandomShot()
{
Point p;
do
{
if (PatternShots.Count > 0)
PatternShots.Remove(p = PatternShots[rand.Next(PatternShots.Count)]);
else do
{
p = FireAroundPoint(HitShots.First());
if (InvalidShot(p)) HitShots.RemoveFirst();
} while (InvalidShot(p) & HitShots.Count > 0);
}
while (InvalidShot(p));
return p;
}
private Point FireTargettedShot()
{
Point p;
do
{
p = FireAroundPoint(new Point(EndPoints[1].Value.X, EndPoints[1].Value.Y));
if (InvalidShot(p) & EndPoints[1] != EndPoints[0])
EndPoints[1] = EndPoints[0];
else if (InvalidShot(p)) NullOutTarget();
} while (InvalidShot(p) & EndPoints[1] != null);
if (InvalidShot(p)) p = FireRandomShot();
return p;
}
private void ResetVars()
{
Shots.Clear();
HitShots.Clear();
PatternShots.Clear();
MissCount = 0;
}
public void NewGame(Size size, TimeSpan timeSpan)
{
gameSize = size;
ResetVars();
SetupPattern();
}
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()
{
if (EndPoints[1] != null) Shots.AddLast(FireTargettedShot());
else Shots.AddLast(FireRandomShot());
return Shots.Last();
}
public void ShotHit(Point shot, bool sunk)
{
HitShots.AddLast(shot);
MissCount = 0;
EndPoints[1] = shot;
if (EndPoints[0] == null) EndPoints[0] = shot;
if (sunk) NullOutTarget();
}
public void ShotMiss(Point shot)
{
if (++MissCount == 6) NullOutTarget();
}
public void GameWon() { }
public void GameLost() { }
public void NewMatch(string opponent) { }
public void OpponentShot(Point shot) { }
public void MatchOver() { }
}
}
稍微压缩，以占用最小的空间在这里，仍然是可读的。
我的电脑现在正在戴尔维修，但这是我上周在哪里:
namespace Battleship
{
using System;
using System.Collections.ObjectModel;
using System.Drawing;
using System.Collections.Generic;
using System.Linq;
public class BSKiller4 : OpponentExtended, IBattleshipOpponent
{
public string Name { get { return "BSKiller4"; } }
public Version Version { get { return this.version; } }
public bool showBoard = false;
Random rand = new Random();
Version version = new Version(0, 4);
Size gameSize;
List<Point> nextShots;
Queue<Point> scanShots;
char[,] board;
private void printBoard()
{
Console.WriteLine();
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
Console.Write(this.board[x, y]);
}
Console.WriteLine();
}
Console.ReadKey();
}
public void NewGame(Size size, TimeSpan timeSpan)
{
this.gameSize = size;
board = new char[size.Width, size.Height];
this.nextShots = new List<Point>();
this.scanShots = new Queue<Point>();
fillScanShots();
initializeBoard();
}
private void initializeBoard()
{
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
this.board[x, y] = 'O';
}
}
}
private void fillScanShots()
{
int x, y;
int num = gameSize.Width * gameSize.Height;
for (int j = 0; j < 3; j++)
{
for (int i = j; i < num; i += 3)
{
x = i % gameSize.Width;
y = i / gameSize.Height;
scanShots.Enqueue(new Point(x, y));
}
}
}
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()
{
if (showBoard) printBoard();
Point shot;
shot = findShotRun();
if (shot.X != -1)
{
return shot;
}
if (this.nextShots.Count > 0)
{
shot = this.nextShots[0];
this.nextShots.RemoveAt(0);
}
else
{
shot = this.scanShots.Dequeue();
}
return shot;
}
public void ShotHit(Point shot, bool sunk)
{
this.board[shot.X, shot.Y] = 'H';
if (!sunk)
{
addToNextShots(new Point(shot.X - 1, shot.Y));
addToNextShots(new Point(shot.X, shot.Y + 1));
addToNextShots(new Point(shot.X + 1, shot.Y));
addToNextShots(new Point(shot.X, shot.Y - 1));
}
else
{
this.nextShots.Clear();
}
}
private Point findShotRun()
{
int run_forward_horizontal = 0;
int run_backward_horizontal = 0;
int run_forward_vertical = 0;
int run_backward_vertical = 0;
List<shotPossibilities> possible = new List<shotPossibilities>(5);
// this only works if width = height for the board;
for (int y = 0; y < this.gameSize.Height; y++)
{
for (int x = 0; x < this.gameSize.Width; x++)
{
// forward horiz
if (this.board[x, y] == 'M')
{
run_forward_horizontal = 0;
}
else if (this.board[x, y] == 'O')
{
if (run_forward_horizontal >= 2)
{
possible.Add(
new shotPossibilities(
run_forward_horizontal,
new Point(x, y),
true));
}
else
{
run_forward_horizontal = 0;
}
}
else
{
run_forward_horizontal++;
}
// forward vertical
if (this.board[y, x] == 'M')
{
run_forward_vertical = 0;
}
else if (this.board[y, x] == 'O')
{
if (run_forward_vertical >= 2)
{
possible.Add(
new shotPossibilities(
run_forward_vertical,
new Point(y, x),
false));
}
else
{
run_forward_vertical = 0;
}
}
else
{
run_forward_vertical++;
}
// backward horiz
if (this.board[this.gameSize.Width - x - 1, y] == 'M')
{
run_backward_horizontal = 0;
}
else if (this.board[this.gameSize.Width - x - 1, y] == 'O')
{
if (run_backward_horizontal >= 2)
{
possible.Add(
new shotPossibilities(
run_backward_horizontal,
new Point(this.gameSize.Width - x - 1, y),
true));
}
else
{
run_backward_horizontal = 0;
}
}
else
{
run_backward_horizontal++;
}
// backward vertical
if (this.board[y, this.gameSize.Height - x - 1] == 'M')
{
run_backward_vertical = 0;
}
else if (this.board[y, this.gameSize.Height - x - 1] == 'O')
{
if (run_backward_vertical >= 2)
{
possible.Add(
new shotPossibilities(
run_backward_vertical,
new Point(y, this.gameSize.Height - x - 1),
false));
}
else
{
run_backward_vertical = 0;
}
}
else
{
run_backward_vertical++;
}
}
run_forward_horizontal = 0;
run_backward_horizontal = 0;
run_forward_vertical = 0;
run_backward_vertical = 0;
}
Point shot;
if (possible.Count > 0)
{
shotPossibilities shotp = possible.OrderByDescending(a => a.run).First();
//this.nextShots.Clear();
shot = shotp.shot;
//if (shotp.isHorizontal)
//{
// this.nextShots.RemoveAll(p => p.X != shot.X);
//}
//else
//{
// this.nextShots.RemoveAll(p => p.Y != shot.Y);
//}
}
else
{
shot = new Point(-1, -1);
}
return shot;
}
private void addToNextShots(Point p)
{
if (!this.nextShots.Contains(p) &&
p.X >= 0 &&
p.X < this.gameSize.Width &&
p.Y >= 0 &&
p.Y < this.gameSize.Height)
{
if (this.board[p.X, p.Y] == 'O')
{
this.nextShots.Add(p);
}
}
}
public void GameWon()
{
this.GameWins++;
}
public void NewMatch(string opponent)
{
System.Threading.Thread.Sleep(5);
this.rand = new Random(System.Environment.TickCount);
}
public void OpponentShot(Point shot) { }
public void ShotMiss(Point shot)
{
this.board[shot.X, shot.Y] = 'M';
}
public void GameLost()
{
if (showBoard) Console.WriteLine("-----Game Over-----");
}
public void MatchOver() { }
}
public class OpponentExtended
{
public int GameWins { get; set; }
public int MatchWins { get; set; }
public OpponentExtended() { }
}
public class shotPossibilities
{
public shotPossibilities(int r, Point s, bool h)
{
this.run = r;
this.shot = s;
this.isHorizontal = h;
}
public int run { get; set; }
public Point shot { get; set; }
public bool isHorizontal { get; set; }
}
}
