Project 3: Generalized Clue

This game is similar to the game called ``Clue'' or ``Cluedo''. There are $n$ items. $k$ of those items ($k \ll n$) are set aside, and the reamining $n-k$ items are distributed randomly (and evenly) among $p$ players. (We'll choose $n$, $k$, and $p$, so that $n-k$ is a multiple of $p$, to avoid uneven distributions of items.) We'll label the items $1$ through $n$.

Players are organized in a circular sequence, and take turns according to that sequence. A turn for player $i$ consists of:

1. Deciding whether to guess the identities of the $k$ items that have been set aside. If player $i$ decides to make this guess, then the guess is communicated to the arbitrator (but not to the other players). The arbitrator decides if the guess is correct or incorrect, and the player's rank will be determined as described below. Either way, player $i$ no longer participates in the game, and player $i$'s items become visible to all remaining players. Remaining players do not know whether player $i$ guessed correctly or not.
2. If the player decides not to guess the hidden items, he chooses an opponent (say player $j$) to interrogate. Player $i$ provides a list of items, and player $j$ must reveal to player $i$ exactly one of those items if they are in player $j$'s possession. If there is more than one item, player $j$ decides which to show. If player $j$ does not have any of the specified items, then player $j$ responds with ``item'' $0$ to indicate this. All players see the set of items specified by player $i$. However, players other than $i$ find out only whether player $j$ responded with a valid item or not; they do not see the identity of the actual item shown to player $i$.

During the course of the game, players accumulate information about the holdings of the other players. Eventually, players should be able to identify the missing $k$ items. Players are ranked in the order in which they correctly identify the missing items. Players that incorrectly guess the missing cards are ranked below the correct-guessers, in the reverse of the order with which the guess was made.

There will be a limit to the number of turns; we will discuss the precise value for this limit in class. Any players remaining after this limit will be forced to guess the missing cards. This limit will be large enough that it is reached rarely, only to finish games in which one or more players never attempt to guess the missing cards.

Your task is to write a player that will play this game well. We will provide a moderator/arbitrator, the details of which will be described later.