Scrabble - source code

The current favored lookahead strategy is traditionally called "Monte Carlo sampling"; it has been used in several areas of endeavour including game playing for many years; I believe the first computer program to use this technique in Scrabble was Richard Hooker and Tony Guilfoyle's Quetzal; it has also been used more famously in Brian Sheppard's Maven, where he calls it "simulation". Very roughly, Monte Carlo sampling in Scrabble consists of picking a random rack from the bag such as your opponent might have, and then finding his best move using that rack. You do this for each of your own moves that you are considering playing. Typically it might do this 20,000 times, to ensure a statistically significant sample. Although in classic AI, this would be done as a Minimax, with a branching ratio of 1 at each ply (possibly with some pruning such as alpha-beta cut-off to keep the exponential explosion under control); in the Scrabble programs listed here, what they call a multi-ply search is actually done as follows: Take two candidate moves A and B. For each candidate, generate a 4-ply sequence of moves, A1-A2-A3-A4 and B1-B2-B3-B4.