CMSC 471 Project Description

September 28, 2004
Prof. Marie desJardins

Project Overview

You must work in groups of two or three (unless you have permission from the instructor to work individually). The goal of the project is to write an "intelligent agent" that can play Battleship 471, a variation of the classic Battleship game.

Project Deadlines and Deliverables

Background: Classic Battleship

In the classic game Battleship, each player has a hidden 10x10 grid on which they place five ships: a patrol boat (which occupies two adjacent spaces), a submarine (which occupies three spaces in a row or column), a destroyer (three spaces), a battleship (four spaces), and a carrier (five spaces). No diagonal ship placements are possible -- that is, every ship must lie along a row or a column.

The players take turns "firing" at grid locations on the opponent's board. If they miss, they record their guess as a miss. If they hit, the opponent must announce which ship was hit. When a player hits all of the spaces in which a particular ship is placed, they must announce that the other player sank that ship.

The first player to sink all of the other player's ships wins the game.

Here's a Java version of the original Battleship game called Armada.

Strategy/Analysis. The game is mostly luck, but there is a small amount of reasoning, since you know how long the opponent's ships are, and that ships must be placed along a row or column. One could imagine using constraint satisfaction techniques to keep track of which locations are possible, necessary, or impossible, and which orientation a ship may have.

Battleship 471

Please note: This project is new this year. Therefore, adjustments to the rules may have to be made as we go along. I don't want to make unnecessary changes, so the game rules will be finalized as of October 12 (that's two weeks from now). Please be thinking about your design, and any modifications to the game play that you think would improve the project, between now and then. Also please be aware that minor changes could be made after that date (e.g., the utilities associated with the different actions), so your player should not be too "hardwired."

Summary. Battleship 471 adds several key elements to the original game:

  1. A variable board size, plus variable number and types of boats.
  2. One-player and two-player modes, with a game server creating the board in both cases.
  3. "Peek" and "Shoot" moves with probabilistic outcomes and variable utilities.
  4. A "Block" move for two-player mode.
  5. A "learnable" board generator with a bias towards certain board configurations (which your agent can try to learn!)

Game Parameters. Your player should take three parameters:

  1. The height of the board.
  2. The width of the board.
  3. A list of two-item lists, where each sublist contains a unique ship name (represented as a symbol) and the length of that ship. For example, the ships in the original game would be represented as:
      '((PATROL 2) (SUBMARINE 3) (DESTROYER 3) (BATTLESHIP 4) (CARRIER 5))
In other words, your agent should be able to play for any board size and any set of pieces -- these game parameters shouldn't be hardwired in. For the purposes of development, you can start with a 10x10 board and the standard set of pieces. Also, when the various "game generators" are released (see Learning, below), the parameters will be fixed for that game generator.

One-Player Mode. This mode will be used for testing only; there will not be a one-player tournament (unless students would like to set one up for fun). In one-player mode, the game server sets up the board. Your agent uses any sequence of Peek and Shoot moves to try to sink all of the ships on the board with the highest final utility . (See below for move descriptions and utilities.) We will provide an API to play repeatable games (and game series), so that you can compare different player versions against each other.

Two-Player Mode. In two-player mode, players alternate turns. Each player can execute zero or one Peek actions, followed by zero or one Shoot actions, followed by zero or one Block actions. (See below for action descriptions.) At the end of the game, the player with the highest utility wins.

In two-player mode, you can see what Peek and Shoot actions the other player executes (including the location that was the target of the Peek or Shoot action), but not the results of those actions. You can see whether the other player performed a Block action, but not the location of the Block. (See below.)

Peek The Peek action is a variable-cost action that, given a board position, tells you what ship -- if any -- is located at that location. The twist is that the more you pay, the more accurate the Peek is. Specifically, you can "pay" anywhere from 1 to 5 "utility points" for a Peek action. The probability that Peek gives you the right answer is equal to (cost*10 + 1/2). That is, if you pay 1 utility point, you have a 60% probability of getting the correct information. If you pay 5 utility points, you have a 100% probability of getting the correct information.

If there is a ship at that location, and Peek reports that there is a ship, it will tell you the correct ship name. If there is no ship, but Peek says that there is a ship, it will tell you a random ship name each time. (So if you get two different ship names from two Peeks at the same location, you know that there is not really a ship there.)

Shoot. The Shoot action has a fixed cost, but probabilistic efficacy. It always costs 10 "utility points" to shoot at a single location. If there is a ship in that location, Shoot randomly destroys a percentage of the ship at that location, from 10% to 100% (always a multiple of 10%). You receive 2 utility points for each 10% destroyed. (If some of the ship was already destroyed, then you only get credit for what's left, even if the Shoot action would have destroyed 100% of the ship. If none of the ship was left at that location when you started shooting, it will give you the same "Missed" response as it does when there is no ship.)

The Shoot action tells you the name of the ship and how much of it was destroyed. If there is no ship at that location (or if the location was Blocked; see below), then you get a report saying that the Shoot action missed.

Block. In two-player mode, you can take a single Block action on each turn. This action shields a specified location from the other player's Shoot action. If they Shoot at that location, they get a report saying that the action missed. They have no direct way to tell whether the failure was because there is no ship, or because you Blocked them.

Board Generator. There will be two divisions for the final tournament: one with a random board generator, and one with a "learnable board generator." All teams will compete in both divisions.

The learnable board generator generates boards randomly, but the boards are subject to a set of cosntraints. These constraints will be represented in terms of the following features:

Learning takes time and data. Therefore, in mid-November, we'll release a couple of practice board generators for you to experiment on, if you choose to include learning in your intelligent agent. The descriptions of the generators will be announced at the end of November. At the same time, the actual tournament board generator will be released. That gives you two weeks before the tournament to try to get your agent to learn the board generator.

There may be some noise in the board generator (i.e., it might sometimes violate some of the constraints). I'll let you know whether there will be any noise, and the nature of the noise, in advance of releasing the board generators. (The tournament generator will be subject to the same type of noise as the practice board generators.)

Please note that reverse-engineering the board generator by observation (rather than having your intelligent) is considered cheating. Any knowledge about the board generator must come from learning within the agent, not from the students.

Also, please note that you do not have to include learning in your agent. If you don't, you may not play as well in the "learnable board generator" division. That's OK and won't be counted against you! (Besides, you never know; the non-learning agents might end up winning...)

Project Requirements

You must use at least two AI techniques/concepts that we are studying this semester in the design of your project. Just hacking together a piece of code that can play the game but doesn't use any AI theory won't receive full credit -- even if it wins the tournament. Conversely, a well designed player that uses AI techniques in an appropriate way -- but that turns out not to beat the other players -- can earn an A. (If I have to choose, I'd rather see a really interesting design than a working player. But both would be nice...) You are certainly welcome to use more than two AI techniques! On the other hand, competition adds spice to life, so performance in the tournament will count towards your grade in the project. See notes on grading, below. Examples of AI techniques that you may wish to use in your game design:
  1. Constraint satisfaction
  2. Backtracking heuristic search and/or local search
  3. Game-playing search
  4. Forward-chaining logical reasoning
  5. Bayesian reasoning
  6. Machine learning
  7. Planning
There are many different possible designs, and there is no right solution. What I will be looking for in grading the project reports are an understanding of AI techniques and how they are applied, and a well thought out overall design for your intelligent agent. The Lisp code itself counts for a portion of the grade, but the design is more important. (See grading notes, below.)

Project Grading

The project will count for 25% of your final course grade. This grade will be determined as follows: Also, I will ask you midway through the semester, and again at the end of the semester, to turn in brief summaries of how the project is going -- how you are dividing the work, whether you think the balance within the team is fair, and whether there are any problems with the team. These are confidential, individual reports that will not count towards your grade, but may help me allocate credit within the team. These reports will also alert me to any developing problems, so please be frank.

Getting Started

The project infrastructure and API should be available by Thursday, October 14. At this point, I suggest that you get started on coding by writing a simple agent for one-player mode, using a simple strategy such as the naive aggressive strategies described below. This will give you experience with the required Lisp interface, a chance to work with the game server, and a feeling for how the game works.

At the same time, you should be designing the high-level approach that you plan to use, and dividing up the coding responsibilities among the members of your team.

Baseline Naive Strategy.

  1. Peek(cost=5) (i.e., probability=1) at every location, starting in the upper left.
  2. When Peek says there's a ship, start Shooting at that location until the ship is destroyed.
This strategy is guaranteed to terminate, but you may have to examine the entire board, and spend a lot of utility points Peeking at empty spots.

Baseline Aggressive Strategy.

  1. Fire at random (but not revisiting a failed location) until you hit something, then blast away at it until it's killed.

Of course, what you really want is a strategy that can reason about the possible and likely locations of ships on the board, and fire at those locations if the expected utility of doing so is greater than the expected utility of some other action.

Circle the Enemy Strategy.

  1. Fire at random (but not revisiting a failed location) until you hit something, then blast away at it until it's killed.
  2. Once you've destroyed one location of a ship, start firing in a "Manhattan circle" (left, right, above, and below) around it (avoiding spots that are known to be empty). Repeat until that ship is completely destroyed.
This strategy is at least a little bit smarter, but not much. It also will be a bit tricker to implement (e.g., what happens if you hit a different ship as you're expanding your "Manhattan circle" around another ship?)