Goals and Outcomes

In the first project of CS 1, you implemented your own terminal Battleship game. But there were no graphics/visuals! This time, you will be able to use a GUI (graphical user interface) to play battleship against two bots that you will write!

You will not receive any credit on this project if you use Python features that have not been covered in lecture or in the problem session cheatsheet. For example, at a minimum, the following are banned for project02:

methods and functions not listed in the problem-solving session or used in lecture
list comprehension
ternary operators
generators of any kind (except range and enumerate)

If you are not sure whether certain features are allowed or would like to request an exception to use more advanced ones, please contact us via the course email at cs001@caltech.edu.

Implementing A Battleship Computer Opponent (D Tests)

Part 1: Automatic Ship Placement

In the first part of the project, you will implement an algorithm for your bots to use to place their ships at the beginning of the game. As a very high-level overview, the algorithm will try to randomly place a ship, check if it’s a valid placement, and continue if it is (or undo and try again if it’s not).

The “main” function that will place the ships is called, well…place_ships. But this algorithm is actually fairly complicated (perhaps surprisingly so!). In Computer Science, one of the most important tools we use is called “abstraction”. The main idea behind abstraction is to zoom in or out on particular details depending on which piece of a program we are currently focusing on. One way (of many!) to accomplish this is “functional decomposition” where, instead of implementing one large function to do a task, we split it up into several smaller functions each of which does it’s own “mini”-task that we can then put together at the end to accomplish our goal.

In this part of the project, we’ve provided a (mandatory) functional decomposition of the problem. We’ll start with smaller functions and put them all together in the end!

The first step to placing all the ships is to place a single ship. For each ship, we must choose an orientation and a top-left location. Throughout the code, we’ve made assumption that True is vertical and False is horizontal. In this project, we will still have a square board, like last time, but we have expanded it to to an \(8 \times 8\) grid.

Since we will be trying to place a lot of ships, we should avoid choosing a top-left location that will result in part of the ship being “off the board”, given the size and orientation.

Your first task is to implement the very function we need.

choose_orientation_and_location(size)

Returns a pair of (orientation, coords), where orientation is True or False, and coords is an \((x, y)\) pair of valid coordinates for the top-left location of a ship. We consider a ship location to be valid if and only if the whole ship fits on the board in the chosen orientation. If no ship can be placed, given the size, coords should be None.

Hint: You should use the BOARD_SIZE constant and a function from the random module when writing this function.

Task 1. Implement the choose_orientation_and_location function in src/computer_placement.py.

In project 1, we had to switch between one-indexed coordinates (for user input) and zero-indexed coordinates. In this project, we are using a graphical interface. Therefore, we can always use zero-indexed coordinates in our code.

Running the Tests

Task 1.5. Now that you’ve written a function, you should test it! In this course, you should never ever ever write all the code and then try to test it all at once! This will lead to hours of extra debugging.

Instead, we will usually provide tests for each individual part; so, you can test that your work is correct up to each checkpoint.

To test your code, click the beaker on the left side of vscode. After a few seconds, you should see a tree with project02-YOURUSERNAMAE at the top! Click the play button on the right, and then open up the list of tests using the arrow on the left side of that tree. Finally, find the subtree D > test_computer_placement.py > test_choose_orientation_and_location. All of the tests inside this part should be passing.

generate_ship_coordinates(location, size, orientation)

Returns a list of \((x, y)\) pairs that represent every square of a ship that starts at location of size squares in the provided orientation. This function may assume the given location and orientation can be used to place a valid ship.

Task 2. Implement the generate_ship_coordinates function in src/computer_placement.py.

Task 2.5. Like before, click on the beaker. Following the same steps as before, this time, look for the D > test_computer_placement.py > test_generate_ship_coordinates subtree.

is_conflict(ship, ships)

Returns True if and only if ship is None or there is overlap between the squares that make up ship and the squares that make up at least one ship in ships.

Recall that a single ship is a list of \((x, y)\) pairs. Thus, ships is a list of lists of \((x, y)\) pairs!

Task 3. Implement the is_conflict function in src/computer_placement.py.

Task 3.5. Like before, click on the beaker. Following the same steps as before, this time, look for the D > test_computer_placement.py > test_is_conflict subtree.

place_ships()

Returns a randomly chosen list of ships to be placed without any conflicts.

Your algorithm should roughly be the following:

For each size in SHIP_SIZES…
- Generate a new ship.
- If the new ship conflicts with any of the already placed ships, generate a new one.
- If it doesn’t, add it to the final list of placed ships.

Hint: You should probably use at least one function you already wrote.

Task 4. Implement the place_ships function in src/computer_placement.py.

Task 4.5. Like before, click on the beaker. Following the same steps as before, this time, look for the D > test_computer_placement.py > test_place_ships subtree.

Part 2: Random Shooting Opponent

Now that you’ve written code to handle the “first phase” of the battleship game, it’s time to write the part that chooses where to attack. Later in the project, you’ll implement a computer opponent that is pretty smart, but we’ll start with one that just randomly chooses a square that hasn’t already been chosen.

All computer opponents will take in a single argument, previous_shots, which is a list of (coords, outcome) pairs, ordered with the most recent shot at the end. For this “easy” computer opponent, you should ignore the outcome part of the pair and only use the \((x, y)\) coords portion.

Before you implement the actual opponent, you should write a function, get_all_shots which “extracts” just the coordinates out of previous_shots:

get_all_shots(previous_shots)

Returns a list of all coordinate pairs in previous_shots.

Task 5. Implement get_all_shots in src/easy_computer.py.

Task 5.5. Like before, click on the beaker. Following the same steps as before, this time, look for the D > test_get_all_shots.py subtree.

easy_computer(previous_shots)

Returns pair of \((x, y)\) coordinates of a random shot that hasn’t already been chosen.

Hint: You should use the BOARD_SIZE constant and a function from the random module when writing this function.

Task 6. Implement the easy_computer function in src/easy_computer.py.

There are no automated tests for your easy_computer! You will have to play the game several times to make sure that everything is working properly!

Task 7. It’s time to play battleship! Open the main.py file from the Explorer sidebar and click the Play button on the top right. The game should appear in your terminal and prompt you to select a difficulty level. Select VS Easy Computer, position your ships by dragging them to valid positions on the board, and attempt to sink all of the easy computer’s ships before it sinks yours!

If the program crashes at any point, there is a bug in your easy_computer (not our code)!

Implementing A Smarter Battleship Computer Opponent (B/A Tests)

Now that you have a basis for a computer opponent that the player can play against, let’s work to make a “harder” computer which will make a (reasonably) informed decision on where to place its next shot.

The “harder” computer opponent should actually take the previous shot outcomes (hit, miss, sunk) into account by looking for “hits” that haven’t sunk a ship yet, and continuing to shoot in adjacent squares until it sinks the ship!

Like before, if we were to put this all into one function, it would be pretty complex. Luckily, we have (again) provided a (required) functional decomposition to help you out. The “B Tests” will consist of writing several helper functions, and the “A Tests” will put together the helper functions into the computer opponent.

Part 3: Shooting at the User…but smarter (B Tests)

As in the previous part, many of these functions will take in a previous_shots argument, which is a list of (coords, outcome) pairs, ordered with the most recent shot at the end. coords will still be an \((x, y)\) pair, but this time we will actually use the outcome which is one of three values: HIT, MISS, SUNK.

Many of our functions will only work over the shots marked as a HIT. So, first, you should write a function to select only the coordinates of the HITs from the previous_shots.

get_hits(previous_shots)

Returns a list of coordinate pairs that were marked as hits in previous_shots.

Task 8. Implement get_hits in src/harder_computer.py.

Task 8.5. Like before, click on the beaker. Following the same steps as before, this time, look for the B > test_get_hits.py subtree.

Next, since we will later be generating “potential” shots to make, we will need a way of filtering out the ones that aren’t valid.

is_valid_shot(shot, processed_shots)

Returns True if and only if shot is (1) within the bounds of the board and (2) isn’t in the list of coordinates provided as processed_shots.

Task 9. Implement is_valid_shot in src/harder_computer.py.

Task 9.5. Like before, click on the beaker. Following the same steps as before, this time, look for the B > test_is_valid_shot.py subtree.

The main thing we’re taking into account in this computer opponent that we didn’t previously is the directions we’re working in; so let’s write some functions to deal with them.

apply_direction(coords, direction)

Returns a new coordinate pair made up by adding together the components of coords and direction, where direction is a pair \((x, y)\) where \(x\) and \(y\) are deltas in each direction, respectively..

find_opposite_shot(coords, direction)

Returns a new coordinate pair made up by adding together the components of coords and the opposite of direction.

Hint: Make sure to avoid code duplication when writing this function.

Task 10. Implement apply_direction and find_opposite_shot in src/harder_computer.py.

Task 10.5. Like before, click on the beaker. Following the same steps as before, this time, look for the B > test_find_opposite_direction.py subtree.

Part 4: Putting It All Together!!! (A Tests)

Lastly, you will combine all of the functions you’ve written into one algorithm that works as described above.

Please note that this is the most complicated algorithm we’ve asked you to implement so far in the course. We are more than happy to help clarify and draw pictures at office hours!!!

harder_computer(previous_shots)

Returns a coordinate pair that is a valid shot that continues in the direction of an unsunk previously found ship whenever possible.

At a high level, the goal is to collect all “candidate” coordinate pairs, prioritizing the ones that “continue” in a direction whenever possible.

For each shot that previously HIT…
- For each possible direction, calculate a new_shot by moving in that direction from shot. Then, consider the following two new candidate shots:
  1. new_shot, itself, is a candidate.
  2. The shot in the opposite direction of new_shot is a candidate if and only if new_shot was a HIT.
If we found any VALID shots opposite from a hit, return one of those.
Otherwise, return any VALID candidate shot we found. If there are no valid candidate shots, return a random unshot square.

Hint 1: You will likely want to keep two separate lists of candidates: one for the “opposite” candidates and one for the “regular” candidates.
Hint 2: You should absolutely use the functions you already wrote as helpers when writing this function.

Task 11. Implement the harder_computer function in src/harder_computer.py.

Task 11.5. Like before, click on the beaker. Following the same steps as before, this time, look for the A subtree, all of the tests should pass now (including gen_tests which test your harder_computer).

My A tests are failing. What’s going on with the test output?

As you gain experience programming, you’ll get better at determining what pieces of test output are useful and which aren’t.

pytest’s output might here be confusing if you haven’t seen a statement like assert shot in list(tree.keys()) before.

We’ve added some print statements to our tests so in the section labeled “Captured stdout call”, you’ll see your proposed shot, the shot history, and the allowed choices with that shot history. If your proposed shot isn’t in the allowed choices, that test will fail.

Beat Your Bot!

Task 12. Now, it’s time to beat your bot! Run the main.py in the top-level directory like before, but choose the harder option this time! Then, play the game!

Correctness and Submission

Task 13. Finally, click on the beaker one last time, and run all the tests. Everything should pass with a green checkmark! If this is the case, you are ready to submit!

Task 14. Open src/main.py in the vscode editor. On the right side of the bar of tabs, you should see a “cloud icon”. Click this icon to upload and submit your work!

Task 15. Once your work successfully submits, click on the View on Gitlab button that pops up. Make sure you see a green checkmark on gitlab, as this will be how we will grade your correctness!