Homework-

For this assignment, turn in two m-files, a function for generating the board named hw6_yourinitials_board_gen, and a script for solving the board named hw6_yourinitials_solve.

It is a rainy day in Amherst, and of course, Eduroam is down, leaving you without any internet connection. To combat this, you and a friend decide to play a game of Battleship. In a traditional game of Battleship, two players place five different ships on a 10x10 board in the location of their choosing, and take turns guessing the locations of the ships on the board. In the real life game, the boards have letters A-J on the y-axis, and 1-10 on the x axis, but since this is MATLAB, each axis will be numerical. Let's set [1 1] to the upper left corner, [1 10] lower left, [10 1] upper right and [10 10] lower right. Note these are basically Cartesian coordinates. But be aware that when refereeing to an element in a Matlab matrix, the row comes first, then the column. So the A(10,1) in a 10x10 matrix is actually the lower left corner.

The sizes of the ships are as follows:

1 - Aircraft Carrier - 5 spaces

2 - Battleship - 4 spaces

3 - Submarine - 3 spaces

4 - Destroyer - 3 spaces

5 - Patrol Boat - 2 spaces

They can be put in any orientation (horizontal or vertical) and location that you want, as long as they do not overlap or go off the board.

If you correctly guess the coordinates of a space occupied by part of a ship, it is considered a "hit". An incorrect guess is considered a "miss". The game ends when one player hits every possible space occupied by a ship (17 total hits).

Board Generation

Create a function named hw6_yourinitials_board_gen with one matrix output Board and no inputs. This function will also have a subfunction called CheckSpaces, described below.

1. Initialize Board as a matrix of zeros that is size 10x10. You will use a 1-5 to signify that a space is occupied (1-5 correspond to the 5 boats listed above), and a 0 for open spaces. Also initialize the length of each ship in a 5x1 vector, in the order given above.

2. Loop over the five ships with a for loop in order to place them on the board.

3. For each ship, use a while loop that runs until the ship has been placed successfully, meaning it is on the board and not overlapping.

4. For each ship, start by picking a random starting location on the board. The starting location can be called initial_coord and is a 1x2 vector. Check if this is a viable starting location, i.e. one that is unoccupied.

5. If the initial location is unoccupied, call a sub-function called CheckSpaces. This function checks the spaces around the initial coordinates to decide if it is a viable location, and updates the Board matrix if it is viable. The inputs to the subfunction are Board, the length of the current ship, the initial coordinates, and the number of the current ship (1-5). The outputs are Board, and a scalar success that is equal to 0 if the ship could not be placed, and 1 if it could. Your subfunction should do the following

a. Call the function "get_limits" that I will provide you. This function tells you the minimum and maximum possible x and y coordinates that are open horizontally and vertically from the initial coordinate. So if the entire row and column is open, it will return 1 and 10 for the min and max in both directions. But, if a row or column is blocked by another ship, it will return an intermediate value that is the first open coordinate available in that direction. Open the function and read the comment that explains it more. You do not have to understand what is happening in the code, though feel free to check it out. But make sure you understand the outputs it gives.

b. Knowing the length of the ship, and the limits of the current row and column, you can now check if the ship can be placed either horizontally or vertically. If it can be placed, use the ship number (1-5) and update Board and success.

c. If both the horizontal and vertical directions are viable, pick this randomly (50% of either). If only one direction is viable, then pick that direction.

d. When placing the ship, at least one part of the ship must occupy the initial coordinate. Beyond that, it is up to you, i.e. the initial coordinate can be the first, last, or in between location on the ship.

6. Your function should output a viable Board, with all five ships placed in non-overlapping positions on the Board, and numbered 1-5. So there will be five 1's, four 2's, three 3's and 4's, and two 5's. Here is an example:

Script -

Create a script named hw6_yourinitials_script.

1. Call your board generation function to generate a random Board to play with.

2. Using a for loop, you will execute 100 iterations, each of which will make random coordinate guesses until all of your ships have sunk.

3. For each iteration, create a new variable Board2 which initially equals Board (Board never changes).

4. For each of the 100 iterations, use a while loop that runs until all the ships have sunk.

5. Within the while loop, guess a random coordinate (which can repeat). Check Board2, and if it is a hit (occupied by a ship, not hit already) change the value at that location to -999. Your loop should run until all entries in Board2 are either 0 or -999.

6. After the while loop ends, calculate the percentage of hits in that iteration (hits divided by total guesses) and save the value in a vector HitPercent. Determine the mean, max, min and standard deviation of HitPercent.

7. Plot a histogram of HitPercent using hist, label axes and use a title, and comment on the results in a few sentences.

Part 2 - create an algorithm that sinks all the ships more efficiently than the random,

brute force method we implemented. Use a lengthy comment to describe your strategy and implementation. Calculate a new variable HitPercent2 and compare it to the baseline value. If you do not attempt Part 2, you can get up to a 90. An additional 20 points are available for a well-executed strategy in part 2.