Battleship Project

From UBC Wiki

Authors: Nathan, Olivia, Will

What is the problem?

Our project will be implementing the 2-person game Battleship. The game involves placing your ships on a board, with the players alternating between bombing the other player's board. Players cannot see each other's boats until they are hit by a salvo. However, they view their own board as the opponent makes guesses. Each board is 10x10 and contains each of the following ships:

  • Aircraft carrier (5 squares)
  • Battleship (4 squares)
  • Cruiser (3 squares)
  • Submarine (3 squares)
  • Destroyer (2 squares)

There is a restriction that no ships can overlap, and they can only be placed vertically or horizontally on the board. The objective of the game is to sink all of your opponent's boats before they sink all of yours.

What is the something extra?

The first iteration of our computer opponent will utilize random selection for boat positions. Going extra we implemented a more complex algorithm for the computer opponent.


This algorithm is as follows: should there be no positions to pick that are adjacent to positions where we know there is a boat, then the computer will select a random position on the board with parity 2. Otherwise, it the algorithm will hit all adjacent positions to a hit square. Because each boat is minimum 2 spaces long, this parity restriction will hit every boat at least once eventually, while also minimizing the random search space.

What did we learn from doing this?

Type declarations are nothing to scoff at. One of the major issues we encountered was that, despite the logic of the code itself seeming fairly reasonable, it was difficult to get it to compile due to type mismatches. We quickly found how using IO in one function causes us to change a significant portion of the call graph that precedes it. Strengthening our conceptual understanding of when to use IO, monads, and arrays was definitely a learning curve and gave us quite a challenge.

Additionally, we learned to be more tactful when implementing recursion. For example, we initially used a function to place a single boat, applied in a foldl for the board setup. When users placed invalid positions or overlapping boats, the program would finish placing the next boats before going back to the previous boat that was added in an invalid way. This would be equivalent in terms of outcome, however the user experience was very confusing and disjointed due to this. We could only reason how this was due to the lazy evaluation of Haskell.

In terms of design, we found it was useful to model games more in terms of a finite automata, where we simply switch between states based on transitions. In our case, we swapped between the states of being a player turn or enemy turn after shots were taken. We would also loop back to the same state if a selected shot was invalid.

A particularly limiting nature of functional programming in haskell was the inability to modify a single stored variable state. We found the utility of returning multiple values at the same time to be essential to creating the game. We had to thread accumulators into many of the functions in order to correctly update the boards and the lists of boats involved.

Finally, we learned how to use testing packages in Haskell!

Links to code etc

https://github.com/wgervasio/Battleship-AI