Battleships: AI

There are currently 2 AIs implemented

• StupidAI: This AI basically does everything at random, so it is not very interesting. ;)
• CleverAI: This AI is much more sophisticated. For detailed documentation, see below.

Both AIs share the same ship placement code (in AIUtil.hs). This is also documented below (-> Initialization).

Clever AI documentation

Table of contents

1. Internal state
2. Initialization
3. Updating internal state
4. Firing
5. Moving ships
6. Benchmarking
7. Results
8. Other approaches

Internal state

The internal state of the AI consists of the following:

• the rules of the current game,
• a tracking grid where the last shots and responses (Hit, Sunk, Water) are stored,
• a list of all previous shots,
• a list of all sunk ships,
• a list of the corresponding sinking times when the respective ship from the above list was sunk.

Initialization

The initalization function aiInit receives the rules and stores them in the internal state. It also generates the AI's fleet by randomly placing ships and backtracking until an admissible placement is found.

Updating internal state

The function aiResponse takes care of that. It adds the last shot to the shot list and updates the list of sunk ships and sinking times. Sunk ships are completely removed from the tracking grid, including the safety margin. This way, we know that a cell marked as a hit does not belong to a sunk ship.

Finding sunk ships

When the AI receives the information that it has sunk a ship, it looks in all directions from the last target. As long as it finds another hit square, it moves further in that direction. Thus it finds the top/left-most and bottom/right-most position of the sunk ship.

Firing

This is currently the most complicated part. Let's split it up into the following parts.

Blocked cells

(I'm not really happy with this name, any suggestions?) A blocked cell is a cell for which it is impossible to be part of a ship, specifically in the following cases:

• If we just found out that at a certain position is water, it is blocked.

• If we just sunk a ship then all its cells including the safety margin are blocked.

• If it is diagonally adjacent to a hit cell: In the situation

  ???
  ?H?
  ???
  

  we know that the squares marked with an X are blocked:

  X?X
  ?H?
  X?X
  

Probabilities

When ships are movable, you often can't tell for sure that a cell is or isn't blocked. So we need to work with probabilities. If the AI just hit water, the probability for this cell to be water is 1. Over time, however, this probability declines. Currently, the decline is modeled as exponential decay with factor 0.98. That means 1 shot later, it is 0.98, then 0.96, then 0.941 etc. The same goes for movable ships.

Scoring

The AI selects its next target by computing a score for each position. A high score means a high probability to hit a ship there. On how this is calculated, see below. Some randomness is added to the scores to make playing more interesting and variable. The amount of randomness depends on the selected difficulty level. The highest scoring position is then selected for the next target.

The scoring depends on whether ships are movable.

Immovable ships

Given a position to score, the AI considers all potential ships that this position is part of. These are weighted according to the probabilities computed before. Also, if a ship is hit or will be sunk in the next move according to the AI's tracking information, it is given an extra high score, because this ship is very likely to exist.

Note that the AI does not consider whole fleets and weights them according to the probabilities, but only does this locally for each position. So it might happen that a position gets a positive score although it would be ruled out if the AI were testing whole fleets instead of individual ships.

Then the AI applies a checkerboard pattern, i.e. multiplies half of the scores by 0.9, so it won't have to hit all cells to find all ships. Positions at the edge of the board naturally allow fewer ships to pass through them. But the AI shouldn't be biased towards the center, so the scores are divided by the scores at the beginning of the game. If we already attacked that position before, its score is 0.

Movable ships

In that case, there are 2 phases.

Search phase: This is what the AI does at the beginning. It strictly follows a checkerboard pattern to find (and not sink!) all ships. Sinking is not beneficial at this stage because it allows ships to move around more freely. Also, hit ships get score 0, because the goal is primarily to find all ships and not to hit the already found ones.

Sink phase: If the AI has hit enough ships (or if the countdown towards the end of the game is running), we move on to the 2nd phase. Currently "enough ships" means that there have been at least

sum . map (`div` 2) $ remaining

hits where remaining :: [Int] stores lengths of the remaining ships. This is the minimum number of hits needed when we want all ships to be hit everywhere the checkerboard pattern allows it. I think this condition can probably be improved upon.

In the 2nd phase, now that we've hopefully found all ships, our strategy is essentially the same as in the immovable case. But it's not useful to use a checkerboard pattern here because that was already used extensively in phase 1.

Moving ships

The AI generates all possible movements of all movable ships and chooses one randomly, or - also randomly - decides not to move in a certain turn at all.

Benchmarking

To have the AI play against itself, do the following:

$ cabal build aibenchmark
$ dist/build/aibenchmark/aibenchmark <args>

where <args> consists of the following arguments

• mov or immov: movable or immovable ships?
• Hard or Medium or Easy: difficulty level
• a number: how many games to play
• --verbose (optional): enable detailed output

Example: aibenchmark immov Hard 20 --verbose will have the AI play 20 games with immovable ships at the highest difficulty level against itself.

To automatically generate statistics of the AI's performance, use the script

$ cd aibenchmark
$ ./genstat.sh

This will write the output of aibenchmarks at different difficulty levels to files in that folder.

Results

Below are some results for immovable and movable ships at the highest difficulty level.

Immovable ships

Average: 49.36 shots.
Minimum: 41 shots.
Maximum: 59 shots.
Median:  50 shots.
Complete list: 
41
42
42
43
43
46
46
46
46
46
46
46
46
47
47
47
47
47
48
48
48
49
49
49
49
50
50
50
50
50
50
51
51
52
52
52
52
52
53
53
53
53
53
53
54
54
54
56
57
59

Movable ships

Average: 62.2 shots.
Minimum: 43 shots.
Maximum: 160 shots.
Median:  55 shots.
Complete list: 
43
47
48
48
49
49
49
49
50
50
51
51
51
52
52
52
52
53
53
53
53
53
54
54
55
55
56
56
56
57
57
57
58
58
58
58
59
60
60
64
66
70
72
79
79
86
95
104
159
160

As we can see, the AI performs quite well most of the time. (median 55)

However, if it is unlucky and can't catch a small 2-cell-ship, it needs many, many shots. I don't know whether/how this can be improved.

Other approaches

These are just some ideas I had first when thinking about a strategy:

• Brute force: Generate all possible ship placements. Assign each placement a probability for that it agrees with our information about the opponent's fleet. For each position take the sum of all these probabilities and choose the position with the highest value for the next target. This is, of course, only practical for very small board sizes. But it might be useful as an additional strategy in the endgame, when there are not many configurations possible.
• Monte Carlo Simulation: Don't generate all possible ship placements, but only, say 1000, but randomly chosen (uniformly, independently) among the set of all possible configurations. Then target the most likely position. As Monte Carlo simulation often works quite well in practice, this might be a good strategy, too. I tried to implement it but it turned out very hard to choose randomly only among the possible placements. So, I discarded that idea. But I think, if someone finds a solution to that problem, it might be a really good strategy.