Project 1: Seven Letter Word

This project was given to the students of the 2009 class. At the end of that project, the students felt that it still had room for further development of the ideas. So we're going to re-use the same project, with one important modification that I'll mention later. The 2010 class will get to see the 2009 reports and submitted code on courseworks, and be able to build on the previous work. Of course, you're welcome to start from scratch if you think you have a new way of approaching the problem. (An advantage of starting with a previous problem is that it is easier to learn the mechanics of working with the provided programming interface.)

Directly building on the code from last year is acceptable, but keep the following points in mind:

• Your solution will be evaluated based on the increment beyond the code you started with. Tweaking a few parameters to slightly improve performance is unlikely to lead to a distinctive solution.
• Last year's code may have limitations that prevent a full exploration of the design space without substantial rewriting. Also, there may be subtle bugs remaining in the code. (Several groups have observed these issues in the past, and have regretted the choice to extend existing code rather than to start from scratch.)
• This year's project is slightly different from last year's. While last year's projects should function correctly, they will not be aware of the new specification.

Here's the 2009 description:

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.

For 2010, we're going to slightly change the bidding process. Instead of stopping when each player has seven letters, we'll allow players with full racks to continue bidding and accumulating letters. There will be a total of 8p letters auctioned. At the end of the auction, the average number of letters per player will be 8, but some players may have 9, some may have 7, and others may possibly have fewer than 7 (which means they won't be able to make any seven letter words). Because of the extra rounds, p can be at most 12 with 98 letter tiles.

Some new things to think about:

• Presumably, the extra letters will increase the chances of getting a seven letter word. How does this change your strategy? Should you aim for higher scoring seven letter words?
• Would it be a good strategy to bid for unneeded letters to prevent an opponent from getting seven letters?
• How does the value of each letter change with this new bidding system?