next up previous contents
Next: Conclusions and future work Up: Games Previous: Bridge

Scrabble

A simulation-based approach has been used for a long time in Scrabble programs. Brian Sheppard, whose Scrabble program Maven defeated Grandmaster Adam Logan (a top-ranked player in the world) in the AAAI-98 Hall of Champions, coined the term ``simulator'' for this type of game-playing program structure.

During the non-endgame stage of a Scrabble game, Maven [24] chooses its moves using simulation to try to determine which move for the computer leads to the maximum number of points. To select a move Maven generates a set of candidate moves, simulates these moves a specific number of trials and chooses the move whose expected value is highest. A simulation trial consists of a two to four ply search of the game tree, except in the pre-endgame where a trial simulates to the end of the game. Since in Scrabble, the opponent's tiles are unknown, they need to be generated for every trial in the simulation and used to play out all the candidates moves. The tile generation is constrained by the tiles in the computer's hand and those that have appeared on the board. Maven does not randomly assign seven of the remaining unknown tiles to the opponent. Instead, it tries to match the distribution actually seen in games. To achieve this, it biases its choice to give the opponent a ``nice'' hand, since strong players like to have a balanced hand with lots of potential.

Opponent modeling is not performed in Maven, since it does not seem to be a critical component in playing strong Scrabble. However, inferences about the opponent's tiles can be done based on previous opponent's moves.


next up previous contents
Next: Conclusions and future work Up: Games Previous: Bridge
Lourdes Pena
1999-09-10