World-championship-caliber Scrabble☆☆SCRABBLE® is a registered trademark. All intellectual property rights in and to the game are owned in the USA by Hasbro Inc., in Canada by Hasbro Canada Corporation, and throughout the rest of the world by J.W. Spear & Sons Limited of Maidenhead, Berkshire, England, a subsidiary of Mattel Inc.
Artificial IntelligencePublished 1 January 2002
Brian Sheppard
Citations124
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
MAVEN combines a selective move generator, simulations of likely game scenarios, and the B* algorithm to produce a world-championship-caliber Scrabble-playing program.
Abstract
Computer Scrabble programs have achieved a level of performance that exceeds that of the strongest human players. Maven was the first program to demonstrate this against human opposition. Scrabble is a game of imperfect information with a large branching factor. The techniques successfully applied in two-player games such as chess do not work here. Maven combines a selective move generator, simulations of likely game scenarios, and the B∗ algorithm to produce a world-championship-caliber Scrabble-playing program.
Keywords
Computer ScienceEconomics, Econometrics and FinanceSocial Sciences
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
Machine LearningLearning to Predict by the Methods of Temporal Differences
3,894 Citations1988Richard S. Sutton
This article introduces a class of incremental learning procedures specialized for prediction-that is, for using past experience with an incompletely known system to predict its future behavior, and proves their convergence and optimality for special cases and relate them to supervised-learning methods.
Machine LearningLearning to predict by the methods of temporal differences
2,758 Citations1988Richard S. Sutton
Communications of the ACMTemporal difference learning and TD-Gammon
1,485 Citations1995Gerald Tesauro
The domain of complex board games such as Go, chess, checkers, Othello, and backgammon has been widely regarded as an ideal testing ground for exploring a variety of concepts and approaches in artificial intelligence and machine learning.
Artificial IntelligenceThe challenge of poker
271 Citations2002Darse Billings, Aaron Davidson +2 more
The design considerations and architecture of the poker program Poki are described, which is a program capable of playing reasonably strong poker, but there remains considerable research to be done to play at world-class level.
arXiv (Cornell University)On-line Policy Improvement using Monte-Carlo Search
210 Citations2025Gerald Tesauro, Gregory R. Galperin
A Monte-Carlo simulation algorithm for real-time policy improvement of an adaptive controller and results are reported for a wide variety of initial policies, ranging from a random policy to TD-Gammon, an extremely strong multi-layer neural network.
Artificial IntelligenceThe B∗ tree search algorithm: A best-first proof procedure
188 Citations1979Hans Berliner
The algorithm, which is named B*, finds a proof that an arc at the root of a search tree is better than any other by attempting to find both the best arc atThe root and the simplest proof, in best-first fashion.
IEEE Transactions on Pattern Analysis and Machine IntelligenceExpected-outcome: a general model of static evaluation
128 Citations1990Bruce Abramson
Overall, the expected-outcome model of two-player games is shown to be precise, accurate, easily estimable, efficiently calculable, and domain-independent.
GIB: Steps Toward an Expert-Level Bridge-Playing Program
110 Citations1999Matthew L. Ginsberg
GIB, the first bridge-playing program to approach the level of a human expert, is described and the results of experiments comparing GIB to both human opponents and other programs are presented.
Communications of the ACMThe world's fastest Scrabble program
74 Citations1988Andrew W. Appel, Guy Jacobson
An efficient backtracking algorithm makes possible a very fast program to play the SCRABBLE® Brand Crossword Game.
Research Showcase @ Carnegie Mellon University (Carnegie Mellon University)The B* tree search algorithm : a best-first proof procedure
51 Citations2018Berliner
DSpace@MIT (Massachusetts Institute of Technology)ON PLAYING WELL IN A SUM OF GAMES
19 Citations1985L. Yedwab
This thesis describes how Berliner''s B* search algorithm can be effectively combined with the approximate solutions to speed up the search for an optimal solution.
Software Practice and ExperienceA faster scrabble move generation algorithm
19 Citations1994Steven A. Gordon
A faster algorithm that uses a GADDAG, a finite automaton that avoids the non‐deterministic prefix generation of the DAWG algorithm by encoding a bidirectional path starting from each letter of each word in the lexicon.
A Scrabble Crossword Game-Playing Program
17 Citations1988Stuart C. Shapiro, Howard R. Smith
A program that plays the SCRABBLE Crossword Game has oeen designed and implemented in SIMULA 67 on a DECSystem-10 and in Pascal on a CYBER 173.
A COMPARISON BETWEEN PROBABILISTIC SEARCH AND WEIGHTED HEURISTICS IN A GAME WITH INCOMPLETE INFORMATION
8 Citations1993Steven A. Gordon
This paper compares the effectiveness of weighted heuristic and probabilistic search approaches for the game of Scrabble.