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. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/contents.html
   2. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/recs.html
   3. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/arch.html
   4. http://www.scrabble.com/
   5. http://www.hasbroscrabble.com/corner/rules.html
   6. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/arch.html
   7. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/lex.html
   8. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/movegen.html
   9. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html#Appel
  10. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/movesel.html
  11. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/contents.html
  12. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/recs.html
  13. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/arch.html