战舰!
早在2003年(当时我17岁),我就参加了战舰AI编码比赛.即使我输掉了那场比赛,我也玩得很开心并从中学到了很多东西.
现在,我想在这场比赛中复活,寻找最好的战舰AI.
这是框架,现在托管在Bitbucket上.
获奖者将获得+450声望!比赛将于2009年11月17日开始.不接受17日零时以外的参赛作品或编辑.(中央标准时间)提前提交您的参赛作品,这样您就不会错过机会!
为了保持这个目标,请遵循竞争精神.
游戏规则:
游戏将在10x10网格上进行.
每个参赛者将5艘船(长度分别为2,3,3,4,5)放置在其网格上.
没有船只可能重叠,但它们可能相邻.
然后竞争对手轮流对对手开枪.
游戏的一个变种允许每次击球射击多次射击,每个幸存的船只射击一次.
如果击球下沉,命中或未命中,对手将通知对手.
当任何一个玩家的所有船只都沉没时,游戏结束.
比赛规则:
竞争的精神是找到最好的战舰算法.
任何被视为违反竞争精神的东西都将被取消资格.
干扰对手是违背竞争精神的.
多线程可以在以下限制下使用:
在轮到你的时候,不超过一个线程可能正在运行.(但是,任意数量的线程可能处于"暂停"状态).
没有线程可以以"正常"以外的优先级运行.
鉴于上述两个限制,您将在转弯期间保证至少3个专用CPU核心.
每个游戏的CPU时间限制为1秒,分配给主线程上的每个竞争对手.
时间不多会导致当前游戏失败.
任何未处理的异常都将导致失去当前的游戏.
允许网络访问和磁盘访问,但您可能会发现时间限制相当令人望而却步.然而,为了减轻时间紧张,增加了一些设置和拆卸方法.
代码应作为答案发布在堆栈溢出上,或者如果太大则链接.
条目的最大总大小(未压缩)为1 MB.
官方说来,.Net 2.0/3.5是唯一的框架要求.
您的条目必须实现IBattleshipOpponent接口.
评分:
101场比赛中最好的51场比赛是一场比赛的胜利者.
所有竞争对手都将相互配对,循环风格.
然后,最好的一半竞争者将参加双重淘汰赛以确定获胜者.(实际上,2的最小功率大于或等于一半.)
我将使用TournamentApi框架进行锦标赛.
结果将在此处公布.
如果您提交了多个条目,则只有您的得分最高的条目才有资格获得双重条目.
祝好运!玩得开心!
编辑1:
感谢Freed,他在Ship.IsValid函数中发现了一个错误.它已被修复.请下载该框架的更新版本.
编辑2:
由于人们对将统计信息持久存储到磁盘等方面非常感兴趣,因此我添加了一些应该提供所需功能的非定时设置和拆除事件.这是一个半破坏性的变化.也就是说:界面已经过修改以添加功能,但不需要它们.请下载该框架的更新版本.
编辑3:
错误修复1:GameWon并且GameLost只在超时的情况下被调用.
错误修复2:如果引擎在每场比赛中超时,则比赛永远不会结束.
请下载该框架的更新版本.
编辑4:
比赛结果:
我的动议是每场比赛做更多的比赛.做50场比赛只是翻硬币.我需要做1000场比赛才能在测试算法之间做出任何合理的区分.
下载Dreadnought 1.2.
策略:
跟踪> 0次点击的船舶的所有可能位置.列表永远不会超过~30K,所以它可以保持准确,不像所有船舶的所有可能位置列表(非常大).
GetShot算法有两个部分,一个用于生成随机镜头,另一个用于尝试完成已经击中的船只.如果有可能的位置(从上面的列表中),我们会随机拍摄,其中所有命中的船都沉没.否则,我们会尝试通过选择射击位置来完成沉没,从而消除最可能的位置(加权).
对于随机镜头,根据其中一个未经破坏的船舶重叠位置的可能性,计算最佳拍摄位置.
自适应算法,将船舶放置在对手在统计上不太可能射击的位置.
自适应算法,它倾向于在对手在统计上更可能放置他的船的位置进行射击.
船只大多不相互接触.
这是我的参赛作品!(最天真的解决方案)
"随机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 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() { }
}
}
这是人们对抗的对手:
http://natekohl.net/files/FarnsworthOpponent.cs
我认为尝试估计任何特定的未探测空间拥有船舶的潜在概率将是有趣的,而不是使用固定的几何启发策略.
要做到这一点,您将探索适合您当前世界观的所有可能的船舶配置,然后根据这些配置计算概率.你可以把它想象成一棵树:
扩大可能的战舰状态http://natekohl.net/media/battleship-tree.png
在考虑了那棵树的所有树叶与你对世界的了解(例如船只不能重叠,所有的击中方格必须是船只等)之后,你可以计算船舶在每个未探测位置发生的频率,以估计出现的可能性.一艘船正坐在那里.
这可以被视为热图,其中热点更可能包含船只:
每个未探索位置的概率热图http://natekohl.net/media/battleship-probs.png
我喜欢这个战舰竞赛的一件事是,上面的树几乎小到可以强制使用这种算法.如果5艘船中每艘船有150个可能的位置,那就是150 5 = 750亿的可能性.而这个数字只会变小,特别是如果你可以消灭整艘船.
我上面链接的对手没有探索整棵树; 在一秒钟之内,还有750亿美元可以进入市场.尽管如此,它还是试图通过一些启发式方法来估计这些概率.
这不是一个完全成熟的答案,但似乎没有什么地方使用常见的代码来弥补真正的答案.因此,我以开源的精神提出了一些扩展/一般类.如果您使用这些,请更改命名空间或尝试将所有内容编译成一个dll不起作用.
BoardView可让您轻松使用带注释的电路板.
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
{
private readonly BoardView view;
public readonly int X;
public readonly int Y;
public T Data;
public double Bias { get; set; }
public Cell(BoardView 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 FoldAll(U acc, Func, U, U> trip)
{
return new[] { Compass.North, Compass.East, Compass.South, Compass.West }
.Select(x => FoldLine(x, acc, trip));
}
public U FoldLine(Compass direction, U acc, Func, 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 North
{
get { return view.SafeLookup(X, Y - 1); }
}
public Cell South
{
get { return view.SafeLookup(X, Y + 1); }
}
public Cell East
{
get { return view.SafeLookup(X+1, Y); }
}
public Cell West
{
get { return view.SafeLookup(X-1, Y); }
}
public IEnumerable> 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 : IEnumerable>
{
public readonly Size Size;
private readonly int Columns;
private readonly int Rows;
private Cell[] history;
public BoardView(Size size)
{
this.Size = size;
Columns = size.Width;
Rows = size.Height;
this.history = new Cell[Columns * Rows];
for (int y = 0; y < Rows; y++)
{
for (int x = 0; x < Rows; x++)
history[x + y * Columns] = new Cell(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 SafeLookup(int x, int y)
{
int index = SafeCalc(x, y, false);
if (index < 0)
return null;
return history[index];
}
#region IEnumerable> Members
public IEnumerator> GetEnumerator()
{
foreach (var cell in this.history)
yield return cell;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public BoardView Transform(Func transform)
{
var result = new BoardView(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,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
}
}
一些扩展,其中一些在主框架中重复功能,但应该由您完成.
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 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 ships,
Point location,
ShipOrientation direction)
{
var temp = new Ship(ship.Length);
temp.Place(location, direction);
var occupied = new HashSet(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 MakeShips(params int[] lengths)
{
return new System.Collections.ObjectModel.ReadOnlyCollection(
lengths.Select(l => new Ship(l)).ToList());
}
public static IEnumerable Shuffle(this IEnumerable 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(this IEnumerable things, Rand rand)
{
int count = things.Count();
if (count == 0)
return default(T);
return things.ElementAt(rand.Next(count));
}
}
}
我最终使用了很多东西.
enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
随机化.安全但可测试,对测试很有用.
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(IEnumerable things)
{
return things.ElementAt(Next(things.Count()));
}
public T PickBias(Func bias, IEnumerable 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!");
}
}
}
我现在没有时间写一个完整的算法,但是这里有一个想法:如果你的对手随机放置船只,那么放置概率不是一个以(5.5,5.5)为中心的简单分布吗？例如,x维度中战舰(5个单位长)的放置可能性如下:
x 1 2 3 4 5 6 7 8 9 10 P(x) 2 4 6 8 10 10 8 6 4 2
相同的计算对y有效.其他船只不会有陡峭的分布,但你最好的猜测仍然是中心.在那之后,数学方法将慢慢地将对角线(可能是普通船的长度,17/5)从中心辐射出去.例如:
........... ....x.x.... .....x..... ....x.x.... ...........
显然,需要在这个想法中增加一些随机性,但我认为纯粹在数学上是这样的.
没有什么比这更复杂但是我想出了什么.它以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 HitShots = new LinkedList();
private LinkedList Shots = new LinkedList();
private List PatternShots = new List();
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 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() { }
}
}
略微浓缩,占据这里的最小空间,仍然可读.
关于比赛引擎的一些评论:
NewGame参数:
如果IBattleshipOpponent :: NewGame用于游戏前设置并采用板卡,它还应该列出船只及其各自的尺寸.在不允许变量船配置的情况下允许可变板尺寸是没有意义的.
船舶密封:
我没有看到任何理由为什么类船舶被密封.除了其他基本的东西,我希望Ships有一个名字,所以我可以输出消息,如("你沉没我的{0}",ship.Name); .我也有其他扩展,所以我认为Ship应该是可继承的.
时间限制:
虽然1秒的时间限制对锦标赛规则有意义,但它完全与调试混淆.BattleshipCompetition应该有一个简单的设置来忽略时间违规,以帮助开发/调试.我还建议调查System.Diagnostics.Process :: UserProcessorTime/Privileged ProcessorTime/TotalProcessorTime,以更准确地查看正在使用的时间.
沉船:
当您沉没一个oppenent的船时,当前的API会通知您:
ShotHit(Point shot, bool sunk);
但没有哪个你沉船!我认为它是人类战舰规则的一部分,你需要宣布"你沉没我的战舰!" (或驱逐舰,或子等).
当人工智能试图冲洗相互对接的船只时,这一点尤其重要.我想请求API更改为:
ShotHit(Point shot, Ship ship);
如果船只是非空的,则意味着该射击是一个沉没的射击,你知道你沉没了哪艘船,以及它有多长.如果射击是非沉没射击,那么船只为空,你没有进一步的信息.
CrossFire已更新.我知道它无法与Farnsworth或Dreadnought竞争,但它比后者快得多,并且在任何人都想尝试的情况下都很简单.这取决于我的库的当前状态,包含在这里以使其易于使用.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;
using System.IO;
using System.Collections.ObjectModel;
namespace Battleship.ShuggyCoUk
{
public class Simple : IBattleshipOpponent
{
BoardView opponentsBoard = new BoardView(new Size(10,10));
Rand rand = new Rand();
int gridOddEven;
Size size;
public string Name { get { return "Simple"; } }
public Version Version { get { return new Version(2, 1); }}
public void NewMatch(string opponent) {}
public void NewGame(System.Drawing.Size size, TimeSpan timeSpan)
{
this.size = size;
this.opponentsBoard = new BoardView(size);
this.gridOddEven = rand.Pick(new[] { 0, 1 });
}
public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection ships)
{
BoardView board = new BoardView(size);
var AllOrientations = new[] {
ShipOrientation.Horizontal,
ShipOrientation.Vertical };
foreach (var ship in ships)
{
int avoidTouching = 3;
while (!ship.IsPlaced)
{
var l = rand.Pick(board.Select(c => c.Location));
var o = rand.Pick(AllOrientations);
if (ship.IsLegal(ships, size, l, o))
{
if (ship.IsTouching(ships, l, o)&& --avoidTouching > 0)
continue;
ship.Place(l, o);
}
}
}
}
protected virtual Point PickWhenNoTargets()
{
return rand.PickBias(x => x.Bias,
opponentsBoard
// nothing 1 in size
.Where(c => (c.Location.X + c.Location.Y) % 2 == gridOddEven)
.Where(c => c.Data == OpponentsBoardState.Unknown))
.Location;
}
private int SumLine(Cell c, int acc)
{
if (acc >= 0)
return acc;
if (c.Data == OpponentsBoardState.Hit)
return acc - 1;
return -acc;
}
public System.Drawing.Point GetShot()
{
var targets = opponentsBoard
.Where(c => c.Data == OpponentsBoardState.Hit)
.SelectMany(c => c.Neighbours())
.Where(c => c.Data == OpponentsBoardState.Unknown)
.ToList();
if (targets.Count > 1)
{
var lines = targets.Where(
x => x.FoldAll(-1, SumLine).Select(r => Math.Abs(r) - 1).Max() > 1).ToList();
if (lines.Count > 0)
targets = lines;
}
var target = targets.RandomOrDefault(rand);
if (target == null)
return PickWhenNoTargets();
return target.Location;
}
public void OpponentShot(System.Drawing.Point shot)
{
}
public void ShotHit(Point shot, bool sunk)
{
opponentsBoard[shot] = OpponentsBoardState.Hit;
Debug(shot, sunk);
}
public void ShotMiss(Point shot)
{
opponentsBoard[shot] = OpponentsBoardState.Miss;
Debug(shot, false);
}
public const bool DebugEnabled = false;
public void Debug(Point shot, bool sunk)
{
if (!DebugEnabled)
return;
opponentsBoard.WriteAsGrid(
Console.Out,
x =>
{
string t;
switch (x.Data)
{
case OpponentsBoardState.Unknown:
return " ";
case OpponentsBoardState.Miss:
t = "m";
break;
case OpponentsBoardState.MustBeEmpty:
t = "/";
break;
case OpponentsBoardState.Hit:
t = "x";
break;
default:
t = "?";
break;
}
if (x.Location == shot)
t = t.ToUpper();
return t;
});
if (sunk)
Console.WriteLine("sunk!");
Console.ReadLine();
}
public void GameWon()
{
}
public void GameLost()
{
}
public void MatchOver()
{
}
#region Library code
enum OpponentsBoardState
{
Unknown = 0,
Miss,
MustBeEmpty,
Hit,
}
public enum Compass
{
North, East, South, West
}
class Cell
{
private readonly BoardView view;
public readonly int X;
public readonly int Y;
public T Data;
public double Bias { get; set; }
public Cell(BoardView 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 FoldAll(U acc, Func, U, U> trip)
{
return new[] { Compass.North, Compass.East, Compass.South, Compass.West }
.Select(x => FoldLine(x, acc, trip));
}
public U FoldLine(Compass direction, U acc, Func, 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 North
{
get { return view.SafeLookup(X, Y - 1); }
}
public Cell South
{
get { return view.SafeLookup(X, Y + 1); }
}
public Cell East
{
get { return view.SafeLookup(X + 1, Y); }
}
public Cell West
{
get { return view.SafeLookup(X - 1, Y); }
}
public IEnumerable> 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 : IEnumerable>
{
public readonly Size Size;
private readonly int Columns;
private readonly int Rows;
private Cell[] history;
public BoardView(Size size)
{
this.Size = size;
Columns = size.Width;
Rows = size.Height;
this.history = new Cell[Columns * Rows];
for (int y = 0; y < Rows; y++)
{
for (int x = 0; x < Rows; x++)
history[x + y * Columns] = new Cell(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 SafeLookup(int x, int y)
{
int index = SafeCalc(x, y, false);
if (index < 0)
return null;
return history[index];
}
#region IEnumerable> Members
public IEnumerator> GetEnumerator()
{
foreach (var cell in this.history)
yield return cell;
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public BoardView Transform(Func transform)
{
var result = new BoardView(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, 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
}
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(IEnumerable things)
{
return things.ElementAt(Next(things.Count()));
}
public T PickBias(Func bias, IEnumerable 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!");
}
}
#endregion
}
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 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 ships,
Point location,
ShipOrientation direction)
{
var temp = new Ship(ship.Length);
temp.Place(location, direction);
var occupied = new HashSet(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 MakeShips(params int[] lengths)
{
return new System.Collections.ObjectModel.ReadOnlyCollection(
lengths.Select(l => new Ship(l)).ToList());
}
public static IEnumerable Shuffle(this IEnumerable source, Battleship.ShuggyCoUk.Simple.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(this IEnumerable things, Battleship.ShuggyCoUk.Simple.Rand rand)
{
int count = things.Count();
if (count == 0)
return default(T);
return things.ElementAt(rand.Next(count));
}
}
}
这是我在空闲时间可以放在一起的最好的,这是不存在的.有一些游戏和匹配统计数据正在进行,因为我设置主要功能循环并连续运行BattleshipCompetition直到我按下一个键.
namespace Battleship
{
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
public class BP7 : IBattleshipOpponent
{
public string Name { get { return "BP7"; } }
public Version Version { get { return this.version; } }
Random rand = new Random();
Version version = new Version(0, 7);
Size gameSize;
List scanShots;
List nextShots;
int wins, losses;
int totalWins = 0;
int totalLosses = 0;
int maxWins = 0;
int maxLosses = 0;
int matchWins = 0;
int matchLosses = 0;
public enum Direction { VERTICAL = -1, UNKNOWN = 0, HORIZONTAL = 1 };
Direction hitDirection, lastShotDirection;
enum ShotResult { UNKNOWN, MISS, HIT };
ShotResult[,] board;
public struct NextShot
{
public Point point;
public Direction direction;
public NextShot(Point p, Direction d)
{
point = p;
direction = d;
}
}
public struct ScanShot
{
public Point point;
public int openSpaces;
public ScanShot(Point p, int o)
{
point = p;
openSpaces = o;
}
}
public void NewGame(Size size, TimeSpan timeSpan)
{
this.gameSize = size;
scanShots = new List();
nextShots = new List();
fillScanShots();
hitDirection = Direction.UNKNOWN;
board = new ShotResult[size.Width, size.Height];
}
private void fillScanShots()
{
int x;
for (x = 0; x < gameSize.Width - 1; x++)
{
scanShots.Add(new Point(x, x));
}
if (gameSize.Width == 10)
{
for (x = 0; x < 3; x++)
{
scanShots.Add(new Point(9 - x, x));
scanShots.Add(new Point(x, 9 - x));
}
}
}
public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection 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()
{
Point shot;
if (this.nextShots.Count > 0)
{
if (hitDirection != Direction.UNKNOWN)
{
if (hitDirection == Direction.HORIZONTAL)
{
this.nextShots = this.nextShots.OrderByDescending(x => x.direction).ToList();
}
else
{
this.nextShots = this.nextShots.OrderBy(x => x.direction).ToList();
}
}
shot = this.nextShots.First().point;
lastShotDirection = this.nextShots.First().direction;
this.nextShots.RemoveAt(0);
return shot;
}
List scanShots = new List();
for (int x = 0; x < gameSize.Width; x++)
{
for (int y = 0; y < gameSize.Height; y++)
{
if (board[x, y] == ShotResult.UNKNOWN)
{
scanShots.Add(new ScanShot(new Point(x, y), OpenSpaces(x, y)));
}
}
}
scanShots = scanShots.OrderByDescending(x => x.openSpaces).ToList();
int maxOpenSpaces = scanShots.FirstOrDefault().openSpaces;
List scanShots2 = new List();
scanShots2 = scanShots.Where(x => x.openSpaces == maxOpenSpaces).ToList();
shot = scanShots2[rand.Next(scanShots2.Count())].point;
return shot;
}
int OpenSpaces(int x, int y)
{
int ctr = 0;
Point p;
// spaces to the left
p = new Point(x - 1, y);
while (p.X >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.X--;
}
// spaces to the right
p = new Point(x + 1, y);
while (p.X < gameSize.Width && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.X++;
}
// spaces to the top
p = new Point(x, y - 1);
while (p.Y >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.Y--;
}
// spaces to the bottom
p = new Point(x, y + 1);
while (p.Y < gameSize.Height && board[p.X, p.Y] == ShotResult.UNKNOWN)
{
ctr++;
p.Y++;
}
return ctr;
}
public void NewMatch(string opponenet)
{
wins = 0;
losses = 0;
}
public void OpponentShot(Point shot) { }
public void ShotHit(Point shot, bool sunk)
{
board[shot.X, shot.Y] = ShotResult.HIT;
if (!sunk)
{
hitDirection = lastShotDirection;
if (shot.X != 0)
{
this.nextShots.Add(new NextShot(new Point(shot.X - 1, shot.Y), Direction.HORIZONTAL));
}
if (shot.Y != 0)
{
this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y - 1), Direction.VERTICAL));
}
if (shot.X != this.gameSize.Width - 1)
{
this.nextShots.Add(new NextShot(new Point(shot.X + 1, shot.Y), Direction.HORIZONTAL));
}
if (shot.Y != this.gameSize.Height - 1)
{
this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y + 1), Direction.VERTICAL));
}
}
else
{
hitDirection = Direction.UNKNOWN;
this.nextShots.Clear(); // so now this works like gangbusters ?!?!?!?!?!?!?!?!?
}
}
public void ShotMiss(Point shot)
{
board[shot.X, shot.Y] = ShotResult.MISS;
}
public void GameWon()
{
wins++;
}
public void GameLost()
{
losses++;
}
public void MatchOver()
{
if (wins > maxWins)
{
maxWins = wins;
}
if (losses > maxLosses)
{
maxLosses = losses;
}
totalWins += wins;
totalLosses += losses;
if (wins >= 51)
{
matchWins++;
}
else
{
matchLosses++;
}
}
public void FinalStats()
{
Console.WriteLine("Games won: " + totalWins.ToString());
Console.WriteLine("Games lost: " + totalLosses.ToString());
Console.WriteLine("Game winning percentage: " + (totalWins * 1.0 / (totalWins + totalLosses)).ToString("P"));
Console.WriteLine("Game losing percentage: " + (totalLosses * 1.0 / (totalWins + totalLosses)).ToString("P"));
Console.WriteLine();
Console.WriteLine("Matches won: " + matchWins.ToString());
Console.WriteLine("Matches lost: " + matchLosses.ToString());
Console.WriteLine("Match winning percentage: " + (matchWins * 1.0 / (matchWins + matchLosses)).ToString("P"));
Console.WriteLine("Match losing percentage: " + (matchLosses * 1.0 / (matchWins + matchLosses)).ToString("P"));
Console.WriteLine("Match games won high: " + maxWins.ToString());
Console.WriteLine("Match games lost high: " + maxLosses.ToString());
Console.WriteLine();
}
}
}
这个逻辑是我最接近Dreadnought的原因,赢得了大约41%的个人比赛.(实际上它确实以52比49的比分赢得了一场比赛.)奇怪的是,这个类对FarnsworthOpponent的表现不如早期版本那么先进得多.
戴尔现在正在修理我的电脑,但这是我上周所在的地方:
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 nextShots;
Queue 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();
this.scanShots = new Queue();
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 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 possible = new List(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; }
}
}
京公网安备 11010802040832号 | 京ICP备19059560号-6 