The idea is to find the optimal game play of battle ship; one that ensures the minimum number of loses - because of the random nature of the game (not knowing where the opponents ship's are) it is impossible to ensure a win.
Naive Ship Placement
I then wanted to find a probability density function (PDF) from which to pick my positions; want to sample (take more shots) more where there are more shots. This was first approached numerically and then analytically. The numerical PDF's were calculated by creating 1 million boards and summing them, and then averaging for the number of boards run (1 million). Ships are placed anywhere on the board under the following conditions:
- The ship is continuous
- Another ship is not present
- Entire ship fits on the board
The key point in implementation is that it is only necessary to
implement ships placement in one orientation, and just transpose the
board to for the other orientation. The board is simply an (n x n)
logical array, where the true (1s) mark the locations of ships.
 |
| PDF of ships of length [2,3,3,4,5] being placed on a 10x10 board |
We observe that as less ships are added (ignoring the aircraft carrier of size 5) that the PDF flattens more.
 |
| PDF of ships of length [2,3,3,4] place on a 10x10 board |
These are not true PDF because they are not normalized to 1, but rather to the amount of ships; i.e. the board of ships [2,3,3,4,5] would sum to 17.
Analytically this was approached by counting the number of ways to arrange a ship of a given size on the board. All possible combinations are worked out for ships of size 2 and 3.
 |
| Possible placements of ships of size two, 9 total. |
|
 |
| Possible combinations of ships of size three. 17 possible combinations. |
Given a position (i,j) on the board, we can then calculate (analytically) the probability that a ship will be placed there, but that will have to wait for tomorrow.
Code for generating Boards:
function [board] = generateBoard(obj)
board = zeros(obj.n,obj.n);
i = 1;
while i <= numel(obj.ships)
ship = obj.ships(i);
ort = (rand>0.5);
x = randi(obj.n);
y = randi(obj.n);
shipEndPoints = [x x+ship-1];
if canPlaceShip(obj,shipEndPoints,y,board,ort)
board = placeShip(shipEndPoints,y,board,ort);
i = i +1;
end
end
end
end
function validPosition = canPlaceShip(obj,shipEndpoints,col,board,ort)
if ort;
board = board';
end
if (shipEndpoints(1) >= 1 && shipEndpoints(2) <= obj.n) && (0 == sum(board(shipEndpoints,col)))
validPosition = true;
else
validPosition = false;
end
end
function board = placeShip(shipEndpoints,col,board,ort)
if ort;
board = board';
end
board(shipEndpoints(1):shipEndpoints(2),col) = ones(abs(diff(shipEndpoints)+1),1);
if ort;
board = board';
end
end