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 to
,
for some arbitrary number
. Two players are each dealt
cards,
where each player has exactly one card of each denomination. Another
deck of
cards (again, one per denomination) is shuffled and
placed face-down on a table. The game takes
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 . 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
and player 2's card has rank
. Then there are three
possible outcomes:
At the end of rounds, the player with the higher score is the winner.
(Equivalently, one could give each player 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
players are tied for the top score, to give
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 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 .