Part I Develop a ScrabbleAgent to find the optimal initial move of a Scrabble game, given the following inputs:

1. An empty Scrabble board. Assume the agent knows how the premium squares work, as well as their locations on the board.

2. The complete SOWPODS word list, containing all 267,751 legal words. 3. A collection of 7 tiles in the agents rack, of which at most 2 may be blank (wildcard) tiles.

The minimum output should be:

RACK: , where represents the tiles in the agents rack.

PASS, if the agents choice is to pass the turn.

EXCHANGE , if the agents choice is to exchange 1 or more tiles from the rack with tiles from the tile bag. Here, should indicate which tiles the agent wants to exchange.

PLACE WORD , if the agent decides to place a word on the board. Here, should be replaced with the word the agent wants to place; indicates the identity of the square where the first letter of the word is to be placed (this can be in format, or a single integer value indicating the column in which the first letter should be placed, since the identity of the row is predetermined by the game rules; indicates how many points the word is worth, based on its placement.

ELAPSED TIME: , to indicate how much time it took for the agent to determine its move. The result can be displayed in seconds or milliseconds. If your agent requires units higher than this, you need to do some more optimization.

The goals your agent should strive to achieve are:

Find the highest scoring word that can be made from the current rack of tiles. If you want to factor in other strategies, such as retaining certain tiles that may be more useful later (e.g., S, blank tiles), feel free to do so, but be sure to note this in your narrative for Part II.

Minimize the number of computationally expensive operations. These operations include such things as generation of all permutations and combinations, complete or near complete traversals of large data structures, and comparisons.

Minimize storage requirements. This problem is complex enough that it can eat up your heap memory if youre not careful, depending on how much memory your system has, and the programming language youre using. Also, remember that although disk storage frees up main memory, it is very expensive in terms of running time.

Minimize running time. You can measure the running time required for an operation by sto ing the system time immediately before the operation is performed, and reading the system time again immediately after the operation is complete. The difference is the running time required for that particular instance, which by itself is of limited use.

When you measure your agents performance, remember that the performance for a single trial usually wont give you much information. You need to perform multiple trials, using different data inputs, and finding the average performance, to give you a better indication of how efficient your agent is.

Specific Design Requirements

1.

2. 3. 4.

Choice of

The arrangements for the tiles in the rack should be read from a flat text file containing a list of test racks. Each rack will be represented by a String of 7 characters. Uppercase letters A-Z will be used for lettered tiles, and the underscore character _ will be used to represent blank tiles. Download an example rack data file. The point of this is to allow rapid batch testing of multiple racks without the need to enter the data for the rack anew for every test. This saves valuable time, and it will allow you to easily re-run an entire test suite if you make a change to your code.

You will need to come up with your own solution to represent the Scrabble board, which will always be empty for the initial move.

You are NOT required to construct your agent to fit with any framework code, as in the previous assignment.

Other than that, there are virtually no restrictions on how you choose to design your agent. Feel free to use any of the ideas presented in the course (including topics we have not yet discussed, if you feel confident enough). You may also use ideas you glean from researching the problem. Of course, you must ultimately design and implement your own agent, and not simply reuse code found elsewhere.

Programming Language

You have language you choose allows you to meet the requirements listed above. The only stipulation is that I must be able to compile and run your code in Windows XP or Windows 7.

some latitude regarding the choice of programming language for this assignment, so long as the

Testing

Although e xhaustive testing for this project will be impractical, you should strive to make sure your code is designed to apply generally to any rack of 7 tiles, even if blank tiles are present. If you need an oracle to guide your testing, there are several available on the internet. Two examples are: Lexical Word Finder (http://www.lexicalwordfinder.com/) and ScrabbleSolver (http://www.scrabblesolver.net/). Although I am providing you with a sample data file for reading in the rack data, the actual test file I use will contain more inputs.

Part II

Write a brief narrative discussing your rationale for the approach you chose. Include in this narrative:

a discussion of why you chose/rejected certain heuristics (e.g., how a heuristic reduced the size of the search space or how it improved running time)

any potential strategic values involved (e.g., saving blanks for later turns)

an attempt to estimate the performance in terms of code complexity; i.e., Big-Oh. You dont have to be exactly correct in your Big-Oh estimate, but you should have a ballpark idea of how your code should theoretically perform.

supporting data such as data from time trials (if you performed time trials)

I am looking for content rather than length for the narrative, so dont feel pressured to write pages and pages for this. Basically all Im asking you to do here is give a rationale for what you chose to do.

Some Advice

Keep things simple. You arent required to solve the entire game of Scrabble, nor are you required to design your agent to play beyond the placement of the initial word (so you wont need to worry about implementing game play between players, using minimax trees, etc.)youre only being asked to build an agent that will try to find an optimal solution to the first move of the game.

Dont worry about getting THE correct answer, because there isnt one. There are, however, many ACCEPT- ABLE answers. There is no specific performance level I am expecting your agent to reach, especially con- sidering the variations in performance that will occur depending on your systems hardware. As a general guide, if your agent takes more than a few seconds to decide on a move, routinely runs out of memory, or consistently returns low-scoring words, you probably need to do some more optimization.

In a similar vein to the previously listed item, dont get so focused on trying to find the best solution that you end up with nothing to turn in. Make sure you first have a solution to turn in that works, and once youve accomplished that, back it up and then play around trying to optimize it as time permits.

Although there is a tremendous amount of publicly available research and data about the game of Scrab- ble, dont become overwhelmed by trying to utilize all this information.