什么是最好的战舰 AI? [英] What is the best Battleship AI?

问题描述

战舰！

早在 2003 年(当时我 17 岁)，我参加了.

策略:

• 跟踪命中 >0 的船只的所有可能位置.该列表永远不会超过~30K，因此可以准确地保留它，这与所有船只的所有可能位置的列表(非常大)不同.

• GetShot 算法有两个部分，一个生成随机镜头，另一个生成随机镜头试图完成沉没已经被击中的船.如果有一个可能的位置(来自上面的列表)所有被击中的船只都沉没，我们会随机射击.否则，我们会尝试通过选择一个位置来完成击沉一艘船，以消除最可能的位置(加权).

• 对于随机射击，根据其中一艘未沉没的船只与该位置重叠的可能性计算最佳射击位置.

• 自适应算法将船只放置在对手在统计上不太可能射击的位置.

• 自适应算法更喜欢在对手在统计上更有可能放置他的船只的位置射击.

• 放置船只时尽量不要相互接触.

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:

1. The game is be played on a 10x10 grid.
2. Each competitor will place each of 5 ships (of lengths 2, 3, 3, 4, 5) on their grid.
3. No ships may overlap, but they may be adjacent.
4. The competitors then take turns firing single shots at their opponent.
   • A variation on the game allows firing multiple shots per volley, one for each surviving ship.
5. The opponent will notify the competitor if the shot sinks, hits, or misses.
6. Game play ends when all of the ships of any one player are sunk.

Rules of the competition:

1. The spirit of the competition is to find the best Battleship algorithm.
2. Anything that is deemed against the spirit of the competition will be grounds for disqualification.
3. Interfering with an opponent is against the spirit of the competition.
4. Multithreading may be used under the following restrictions:
   • No more than one thread may be running while it is not your turn. (Though, any number of threads may be in a "Suspended" state).
   • No thread may run at a priority other than "Normal".
   • Given the above two restrictions, you will be guaranteed at least 3 dedicated CPU cores during your turn.
5. A limit of 1 second of CPU time per game is allotted to each competitor on the primary thread.
6. Running out of time results in losing the current game.
7. Any unhandled exception will result in losing the current game.
8. Network access and disk access is allowed, but you may find the time restrictions fairly prohibitive. However, a few set-up and tear-down methods have been added to alleviate the time strain.
9. Code should be posted on stack overflow as an answer, or, if too large, linked.
10. Max total size (un-compressed) of an entry is 1 MB.
11. Officially, .Net 2.0 / 3.5 is the only framework requirement.
12. Your entry must implement the IBattleshipOpponent interface.

Scoring:

1. Best 51 games out of 101 games is the winner of a match.
2. All competitors will play matched against each other, round-robin style.
3. The best half of the competitors will then play a double-elimination tournament to determine the winner. (Smallest power of two that is greater than or equal to half, actually.)
4. I will be using the TournamentApi framework for the tournament.
5. The results will be posted here.
6. If you submit more than one entry, only your best-scoring entry is eligible for the double-elim.

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.

这篇关于什么是最好的战舰 AI?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！