Maven is an artificial intelligence Scrabble player, created by Brian Sheppard. It has been used in official licensed Hasbro Scrabble games.
Algorithms
Game phases
Maven's gameplay is sub-divided into three phases: The "mid-game" phase, the "pre-endgame" phase, and the "endgame" phase.
The "mid-game" phase lasts from the beginning of the game up until there are nine or fewer tiles left in the bag. The program uses a rapid algorithm to find all possible plays from the given rack, and then part of the program called the "kibitzer" uses simple heuristics to sort them into rough order of quality. The most promising moves are then evaluated by "simming", in which the program simulates the random drawing of tiles, plays forward a set number of plays, and compares the points spread of the moves' outcomes. By simulating thousands of random drawings, the program can give a very accurate quantitative evaluation of the different plays. (While a Monte Carlo search, Maven does not use Monte Carlo tree search because it evaluates game trees only 2-ply deep, rather than playing out to the end of the game, and does not reallocate rollouts to more promising branches for deeper exploration; in reinforcement learning terminology, the Maven search strategy might be considered "truncated Monte Carlo simulation". A true MCTS strategy is unnecessary because the endgame can be solved. The shallow search is because the Maven author argues that, due to the fast turnover of letters in one's bag, it is typically not useful to look more than 2-ply deep, because if one instead looked deeper, e.g. 4-ply, the variance of rewards will be larger and the simulations will take several times longer, while only helping in a few exotic situations: "We maintain that if it requires an extreme situation like CACIQUE to see the value of a four-ply simulation then they are not worth doing." As the board value can be evaluated with very high accuracy in Scrabble, unlike games such as Go, deeper simulations are unlikely to change the initial evaluation.)
The "pre-endgame" phase works in almost the same way as the "mid-game" phase, except that it is designed to attempt to yield a good end-game situation.
The "endgame" phase takes over as soon as there are no tiles left in the bag. In two-player games, this means that the players can now deduce from the initial letter distribution the exact tiles on each other's racks. Maven uses the B-star search algorithm to analyze the game tree during the endgame phase.
Move generation
Maven has used several algorithms for move generation, but the one that has stuck is the DAWG algorithm. The GADDAG algorithm is faster, but a DAWG for North American English is only 0.5 MB, compared to about 2.5 MB for a GADDAG. That makes a significant difference for download games, whereas the speed advantage is not important. (Note that unimportant does not mean that the difference is small, merely that users cannot tell the difference. The GADDAG is perhaps twice as fast, but both algorithms are fast enough.)
Rack evaluation
The first (1986) version of Maven used a set of about 100 patterns to value racks. Every single tile had a value (27 patterns). Each duplicate had a value (22 patterns). There were patterns for triplicates and quads for letters that have enough representation in the bag. Finally, the QU combination was a pattern.
Soon after the first version, Maven acquired rack evaluation terms for vowel/consonant balance and Q/U distribution. Vowel/consonant balance was a table lookup based on the count of vowels and consonants left in the rack. Q/U distribution varied the values of Q and U using a table lookup indexed by how many of each remained in the bag.
Shortly thereafter, Maven acquired a tile duplication evaluator. The idea was to vary a rack depending on the chance of drawing duplicates. For example, A is generally better than I as a tile, but if there are 7 A's and only 2 I's left in the bag, then maybe we should prefer to keep the I.
Parameter fitting was accomplished by tuning the values to predict the total of future scores. Nowadays this would be called Temporal Difference Learning.
This rack evaluation design was original to Maven. It was very successful in competing with the human champions of the day.
The design was later extended by other researchers. Mark Watkins championed what he called "tile synergy patterns." These are combination like ADES which form the basis of many high-scoring words. This is a natural extension of the design, which does significantly improve play. Maven's pattern set gradually expanded from the base set of 100 to well over 400.