Beating the Best in HackerRank Battleship
This blog post details my quest to attain the top score in Battleship on the website HackerRank.
Part 1: Targeting
Step 1: A Good Algorithm
By using a distribution heatmap of all of the possible places for ships to be placed, and updating the remaing ships as they sink, you can build a strong Battleship target-guessing AI knowing only invalid squares (out-of-boundary, miss, sink, hit). For example, at the start, a heatmap might look like this:
1 3 6 10 15 15 10 6 3 1
3 6 10 15 25 25 15 10 6 3
6 10 15 25 40 40 25 15 10 6
10 15 25 40 70 70 40 25 15 10
15 25 40 70 99 99 70 40 25 15
15 25 40 70 99 99 70 40 25 10
10 15 25 40 70 70 40 25 15 10
6 10 15 25 40 40 25 15 10 6
3 6 10 15 25 25 15 10 6 3
1 3 6 10 15 15 10 6 3 1
And with a miss (MM, near the centre):
1 3 6 10 15 15 10 6 3 1
3 6 10 15 25 25 15 10 6 3
6 10 15 25 25 40 25 15 10 6
10 15 25 40 15 70 40 25 15 10
15 25 25 15 MM 15 25 40 25 15
15 25 40 70 15 99 70 40 25 10
10 15 25 40 25 70 40 25 15 10
6 10 15 25 40 40 25 15 10 6
3 6 10 15 25 25 15 10 6 3
1 3 6 10 15 15 10 6 3 1
This is documented more throughly and clearly at DataGenetics although Nick chose to employ a hunt mode and a target mode which both operate using the same logic, whereas I chose to simply update the heatmap with additional weights: see next step.
Step 2: Additional Weights
Weight #1: Having a number of hits overlapping with the distribution of the remaining ships, for example:
HH 40 35 23 15 15 10 6 3 1
40 6 10 15 25 25 15 10 6 3
35 10 15 25 40 40 25 15 10 6
23 15 25 40 70 70 40 25 15 10
15 25 40 70 99 99 70 40 25 15
15 25 40 70 99 99 70 40 25 10
10 15 25 40 70 70 40 25 15 10
6 10 15 25 40 40 25 15 10 6
3 6 10 15 25 25 15 10 6 3
1 3 6 10 15 15 10 6 3 1
HH 40 35 23 15 15 10 6 3 1
HH 75 50 35 30 25 15 10 6 3
99 10 15 25 40 40 25 15 10 6
40 15 25 40 70 70 40 25 15 10
33 25 40 70 99 99 70 40 25 15
24 25 40 70 99 99 70 40 25 10
14 15 25 40 70 70 40 25 15 10
6 10 15 25 40 40 25 15 10 6
3 6 10 15 25 25 15 10 6 3
1 3 6 10 15 15 10 6 3 1
As you can see in this case, cell (1, 3) has a high score of 99, because there could be a 3, 4, or 5 length ship with two confirmed hits. Do note, that cells (2, 1) and (2, 2) still have high scores, as these hits could potentially be two horizontally placed ships on top of one-another.
HH 40 35 23 15 15 10 6 3 1
HH 75 50 35 30 25 15 10 6 3
MM 10 15 25 40 40 25 15 10 6
3 15 25 40 70 70 40 25 15 10
5 25 40 70 99 99 70 40 25 15
7 25 40 70 99 99 70 40 25 10
7 15 25 40 70 70 40 25 15 10
5 10 15 25 40 40 25 15 10 6
3 6 10 15 25 25 15 10 6 3
1 3 6 10 15 15 10 6 3 1
At this point we have discovered that in fact they are two horizontally placed ships. Trust me though, if you have multiple hits in a row, it is always a good idea to follow them.
In the above referenced link, Nick's algorithm decides against this, in favour of an unaltered probability density function as seen below -- a snapshot from his website.
Weight #2: Invalid squares surrounding a hit.
This seems a bit unusual at first glance, but it helps us prioritise known ship locations. Take the following board as an example:
--M-----MH
-MHM------
----------
----------
----H-----
----------
----------
----------
----------
----------
Here we have three hits, but how does our AI know which one to discover around? With the algorithm we have discussed up to now, we would expect the AI to pick one of the squares next to the hit near the centre, but we know as humans, that there are two much better moves available to us. These moves are on the bottom of the two other hits near the top, because these are both guaranteed to hit, since the ships have not been sunk.
We can use an additional weighting formula to value these squares higher based on the invalid squares around the hit.
Step 3: Heuristics
As humans, it is very simple for us to discover heuristics to use to increase the efficiency of AI several fold. One of these heuristics we can use in Battleship, is the idea that players will rarely want to place their ships next to each other. The reason for this is simple: so a player's opponent does not 'accidently stumble across' their other ships.
We can use this to delay targetting squares next to confirmed hits after those that are not next to ships.
Now I know what you're thinking: "What if they specifically placed ships next to each other just to beat this heuristic?" I've got you covered! Most opponents will not do this, but some will. I do not employ this heuristic until there are no remaining ships bar the one-square ships. The one-square ships can be a nightmare to find and so we can use this heuristic to find those single ships that are mostly luck in finding. For those players that like putting ships next to each other, we can turn on and off this heuristic based on whether previous ships found were next to each other or not, before only the one-square ships are remaining.
The next question that comes to mind is: "What if they put the single ships next to each other?" This is a good question, and plays against our heuristic extremely well. This is why we always check the squares surrounding any found one-square ships once one-square ships are the only ones remaining.
Step 4: Static Predictions
Often times people will write their AI to be in a range of specific places, or even hard-code their entire fleets positions! First we will discuss common cases and the pros and cons of doing this.
A common strategy based on the probability density function is to place ships where the function returns the lowest values on a blank board, such as corners and edges. Although this idea is good, it has two flaws:
- It is absolutely destroyed by parity search, and
- It is rather predictable.
Point 1 doesn't help us, as we are using a PDF and not parity search, but point 2 does give us some useful information. For this reason, if one-square ships are the only ships remaining, our AI will check corners before randomly crawling the remaining spaces. Otherwise, the PDF will find the longer ships, even if they are in the corners.
If a player hard-codes their fleet's positions, they can place them in such a way that it 'games' a specific player's AI and beats them with 100% certainty. Due to this, I believe that players should not be able to hard-code the positions of their ships. Having said that, they can. "Well Jeremy," I hear you say, "what can we do about it?"
This solution is rather simple, albiet tedius. The nature of the game dictates that the above would in fact be an advantage -- were we not able to watch the replays of games. Since we can watch replays and even download matches in batch, we can notice patterns between layouts of single-square ships, and based of the position of one, predict the position of another. This means that for opponents that have static positioning of their ships, we only need to find one of the single-square ships to know where the other is.
You may consider this cheating, I consider it fair play as mentioned above, one can statically position ships to their advantage, why can't we statically make predictions about where their ships may be?
Part 2: Positioning
Most of this was referenced in part 1, but we shall go over it to be clear.
Step 1: Do not place ships next to each other.
We avoid this so that the opponent does not 'accidently happen across' another one of our ships, after already finding one.
Step 2: Do place single-space ships next to each other.
Okay I know I'm contradicting myself here, but I have a few good reasons!
The first being the reason referenced above: If an opponent has a search that prioritizes squares that are not next to ships, they will search every square that is not next to a ship before begining to search squares that are next to ships.
The second reason being that the two single-square ships are on different parities, this means a parity search will have to complete at least one full-board parity search before finding both one-square ships. Pretty neat, huh?
The third reason is part of the second. I found that a lot of parity search bots were alternating parity with each half or quarter of the board, and so even though my single-square ships were on seperate parities, they were still found in a single iteration of the parity search. If the two ships are next to each other, this issue will be much less likely to occur.
Having said all of this, I found implementing this rather successful, though as referenced in Part 1, it can be risky if your opponent employs the strategy of looking around the found single-square ship. I did not come across any other bots on HackerRank that did this, though. Lucky me.
Step 3: Do not place ships in corners.
As mentioned above, parity searches find ships in corners very quickly, and in addition, even our PDF-based bot looks in corners as part of the static predictions. It is always good practice to be able to counter your own plays, as somebody smarter than you has already thought of them.
Step 4: Try to favour edges over the centre.
This is only a small optimisation, but will help give you a few more turns against a PDF search. This does not help against parity search.
Step 5: Always, always, always use some form of randomisation when placing ships.
By statically placing ships you are putting yourself at risk of being statically predicted.
Additional Notes
When I was writing my bot, I started with the PDF heatmap, and quickly realised that near the top of the leaderboard, the winner is the person who gets lucky with the single-square ship discoveries. Statically placing ships in the same location as the Judge-bot and using the PDF heatmap with no additional weights reached a score of 22.02, approximately rank 468 out of 605. Not good.
After randomising the positions of my ships, my score rose to 39.09, approximately rank 50. Much better!
After adding the target weights described above, my score rose to 44.15! Rank 5! I was happy with this result, but not satisfied. I wanted #1, so I took a step back to think about what I could have done better. This is when I had realised that I had been focusing too hard on what my targets were, and not focusing enough on the positioning of my own ships.
I sat down and watched some games, watched how other bots played and what my weaknesses were in terms of positioning. I then thought of and implemented the above 5 positioning steps and reached a score of 48.62, eclipsing the previous rank #1 by over three points!
Again, I was happy with this result, and for some reason was not satisfied that I had done enough. I had to do better. This is where the static analysis came in. Through the static predictions, I was able to reach a score of 53.21, and since then I've thought of new ways to improve the bot if anybody ever beats me, or comes close.
To close off, the Battleship Bot PvP experience on HackerRank started off as an exercise in building an efficient algorithm for placing and targetting ships, and finished as an exercise in out-thinking other programmers.
As they say: Play the player, not the cards.
Edit: Since this article was written, my score has dropped significantly due to people targetting my algorithm. The reason for this is that score given for a win is based on the score of the opponent, so everybody wants to beat me in order to achieve the highest score possible. Having said that, I am still #1.