Probability matrix:
Probability matrix is a two-dimensional matrix that represents the probability of each cell to be a member of any ship size. In other words, the probability of any cell is the possible number of times it can be a member of any ship. During the game the probability matrix is updating. The minimum value of probability is zero while the maximum value is 34.
The image below shows the probability matrix at the start of the game before any shooting.
As an example, the following animated gif image shows how the probability of cell A1 is calculated for the probability matrix shown above:
5-cell ship:
Number of probabilities to be placed horizontally in single row=6
Number of probabilities to be placed horizontally=6*10=60
Number of probabilities to be placed vertically=6*10=60
Total number of probabilities=120
4-cell ship:
Number of probabilities to be placed horizontally in single row=7
Number of probabilities to be placed horizontally=6*10=70
Number of probabilities to be placed vertically=6*10=70
Total number of probabilities=140
3-cell ship:
Number of probabilities to be placed horizontally in single row=8
Number of probabilities to be placed horizontally=6*10=80
Number of probabilities to be placed vertically=6*10=80
Total number of probabilities=160
2-cell ship:
Number of probabilities to be placed horizontally in single row=9
Number of probabilities to be placed horizontally=6*10=90
Number of probabilities to be placed vertically=6*10=90
Total number of probabilities=180
Number of combinations of placement of ships in Battleship game= 180*160*160*140*120=77,414,400,000
Efficiency measures:
The minimum number of shots possible to finish battleship game for the luckiest person on earth is 17 (20 if the ship's will not be declared).
The maximum number of shots possible to finish battleship game for the most stupid person on earth is 100.
Small ships consumes more shots to detect. So, the strategy aims to hit the largest ships first.
The maximum number of shots to get the first correct hit should be 20. If your technique reach the first hit after this number of iterations then it is not efficient. You can randomly select one of the predefined cells below to shorten number of iterations. The following is valid if all cells of this technique are shot:
Probability to hit ship
|
Size in blocks
|
Probability
|
5
|
100%
|
4
|
80%
|
3
|
60%
|
2
|
40%
|
The following cells pattern can be used to detect 4-blocks ship size with the given probabilities:
Probability to hit ship
|
Size in blocks
|
Probability
|
5
|
100%
|
4
|
100%
|
3
|
75%
|
2
|
51.11%
|
The following cells pattern can be used to detect 3-blocks ship size with the following probabilities:
Probability to hit ship
|
Size in blocks
|
Probability
|
5
|
100%
|
4
|
100%
|
3
|
100%
|
2
|
66.67%
|
The maximum number of shots for the worst-luck person to finish a game should be 75 shot (using checker board strategy of 50 shots, with no ships placed on borders, no ships adjacent to each other, ships detected 2,3,3,4,5 successively). If number of shots is more than 75, then the technique is stupid. For the versions where the player should also recognize the ship size (ship size is not declared), the number should be 79.
The following is valid if all cells in checker board strategy are shot:
[1] The probability of first hit of 5-blocks ship is 100%
[2] The probability of first hit of 4-blocks ship is 100%
[3] The probability of first hit of 3-blocks ship is 100%
[4] The probability of first hit of 2-blocks ship is 100%
Cell status:
The possible status for any cell in this game is shown below:
Unknown: a cell that has not been shot yet
Missed: a cell that has been shot, but it is empty
Hit: a cell that has been shot and it is not empty
Sunk: a cell that is a part of sunk ship
Blocked: a cell that lies in the surrounding of sunk ship (this status is used in game version where the ship size is not declared)
Game ID:
The game identifier is a unique identifier that describes the game. It describes where the ships were positioned, their orientations, and the locations of shots. For the purpose of benchmarking of the code, I created this identifier for each game played, so I can build results based on unique games.
The following image shows the maximum possible number of shots (iterations) for each ship size once one block is hit:
If one shot is correct then, set the status to "Partial hit" select the neighboring cell with maximum probability. Shot neighboring cells until the whole ship is sunk.
If two adjacent cells are correct hit, then the orientation of ship is known. Select the neighboring cell with maximum probability on the same row or column
The ship is then sunk when one of the following takes place:
[1] All neighboring cells are missed or blocked
[2] Number of hit cells equals the maximum size of unknown ships
[3] Total probability of neighboring cell equals zero
After ship is sunk, get its size, and remove it from the unknown ship sizes.
After ship is detected (and not declared), mark the cells around as blocked.
After a ship is detected, you can define cells that will detect the maximum available ship size.
Number of vertical probabilities for a given ship size to pass through certain cell=Minimum(No. of allowed cells on top+1, No. of allowed cells on bottom+1, Ship size-No. of hit cells).
Number of horizontal probabilities for a given ship size to pass through certain cell=Minimum(No. of allowed cells on left +1, No. of allowed cells on right +1, Ship size-No. of hit cells).
The total probability for a give ship size=Vertical probabilities+Horizontal probabilities
The total probability for all unknown ship sizes is then the summation of total probabilities for all unknown ship sizes.
Where the acronym "allowed cells" are those cells having the status "Unknown" or "Hit".
Note: the previous formula is applicable where ship size is higher than or equal the number of hit cells.
The following is an animated gif image for one random game using the previously mentioned algorithm:
Key words:
Battleship board game
Battleship game best strategy
Battleship game strategies
Battleship game probability function
Battleship game probability matrix
Battleship game number of combinations
Battleship game solver
Battleship game best efficiency
Battleship game patterns
