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