Scrabble® [1]Back to Contents Prev: [2]Recommendations Next: [3]Infrastructure Architecture _________________________________________________________________ Introduction The intent of this project was to investigate the artificial intelligence problem of teaching a computer to play the game of [4]Scrabble. Scrabble is a popular board game that involves the placement of letters on a board to form words, which are scored based on a point value assigned to each letter and its particular placement on the board. This document assumes an understanding of the [5]rules of Scrabble. Game Infrastructure A pre-requisite of this investigation is the existence of an infrastructure that provides: 1. Appropriate programmatic interfaces to the concepts of Scrabble gameplay, including the game board, player letter racks, letter tiles, scoring rules, legal word formation rules, etc. 2. A user interface that allows easy observation and participation in gameplay. Some preliminary research suggested that no such freely available infrastructure exists for Scrabble (unlike, for example, the game of chess), and thus design and development of an [6]appropriate infrastructure was necessary. Computer Game Play Scrabble is a turn-based game; algorithmically, it is helpful to consider the problem of making a move in Scrabble as 2 sub-problems: 1. Generating possible moves for a particular turn. 2. Choosing the "best" move amongst those possibilities (where "best" is defined as the one that has the greatest chance of leading to victory). The problem of generating possible moves for a particular turn is intimately associated with the issue of [7]lexicon representation; while it can be considered a given that for a computer to play Scrabble it must have a lexicon of words that it "knows", the ways in which such a lexicon can be represented are many-fold, and the choice of representation will constrain the manner in which possible moves are found. This project implements a modified version of an [8]exhaustive move search algorithm due [9]Appel and Jacobson. Due to time constraints, this project implements a very simple greedy move selection algorithm. The problem of choosing the "best" move amongst all candidate moves is quite complex. As selection of letters is random, and the number of candidate moves each turn often high (on the order of hundreds), the branching factor of the game tree is extremely large; strategies for picking a move based on some heuristic guidelines, and the idea of using probabilistic simulation are discussed in the section on [10]move selection. _________________________________________________________________ [11]Back to Contents Prev: [12]Recommendations Next: [13]Infrastructure Architecture References 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.