Scrabble® [1]Back to Contents Prev: [2]Move Generation Algorithm Next:
   [3]References
     _________________________________________________________________
   
                           Move Selection Strategies
                                       
   With a list of all possible moves determined, the next step is to
   actually pick one of those moves to make. A standard approach to
   problems of this nature involves deriving some heuristic algorithms
   that can evaluate the strength of a particular move in terms of its
   contribution to an eventual victory. This section discusses some
   heuristics that apply to Scrabble.
   
The Simple Greedy Heuristic

   The simple greedy heuristic is to just pick the highest scoring
   (point-wise) move each turn. Details concerning the performance of
   this algorithm with respect to itself and human players are given in
   the [4]Conclusions. Obviously this heuristic maximizes immediate gain
   in score; in order to see why this is not necessarily the best path to
   victory, we need to examine what kinds of strategy exists in Scrabble.
   
Scrabble Move Strategy

  Opponent Search
  
   Scrabble is a largely a game of imperfect information; throughout most
   of the game, there is uncertainty with regard to what tiles will be
   drawn, and what tiles are held by opponents. This is unlike games like
   chess or checkers, where the opponent's state is known perfectly. This
   kind of informational uncertainty makes the standard game-tree
   opponent search strategy essentially intractable (due to the
   staggeringly high branching factor caused by the possible combinations
   of held tiles, playable moves and drawn tiles), and questionable in
   effectiveness throughout most of the game since the probability of
   correctly guessing the opponent's rack and next move during any
   particular turn is very low.
   
   One notable exception to this situation is in the end game. By
   enumerating the tiles that have been played and the tiles held
   personally, at a certain point towards the end game (depending on the
   number of players) it is possible for each player to know exactly what
   other players hold and/or what tiles remain to be drawn. In this
   situation, opponent search becomes a feasible strategy, since the
   branching factor is much reduced.
   
  Rack Leave Heuristics
  
   A standard component of Scrabble strategy involves considering what
   tiles will be left on one's rack after making a particular move. This
   is important because certain letter combinations are more prone to
   form long and/or high scoring words; for example, ING, LY, ATE, etc.
   This also argues for the selective retention of individual
   high-scoring letters, in the hopes of being able to utilize them in
   even higher scoring words than are currently possible.
   
   This leads naturally to the idea evaluating rack leave using a
   heuristic function, and weighting move selection accordingly.
   [5]Gordon considers a number of such heuristics, which account for
   such issues as duplicate tiles and vowel-consonant mix. [6]Edley
   sketches out some recommendations for weighting vowels and consonants.
   This is a very fruitful area for continued investigation.
   
  Move Placement Heuristics
  
   Another commonly exploited strategic area in Scrabble concerns the
   manner in which moves "open up" or "close" areas of the board, in the
   sense of creating or denying areas on the board which have the
   potential to lead to high scoring moves (because they contain high
   scoring letters, easily extendable word fragments, a surfeit of bonus
   score squares or some combination of these factors). [7]Edley has a
   basic discussion of such issues while [8]Ballard goes into
   considerably greater depth discussing how Scrabble players analyze
   complex game situations. Effectively codifying this kind of knowledge
   in terms of a heuristic function seems to be an open problem.
     _________________________________________________________________
   
   [9]Back to Contents Prev: [10]Move Generation Algorithm Next:
   [11]References

References

   1. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/contents.html
   2. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/movegen.html
   3. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html
   4. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/conclude.html
   5. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html#Gordon2
   6. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html#Edley
   7. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html#Edley
   8. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html#Ballard
   9. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/contents.html
  10. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/movegen.html
  11. http://www.ece.uwaterloo.ca/~k2tam/Scrabble/refs.html