Battleship (Ship Placement)

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)
            % Allocating space for the board
            board = zeros(obj.n,obj.n);

            i = 1;
            while i <= numel(obj.ships)
                ship = obj.ships(i);

                % Determining Orientation
                ort = (rand>0.5);

                % Determining Position
                x = randi(obj.n);
                y = randi(obj.n);
                shipEndPoints = [x x+ship-1];

                % Placing Ship, if it is a valid position
                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
% Logical Values for Board Placement
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
% Spots are now filled
board(shipEndpoints(1):shipEndpoints(2),col) = ones(abs(diff(shipEndpoints)+1),1);
% Need to Flip Back
if ort;
    board = board';
end
end