최고의 전함 AI는 무엇입니까?
https://stackoverflow.com/questions/1631414
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
전함!
2003년(제가 17살이었을 때)에 저는 대회에 참가했습니다. 전함 AI 코딩대회.비록 그 대회에서 졌지만, 저는 정말 즐거웠고 많은 것을 배웠습니다.
이제 최고의 전함 AI를 찾기 위한 이 경쟁을 부활시키고 싶습니다.
여기는 이제 Bitbucket에서 호스팅되는 프레임워크.
우승자는 +450 평판을 받게 됩니다! 대회는 다음달부터 진행될 예정이다. 2009년 11월 17일.17일 0시 이후에는 입력이나 수정이 허용되지 않습니다.(Central Standard Time) 항목을 일찍 제출하므로 기회를 놓치지 마십시오!
이것을 유지하려면 목적, 대회 정신을 따르십시오.
게임의 규칙:
- 게임은 10x10 그리드에서 진행됩니다.
- 각 참가자는 5개의 선박(길이 2, 3, 3, 4, 5)을 그리드에 배치합니다.
- 함선은 겹쳐질 수 없지만 인접할 수는 있습니다.
- 그런 다음 경쟁자들은 차례로 상대에게 단발 사격을 가합니다.
- 게임의 변형에서는 발리당 여러 발을 발사할 수 있으며, 살아남은 선박마다 하나씩 발사할 수 있습니다.
- 상대방은 샷이 가라앉거나, 맞거나, 빗나가면 선수에게 알립니다.
- 한 플레이어의 선박이 모두 침몰하면 게임 플레이가 종료됩니다.
대회 규칙:
- 최고의 배틀쉽 알고리즘을 찾는 것이 대회의 정신입니다.
- 대회 정신에 어긋난다고 판단되는 모든 행위는 실격 사유가 됩니다.
- 상대방을 방해하는 것은 경쟁 정신에 어긋납니다.
- 멀티스레딩은 다음 제한 사항에 따라 사용될 수 있습니다.
- 자신의 차례가 아닌 동안에는 하나 이상의 스레드가 실행될 수 없습니다.(그러나 "일시중단" 상태에 있는 스레드 수에는 제한이 없습니다.)
- 스레드는 "일반" 이외의 우선순위로 실행될 수 없습니다.
- 위의 두 가지 제한 사항을 고려하면 자신의 차례 동안 최소 3개의 전용 CPU 코어가 보장됩니다.
- 게임당 1초의 CPU 시간 제한이 기본 스레드의 각 경쟁자에게 할당됩니다.
- 시간이 부족하면 현재 게임에서 패배하게 됩니다.
- 처리되지 않은 예외가 있으면 현재 게임에서 패배하게 됩니다.
- 네트워크 액세스 및 디스크 액세스는 허용되지만 시간 제한이 상당히 제한적일 수 있습니다.그러나 시간 부담을 완화하기 위해 몇 가지 설정 및 분해 방법이 추가되었습니다.
- 코드는 답변으로 스택 오버플로에 게시되어야 하며, 너무 크면 링크되어야 합니다.
- 항목의 최대 총 크기(압축되지 않음)는 1MB입니다.
- 공식적으로는 .Net 2.0 / 3.5가 유일한 프레임워크 요구사항입니다.
- 귀하의 항목은 IBattleshipOpComponent 인터페이스를 구현해야 합니다.
점수:
- 101개 게임 중 51개 게임을 가장 잘한 게임이 해당 경기의 승자가 됩니다.
- 모든 참가자는 라운드 로빈 방식으로 서로 대결하여 플레이합니다.
- 그런 다음 참가자 중 상위 절반이 더블 엘리미네이션 토너먼트를 플레이하여 승자를 결정합니다.(실제로는 절반보다 크거나 같은 가장 작은 2의 거듭제곱입니다.)
- 나는 토너먼트Api 토너먼트를 위한 프레임워크.
- 결과는 여기에 게시됩니다.
- 두 개 이상의 출품작을 제출하는 경우 가장 높은 점수를 받은 출품작만 더블 엘리밍 자격을 얻게 됩니다.
행운을 빌어요!재미있게 보내세요!
편집 1:
덕분에 해방됨, 누가 오류를 발견했는지 Ship.IsValid 기능.문제가 해결되었습니다.업데이트된 버전의 프레임워크를 다운로드하세요.
편집 2:
디스크 등에 통계를 유지하는 데 상당한 관심이 있었기 때문에 필요한 기능을 제공해야 하는 몇 가지 시간 제한이 없는 설정 및 해제 이벤트를 추가했습니다.이것은 반 파괴적인 변화.즉 말하자면:기능을 추가하도록 인터페이스가 수정되었지만 본문은 필요하지 않습니다.업데이트된 버전의 프레임워크를 다운로드하세요.
편집 3:
버그 수정 1: GameWon 그리고 GameLost 타임아웃이 발생한 경우에만 전화를 받았습니다.
버그 수정 2:게임마다 엔진의 시간이 초과된다면 경쟁은 결코 끝나지 않을 것입니다.
업데이트된 버전의 프레임워크를 다운로드하세요.
편집 4:
토너먼트 결과:
해결책
나는 경기당 더 많은 게임을 하기로 동의했습니다.50개의 게임을 하는 것은 단지 동전을 던지는 것과 같습니다.테스트 알고리즘 간의 합리적인 구별을 얻으려면 1000개의 게임을 수행해야 했습니다.
다운로드 드레드노트 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<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() { }
}
}
사람들이 대결할 상대는 다음과 같습니다.
고정된 기하학에서 영감을 받은 전략을 사용하는 대신에 기본 확률을 추정 어떤 특정 미지의 공간에는 배가 있다는 것입니다.
이를 올바르게 수행하려면 현재 세계관에 맞는 선박의 가능한 모든 구성을 탐색한 다음 해당 구성을 기반으로 확률을 계산해야 합니다.나무를 탐색하는 것과 같다고 생각할 수 있습니다.
가능한 전함 상태의 확장 http://natekohl.net/media/battleship-tree.png
당신이 세상에 대해 알고 있는 것과 어울리는 그 나무의 모든 나뭇잎을 고려한 후에 (예:함선은 겹칠 수 없으며 모든 적중 사각형은 함선이어야 합니다. 등) 탐험되지 않은 각 위치에서 선박이 얼마나 자주 발생하는지 계산하여 선박이 그곳에 있을 가능성을 추정할 수 있습니다.
이는 핫스팟에 선박이 포함될 가능성이 더 높은 열 지도로 시각화할 수 있습니다.
각 미개척 위치에 대한 확률 히트맵 http://natekohl.net/media/battleship-probs.png
이 전함 대회에서 제가 좋아하는 점 중 하나는 위의 트리가 이런 종류의 알고리즘을 무차별 공격할 수 있을 만큼 작다는 것입니다.5척의 선박 각각에 대해 최대 150개의 가능한 위치가 있다면 이는 150개입니다.5 = 750억 가지 가능성.그리고 그 숫자는 더욱 작아질 뿐입니다. 특히 함선 전체를 제거할 수 있는 경우에는 더욱 그렇습니다.
위에 링크한 상대는 트리 전체를 탐색하지 않습니다.750억 달러는 1초도 채 안 되기에는 여전히 큰 규모입니다.그러나 몇 가지 경험적 방법을 사용하여 이러한 확률을 추정하려고 시도합니다.
완전히 맹렬한 답변은 아니지만 일반적인 코드로 실제 답변을 혼란스럽게하는 점은 거의 없습니다. 따라서 나는 오픈 소스의 정신으로 확장/일반 클래스를 제시합니다. 이것을 사용하는 경우 네임 스페이스를 변경하거나 모든 것을 하나의 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<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
}
}
일부 확장자,이 중 일부는 기본 프레임 워크에서 기능을 복제하지만 실제로 수행해야합니다.
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));
}
}
}
내가 많이 사용하게됩니다.
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<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!");
}
}
}
지금은 완전한 알고리즘을 작성할 시간이 없지만 다음과 같은 생각을 해보겠습니다.상대가 무작위로 배를 배치했다면 배치 확률은 (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<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() { }
}
}
여기에서 최소한의 공간을 차지하기 위해 약간 압축되어 있으며 여전히 읽을 수 있습니다.
경쟁 엔진에 대한 몇 가지 의견 :
NewGame 매개 변수 :
iBattleshipopponent :: NewGame이 게임 전 설정을위한 것이고 보드 크기를 가져 오면 선박과 해당 크기의 목록도 가져와야합니다. 가변 선박 구성을 허용하지 않고 가변 보드 크기를 허용하는 것은 의미가 없습니다.
선박은 봉인됩니다 :
클래스 선박이 봉인 된 이유는 없습니다. 다른 기본 사항 중에서도 선박이 이름을 갖기를 원하므로 다음과 같은 메시지를 출력 할 수 있습니다. ( "당신은 내 {0}를 가라 앉았습니다", ship.name);. 나는 다른 연장도 염두에두고 있으므로 선박은 상속 될 수 없다고 생각합니다.
시간 제한 :
1 초의 시간 제한은 토너먼트 규칙에 적합하지만 디버깅을 완전히 엉망으로 만듭니다. 전함 경쟁은 개발/디버깅을 돕기 위해 시간의 폭력을 무시할 수있는 쉽게 설정해야합니다. 또한 System.Diagnostics.Process :: 사용자 프로세스 현상 / 권한이있는 ProcessOrtime / TotalProcessortime을 조사하는 것이 좋습니다.
침몰 함 :
현재 API는 상대방의 선박을 가라 앉을 때 알려줍니다.
ShotHit(Point shot, bool sunk);
하지만 어느 당신을 가라 앉으세요! 나는 "당신이 내 전함을 가라 앉았다"고 선언 해야하는 인간의 배틀 규칙의 일부를 고려합니다. (또는 구축함 또는 서브 등).
이것은 AI가 서로 맞은 배를 씻어 내려고 할 때 특히 중요합니다. API 변경을 요청하고 싶습니다.
ShotHit(Point shot, Ship ship);
만약에 배 널이 아닌 것은 샷이 싱킹 샷 이었음을 의미하며, 당신이 어느 배를 가라 앉았는지, 얼마나 길었는지 알고 있습니다. 샷이 싱크하지 않은 샷이라면, 선박은 null이며, 더 이상의 정보가 없습니다.
크로스 파이어 업데이트. 나는 그것이 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<OpponentsBoardState> opponentsBoard = new BoardView<OpponentsBoardState>(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<OpponentsBoardState>(size);
this.gridOddEven = rand.Pick(new[] { 0, 1 });
}
public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection<Ship> ships)
{
BoardView<bool> board = new BoardView<bool>(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<OpponentsBoardState> 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<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
}
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!");
}
}
#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<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, 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<T>(this IEnumerable<T> things, Battleship.ShuggyCoUk.Simple.Rand rand)
{
int count = things.Count();
if (count == 0)
return default(T);
return things.ElementAt(rand.Next(count));
}
}
}
이것은 내가 자유 시간에 모일 수있는 최선의 방법입니다. 이것은 존재하지 않습니다. 키를 누를 때까지 기본 함수를 루프하고 지속적으로 전함을 실행하기 위해 게임과 일치하는 통계가 진행되고 있습니다.
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<Point> scanShots;
List<NextShot> 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<Point>();
nextShots = new List<NextShot>();
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<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()
{
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<ScanShot> scanShots = new List<ScanShot>();
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<ScanShot> scanShots2 = new List<ScanShot>();
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에 대해 훨씬 덜 발전한 이전 버전으로서 잘 작동하지 않습니다.
내 컴퓨터는 지금 Dell에 의해 수리 중이지만 지난 주에있는 곳입니다.
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; }
}
}
당신이 당신의 분석을 강요하는 경우, 당신은 공급 된 무작위 탑재료의 메커니즘을 비효율적으로 발견 할 수 있습니다. 그것은 이미 대상 위치를 재 선출 할 수있게하고 프레임 워크가 아직 터치하지 않은 사람 또는 이동당 타임 미트가 만료 될 때까지 반복 할 수 있도록합니다.
이 상대는 비슷한 동작을 가지고 있습니다 (유효 배치 분포는 동일합니다)는 자체적으로 자체적으로 확인하고 호출 당 하나의 임의의 숫자 생성 만 소비합니다 (상각)).
이것은 내 확장/라이브러리 답변에서 클래스를 사용하며 주요 방법/상태 만 제공합니다.
셔플이 들어 올렸습니다 여기서 Jon Skeet의 대답
class WellBehavedRandomOpponent : IBattleShipOpponent
{
Rand rand = new Rand();
List<Point> guesses;
int nextGuess = 0;
public void PlaceShips(IEnumerable<Ship> ships)
{
BoardView<bool> board = new BoardView<bool>(BoardSize);
var AllOrientations = new[] {
ShipOrientation.Horizontal,
ShipOrientation.Vertical };
foreach (var ship in ships)
{
while (!ship.IsPlaced)
{
var l = rand.Pick(board.Select(c => c.Location));
var o = rand.Pick(AllOrientations);
if (ship.IsLegal(ships, BoardSize, l, o))
ship.Place(l, o);
}
}
}
public void NewGame(Size size, TimeSpan timeSpan)
{
var board = new BoardView<bool>(size);
this.guesses = new List<Point>(
board.Select(x => x.Location).Shuffle(rand));
nextGuess = 0;
}
public System.Drawing.Point GetShot()
{
return guesses[nextGuess++];
}
// empty methods left out
}
저는 참여할 수는 없지만 시간이 있으면 구현하고 싶은 알고리즘은 다음과 같습니다.
첫째, 명중을 감지하면 배의 나머지 부분을 즉시 추적하지 않습니다. 배 위치 테이블을 만들고 배를 완전히 가라앉히기 시작하기 전에 적어도 한 번은 5개를 모두 명중했는지 파악합니다.(이것은 다중 샷 변형에 대한 잘못된 정책입니다. 설명 참조)
- 중앙을 누르세요(아래 마지막 참고 사항 참조 - '중앙'은 설명의 편의를 위한 것일 뿐입니다).
- 중앙 오른쪽 4번 지점을 터치하세요.
- 중앙에서 아래쪽 1번 지점과 오른쪽 지점 1번을 공격하세요.
- 이전 타격의 오른쪽 4번째 지점을 공격합니다.
해당 패턴으로 계속 진행합니다(보드를 채우는 3개의 공간으로 구분된 대각선으로 끝나야 함). 이는 4개 및 5개 길이의 보트 모두에 적용되어야 하며 통계적으로 많은 수의 3개 및 2개 보트에 적용되어야 합니다.
대각선 사이에서 무작위로 지점을 치기 시작하면 아직 발견되지 않은 2~3개의 길이 보트를 잡을 수 있습니다.
5개의 히트를 감지하면 5개의 히트가 별도의 보트에 있는지 확인합니다.두 번의 히트가 동일한 수평 또는 수직선에 있고 서로 5개 위치 내에 있는 위치 근처에서 몇 번 더 샷을 하면 비교적 쉽습니다(같은 보트에서 두 번의 히트일 수 있음).만약 그들이 별도의 배라면 계속해서 모든 배를 침몰시키십시오.동일한 보트인 것으로 확인되면 5개의 보트를 모두 찾을 때까지 위의 채우기 패턴을 계속합니다.
이 알고리즘은 간단한 채우기 알고리즘입니다.주요 특징은 아직 알지 못하는 선박이 있을 때 알고 있는 선박을 침몰시키는 데 시간을 낭비하지 않으며 비효율적인 채우기 패턴을 사용하지 않는다는 것입니다(즉, 완전히 무작위 패턴은 낭비가 됩니다).
최종 참고사항:
A) "센터"는 보드의 임의의 시작점입니다.이는 이 알고리즘의 주요 약점을 제거합니다.B) 설명에는 처음부터 즉시 대각선을 그리는 것으로 나와 있지만 이상적으로 알고리즘은 해당 대각선을 따라 있는 '임의' 위치에서만 촬영합니다.이는 경쟁자가 자신의 선박이 예측 가능한 패턴에 부딪힐 때까지의 시간을 측정하는 것을 방지하는 데 도움이 됩니다.
이는 (9x9)/2+10 샷 미만의 모든 함선을 얻을 수 있다는 점에서 '완벽한' 알고리즘을 설명합니다.
그러나 다음과 같이 크게 개선될 수 있습니다.
배가 충돌하면 '내부' 대각선을 그리기 전에 크기를 확인하십시오.2개의 배를 발견했을 수도 있습니다. 이 경우 내부 대각선을 단순화하여 3개의 크기 배를 더 빨리 찾을 수 있습니다.
게임의 단계를 파악하고 그에 따라 행동하세요.이 알고리즘은 게임의 특정 시점까지는 좋을 수 있지만 최종 게임의 일부로 다른 알고리즘이 더 나은 이점을 제공할 수 있습니다.또한, 다른 플레이어가 당신을 이길 가능성이 매우 높다면 다른 알고리즘이 더 잘 작동할 수 있습니다. 예를 들어 위험도가 높은 알고리즘은 더 자주 실패할 수 있지만 작동하면 빠르게 작동하며 당신보다 승리에 더 가까운 상대를 이길 수 있습니다. .
경쟁자의 플레이 스타일을 식별하십시오. 이는 그들이 함선 배치를 계획하는 방법에 대한 단서를 제공할 수 있습니다. 즉, 자신의 알고리즘이 자신의 함선 배치 방법을 가장 빠르게 식별할 가능성이 높습니다. 가지고 있는 유일한 도구가 망치뿐인 경우, 모든 것이 못처럼 보인다)
-아담
내 항목.
굉장히 특별한 것은 없으며, 내가 가진 모든 좋은 아이디어를 추가 할 시간이 없었습니다.
그러나 그것은 상당히 잘 작동하는 것 같습니다. 우리는 그것이 경쟁에서 어떻게하는지 볼 것입니다 :
(이것을 파일에 넣으십시오 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;
}
}
이것은 Minimax가 아닙니다. 실제로 배를 배치 한 후, 각 플레이어가 스스로 플레이 할 수 없어서 여러 번의 턴으로 인해 모든 상대선을 가라 앉히는 데 걸렸습니까? 턴이 적은 승리는 승리합니다.
나는 히트 선박을 가라 앉히고 선박이 숨길 수있는 나머지 장소를 다루기 위해 샷 수를 최소화하려고 노력하는 것 외에도 좋은 일반적인 전략이 있다고 생각하지 않습니다.
물론 무작위가 아닌 것에 대한 반대 전략이있을 수 있습니다. 그러나 나는 가능한 모든 플레이어들에게 좋은 전략이 있다고 생각하지 않습니다.
실제로, 나는 퍼즐의 가장 큰 문제는 본질적으로 두 가지 움직임이 있다는 것입니다. 한 번의 움직임은 배를 배치하고, 다른 하나는 적의 선박을 찾는 것입니다 (그러나 두 번째 부분은 임의의 요인으로 시계를이기는 것 외에도 '알고리즘 실행')을 제외하고는 두 번째 부분이 될 수 있음을 세분화했습니다). 적의 전략을 결정하고 대응하려는 메커니즘은 없으며, 이는 "록 페이퍼 가위"의 연속적인 라운드를 기반으로 비슷한 경쟁을하는 것입니다.
또한 게임을 네트워크 프로토콜로 지정한 다음 모든 솔루션이 C#이어야한다고 지시하는 대신 C#에서 해당 프로토콜을 구현하기위한 프레임 워크를 제공하면 더 시원 할 것이라고 생각합니다.
편집 : 경쟁 규칙을주의 깊게 읽지 않았기 때문에 초기 요점을 철회합니다.
나는 항상 중간에서 시작하고 그 한 지점에서 나선형을 좋아하는 것을 좋아했습니다. 그 지점에서 1 개 이상의 빈 공간을 남기지 않기 위해 Goddam Sub를 설명하기 위해 다른 지점 사이에 1 개 이상의 빈 공간이 남았습니다. B-선시가 마지막 인 경우, 샷은 낭비 된 샷을 최소화하기 위해 4 개의 공간 만 남겨야 만하면
영국 컴퓨터 소사이어티를 대신하여 서리 대학교의 제임스 헤더 (James Heather)와 비슷한 경쟁이있었습니다.
자원에 대한 제한 사항, 즉 턴당 최대 프로세서 시간, 이동 사이에 상태가 저장 될 수 없으며 최대 힙 크기가 부과되었습니다. 시간을 제한하기 위해 AI는 타임 슬롯 내 어느 시점에서든 이동을 제출할 수 있으며 턴이 끝날 때 이동을 요청받을 것입니다.
매우 흥미 롭습니다 - 자세히보기 : http://www.bcsstudentcontest.com/
더 많은 아이디어를 줄 수 있습니다.
그대로, 솔루션은 Ubuntu 9.10 Linux의 Monodevelop에서 수정없이 열리고 실행됩니다.
당신은 다음과 같이 썼습니다.
- 경쟁의 정신에 반대하는 것은 실격의 근거가 될 것입니다.
- 상대를 방해하는 것은 경쟁의 정신에 반대합니다.
"경쟁의 정신에 대한"와 "상대방을 방해"하는 것을 정의하십시오.
또한 - 단순화하려면 다음을 추천합니다.
- 상대방의 CPU 슬롯 중에 CPU를 전혀 사용하지 못하게하십시오.
- 스레드 병렬 처리를 허용하지 않고 대신 단일 스레드에서 더 많은 CPU를 제공하십시오. 이것은 AI의 프로그래밍을 단순화하고 어쨌든 CPU/메모리에 묶인 사람을 해치지 않을 것입니다.
추신 - 여기에 숨어있는 CS Post -Docs에 대한 질문 :이 게임은 해결할 수 없다 (즉, 단일 최상의 전략이 있습니까?). 그렇습니다. 보드 크기와 단계의 수로는 Minimax 등의 필수를 의무적으로 만들지 만 여전히 궁금해해야합니다.
나는 상대방의 임의의 종자와 호출 패턴을 리버스 엔지니어링하는 사람이 이길 것으로 예상합니다.
그럴 가능성이 확실하지 않습니다.
아마도 게임의 변형으로 일련의 이들을 실행하는 것이 가능할 것입니다.
3D 비행기와 같은 물건을 추가하거나 턴을 위해 촬영 대신 촬영 대신 단일 선박을 움직일 수 있으면 게임이 공정한 부분을 바꿀 수 있습니다.
1 초 총 게임 시간은 기계에 따라 다릅니다. CPU 운영의 2 초만에 토너먼트 머신에 비해 내 기계에서 다를 것입니다. 전장 선박 알고리즘을 최적화하여 1 초 이내에 가장 많은 CPU 시간을 활용하면 더 느린 토너먼트 머신에서 실행되면 항상 잃게됩니다.
프레임 워크 의이 한계를 해결하는 방법을 잘 모르겠지만 해결해야합니다.
...
한 가지 아이디어는이 경쟁에서 수행 한 일을하는 것입니다. http://www.bcsstudentcontest.com/
최대 총 게임 시간과 달리 최대 턴당 최대 시간을 갖습니다. 이런 식으로 알고리즘을 알고있는 시간 내에 맞게 제한 할 수 있습니다. 게임은 50 ~ 600 회 이상 지속될 수 있습니다. 내 알고리즘이 총 게임 시간을 관리하면 최상의 작업을 수행하기에 충분한 시간을주지 않거나 너무 많은 시간을주고 잃을 수 있습니다. 전함 알고리즘 내에서 총 게임 시간을 관리하는 것은 매우 어렵습니다.
총 게임 시간이 아닌 턴 시간을 제한하기 위해 규칙을 변경하는 것이 좋습니다.
편집하다
가능한 모든 샷을 열거 한 다음 순위를 매기는 알고리즘을 작성하면 최고 순위 샷을 얻습니다. 가능한 모든 샷을 생성하는 데 너무 오래 걸릴 것이므로 알고리즘을 일정 시간 동안 실행 한 다음 중지 할 것입니다.
턴 기반 한계가 있으면 알고리즘을 0.9 초 동안 실행하고 최고 순위 샷을 반환하고 턴 시간 제한과 잘 어울릴 수 있습니다.
1 초의 총 게임 시간으로 제한되면 각 턴마다 알고리즘이 얼마나 오래 실행되어야하는지 결정하기가 어렵습니다. CPU 시간을 최대한 활용하고 싶습니다. 게임이 500 라운드에서 지속되면 각 턴마다 0.002 초로 제한 할 수 있지만, 게임이 100 라운드 지속되면 각 턴마다 0.01 초의 CPU 시간을 줄 수 있습니다.
알고리즘이 샷 공간의 반기적 인 검색을 사용하여 현재 제한 사항으로 최고의 샷을 찾는 것은 비현실적입니다.
1 초 총 게임 시간은 게임에서 경쟁하는 데 효과적으로 사용할 수있는 알고리즘 유형을 제한하는 것입니다.
나는 실제 코드를 넣지 않아 여기서 겁을 먹습니다. 그러나 나는 일반적인 관찰을 위험에 빠뜨릴 것입니다.
- 모든 선박의 크기가 2 개 이상이므로 Space Quest V에서 게임 구현에서 본 최적화를 사용할 수 있습니다.이 게임은 대상을 찾는 동안 다이아몬드 패턴의 대체 셀에서만 발사됩니다. 이것은 사각형의 절반을 제거하지만 여전히 모든 선박을 찾을 수 있다고 보장합니다.
- 목표를 찾을 때 무작위 발사 패턴은 통계적으로 많은 게임에서 최상의 결과를 얻을 수 있습니다.
! [확률 밀도] [1] 이미지 설명 입력 그녀
! [여기에 이미지 설명 입력] [2
나는 Randon Shooting vs a Dumb Hunt/Target과 마지막으로 정교한 검색의 결과를 비교하는 실험을 실험했습니다.
최상의 솔루션은 나머지 선박에서 개별 정사각형이 사용될 가능성에 대한 확률 밀도 함수를 만드는 것 같습니다.
여기에서 내 결과를 볼 수 있습니다 여기에 링크 설명을 입력하십시오
"전함"은 고전적인 컴퓨터 과학 NP- 완성 문제로 알려진 것입니다.
http://en.wikipedia.org/wiki/list_of_np-complete_problems
(전함을 찾으십시오 - 게임과 퍼즐 아래에 있습니다)
제휴하지 않습니다 StackOverflow
