Next: About this document ... Up: W4444 Programming and Problem Previous: Project 3: Railway Auction
You are part of a commando team whose job is to parachute into an unknown area, locate a ``package,'' and deliver it to a target location. This is a cooperative game, in which each group plays the role of one commando in the team. However, one of the commandos is a spy, whose job is to disrupt the effort. The identity of the spy is unknown at the start to all but the spy.
The field of operations is a 100x100 grid of cells, some of which are covered by water, and are impassable. The remaining land cells may be either in good condition or muddy. At the start of the game each commando has a map of the field, including the water cells, but not including any information about the condition of the land cells. The commando knows his own starting position, but not the starting positions of the other team members. The target location and package location are initially unknown, and must be discovered by exploring the territory.
Soldiers can move one cell orthogonally in two time units, and diagonally in three time units if the cell they are moving to is in good condition. If the ground is muddy, the time taken is doubled. Soldiers can see all cells whose centers are no more than three cell-widths from the center of the cell they occupy. In those cells, soldiers see the condition of the cell, any soldiers in the cell (including their identity), and whether the cell contains the package or target.
When soldiers occupy the same cell, they can exchange information to help each other explore the field. The details of this exchange will be explained below. Eventually, the team must collectively figure out a path from the package to the target that traverses only cells in good condition. The package is heavy, and cannot be carried through muddy terrain. (You may assume that the map contains a path from package to target over cells in good condition.) Further, it takes three soldiers to carry the package, so three soldiers must agree on a path while occupying the cell containing the package. The protocol for agreement will also be detailed below.
When two soldiers communicate, they each transmit a set of records of the following form:
In a list, the tuples are in timestamp order, so
. The meaning of the sublist of soldier-timestamp pairs is that
solder s1 claims to have directly observed the cell (x,y) and
reported the observation to soldier s2 at time t1. Soldier s2
then passed on this information to soldier s3 at timestamp s2, and
so on until the information arrives at soldier sk. sk should be
the id of the soldier providing the information in the exchange, and
tk should be the current timestamp. Thus, to pass on information,
the simplest thing to do is to append your own id and the current
timestamp to all the lists you have, including a
(x,y,c,pt,(s,t))
list for each cell you've observed directly. These lists track the
provenance of the information gained, which will be important because
the information gained from the spy may be unreliable.
Soldiers are not obliged to keep or pass on every detail of what they learn. For example, if the player's own id appears in a list she is receiving, then that information is somehow stale, since the soldier already knew the cell's status earlier and it has just been passed through a few more hands. Similarly later information (e.g., a direct observation) might override earlier second-hand information about a cell. Deciding what information to keep and what to discard is an important part of this project. Keep in mind that some of the information may have come from a spy, and so some redundancy may be needed to detect false information. For example, if you've heard about the status of cell (x,y) from two independent chains of teammates, you may choose to share two lists with the same (x,y) coordinates when you exchange information. (Be careful! Bugs in your code leading to inaccurate information may mean that your teammates misidentify you as the spy.)
Eventually, some members of the team will believe they have found a safe path from the package to the target through cells in good condition. Such players should move to the location of the package and announce the proposed path to any other teammates located there. After any announcement, all other soldiers at the location can choose to agree to a proposed path. Only players at the package location hear the announcement. If at least two additional soldiers support a path, then those three soldiers pick up the package and follow the path, ending the game. If multiple paths get support then nothing happens, and the game continues until the outcome of the announcement phase is a single path with sufficient support.
The result of the game can be either success or failure. Failure can happen if either (a) the game times out before the team can complete the task; or (b) the team commits to a path for the package that is not viable, i.e., it passes through a muddy cell, or it does not end at the target location. A successful team scores the time taken to deliver the package, which is computed as the timestamp at the time the group committed to a path, plus 5 times the time needed for a single soldier to complete the path (since it's slow going when you're carrying the package). So there is an incentive to find a short path to transport the package. A smaller score is better. A failed outcome scores double the timeout interval. (We might want to discuss in class whether the two different kinds of failure be scored differently.) From the point of view of the spy, a higher score is better.
The spy has access to exactly the same interfaces and information as the regular players. However, the spy's goal is to disrupt the team, and ideally cause it to fail. The spy could try to do that by giving out information that is always false. However, such an approach may make it easy to detect the spy. A more nuanced approach may make detection harder, but there is still a lot of scope for deciding what to do to disrupt the team: selectively give out false information, announce a non-viable path, etc. Even when detected by some teammates, the spy may not be known to all teammates.
The map used in the game is a parameter. It includes the status of every cell, the locations of the target and package, and a list of 30 land cells that are candidate starting points in the game. If there are 8 members of the team in a given game, for example, then the first 8 cells on the starting point list are used, and players are randomly assigned to the starting cells. This way, maps can be used for teams of up to 30, including games where multiple players from each group are included. At the start of the project we'll ask groups to come up with interesting maps. Maps must have the following properties: (a) all land cells are reachable from each other; (b) the target must be reachable from the package via a path over cells in good condition, meaning also that the target and package themselves are on different cells that are both in good condition.
The timeout limit is a parameter to the simulation that is known to all players. We'll develop some experience with the game before settling on specific numbers.
At the end of the project we'll run several tournaments over a variety of maps. We'll run variants with all groups together, as well as variants with just subsets of the groups, to see how the presence/absence of certain players influences the score.
Some things to think about: