Project 3: Let's Get Together

In this game, players cooperate to find each other to exchange information. Suppose there are $n$ players. There are $n$ pieces of information which we'll number $1,2,\ldots,n$, and player $i$ starts with the piece of information labeled $i$.

Each player moves around a grid of size $l$ by $w$, which wraps when one moves off the edge. When two (or more) players occupy the same cell of the grid, they exchange all of the information they hold. For example, if players 2 and 5 meet on a cell, then player 2 learns information unit 5, and player 5 learns information unit 2. If player 5 later meets player 7 on some grid cell, then player 7 learns both items 2 and 5 from player 5, and player 5 learns whatever player 7 knows.

The game ends when one player (it doesn't matter which) learns all of the information units. Every player receives the same score, which is simply the number of turns it took to reach the end state. The game is cooperative: all players have an interest in meeting other players to minimize the number of turns needed. The aim is to minimize, over many runs of the game, the average score.

We'll run several tournaments to test your players. In one tournament all players will be running code from a single group. In other tournaments, players will be randomly selected from different groups. The same code must be used for both tournaments: there will be no special flag set for single-group tournaments. We'll try various values of $n$, $l$, and $w$; we'll discuss which values to use in class.

Players start at random positions on the grid, and they know the values of $n$, $l$ and $w$. Players do not know their coordinates on the grid. (This excludes certain strategies, such as ``everybody meet at (3,5)''.) All players get is local information as described below. When a player moves onto a cell, the cell ``remembers'' the identity of the information units that have passed though that square. (Visiting a cell twice is the same as visiting it once, unless a player has gathered additional information units.) Even though the cell records the identity of the information units, players cannot learn information from the cells themselves; they need to learn from other players directly.

A player has access to the following information about the cell currently occupied, together with the eight surrounding cells:

• The identities of players who might be on those cells (but not the items of information that they know).
• Which information units have passed through that cell.

On each turn, a player can move one cell either orthogonally or diagonally, or may choose to stay put. At the end of a turn, players who occupy the same cell exchange their units of information.

Some initial things to think about:

• Would you use the cell memory to decide which direction to move in? If so, how?
• How do two players next to each other coordinate their movements so that they end up on the same square?
• Should a player's strategy change once it has exchanged information with some of the other players? How many other players?
• After an exchange, the two (or perhaps more) parties have the same information. Should they coordinate their subsequent moves, and if so, in what way?
• Meeting a player a second time could be useful if that player has learned more information in the intervening period. Yet it would be a waste of time to repeatedly meet the same players over and over again. How does one balance these conflicting goals?

Your code should be written in Java. The precise specifications will be provided later.