반응형
최고의 전투함 AI는 무엇입니까?
전함!
지난 2003년(제가 17살 때), 저는 전함 AI 코딩 대회에 참가했습니다.비록 그 대회에서 졌지만, 저는 매우 재미있고 많은 것을 배웠습니다.
이제, 저는 최고의 전함 AI를 찾아 이 경쟁을 부활시키고 싶습니다.
이것이 현재 비트버킷에서 호스팅되는 프레임워크입니다.
우승자에게는 +450개의 명성이 수여됩니다!대회는 2009년 11월 17일부터 개최됩니다.17일 0시 이후의 출품작이나 편집은 접수되지 않습니다.(중앙 표준시) 기회를 놓치지 않도록 일찍 입력 사항을 제출하십시오!
이 목표를 지키기 위해서는 경쟁의 정신을 따라야 합니다.
게임 규칙:
- 게임은 10x10 그리드에서 진행됩니다.
- 각 선수는 각각 5척의 배(길이 2, 3, 3, 4, 5)를 그리드에 배치합니다.
- 어떤 배도 중복될 수 없지만 인접해 있을 수 있습니다.
- 그리고 나서 선수들은 교대로 상대 선수에게 한 발을 쏘게 됩니다.
- 이 게임의 변형은 발리마다 여러 발을 발사할 수 있으며, 생존하는 배마다 한 발씩 발사할 수 있습니다.
- 상대방은 샷이 가라앉거나, 맞거나, 빗나가면 선수에게 알립니다.
- 게임 플레이는 한 플레이어의 모든 배가 침몰할 때 종료됩니다.
경기 규칙:
- 대회의 정신은 최고의 전함 알고리즘을 찾는 것입니다.
- 경기 정신에 어긋난다고 판단되는 모든 것은 실격 사유가 됩니다.
- 상대를 방해하는 것은 경쟁 정신에 어긋납니다.
- 멀티스레딩은 다음과 같은 제한 사항에 따라 사용할 수 있습니다.
- 사용자의 차례가 아닌 동안에는 두 개 이상의 스레드가 실행될 수 없습니다. (단, 임의의 스레드가 "일시 중단" 상태일 수 있습니다.)
- 스레드는 "정상" 이외의 우선 순위로 실행될 수 없습니다.
- 위의 두 가지 제한 사항을 고려할 때 차례가 진행되는 동안 최소 3개의 전용 CPU 코어가 보장됩니다.
- 게임당 CPU 시간은 기본 스레드의 각 선수에게 최대 1초가 할당됩니다.
- 시간이 부족하면 현재 게임에서 집니다.
- 처리되지 않은 예외는 현재 게임에서 패배합니다.
- 네트워크 액세스와 디스크 액세스가 허용되지만 시간 제한이 상당히 제한적일 수 있습니다.그러나 시간 변형을 완화하기 위해 몇 가지 설정 및 해체 방법이 추가되었습니다.
- 코드는 스택 오버플로에 응답으로 게시하거나, 너무 크면 연결해야 합니다.
- 항목의 최대 총 크기(압축되지 않음)는 1MB입니다.
- 공식적으로 .Net 2.0 / 3.5가 유일한 프레임워크 요구사항입니다.
- 항목은 IBattleshipOptor 인터페이스를 구현해야 합니다.
점수 매김:
- 101경기 중 최고 51경기가 경기의 승자입니다.
- 모든 선수는 라운드 로빈 방식으로 서로 경기를 진행합니다.
- 그리고 나서 선수의 상위 절반이 더블 엘리미네이션 토너먼트를 하여 우승자를 결정합니다. (실제로 2의 최소승이 절반 이상입니다.)
- 저는 토너먼트 API 프레임워크를 토너먼트에 사용할 것입니다.
- 결과가 여기에 게시됩니다.
- 두 개 이상의 항목을 제출할 경우 가장 점수가 높은 항목만 더블림을 받을 수 있습니다.
행운을 빕니다.재미있게 보내!
1 편집 1:
오류를 발견한 Freed 덕분에Ship.IsValid기능. 그것은 고쳐졌습니다.프레임워크의 업데이트된 버전을 다운로드하십시오.
2 편집 2:
디스크에 통계를 유지하는 등에 많은 관심이 있었기 때문에 필요한 기능을 제공해야 하는 몇 가지 비시간 설정 및 해체 이벤트를 추가했습니다.이것은 획기적인 변화입니다.즉, 인터페이스가 기능을 추가하도록 수정되었지만 기능을 위한 본문은 필요하지 않습니다.프레임워크의 업데이트된 버전을 다운로드하십시오.
3편집 3:
1: 버그수 1:GameWon그리고.GameLost시간 초과의 경우에만 호출되었습니다.
버그 픽스 2: 만약 엔진이 매 게임마다 타임아웃을 한다면, 경쟁은 결코 끝나지 않을 것입니다.
프레임워크의 업데이트된 버전을 다운로드하십시오.
4편집 4:
토너먼트 결과:
저는 경기당 훨씬 더 많은 경기를 하자는 동의에 찬성합니다.50개의 게임을 하는 것은 단지 동전 던지기일 뿐입니다.테스트 알고리즘을 합리적으로 구분하기 위해서는 1000개의 게임을 해야 했습니다.
전략:
히트 수가 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개의 위치가 가능하다면, 그것은5 150 = 750억 개의 가능성입니다.그리고 그 숫자는 더 작아질 뿐입니다. 특히 전체 선박을 제거할 수 있다면 말이죠.
제가 위에 연결한 상대는 나무 전체를 탐험하지 않습니다. 750억은 여전히 1초도 안에 들어가기에는 너무 큽니다.하지만 몇 가지 휴리스틱의 도움을 받아 이러한 확률을 추정하려고 시도합니다.
완전한 답변은 아니지만 일반적인 코드로 실제 답변을 혼란스럽게 하는 것은 의미가 없어 보입니다.따라서 저는 오픈 소스의 정신으로 몇 가지 확장/일반 클래스를 제시합니다.만약 당신이 이것들을 사용한다면 네임스페이스를 변경하거나 모든 것을 하나의 dll로 컴파일하려고 시도하지 마세요.
보드 보기를 사용하면 주석이 달린 보드로 쉽게 작업할 수 있습니다.
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은 사전 게임 설정을 위해 제작되었으며 보드 크기를 사용합니다. 또한 선박 목록과 각각의 크기를 사용해야 합니다.다양한 선박 구성을 허용하지 않고 보드 크기를 가변적으로 허용하는 것은 말이 안 됩니다.
선박은 봉인되어 있습니다.
함선이 봉쇄된 이유를 모르겠어요다른 기본적인 것들 중에서, 저는 Ships에 이름이 있기를 바랍니다. 그래서 저는 ""You sink my {0}", ship"과 같은 메시지를 출력할 수 있습니다.이름);. 다른 확장자도 염두에 두고 있으므로 Ship은 상속 가능해야 한다고 생각합니다.
시간 제한:
1초의 제한 시간이 토너먼트 규칙에 적합하지만 디버깅이 완전히 엉망이 됩니다.전함 경쟁은 개발/디버깅을 지원하기 위해 시간 위반을 무시하기 쉬운 설정이어야 합니다.저는 또한 시스템을 조사하는 것을 제안합니다.진단.프로세스:사용자 프로세서시간 / 권한 있는 프로세서시간 / 총 프로세서사용 중인 시간을 보다 정확하게 확인할 수 있는 시간입니다.
침몰선:
현재 API는 상대방의 배를 침몰시켰을 때 다음과 같이 알려줍니다.
ShotHit(Point shot, bool sunk);
하지만 어떤 배를 침몰시켰는지는!나는 당신이 "당신이 내 전함을 침몰시켰다!"(또는 구축함, 잠수함 등)고 선언해야 하는 것이 인간-전함 규칙의 일부라고 생각합니다.
이것은 AI가 서로 부딪히는 배들을 쫓아내려고 할 때 특히 중요합니다.다음으로 API 변경을 요청합니다.
ShotHit(Point shot, Ship ship);
배가 null이 아닌 경우, 이는 총성이 싱킹샷이었음을 의미하며, 어떤 배를 침몰시켰는지, 얼마나 길었는지 알 수 있습니다.만약 총격이 가라앉지 않은 총격이었다면, 함선은 무효이며, 당신은 더 이상의 정보를 가지고 있지 않습니다.
저는 참여할 수 없지만, 시간이 있다면 구현할 알고리즘은 다음과 같습니다.
먼저, 내가 타격을 감지했을 때 나는 즉시 나머지 배를 뒤쫓지 않습니다. 나는 배 위치 표를 만들고 완전히 가라앉히기 전에 적어도 한 번은 다섯 개를 모두 타격했는지 여부를 파악합니다. (다중 샷 변형에 대한 나쁜 정책입니다. 댓글 참조)
- 가운데를 누릅니다(아래 최종 참고 사항 참조 - 'center'는 설명을 위한 편의일 뿐입니다).
- 중앙의 오른쪽에 있는 4번 지점을 치세요.
- 1번 지점을 아래로 치고 1번 지점은 중앙 오른쪽으로 치십시오.
- 이전 히트의 오른쪽에 있는 4번 지점을 타격합니다.
해당 패턴으로 계속합니다(보드를 채우는 3개의 공백으로 구분된 대각선으로 끝나야 함).이것은 모든 4척과 5척의 보트, 그리고 통계적으로 많은 3척과 2척의 보트에 부딪힐 것입니다.
대각선 사이에 있는 지점들을 무작위로 치기 시작하면, 이것은 아직 발견되지 않은 2개와 3개의 길이의 보트를 잡을 것입니다.
5개의 히트를 감지하면 5개의 히트가 다른 보트에 있는지 확인합니다.이는 두 개의 타격이 동일한 수평 또는 수직 라인에 있고 서로 5개의 위치 내에 있는(같은 보트에서 두 개의 타격이 있을 수 있음) 위치 근처에서 몇 번 더 사격하면 비교적 쉽습니다.만약 그것들이 별개의 배라면, 모든 배를 계속 침몰시킵니다.동일한 보트인 경우 5개 보트가 모두 위치할 때까지 위의 채우기 패턴을 계속합니다.
이 알고리즘은 간단한 채우기 알고리즘입니다.주요 특징은 알지 못하는 선박이 여전히 있을 때 알고 있는 선박을 침몰시키는 데 시간을 낭비하지 않으며 비효율적인 충전 패턴을 사용하지 않는다는 것입니다(즉, 완전히 무작위적인 패턴은 낭비가 될 수 있습니다).
최종 참고 사항:
"중심"은 보드에서 임의의 시작점입니다.이렇게 하면 이 알고리즘의 주요 약점이 제거됩니다.설명은 시작부터 대각선을 바로 그리는 것을 나타내지만, 이상적인 알고리즘은 대각선을 따라 있는 '랜덤' 위치에서만 촬영합니다.이를 통해 경쟁사가 예측 가능한 패턴에 의해 선박이 충돌할 때까지 시간을 측정하는 것을 방지할 수 있습니다.
이것은 모든 배를 (9x9)/2+10 샷 아래에 넣을 수 있다는 점에서 '완벽한' 알고리즘을 설명합니다.
그러나 다음과 같이 크게 개선될 수 있습니다.
일단 배가 충돌하면, '내부' 대각선을 만들기 전에 크기를 확인합니다.당신은 2척의 배를 찾았을 수도 있습니다. 이 경우 내부 대각선을 단순화하여 3개의 크기 배를 더 빨리 찾을 수 있습니다.
게임의 단계를 식별하고 그에 따라 행동합니다.이 알고리즘은 게임의 특정 시점까지 좋을 수 있지만 다른 알고리즘은 최종 게임의 일부로 더 나은 이점을 제공할 수 있습니다.또한, 다른 플레이어가 당신을 물리칠 때가 가까우면, 다른 알고리즘이 더 잘 작동할 수 있습니다. 예를 들어, 고위험 알고리즘은 더 자주 실패할 수 있지만, 그것이 작동할 때 그것은 빠르게 작동하고 당신보다 승리에 가까운 상대를 이길 수 있습니다.
경쟁업체의 플레이 스타일을 파악합니다. 즉, 경쟁업체가 선박 배치를 어떻게 계획하는지에 대한 단서를 제공할 수 있습니다. (즉, 자체 알고리즘이 선박 배치 방법을 가장 빠르게 식별할 가능성이 높습니다. 만약 유일한 도구가 망치라면 모든 것이 못처럼 보입니다.)
-아담
크로스파이어가 업데이트되었습니다.나는 그것이 판스워스나 드레드노트와 경쟁할 수 없다는 것을 알지만, 그것은 후자보다 훨씬 빠르고 누군가가 시도하고 싶어할 때를 대비해 놀기 쉽습니다.이는 사용하기 쉽게 하기 위해 여기에 포함된 라이브러리의 현재 상태에 따라 달라집니다.
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();
}
}
}
이 논리는 제가 드레드노트를 이기는 데 가장 가까웠고, 개인전의 약 41%를 이겼습니다.(실제로 52대 49로 한 경기를 이겼습니다.)이상하게도, 이 클래스는 Farnsworth Opartonent에 비해 훨씬 덜 발전된 이전 버전만큼 좋지 않습니다.
제 컴퓨터는 지금 델에 의해 수리되고 있습니다. 하지만 지난주에 제가 있었던 곳은 바로 여기입니다.
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; }
}
}
분석을 무리하게 강제하는 경우 제공된 랜덤 상대의 역학이 매우 비효율적이라는 것을 알게 될 수 있습니다.이 기능을 사용하면 이미 대상으로 지정된 위치를 다시 선택할 수 있으며, 프레임워크는 아직 터치하지 않은 위치에 도달하거나 이동당 시간 제한이 만료될 때까지 반복하도록 강제합니다.
이 상대는 유사한 행동을 합니다(유효 배치 분포는 동일합니다). 건전성 검사 자체를 수행하고 통화당 하나의 무작위 숫자 생성(아모티드)만 소비합니다.
이것은 내선번호/라이브러리 답변의 클래스를 사용하며 나는 주요 메서드/상태만 제공합니다.
여기서 존 스키트의 대답에서 셔플이 해제됩니다.
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
}
나의 출품작.
끔찍하게 특별한 것도 아니고, 제가 가지고 있는 좋은 아이디어들을 다 추가할 시간도 없었어요.
하지만 꽤 잘 하는 것 같습니다.경쟁사에서 어떤 결과가 나오는지 살펴보겠습니다.
(이것을 파일에 넣으십시오.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-ship이 마지막이었다면 사격은 낭비되는 사격을 최소화하기 위해 4개의 공간만 남겨두면 되었습니다.
서리 대학의 제임스 헤더 박사가 영국 컴퓨터 협회를 대표하여 운영한 비슷한 대회가 있었습니다.
리소스에 제한이 적용되었습니다. 즉, 턴당 최대 프로세서 시간, 이동 간에 상태를 저장할 수 없음, 최대 힙 크기가 적용되었습니다.시간을 제한하기 위해 AI는 시간 간격 내의 임의의 시점에서 이동을 제출할 수 있으며 회전이 종료되면 이동을 요청받을 수 있습니다.
매우 흥미롭습니다. 자세한 내용은 http://www.bcsstudentcontest.com/ 에서 확인하십시오.
더 많은 아이디어를 드릴 수 있습니다.
그대로, 솔루션은 ubuntu 9.10 Linux의 monodevelop에서 수정 없이 열리고 실행됩니다.
작성한 내용:
- 경기 정신에 어긋난다고 판단되는 모든 것은 실격 사유가 됩니다.
- 상대를 방해하는 것은 경쟁 정신에 어긋납니다.
"경쟁 정신의 향상"과 "상대와의 간섭"을 정의해 주시겠습니까?
또한 - 단순화를 위해 다음 작업을 수행할 것을 권장합니다.
- 상대 CPU 슬롯 중에 CPU 사용을 전혀 허용하지 않습니다.
- 스레드 병렬화를 허용하지 않고 대신 단일 스레드에서 CPU 시간(초)을 더 줍니다.이것은 인공지능의 프로그래밍을 단순화할 것이고 어쨌든 CPU/메모리에 얽매인 사람은 해치지 않을 것입니다.
PS - 여기 잠복해 있는 CS 포스트 닥터들을 위한 질문: 이 게임은 해결 가능하지 않나요? (즉, 최고의 단일 전략이 있나요?)네, 보드 크기와 스텝 수가 미니맥스 등을 의무화하고 있지만, 여전히 의문이 듭니다...바둑과 체스의 복잡성과는 거리가 멉니다.
저는 상대편의 랜덤 시드와 콜 패턴을 리버스 엔지니어링하는 사람이 이길 것이라고 예측합니다.
하지만 그것이 얼마나 가능성이 있는지는 확실하지 않습니다.
또한 게임의 변형으로 이러한 시리즈를 실행하는 것이 가능할 것입니다.
3D 비행기와 같은 것들을 추가하거나 턴을 위해 촬영하는 대신 한 척의 배를 움직일 수 있는 것은 아마도 게임을 상당히 변화시킬 것입니다.
1초의 총 게임 시간은 기계에 따라 다릅니다.한 번은 제 컴퓨터에서 CPU 작업의 초가치가 토너먼트 기계와 다를 것입니다.1초 이내에 가장 많은 CPU 시간을 활용하도록 배틀쉽 알고리즘을 최적화하면, 더 느린 토너먼트 기계에서 실행될 수 있으며, 항상 패배합니다.
프레임워크의 이러한 한계를 어떻게 극복해야 할지는 잘 모르겠지만, 해결되어야 합니다.
...
한 가지 아이디어는 이 대회에서 했던 것을 하는 것입니다. http://www.bcsstudentcontest.com/
그리고 최대 총 게임 시간에 비해 턴당 최대 시간을 가집니다.이렇게 하면 알고리즘이 정해진 시간 내에 맞도록 제한할 수 있습니다.게임은 50~600회 이상 지속될 수 있으며, my 알고리즘이 총 게임 시간을 관리하는 경우 최고의 작업을 수행할 수 있는 충분한 시간을 주지 못하거나 너무 많은 시간을 주고 잃을 수 있습니다.전함 알고리즘 내에서 총 게임 시간을 관리하는 것은 매우 어렵습니다.
저는 전체 경기 시간이 아닌 턴 시간을 제한하도록 규칙을 변경할 것을 제안합니다.
편집
만약 제가 가능한 모든 샷을 열거하고 순위를 매기는 알고리즘을 작성했다면, 가장 높은 순위의 샷을 찍습니다.모든 가능한 샷을 생성하는 데 시간이 너무 오래 걸리기 때문에 알고리즘을 일정 시간 동안 실행한 후 중지할 것입니다.
턴 기반 제한이 있다면 알고리즘을 0.9초 동안 실행하고 최고 순위 샷을 반환할 수 있으며 턴 시간 제한을 잘 지킬 수 있습니다.
만약 내가 총 게임 시간을 1초로 제한한다면, 각 턴에 대해 알고리즘을 얼마나 실행해야 하는지 결정하는 것입니다.CPU 시간을 최대화하고 싶습니다.한 게임이 500라운드 동안 지속되면 각 턴을 0.002초로 제한할 수 있지만, 한 게임이 100라운드 동안 지속되면 각 턴에 0.01초의 CPU 시간을 줄 수 있습니다.
알고리즘이 현재 제한이 있는 최상의 샷을 찾기 위해 샷 공간의 반 전체 검색을 사용하는 것은 비현실적일 것입니다.
1초의 총 게임 시간은 게임에서 경쟁하기 위해 효과적으로 사용될 수 있는 알고리즘의 유형을 제한하고 있습니다.
나는 실제 코드를 넣지 않음으로써 여기서 물러날 것입니다. 그러나 나는 몇 가지 일반적인 관찰을 위험에 빠뜨릴 것입니다.
- 모든 선박의 크기가 최소 2개의 셀이기 때문에, 당신은 스페이스 퀘스트 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' 카테고리의 다른 글
| XSLT에 스플릿() 기능이 있습니까? (0) | 2023.05.26 |
|---|---|
| '제출' 버튼을 비활성화하는 방법은 무엇입니까? (0) | 2023.05.26 |
| 이중 따옴표를 기본 따옴표 형식으로 사용하여 파이썬 사전을 만드는 방법은 무엇입니까? (0) | 2023.05.26 |
| VBA를 통해 Range 클래스의 선택 방법이 실패했습니다. (0) | 2023.05.26 |
| Node.js의 파일 읽기 (0) | 2023.05.26 |