What is the best Battleship AI?
Battleship!
Back in 2003 (when I was 17), I competed in a Battleship AI coding competition. Even though I lost that tournament, I had a lot of fun and learned a lot from it.
Now, I would like to resurrect this competition, in the search of the best battleship AI.
Here is the framework, now hosted on Bitbucket.
The winner will be awarded +450 reputation! The competition will be held starting on the 17th of November, 2009 . No entries or edits later than zero-hour on the 17th will be accepted. (Central Standard Time) Submit your entries early, so you don't miss your opportunity!
To keep this OBJECTIVE , please follow the spirit of the competition.
Rules of the game:
Rules of the competition:
Scoring:
Good luck! Have fun!
EDIT 1:
Thanks to Freed, who has found an error in the Ship.IsValid function. It has been fixed. Please download the updated version of the framework.
EDIT 2:
Since there has been significant interest in persisting stats to disk and such, I have added a few non-timed set-up and tear-down events that should provide the required functionality. This is a semi-breaking change . That is to say: the interface has been modified to add functions, but no body is required for them. Please download the updated version of the framework.
EDIT 3:
Bug Fix 1: GameWon and GameLost were only getting called in the case of a time out.
Bug Fix 2: If an engine was timing out every game, the competition would never end.
Please download the updated version of the framework.
EDIT 4:
Tournament Results:
I second the motion to do a lot more games per match. Doing 50 games is just flipping a coin. I needed to do 1000 games to get any reasonable distinction between test algorithms.
Download Dreadnought 1.2.
Strategies:
keep track of all possible positions for ships that have >0 hits. The list never gets bigger than ~30K so it can be kept exactly, unlike the list of all possible positions for all ships (which is very large).
The GetShot algorithm has two parts, one which generates random shots and the other which tries to finish sinking an already hit ship. We do random shots if there is a possible position (from the list above) in which all hit ships are sunk. Otherwise, we try to finish sinking a ship by picking a location to shoot at which eliminates the most possible positions (weighted).
For random shots, compute best location to shoot based on the likelihood of one of the unsunk ships overlapping the location.
adaptive algorithm which places ships in locations where the opponent is statistically less likely to shoot.
adaptive algorithm which prefers to shoot at locations where the opponent is statistically more likely to place his ships.
place ships mostly not touching each other.
Here is my entry! (The most naive solution possible)
"Random 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() { }
}
}
Here's an opponent for people to play against:
Instead of using a fixed geometry-inspired strategy, I thought it would be interesting to attempt to estimate the underlying probabilities that any particular unexplored space holds a ship.
To do this right, you'd explore all possible configurations of ships that fit your current view of the world, and then compute probabilities based on those configurations. You could think of it like exploring a tree:
an expansion of possible battleship states http://natekohl.net/media/battleship-tree.png
After considering all leaves of that tree that jive with what you know about the world (eg ships can't overlap, all hit squares must be ships, etc.) you can count how often ships occur at each unexplored position to estimate the likelihood that a ship is sitting there.
This can be visualized as a heat map, where hot spots are more likely to contain ships:
a heat map of probabilities for each unexplored position http://natekohl.net/media/battleship-probs.png
One thing I like about this Battleship competition is that the tree above is almost small enough to brute-force this kind of algorithm. If there are ~150 possible positions for each of the 5 ships, that's 1505 = 75 billion possibilities. And that number only gets smaller, especially if you can eliminate whole ships.
The opponent that I linked to above doesn't explore the whole tree; 75 billion is still to big to get in under a second. It does attempt to estimate these probabilities, though, with the help of a few heuristics.
链接地址: http://www.djcxy.com/p/6774.html上一篇: 是否有任何情况下，Rope数据结构比字符串生成器更有效
下一篇: 什么是最好的战列舰AI？