Distributed Computing -- Final Project
Project: Ant Wars
You will be playing both sides of a two player adversarial game.
The two players are called Finder and Responder.
The Finder must find one simple
path (i.e. no repeated nodes) for a shortest path,
for a path (if any) with distance one greater
to the destination, and for a single path (if any)
with distance two greater than the optimal path
from a given source to a given destination.
(That is, if the minimum distance is d, then one path
for distance d, one path for distance d+1,
and one for distance
Call those paths the Golden Paths.
The Responder specifies (and displays) a topology and then responds to requests
about local routing information
from "ants" that are exploring the network.
The ants communicate with a Finder manager to get orders
and convey information.
When the Finder manager is satisfied that it has found the Golden Paths,
it reports these to the Responder who displays them as well as
the time (in terms of rounds) that the Finder has spent.
To win the competition, a team (one or
two people) must correctly find the Golden Paths and
must do so in as little time as possible.
The network is built from a template
consisting of a 20 wide by 30 high checkerboard.
The checkerboard has a black square in the bottom left corner
and a black square in the top right corner.
(If you are not familiar with checkerboards
here is one that is only
8 by 8, but it also has black squares in both the bottom left
corner and the top right corner.)
In the template,
each black square is connected to its neighboring black squares.
The red squares have no connections.
The black squares are also called nodes.
Thus there are 300 nodes.
The source node is node number 11 on the bottom row (starting with
node number 1 in the bottom left corner and counting both the red
and black squares).
This is abbreviated (1,11).
The destination node is node number 10 on the top row (starting with
node number 1 in the top left corner).
This is abbreviated (30,10).
The Responder removes all the links
from at most 50 of these nodes, perhaps even disconnecting
the source node from the destination node.
The Responder displays this graph for the audience to see.
Please design your programs to be independent of these specific numbers
in case we decide to change them.
Here is a nice
The Finder is one Java process.
Every ant has an identifier and is a Java thread.
When an ant is killed, its thread dies.
The Finder manager is also a Java thread.
The Responder is a second Java process.
Communication between the Finder and Responder is through RMI.
the specification of Ariel Cohen.
"It contains my java files, the files I provided to the
students (classes, documentation, batch files and etc.), an example of
RMI which I implemented, a reference implementation for the project
and my Web page for the project."
If you don't understand it, please ask on the mailinglist.
Our Ant Wars competition will be on December 7.
The prof will assign pairs to compete with one another.
While the competition is taking place, each team will explain
its strategy. The overall winners will receive chocolate.
Remember that each team consists of one or two people
On each turn, the Finder should take no more than 5 seconds per move.
The same holds for the Responder.
The competition will take place on the Sun computers
or on Ariel's laptop.