Project 1: Bidding Wars

This problem is based on a game described to me by Jenny Finkel, a student in 4444 last year.

Imagine a deck of cards in which cards are numbered from $1$ to $n$, for some arbitrary number $n$. Two players are each dealt $n$ cards, where each player has exactly one card of each denomination. Another deck of $n$ cards (again, one per denomination) is shuffled and placed face-down on a table. The game takes $n$ turns. Each turn proceeds as follows.

The top card of the deck is turned over. Each player sees that card. Let's say it has rank $k$. Each player selects a card from his/her hand and places it face-down on the table. Once both cards have been chosen, they are exposed simultaneously. Suppose player 1's card has rank $p_1$ and player 2's card has rank $p_2$. Then there are three possible outcomes:

$\parbox{5in}{ \begin{itemize} \item[$p_1>p_2$] Player 1 \lq\lq wins'' and... ...either player \lq\lq wins'' and neither player adds to his/her score. \end{itemize}}$

At the end of $n$ rounds, the player with the higher score is the winner.

(Equivalently, one could give each player $k/2$ when there is a tie. This does not make a difference to the present game. However, if one were to generalize the game to more than two players, it would make sense, when $p$ players are tied for the top score, to give $k/p$ to each such player.)

Your job is to write a computer player for this game. There is strategy in this game, some obvious and some subtle. We'll discuss some strategy in class. The main aim of the game is to win rounds by as small a margin as possible. Winning a card with mediocre $k$ by a big margin means that the player could be at a disadvantage later in the game, as the opponent has more bidding power. It will also pay to remember past bids, because a card can be used in only one round.

We'll provide software to interact with your players. Your player will not know the identity of its opponent, but it will get to play many games against the same opponent. Thus, a player could conceivably learn its opponents behavior and adjust its own style of play.

At the end of the project, we'll run tournaments for various values of $n$.