# Distributed Computing -- Final Project

## Project: Ant Wars

• Overall idea 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 d+2.) 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. For communication please follow the specification of Ariel Cohen. Ariel writes: "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.