321:
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
121:
216:
25:
66:
488:
The case of a PEG-1 is important, because almost half of all games pass through that state. Maven can play out such states exhaustively in almost all cases. That is, for all legal moves Maven can play out the resulting endgames (up to 8 for each legal move), and calculate which side will win the game
476:
A further refinement makes Maven's endgame solutions asymptotically optimal even in the presence of errors. When the B* search terminates with a proof that one move is best, and there is still time remaining, then Maven widens its estimates by 1 point and searches again. These re-searches are usually
472:
It turns out that it is possible to estimate upper and lower bounds on endgame positions. These bounds are correct (that is, the true value lies within the interval) for the overwhelming majority of positions. Since B* is reasonably robust in the presence of a small percentage of error in the bounds,
416:
Maven's version of exhaustive rack evaluation has added that ability. In Maven, each rack has its own liner evaluator, where the value of that rack varies as a function of the chance of drawing a duplicate, the chance of drawing a vowel, and the chance of drawing Q and U. This system has 5 parameters
334:
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
370:
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
320:
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
383:
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
379:
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
441:
By the mid-1990s, computers had become fast enough that Maven used simulation to choose moves in competitive games under tournament time controls. Algorithmic improvements were important to scaling simulation for this purpose. The most important innovation was to vary the number of trials given to
401:
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
499:
This policy does not produce play that is theoretically perfect, because it is impossible to know what the true initial distribution of unseen tiles should be. Assuming a uniform distribution does well, and it is possible to calculate inferences about unseen tiles that marginally improves on that
329:
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
460:
The problem with Alpha Beta is that some
Scrabble endgames require 14 moves to play out, and it is not possible to search that deeply. This is not merely a theoretical possibility. When one player is "stuck" with a tile, then playing out all remaining tiles is impossible. In that situation the
503:
Another limitation is that Maven is not addressing the "hidden information" aspect of such situations. That is, in theory there are situations where players maximize expectation by randomly choosing moves according to a probability distribution. Maven is choosing pure strategies at each node.
437:
The process was to select N candidate moves using the score+rack heuristic. Then play out those moves hundreds or thousands of times to see which candidate performs best. You can vary the depth of the playout to suit your purpose; play two or four moves ahead to get a good idea about point
387:
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.
409:. This is the "exhaustive" architecture, where the program has a different rack evaluation parameter for each of the 3 million possible combinations of 0 to 7 tiles. With the advances in computer power over the last decade, it has become possible to tune such large parameter sets.
412:
The downside of using an exhaustive approach is that Maven lost the ability to vary evaluations as a function of the tiles that remained in the bag. The point is that the exhaustive rack evaluator does not have terms that relate a rack's value to the possible draws from the bag.
489:
in each case. Because there are some situations (e.g., two blanks, stuck-with-Q) that require extra effort, the calculation is performed progressively. That is, Maven expands its analysis first where the decision is close and relevant.
345:
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
495:
One feature of these low-tile situations is that it is very hard to safely prune the list of legal moves. For example, the optimal play is ranked behind more than 50 other moves by the score+rack heuristic more than 1% of the time.
468:
search algorithm is a selective-depth, progressive-widening algorithm that guarantees to find optimal solutions to two-player games when one can compute upper and lower bounds on the values of each position.
477:
very quick, because the tree from the previous search is still largely valid. Repeated use of this policy will progressively identify errors, starting with the smallest (and presumably most likely) errors.
429:
had studied
Scrabble by playing out individual positions dozens of times, and tabulating results. He suggested that with Maven's speed, it should be possible to automate that process in overnight runs.
442:
candidates so that more successful candidates receive more effort. It was also helpful to control the racks so that all candidate moves were sampled against the same, unbiased distribution.
325:
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
300:
player, created by Brian
Sheppard in 1986. It is no longer commercially available, the rights having been bought by Hasbro in 1996. It has been used in official licensed
342:
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.
131:
492:
In a PEG-2 it is normally not possible to exhaustively examine all move sequences, so Maven goes as far as it can in the time available.
522:
277:
259:
102:
84:
76:
52:
38:
485:
When only 1 or 2 tiles remain in the bag ("PEG-1" or "PEG-2"), it is possible to perform exhaustive searches of the state space.
453:
Strong play in
Scrabble endgames is much harder than it looks. In theory, endgames are a game of perfect information, so the
391:
Parameter fitting was accomplished by tuning the values to predict the total of future scores. Nowadays this would be called
226:
189:
146:
398:
This rack evaluation design was original to Maven. It was very successful in competing with the human champions of the day.
445:
Analysis of games played by Maven's simulation engine suggest that Maven has surpassed the skill level of human champions.
317:
Maven's gameplay is sub-divided into three phases: The "mid-game" phase, the "pre-endgame" phase, and the "endgame" phase.
161:
392:
168:
554:
405:
Maven has since switched to a completely different architecture, proposed by John O'Laughlin and implemented in
175:
241:
347:
322:
294:
237:
157:
434:
named this process "simulation", though it goes by the name "rollout" in backgammon, and "playout" in Go.
326:
44:
371:
cannot tell the difference. The GADDAG is perhaps twice as fast, but both algorithms are fast enough.)
431:
454:
426:
406:
531:
363:
182:
330:
useful to look more than 2-ply deep, because if one instead looked deeper, e.g. 4-ply, the
535:
548:
120:
359:
336:
457:
algorithm should work. But in practice Alpha Beta works badly on
Scrabble.
461:
optimal strategy for both sides is usually to play one tile on each turn.
138:
438:
differential, or play to the end of the game to measure winning chances.
331:
297:
367:
339:, deeper simulations are unlikely to change the initial evaluation.)
301:
244:. Statements consisting only of original research should be removed.
520:
Sheppard, Brian (2002). "World-championship-caliber
Scrabble".
402:
gradually expanded from the base set of 100 to well over 400.
209:
114:
59:
18:
465:
335:
with very high accuracy in
Scrabble, unlike games such as
473:
Maven can solve endgames that other approaches cannot.
233:
142:
350:to analyze the game tree during the endgame phase.
417:per rack, for about 15 million parameters in all.
8:
147:introducing citations to additional sources
358:Maven has used several algorithms for move
53:Learn how and when to remove these messages
278:Learn how and when to remove this message
260:Learn how and when to remove this message
103:Learn how and when to remove this message
137:Relevant discussion may be found on the
512:
16:Artificial intelligence Scrabble player
384:how many of each remained in the bag.
464:Maven uses a different approach. The
7:
362:, but the one that has stuck is the
75:tone or style may not reflect the
14:
34:This article has multiple issues.
214:
130:relies largely or entirely on a
119:
85:guide to writing better articles
64:
23:
42:or discuss these issues on the
1:
536:10.1016/S0004-3702(01)00166-7
393:Temporal Difference Learning
304:Scrabble games since then.
240:the claims made and adding
571:
425:The great human champion
523:Artificial Intelligence
348:B-star search algorithm
323:Monte Carlo tree search
295:artificial intelligence
481:Exhaustive pre-endgame
327:reinforcement learning
158:"Maven" Scrabble
143:improve this article
455:Alpha-beta pruning
225:possibly contains
555:Scrabble software
288:
287:
280:
270:
269:
262:
227:original research
208:
207:
193:
113:
112:
105:
79:used on Knowledge
77:encyclopedic tone
57:
562:
540:
539:
517:
283:
276:
265:
258:
254:
251:
245:
242:inline citations
218:
217:
210:
203:
200:
194:
192:
151:
123:
115:
108:
101:
97:
94:
88:
87:for suggestions.
83:See Knowledge's
68:
67:
60:
49:
27:
26:
19:
570:
569:
565:
564:
563:
561:
560:
559:
545:
544:
543:
519:
518:
514:
510:
483:
451:
423:
380:was a pattern.
377:
375:Rack evaluation
366:algorithm. The
356:
354:Move generation
315:
310:
284:
273:
272:
271:
266:
255:
249:
246:
231:
219:
215:
204:
198:
195:
152:
150:
136:
124:
109:
98:
92:
89:
82:
73:This article's
69:
65:
28:
24:
17:
12:
11:
5:
568:
566:
558:
557:
547:
546:
542:
541:
511:
509:
506:
482:
479:
450:
447:
432:Brian Sheppard
422:
419:
376:
373:
355:
352:
314:
311:
309:
306:
286:
285:
268:
267:
222:
220:
213:
206:
205:
141:. Please help
127:
125:
118:
111:
110:
72:
70:
63:
58:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
567:
556:
553:
552:
550:
537:
533:
529:
525:
524:
516:
513:
507:
505:
501:
497:
493:
490:
486:
480:
478:
474:
470:
467:
462:
458:
456:
448:
446:
443:
439:
435:
433:
428:
420:
418:
414:
410:
408:
403:
399:
396:
394:
389:
385:
381:
374:
372:
369:
365:
361:
353:
351:
349:
343:
340:
338:
333:
328:
324:
318:
312:
307:
305:
303:
299:
296:
292:
282:
279:
264:
261:
253:
243:
239:
235:
229:
228:
223:This article
221:
212:
211:
202:
191:
188:
184:
181:
177:
174:
170:
167:
163:
160: –
159:
155:
154:Find sources:
148:
144:
140:
134:
133:
132:single source
128:This article
126:
122:
117:
116:
107:
104:
96:
86:
80:
78:
71:
62:
61:
56:
54:
47:
46:
41:
40:
35:
30:
21:
20:
527:
521:
515:
502:
500:assumption.
498:
494:
491:
487:
484:
475:
471:
463:
459:
452:
444:
440:
436:
424:
415:
411:
404:
400:
397:
390:
386:
382:
378:
357:
344:
341:
319:
316:
290:
289:
274:
256:
250:January 2010
247:
224:
199:January 2010
196:
186:
179:
172:
165:
153:
129:
99:
93:January 2010
90:
74:
50:
43:
37:
36:Please help
33:
530:(1–2): 14.
427:Ron Tiekert
313:Game phases
508:References
421:Simulation
360:generation
308:Algorithms
234:improve it
169:newspapers
39:improve it
238:verifying
139:talk page
45:talk page
549:Category
332:variance
298:Scrabble
449:Endgame
407:Quackle
232:Please
183:scholar
368:GADDAG
302:Hasbro
293:is an
185:
178:
171:
164:
156:
291:Maven
190:JSTOR
176:books
364:DAWG
162:news
532:doi
528:134
236:by
145:by
551::
526:.
466:B*
395:.
337:Go
48:.
538:.
534::
281:)
275:(
263:)
257:(
252:)
248:(
230:.
201:)
197:(
187:·
180:·
173:·
166:·
149:.
135:.
106:)
100:(
95:)
91:(
81:.
55:)
51:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
