Clone this wiki locally
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
- Internal state
- Updating internal state
- Moving ships
- Other approaches
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.
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
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.
This is currently the most complicated part. Let's split it up into the following parts.
(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
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.
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.
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.
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
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.
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.
To have the AI play against itself, do the following:
$ cabal build aibenchmark $ dist/build/aibenchmark/aibenchmark <args>
<args> consists of the following arguments
immov: movable or immovable ships?
Easy: difficulty level
- a number: how many games to play
--verbose(optional): enable detailed output
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.
Below are some results for immovable and movable ships at the highest difficulty level.
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
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.
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.