Project 2: Scout

You are at war and allied forces have surrounded an enemy-controlled region. However, you do not know where in this region the enemy is located. To help focus the impending attack, you send in scouts to learn the enemy positions. The scouts have a limited time to search, and report back to the allied force that is waiting on the perimeter. To prevent enemy interceptions, scouts cannot send any radio transimissions. All communication must occur face-to-face, i.e., when the scout is co-located with the allied force, or with another scout.

The enemy region of interest is an n by n grid which we'll give coordinates (1,1) through (n,n). We'll vary n during this project to see how the size of the region affects strategy. There are allied outposts just outside the four corners of this region, at (0,0), (0,n+1), (n+1,0) and (n+1,n+1). Scouts can move anywhere within the (n+2) by (n+2) square region including the corridor on the perimeter of the enemy region, but if they try to move beyond that, the simulator will inform them that they have reached the edge of the map. Some unknown number E of cells in the grid are occupied by enemy units, with at most one enemy unit per cell. Scouts can observe the occupants of their current cell, as well as each of the 8 neighboring cells. Scouts can sense the presence of enemies, other scouts, or landmarks (see below) in adjacent cells. This information can be recorded and/or used to help the scout navigate.

S scouts parachute in to the enemy region during a storm, meaning that each scout arrives in a random cell within the enemy region. Scouts do not initially know their own coordinates. Scouts have been provisioned with maps showing a handful of landmarks that are scattered throughout the enemy region. Once a scout encounters a landmark or an allied outpost, the scout can orient themselves on the grid, since they have a compass to determine which direction is north.

When two scouts occupy the same cell, they may exchange information so that both scouts become aware of the territory covered by each of them. Each scout has a unique identifier, so that scouts know whom they encounter, and can tell which scout is in an adjacent cell.

This is a single-group game: all scouts will be running the same code written by you. Nevertheless, because scouts have unique identifiers, you are able to give specialized roles to some of your scouts.

Under normal conditions, scouts take two time units to travel orthogonally, or three time units to travel diagonally. However, when on a cell containing an enemy unit, scouts must be much more stealthy. As a result, leaving or entering a cell with an enemy unit takes six time units when traveling orthogonally, or 9 time units traveling diagonally. There is no requirement that scouts enter cells containing enemies, since scouts can observe enemies from adjacent cells. However, sometimes there may be enemy positions that are surrounded by other enemy positions so that they can only be discovered by scouts that cross enemy positions.

The whole simulation lasts t time units, after which the allied forces are obliged to attack with the information they have. The outpost updates its local information each time it is visited by a scout. Your score corresponds to the quality of the information at each of the four allied outposts at the end of the simulation. For each outpost, one point is scored for each known empty cell. For each outpost, 1000 points is scored for each known enemy location. Finally, for each enemy cell that was not identified at any outpost, 5000 points is subtracted from the score. (If an outpost makes errors, such as stating there's an enemy where no enemy exists, or vice versa, then 1000 points is lost for each such error. Note that outposts are not required to specify an occupant for every cell.)

Scouts enter the simulation knowing their own identifier, n, t, and S, but not E. They can keep information about their history in local data structures, but that information is not visible to other scouts or outposts. The simulator will expect you to implement methods for scout movement, scout communication with other scouts, and scout communication with outposts. At the beginning of a turn, scouts may communicate before moving if there is a scout or outpost on the same cell. All communication steps among all scouts are resolved before any movement orders are processed. The simulator will automatically keep track of the number of turns needed to complete a move. A scout that is in transit between cells will appear to other scouts to be in its source cell (and available for communication there) until the move is complete, typically two or three time units later.

We'll run tournaments at the end of the project for various parameter settings, as decided by the class. Typical values of n will be in the range 10 to 100. t will be small enough that complete exploration of the region by a single scout is far from feasible, while exploration by S scouts is possible. Given that the initial placement is random, we'll run a number of simulations for each parameter setting to minimize biases. We'll also use a randomization seed so that each group can be given identical starting positions in the tournament runs.

The simulator will read in a ``map'' that specifies where the landmarks are located, and this information is available to the scouts. The simulator will also read in a file containing the enemy positions. As part of the project, you'll be expected to also generate enemy placements that are adversarial to scouts, i.e., that are hard to score well against. We'll rate placements as well as scouts.