A little while ago (in Spring 1999 to be exact), as part of a
programming competition at IIT Delhi,
I wrote a small scrabble playing program in Java. It is a two-player game, you
against the computer. Please download it, play, and feel free to send me
feedback. The java source code is available below, and a brief description of
the algorithm is at the end of this page.
Note that you will have to compile
the source code for your machine in order to run the program: Go to
http://java.sun.com/ for java compilers, IDEs,
etc. The program was last successfully tested in November 2004 on Windows XP
(Using NetBeans IDE 3.6) and SunOS 5.8.
The entire source code, plus a README file, a LICENSE file, and two dictionaries, is available as a WinZipped file (scrabble.zip, 189 K). The main executable class is ``Scrabbler''.
There are fifteen
.java source files, which are briefly described below :
1. Cell.java: A single cell on the scrabble
board. The board comprises 15*15 cells.
2. Letter.java: A single letter tile. It
begins life in the LetterBag, goes to one of
the players, who then plays it on the board - its final place of residence.
3. LetterBag.java: The bag where all the
letters are initially kept. After a player
makes a move, he/she replenishes his/her tiles by picking new tiles from the
LetterBag.
4. ScrabbleBoard.java: The scrabble
board. It provides lots of methods to control
the play of the game, place letters, do validity checks, compute scores, etc.
5. ScrabbleDictionary.java: The
dictionary file is loaded into this class. Supports
queries to validate words.
6. Player.java: The abstract super-class of
the human and computer players.
7. HumanPlayer.java: The human player.
8. ComputerPlayer.java: The computer
player.
9. Screen.java: The graphical representation
of the scrabble board, extends Canvas.
10.ScoreScreen.java: The graphical
representation of the score.
11.LetterScreen.java: Displays human's
letters.
12.Dialog.java: Displays a single line
message.
13.NewRandom.java: Generates random
integers.
14.HelpFrame.java: The Help frame.
15.Scrabbler.java: The main class which
starts up the whole program.
This section describes the procedure used by the ComputerPlayer class to figure out what to play. Students of CS Theory: please note that while the algorithm has a very high (almost laughably high) time complexity, it functions well (and reasonably fast) in practice with the two dictionaries provided, and this despite the fact that it's coded in Java. Students of Artificial Intelligence: I make no claim that the heuristics used by this program are in any way theoretically satisfactory; once again, the point is that the program was found to be a sufficiently challenging competitor for most of my colleagues. Moreover, this particular strategy was selected after trial-and-error over other algorithms which were found to be inferior.
The algorithms begins by scanning the entire dictionary for words that are either:
It then scans the entire board (15 x 15 cells), and for each cell, checks each fully- and almost- formable word to see if it can be placed there given the past placement of tiles and the rules of scrabble. Every word that constitutes a legal move is added to a list of eligible moves. The score of that word is computed. Then, in an attempt to model strategic behavior, the computer player updates the score for each eligible move by the following rules:
The computer then plays its highest scoring eligible move, except if the highest scoring eligible move nets less than 6 points, in which case the computer changes letters.
If you are interested in updating the rules or changing the algorithm, it should be fairly easy to do in the source code. Good luck!