Course:CPSC312-2017-Battleship

Battleship

Authors: Tak P, Trevor L

What is the problem?

Our goal is to build a simple battleship game in which a human player can play against a semi-intelligent opponent. The program will follow a set of predefined knowledge according to the domain and rules of the game. This includes, but is not limited to, the conditions under which either player has won, the rules governing the progression of the game, etc.

A brief description of the game can be found here: [Wikipedia] Battleship_(game)

Example Queries:

• validStartBoard(playerBoard) - returns true if starting board configuration is legal
• fireAt(a, 5, Result) - returns true if firing at coordinate is legal for some Result (“hit”, “miss”)
• receiveFire(a, 5, Result, PlayerBoard, OpponentBoard) - return true if the coordinates result in some Result (“hit” or “miss”) and some new marked Boards
• win(OpponentBoard) - returns true if all ships have been sunk (win condition has been met)
• nextMove(OpponentBoard, X, Y) - return true if some legal next move with coordinates (X, Y) exists
• isPlayerTurn(OpponentBoard, ReturnBoard) - returns true if computer has selected a valid move and the win conditions have not been met.

What is the something extra?

We will attempt to build an agent that takes more sophisticated approach than brute force for defeating the human player. This could include a probabilistic predictor or a heuristic for determining the best successive moves to make.

What did we learn from doing this?

Overall, logic programming was suitable for the task. We have built a simplified version of the battleship game, where a human player can play against a computer opponent that uses a simple algorithm to determine moves. This includes the basic infrastructure to be able to have a running turn-based game, validation methods which uses sets of rules to determine the validity of an action or state and following rules surrounding the winning conditions of the game. We have completed this with logic programming including statically and dynamically declaring clauses, backtracking search for pattern matching, and list manipulation.

For example, the occupiedValid clause employs backtracking search for pattern matching to determine whether ship placements on a board are valid. The countShips clauses describe the basic rules and patterns where a ship could be located, and marks counted ships on a resulting board. To determine valid placements, it first pattern matches along individual rows, recording the resulting match pattern and the number of ship. It then recombines the resulting rows as a new board, at which point it goes down the individual columns to pattern match and count the ships. If the final number of ships doesn’t match the expected number of ships, it can backtrack and try different combinations of the rules for patterns set out in countShips to attempt to get the correct number of ships. Only after it finds a set of matches that have a correct number of ships does it return ‘true’ for a board being valid. Thus, logic programming is definitely well suited to determine validity of a battleship board.

One of the questions we set out to answer was whether we can build an agent that takes a more sophisticated approach than brute force to defeat a human player. We have been able to do this using a simple heuristic using two modes: a hunt mode where the computer looks for a ship using a combination of random choices with a numerical calculation for the likeliness of a square to contain a ship, and a destroy mode where the computer has hit a ship and will now look for adjacent squares for the remaining part of the ship (since all of our ships are size 2). This ‘more sophisticated approach’ is all done in logic programming, using simple addition, sorting, dynamic state declaration, static declaration of clauses and recursive manipulation of lists.

The approach is contained in a series of clauses: computer_move, react, calculate, calculateAdjacents, canAttempAdjacents, checkNeighbouts and take. In unison, these clauses assign a numerical value to each square; the higher the value, the more ‘likely’ there is a ship in that square. At each step in the game, the previous moves completed are recorded by the tracking board. Using the information from the tracking board (a list), these clauses create an ordered list of the squares by how likely a ship is to be present. This is accomplished using simple addition, difference lists, and static/dynamical declaration of clauses and propositions for rules and cases. As such, we have been able to use logic programming to set up a dynamic set of rules to systematically determine possible next best steps.

Submission

Battleship can be found on [Github ].