Project 4: Tunnel

Tunnel is a card game invented by the instructor.

1.

13 cards are distributed to each of 4 players. Visualize the players sitting around a square table, as in bridge. Players sitting opposite each other are partners, but they do not know each other's identity. Partners thus do not have any established ``conventions.''

2.

One or more rounds of questions follows. A question consists of a player asking his/her partner whether the partner has a given card. The partner answers truthfully. (As we'll implement it, the game mediator will answer the questions.) Both the question and the answer are heard by all players.

3.

A round consists of each of the four players, in clockwise order starting from the ``dealer,'' asking a question. There are r rounds, where r is a parameter.

4.

After the questions have finished, all four players separately predict the outcome of the game, without knowledge of the other players' predictions. (More about outcomes below.) The prediction takes the form of a sequence of integers. The aim of the game is to predict the sequence accurately.

5.

The outcome of the game is determined according to the following deterministic rules. (There are no decisions to be made by the players in this part of the game.) The dealer and his/her partner pool their cards. They ``play'' each card that is the highest in its suit, until the highest card remaining in each suit is held by the opponents. Let us call the number of played cards n<sub>1</sub>. At that point, the opponents (who also pool their cards) do likewise, playing n<sub>2</sub> cards until all the top remaining cards are held by the dealer's side. Both teams alternate until 13 cards have been played altogether. So, even if a team has the next 6 high cards, if 10 cards have already been played then the final number in the sequence is 3, not 6. The sum of the entries in the sequence must be 13. The ``outcome'' is the sequence $n_1,n_2,\ldots$.

Here's an example of the play of the cards. We will call the players North, South, East and West, and will always assume South is the dealer. Suppose North/South have the following cards:

$\spadesuit$

A K T 9 7 4

$\heartsuit$

Q J 8 7 6 3 2

$\diamondsuit$

K J 9 5 3

$\clubsuit$

A J T 7 6 4 3 2

which leaves East/West with

$\spadesuit$

Q J 8 6 5 3 2

$\heartsuit$

A K T 9 5 4

$\diamondsuit$

A Q T 8 7 6 4 2

$\clubsuit$

K Q 9 8 5

North/South have 3 high cards, namely A $\spadesuit$, K $\spadesuit$, and A$\clubsuit$. So n₁=3. After those cards have been played, East/West have 7 high cards, namely Q $\spadesuit$, J $\spadesuit$, A $\heartsuit$, K $\heartsuit$, A $\diamondsuit$, K$\clubsuit$, and Q$\clubsuit$. So n₂=7. North/South then have 7 high cards, but since 10 cards have already been played, n₃=3.

The sequence can't be longer than 5 entries. (Why? What is the probability of exactly five numbers in the sequence?)

Scoring. The score of a player depends on how close the predicted sequence is to the actual sequence. The following pseudo-code describes how the score is calculated:

score = 0;
index = 1;
score_per_index = 60/(actual_sequence_length);
while (index <= actual_sequence_length) {
      score += score_per_index;
      if (guess[index] != sequence[index])
           {
            score -= 3*abs(guess[index]-sequence[index]);
            break;
           }
}

Suppose there are 3 elements in the real sequence, as above. Then, if the first number in the sequence is correct, you score 20 points plus the score for the subsequence starting with n₂. Otherwise you score 20 points less three times the absolute difference between your guess for n₁ and the real value, with no additional contribution from the rest of the sequence. Thus there is a high incentive to get the first elements of the sequence exactly correct. The maximum possible score is always 60. It is theoretically possible to obtain a negative score.

With a correct sequence of (3,7,3), a guess of (3,7,3) would score 60, a guess of (3,6,4) would score 37, a guess of (5,7,1)would score 14, and a guess of (3,5,4,1) would score 34.

Strategy. The aim is to maximize your score. You can see your cards, but need to make inferences about your partner's cards (and, by elimination, about your opponents' cards). The dealer's team may have an inherent advantage because they start the play, and we will try to quantify that advantage during class. Your partner will be predicting the sequence too, so you will be competing with him/her/it to accurately predict the outcome.

Some initial tips for deciding which cards to ask for:

• Focus on the high cards, since they impact the initial numbers in the sequence the most.
• If you have a longish sequence of consecutive or almost-consecutive cards, then ask about the gaps above and/or between them. (Why might this heuristic help?)
• Remember that the opponents (and your partner) hear the question and answer too. Choose cards that you think give you more information than the others.
• Misleading opponents by asking for a card you actually have in your hand might be a useful strategy.

We will provide software that chooses four players at random and plays a game between them, tallying the scores. At the end of the project, we will run a tournament between all players.

In addition to programming a good strategy, you should also try to determine a good value of r for a balanced game. If r is too small, scores will be consistently low. If r is too large, scores will be consistently high. Try to find a range of rs such that the variance of the score from game to game is high.

Your program must conform to interface specifications that will be supplied later.