Project 1: Escape

You and a group of friends are trapped in a large dark room. There is loud noise in the background, so you cannot communicate verbally. There are n handles distributed thoughout the room, where n is the number of people in the room. The way to escape is for each player to hold a distinct handle at a particular moment in time. When that happens, an exit from the room opens and you are free.

The game takes place in turns. Each player can choose a handle (numbered 1 through n) to hold on that turn. Each player has a different randomly generated numbering scheme, so that players cannot figure out in advance something like ``player i goes to handle i''. If every player has a unique handle, the game is over, and all players score the number of turns it took to achieve this state. If not, each player is told how many players attempted to hold the handle they went for, and the identity of those players. This information is available by touch, apparently. Based on this information, players can choose which handles to go for on subsequent turns. Player numbering is also randomized among the players, so players cannot gain information from a predefined player order.

One annoying rule of this game: If more than one player grabbed handle i on a turn, then none of those players can grab handle i on the next turn. This rule is particularly problematic for n=2. (Why?)

We'll explore two versions of this game, and your player will know which version they are playing:

Co-ordinated

You get to program all n players, and you can build in knowledge of protocols, so that player j might be able to anticipate some of player i's moves. Remember though that each player has a different numbering of the handles, so the ability to make predictions may be limited.

Independent

You program only one of the players, and other players (e.g., those programmed by other groups, or the supplied RandomPlayer) may use different protocols.

For each game version, your aim is to exit the room in as few turns as possible.

Some things to think about:

• Can you estimate the expected completion time for a true RandomPlayer?
• How do you think the completion time for the Co-ordinated version of the game might scale with n?
• Might it be possible (after accumulating enough information) to make predictions about the other players' behaviors even in the Independent game version?