Battleship Optimization
Steve Myrick & Lofton Anderson
University of North Carolina Wilmington
Abstract
The purpose of this study is to examine the advantages of multiple algorithms to effectively solve a game of the classic Milton-Bradley game of Battleship. Understanding the basic rules of Battleship, a human could solve the game, however the goal of this study is to find an algorithm or multiple algorithms that could solve the game of Battleship in less moves than the average human. Each game is played to completion as the algorithms do not face an opponent and therefore can not lose the game. In the one hundred cells of a traditional Battleship board, seventeen spaces are filled by ships. The algorithms each check cells in a predetermined logic to locate these seventeen spaces in the least number of checks. Each algorithm is written in Java 8 using two-dimensional arrays to model the board with 200,000 randomly generated boards as the sample size. Each algorithm produces a result of the average amount of checks to locate all ships and the algorithms are ranked by effectiveness with low numbers considered more effective. In this set of algorithms, the “Modified Every Third” search is the most effective using on average 60 checks to locate all ships.
Key Words: Array Comprehension, Battleship, Java, Search, Optimization
1. Introduction
Popularized in 1967 by Milton Bradley, Battleship is a board game that is simple to understand yet hard to master. While most games of Battleship are played with two players with the goal of the game to sink all of the opponent’s battleships before the player’s are sunk, these algorithms are written simply to reduce the amount of moves it takes to guess ship locations. Therefore, the use of these algorithms should improve the average human player’s win rate if implemented correctly.
The algorithms are subject to a standard set of rules. The board is always a 10x10 grid. There are always a total of 5 ships with lengths of 5, 4, 3, 3, and 2. Ships can only be placed horizontally or vertically, never diagonally. The ships must stay within the outer bounds of the board; a ship can not wrap around to the opposite side of the board. There is no opponent, therefore the algorithms can not lose the game and there is no notification if a ship is sunk. No ships may overlap, however they can be adjacent.
2. Formal Problem Statement
For a two-dimensional array modeling a blank Battleship Board Bb = (X, X, X, X, X, X, X, X, X, X) and X = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0) with a filled cell CF = 1 and an empty cell CE = 0, fill two-dimensional array Bb with joined ships S1 (weight 1, length 5), S2 (weight 1, length 4), S3 (weight 2, length 3), S4 (weight 1, length 2) by replacing CE with CF placed either in the same column or row. Search the board with a standard logic keeping track of number of hits H and number of guesses G, recording G when H = 17. Report the average number of guesses, calculated by (ΣG)/N where N is the number of boards checked.
3. Context
Since the game of Battleship has been around for over 50 years, many strategies have been created for playing this game. Strategies can be broken down into human strategies and computer strategies. With large amounts of memory and computational power, a computer algorithm should be able to produce a more favorable result, however it lacks human intuition. A strategy set in place by a human, however, benefits from intuition, even if it lacks the memory of a computer. In this project, the algorithms are modeled in a way that they could be used by a human to statistically win more games while still being able to understand and implement the logic behind the strategy.
4. Linear Search
Utilizing brute force, the Linear Search method is the most basic type of searching algorithm. The algorithm starts in the upper, leftmost cell, and examines every cell one-by-one down the row to check whether the cell is empty or occupied by a battleship. After completing the row, the search advances to the next row, and continues to check every cell one by one down the row. If a battleship is found, the algorithm takes note, and then exhaustively continues searching the board, cell-by-cell, row-by-row, until all 17 battleship cells have been found and recorded.
Although this type of searching method is easy to implement, it is not the most optimal. Because this algorithm checks the board in a linear fashion, if a battleship is placed at the bottom of the board, than the algorithm will have to search more cells to reach the bottom of the board, returning a greater number of guesses. Alternatively, if every battleship is placed at the top of the board, this algorithm will find them quickly, end early, and return a lower number of guesses. This algorithm also doesn’t take any special recognition into account if a battleship cell is found. Instead of searching around the found battleship cell for another “hit”, the algorithm continues to search the rest of the row.
Figure 4.1
After running this specific searching method on 200,000 randomly generated battleship boards, the average total number of guesses need to find every battleship was 88.50 guesses. This was the second worst average number of guesses needed to win the game with respect to the 8 algorithms tested. In figure 4.1, the graph contains an almost perfect quadratic curve, but with jagged variation. This is likely because of the fact that the algorithm tends to finish the search, by finding all of the battleship cells, at the end of the rows instead of the beginning.
5. Random Search
While Java’s implementation of random is not truly random, for this application it is useful enough. In this algorithm two numbers, ranging one through ten, are randomly generated. These numbers equate to which row and column the algorithm will check next. To prevent the algorithm from checking the same cell twice and double counting a guess, a second a dimensional array is created, we will call this the “check array.” When a cell is examined, it is noted and recorded in the check array. Every time a row and column combination is generated, the algorithm checks first to see if it has already been guessed and recorded in the check array. If it has not, it records the new guess, and the cell is examined. If the cell has already been guessed, a new row and column combination is randomly generated. This process continues until every possible position has been checked, or the 17 battleship spaces have been found.
While the random algorithm has the ability to play a perfect game, finding all 17 ship cells in 17 guesses, the odds of that happening are so insignificant that it can be considered zero. This algorithm is not optimal because, much like the Linear Search algorithm, it doesn’t take any special recognition into account if a battleship cell is found. Instead of searching around the found battleship cell for another “hit”, the algorithm continues to randomly search positions around the board. This searching method is even worse than the linear algorithm because of the nature of randomness. If a battleship is placed in the first 5 cells, and the linear algorithm is used, it would take 5 guesses to find the battleship. However, if the Random algorithm is used, it could take anywhere from 5-100 guess to find the ship.
Figure 5.1
After running this specific searching method on 200,000 randomly generated battleship boards, the average total number of guesses need to find every battleship was 95.39 guesses. This was the worst average number of guesses needed to win the game with respect to the 8 algorithms tested. In figure 5.1, the Random Search, we see a very strong quadratic curve. This is because in order to find every battleship, the Random Search algorithm had to almost search almost the entire board.
6. Modified Linear Search
Similar to the Linear Search algorithm, the Modified Linear Search algorithm utilizes brute force, and starts in the upper, leftmost cell, and examines every cell one-by-one through the row to check whether the cell is empty or occupied by a battleship. After the row has been fully check, it continues with the same process with the next row, and so on. The Modified Linear Search algorithm also takes advantage of a separate two-dimensional array, a check array, similar to the Random Search algorithm, which is used to eliminate the possibility of a guess being recorded and double counted twice. The difference between the Linear Search algorithm and the Modified Linear Search algorithm is what the Modified Linear Search algorithm does when a battleship is “hit” or found. Once a battleship cell has been found, the algorithm will search above, below, to the left, and to the right of the original hit location, While you are checking a certain direction from the original hit, if another battleship hit is recorded, it will continue to check in the same direction until a vacant cell is found. Once a vacant cell is found, it will return to checking the remaining directions from the original hit. If the remaining cells surrounding the hit are empty, then the algorithm will continue to search the grid cell-by-cell, row-by-row, and continuing after the original hit location, until all other battleship cells have been found.
By adding the modified search technique when a battleship cell has been found, it improves the original Linear Search algorithm tremendously. However, the same natural problems occur. If a battleship is placed horizontally at the bottom of the board, the algorithm will have to search more cells to reach the bottom of the board, returning a greater number of guesses.
Figure 6.1
After running this specific searching method on 200,000 randomly generated battleship boards, the average total number of guesses need to find every battleship was 82.20 guesses. This was the third worst average number of guesses needed to win the game with respect to the 8 algorithms tested. Figure 6.1 is similar to figure 4.1 in the fact that figure 6.1 also has quadratic curve qualities, but it differs from figure 4.1 because the average amount of guesses to win the game was lower, thus being more optimal.
7. Modified Random Search
The Modified Random Search utilizes the most humanistic approach to the game of Battleship. Similar to the Random Search algorithm, the Modified Random Search algorithm takes two randomly generated numbers, ranging one through ten, and equates them to which row and column the algorithm will check next. The algorithm checks the content of the randomly generated cell. If the cell is empty, the guess is counted, and another cell is randomly generated and checked again. If a cell is occupied by a battleship, this algorithm utilizes the modified check described in the Modified Linear Search algorithm above (Heading 6), by searching above, below, to the left, and to the right of the original hit location, and continuing to check in a specific direction if the cell contains a battleship. This process continues until every possible position has been checked, or the 17 battleship spaces have been found. This algorithm also takes advantage of a check array, to eliminate the double counting of the same two possible guesses.
As stated above, this algorithm closely resembles that of the average humanistic approach to Battleship. A human player would randomly guess around the board until a battleship is found. After finding the battleship, they would continue to search around the original hit location until the entire battleship has been destroyed. There is a reason this strategy is commonly used. Opposed to the nature of randomness hurting the Random Search algorithm, in the Modified Random Search algorithm, the nature of randomness in addition to the modified search technique greatly improves the probability of finding all 17 battleship cell locations before searching the entire board.
Figure 7.1
After running this specific searching method on 200,000 randomly generated battleship boards, the average total number of guesses need to find every battleship was 68.89 guesses. This was the fourth best average number of guesses needed to win the game with respect to the 8 algorithms tested. In figure 7.1, we see that the Modified Random Search Guess Frequency starts to resemble that of normal standard distribution or bell shaped curve. The graph shows that this specific searching method has a better chance to return a lower number of guesses than previously mentioned searches.
8. Modified Every Other Search
Similar to the Linear Search algorithm, this algorithm starts in the upper, leftmost cell, but instead of examining every cell one-by-one through the row, it skips every other cell. This effectively cuts the board size in half because it only checks every other space. Since there is no ship that has a length of 1, by checking every other space will always make contact with every ship by the 50th regular check. This specific algorithm also takes into account the modified check when a battleship cell is discovered, searching above, below, to the left, and to the right of the original hit location, continuing to check in a specific direction if the cell contains a battleship. Included as well is a check array, to eliminate the double counting of the same two possible guesses.
An issue with this algorithm is the fact that it does not account for ships that have been sunk. Since the computer does not respond with a notification confirming that a battleship has been sunk, the algorithm can not adjust to a larger gap in between guesses. For example, if the only ship that remained on the board was the ship of length 5, every other space would not have to be checked, just every fifth space. Since this algorithm does not adjust for sunken ships, there will be spaces that are checked unnecessarily.
Figure 8.1
After running this specific searching method on 200,000 randomly generated battleship boards, the average total number of guesses need to find every battleship was 61.50 guesses. This was the second best average number of guesses needed to win the game with respect to the 8 algorithms tested. In figure 8.1 we see a huge drop off in guess frequencies once the guess count reaches 70 guesses. This is because the Modified Every Other Search algorithm can search and check almost the entire board in 50 guesses. After it has searched the entire board, it goes back to the beginning, in this case the top left corner of the board, and runs the same check on the cells it skipped. With this method, this algorithm is able to achieve a high concentration of low guess counts.
9. Modified Every Third Search
This search method is fundamentally the exact same as the Modified Every Other Search, but instead of every other cell being checked, every third cell is being checked. Instead of cutting the board in half similar to the Modified Every Other Search, this algorithm essentially cuts the board size to one-third the original size. This specific algorithm also takes into account the modified check when a battleship cell is discovered, searching above, below, to the left, and to the right of the original hit location, continuing to check in a specific direction if the cell contains a battleship, and a check array, as to eliminate the double counting of the same two possible guesses.
Although this algorithm cuts the board size to one-third the original size, it has the potential to leave holes for the battleship of length two. This is an issue because in order to fill in the hole that is left by the initial run-through of this algorithm, it must backtrack, and potentially go through another one third of the board to cover its tracks. So while the best case scenario is that it will cover the board in one third of the amount of guesses it originally would, it has the potential necessity to cover two thirds or more of the board to be able to find all 17 battleship cells.
Figure 9.1
After running this specific searching method on 200,000 randomly generated battleship boards, the average total number of guesses need to find every battleship was 60.62 guesses. This was the best average number of guesses needed to win the game with respect to the 8 algorithms tested. In figure 9.1, we see the same trend of guess frequencies found in figure 8.1. This trend is present because, most of the time, every battleship was found during the first pass of the game board during the search. If all battleships were not found, the algorithm must take another pass of the board, checking cells that have yet to be checked. The maximum about of passes this algorithm can take of the board is 3 before checking every cell. The first drop off and plateau represents when the algorithm found every battleship on the second pass of the game board, just as the third drop off represents the third pass of the game board.
10. Spiral Search
The Spiral Search algorithm takes a different approach to searching the board. This algorithm searches the center of the board first, and then in a counter-clockwise rotation, expanding from the middle to the outer rim of the board. This is done by hard coding certain points to check into an array, and then iterating through the array and checking every point. The same concept of the modified check when a battleship is found applies to this algorithm, as well as utilizing a check array to eliminate the double counting of the same two possible guesses.