Project 4: Seven Letter Word

In the game of Scrabble, there's a 50-point bonus for using all seven letters on your rack. In this project we'll also aim for seven letter words, but the game will be somewhat different. There are p players in the game, where p is at most 14. We'll probably try games in which all teams have one player in the game, but it might also be interesting to try, say, 2-player games between random players. Players do not know the identity of their opponents.

There is a common pool of 98 letters distributed as in Scrabble, but without the blanks. Each player starts with n concealed letters known only to that player, with n anywhere from 0 to 7. Players then bid for letters, with each letter in turn (appearing in random order) going to the highest bidder until each player has seven letters. Letters are selected without replacement, so once somebody has the single ``Z'' nobody else will have a ``Z''. The bidding process will be described in more detail below. Apart from the initial n letters, all letters are visible to all players.

Once players have their seven letters, each player tries to make as high-scoring a word as they can. A word scores exactly what the word would have scored in Scrabble according to the points associated with the letters. In addition, a player who uses all seven letters receives a 50 point bonus. There is no bonus for words contining fewer than seven letters. The score is added to the player's total score, and the game restarts from scratch with fresh letters. After r rounds of the game, the players' total scores are compared, and the player with the highest score is the winner.

Players bid with points. Each player starts with 100 points to enable them to bid at the start of the game. As the game progresses, the point total will change as the players lose points to get letters, then gain points as they create words. A player cannot bid more points than he/she possesses, and a bid of zero points is allowed. Bids are public information: every player knows how much each player bid on each letter.

Players submit a single bid for each letter, and the player who obtains the letter is determined according to the rules of a Vickrey auction. If there is a tie for the high bid, the simulator will choose among them randomly. All bids are made simultaneously, without knowledge of other players' bids for that letter. Once a player obtains seven letters, they no longer participate in the bidding.

A word will be considered valid if and only if it appears in a standard word list that we will supply. It will be based on well-known word-lists, e.g., see http://wordlist.sourceforge.net/.

Some things to think about:

• When is it worth bidding a lot for a letter? How badly would you need a letter to bid (say) 20 points for it?
• Should you care about preventing an opponent from achieving a seven letter word?
• Can you use an opponent's bidding behavior to guess his/her private letters?
• Are the early letters more or less valuable than the later letters? How would you balance trying to get your letters early with waiting for better letters than might come later.
• What are good letters in this game?

At the end of the project, we'll run a set of tournaments for various values of n, to see whose players perform best.