반응형
최고의 전함 AI는 무엇입니까?
전함!
2003 년 (17 살 때)에 전함 AI 코딩 경쟁에 참가했습니다. 토너먼트를 잃어 버렸지 만 많은 재미가 있었고 많은 것을 배웠습니다.
이제 최고의 전함 AI를 찾아이 경쟁을 부활시키고 싶습니다.
다음은 현재 Bitbucket에서 호스팅되는 프레임 워크 입니다.
우승자는 +450의 평판을 얻습니다! 대회는 2009 년 11 월 17 일에 시작됩니다 . 17 일 0시 이후의 항목이나 편집 내용은 허용되지 않습니다. (중부 표준시) 응모작을 일찍 제출하여 기회를 놓치지 마십시오!
이 목표 를 유지하려면 경쟁의 정신을 따르십시오.
게임의 규칙:
- 게임은 10x10 그리드에서 재생됩니다.
- 각 선수는 5 척의 배 (길이 2, 3, 3, 4, 5)를 그리드에 배치합니다.
- 선박은 겹칠 수 없지만 인접 할 수 있습니다.
- 그런 다음 선수들은 상대편에서 차례대로 한 번의 발사를한다.
- 게임의 변형으로 발리 당 생존 한 배당 하나씩 여러 발을 발사 할 수 있습니다.
- 상대방은 샷이 가라 앉거나 부딪 치면 경쟁자에게 알립니다.
- 한 플레이어의 모든 함선이 침몰되면 게임 플레이가 종료됩니다.
경쟁 규칙 :
- 경쟁의 정신은 최고의 전함 알고리즘을 찾는 것입니다.
- 경쟁의 정신에 반하는 것으로 여겨지는 것은 실격의 근거가됩니다.
- 상대방을 방해하는 것은 경쟁의 정신에 위배됩니다.
- 멀티 스레딩은 다음 제한 사항에 따라 사용될 수 있습니다.
- 귀하의 차례가 아닌 동안 하나 이상의 스레드가 실행될 수 있습니다. (다수의 스레드가 "일시 중단"상태 일 수 있습니다).
- "정상"이외의 우선 순위로 스레드를 실행할 수 없습니다.
- 위의 두 가지 제한 사항을 감안할 때, 턴 동안 최소 3 개의 전용 CPU 코어가 보장됩니다.
- 게임당 1 초의 CPU 시간 제한은 기본 스레드의 각 경쟁자에게 할당됩니다.
- 시간이 없으면 현재 게임에서 패배합니다.
- 처리되지 않은 예외는 현재 게임에서 패배합니다.
- 네트워크 액세스 및 디스크 액세스는 허용되지만 시간 제한은 상당히 금지되어 있습니다. 그러나 시간 왜곡을 완화하기 위해 몇 가지 설정 및 분해 방법이 추가되었습니다.
- 코드는 스택 오버플로에 대한 답변 또는 너무 큰 경우 링크로 게시해야합니다.
- 항목의 최대 총 크기 (비 압축)는 1MB입니다.
- 공식적으로 .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<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() { }
}
}
여기에 최소한의 공간을 차지하고 읽을 수 있도록 약간 압축되었습니다.
경쟁 엔진에 대한 의견 :
새로운 게임 파라미터 :
IBattleshipOpponent :: NewGame이 사전 게임 설정 용이며 보드 크기를 사용하는 경우, 선박 및 해당 크기 목록도 가져와야합니다. 가변 선박 구성을 허용하지 않고 가변 보드 크기를 허용하는 것은 의미가 없습니다.
선박은 밀봉되어 있습니다 :
클래스 함선이 봉인 된 이유가 없습니다 다른 기본 사항 중에서 Ships에 이름이 있기를 원하므로 ( "You sunk my {0}", ship.Name); . 다른 확장 기능도 염두에두고 Ship은 상속 가능해야한다고 생각합니다.
시간 제한 :
토너먼트 규칙에는 1 초의 시간 제한이 적합하지만 완전히 디버깅에 혼란을줍니다. 전함 경쟁은 개발 / 디버깅을 돕기 위해 시간 위반을 무시할 수있는 쉬운 환경을 갖추어야합니다. 얼마나 많은 시간이 사용되는지 더 정확하게 볼 수 있도록 System.Diagnostics.Process :: UserProcessorTime / Privileged ProcessorTime / TotalProcessorTime을 조사하는 것이 좋습니다.
침몰선 :
현재 API는 상대방의 함선을 침몰했을 때 알려줍니다.
ShotHit(Point shot, bool sunk);
그러나 당신이 침몰 한 배는 아닙니다 ! 나는 당신이 "전함 침몰했습니다!"라고 선언해야하는 인간-전함 규칙의 일부라고 생각합니다. (또는 구축함 또는 하위 등).
AI가 서로 맞대고있는 선박을 플러시하려고 할 때 특히 중요합니다. 다음과 같이 API 변경을 요청하고 싶습니다.
ShotHit(Point shot, Ship ship);
배가 널이 아닌 경우 , 그 샷은 가라 앉은 샷임을 의미하며, 어떤 함선이 침몰했는지, 얼마나 오래 걸 렸는지 알 수 있습니다. 샷이 싱킹되지 않은 샷인 경우 ship은 null이며 추가 정보가 없습니다.
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<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));
}
}
}
이것은 자유 시간에 함께 할 수있는 최선의 것입니다. 내가 키를 누를 때까지 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<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; }
}
}
분석을 강제로 수행하는 경우, 제공된 RandomOpponent의 메커니즘이 매우 비효율적 일 수 있습니다. 이미 대상 위치를 다시 선택할 수 있으며 아직 터치하지 않은 위치에 도달하거나 이동 당 시간 제한이 만료 될 때까지 프레임 워크에서 강제로 반복 할 수 있습니다.
이 상대방은 행동이 비슷합니다 (유효 배치 분포는 동일합니다).
이것은 내 확장 / 라이브러리 응답의 클래스를 사용하며 주요 메소드 / 상태 만 제공합니다.
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을 센터 오른쪽으로 내리세요
- 이전 명중의 오른쪽에있는 지점 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;
}
}
이것은 미니 맥스가 아닙니다. 실제로 배를 배치 한 후에는 각 플레이어가 스스로 플레이 할 수 없어서 모든 상대 배를 침몰시키는 데 몇 차례의 회전이 있었습니까? 덜 적은 것이 승리합니다.
나는 적의 함선을 가라 앉히고 배가 숨길 수있는 나머지 가능한 장소를 포괄하기 위해 총 수를 최소화하려고하는 일반적인 전략이 없다고 생각합니다.
물론 무작위가 아닌 모든 것에 대한 대응 전략이있을 수 있습니다. 그러나 나는 모든 가능한 플레이어들에게 좋은 전략이 있다고 생각하지 않습니다.
실제로, 퍼즐의 가장 큰 문제는 본질적으로 두 가지 움직임이라는 것입니다. 한 가지 움직임은 당신의 배를 배치하는 것이고 다른 하나는 적의 함선을 찾는 것입니다 (그러나 두 번째 부분은 임의의 요인으로 시계를 치려고 시도하는 것 외에도 '알고리즘을 실행하십시오'). 적의 전략을 결정한 다음 대응하려는 메커니즘이 없기 때문에 "바위 가위"의 연속적인 라운드를 기반으로하는 유사한 경쟁이 꽤 흥미로워집니다.
또한 게임을 네트워크 프로토콜로 지정한 다음 모든 솔루션이 C #이어야한다고 지시하기보다는 C #에서 해당 프로토콜을 구현하기위한 프레임 워크를 제공하면 더 멋지다고 생각합니다.하지만 그것은 제 의견입니다.
편집 : 경쟁 규칙을주의 깊게 읽지 못했기 때문에 초기 포인트를 철회했습니다.
나는 항상 중간에서 시작하여 그 지점에서 멀어지는 것을 좋아했습니다. 다른 지점 사이에 빈 공간이 하나도 남지 않아 그 대담 하위를 설명했습니다 ... 샷 사이의 공간은 침몰 한 선박에 따라 다릅니다. B- 선박이 마지막이라면, 샷은 낭비 된 샷을 최소화하기 위해 그 사이에 4 개의 공간 만 남겨두면됩니다.
영국 컴퓨터 학회를 대신하여 써리 대학교의 제임스 헤더 박사도 비슷한 경쟁을 벌였습니다.
리소스 당 제한이있었습니다. 즉, 회 전당 최대 프로세서 시간, 이동 사이에 상태를 저장할 수없고 최대 힙 크기가 부과됩니다. 시간을 제한하기 위해 AI는 타임 슬롯 내의 어느 시점에서든 이동을 제출할 수 있으며 턴 종료시 이동을 요청합니다.
매우 흥미 롭습니다-http: //www.bcsstudentcontest.com/ 에서 자세히 알아보십시오
더 많은 아이디어를 줄 수 있습니다.
그대로, 우분투 9.10 리눅스에서 단일 개발에서 솔루션이 수정없이 열리고 실행됩니다.
당신은 썼습니다 :
- 경쟁의 정신에 반하는 것으로 여겨지는 것은 실격의 근거가됩니다.
- 상대방을 방해하는 것은 경쟁의 정신에 위배됩니다.
"경쟁의 정신에 대하여"와 "상대방과의 간섭"을 정의 하시겠습니까?
또한-단순화하기 위해 다음을 권장합니다.
- 상대방의 CPU 슬롯 동안 CPU 사용을 전혀 금지하십시오.
- 스레드 병렬 처리를 허용하지 않고 단일 스레드에서 더 많은 CPU 초를 제공하십시오. 이것은 AI 프로그래밍을 단순화 시키며 어쨌든 CPU / 메모리에 묶인 사람에게 해를 끼치 지 않을 것입니다.
추신-여기 숨어있는 CS 박사 후반의 질문 :이 게임을 해결할 수 있습니까 (즉, 최선의 단일 전략이 있습니까?). 예, 보드 크기와 단계 수는 minimax를 필수 조건으로 만들지 만 여전히 궁금합니다. Go와 체스와는 복잡하지 않습니다.
나는 상대방의 무작위 시드와 콜 패턴을 리버스 엔지니어링하는 사람이 이길 것이라고 예측합니다.
그 정도가 확실하지 않습니다.
아마도 게임에서 변형을 사용하여 일련의 항목을 실행할 수도 있습니다.
3D 비행기와 같은 물건을 추가하거나 차례를 쏘지 않고 단일 함선을 움직일 수 있다면 게임이 약간 바뀔 것입니다.
총 1 초의 게임 시간은 기계마다 다릅니다. 토너먼트 머신과 비교할 때 두 번째 가치의 CPU 조작이 내 머신에서 다릅니다. 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]
나는 랜던 슈팅의 결과와 벙어리 사냥 / 타겟, 그리고 정교한 검색 결과를 비교하는 실험을했다.
가장 좋은 해결책은 나머지 선박이 개별 제곱을 사용할 가능성에 대한 확률 밀도 함수를 생성하고 가장 높은 값을 가진 제곱을 목표로하는 것 같습니다.
내 결과를 볼 수 있습니다 여기 에 링크 설명을 입력하십시오
"전함"은 고전적인 컴퓨터 과학 NP- 완전 문제로 알려져 있습니다.
http://en.wikipedia.org/wiki/List_of_NP-complete_problems
(전함을 찾으십시오-게임과 퍼즐 아래에 있습니다)
참고 URL : https://stackoverflow.com/questions/1631414/what-is-the-best-battleship-ai
반응형
'Programing' 카테고리의 다른 글
| 문자열에서 숫자 추출 (“get”) (0) | 2020.03.09 |
|---|---|
| 16 진수 색상 값을 사용하는 방법 (0) | 2020.03.09 |
| Node.js 및 MySQL에 어떤 ORM을 사용해야합니까? (0) | 2020.03.09 |
| 핵심 데이터 대 SQLite 3 (0) | 2020.03.09 |
| 명령 행에서 JUnit 테스트 케이스를 실행하는 방법 (0) | 2020.03.09 |