Scrabble

(a subtopic of Games & Puzzles)

Contents Good Places to Start Readings Online Related Web Sites Related Pages More Readings

Good Places to Start Robot learns to play dirty Scrabble. New Scientist (January 16, 2007: Issue 2586, page 23; subscription req'd). "Beating people at Scrabble is already no contest for computer programs, which can easily memorise entire dictionaries. Now a Scrabble-playing program has gone one better by playing dirty. Developed by Eyal Amir and Mark Richards at the University of Illinois, Urbana-Champaign, the program is able to predict which letter tiles other players hold, and use this information to choose moves which block a high-scoring word that an opponent might otherwise have played. ... [Amir] presented the bot at a conference on artificial intelligence in Hyderabad, India this week."

• Also see: Winning computer program created by graduate student beats world champion Scrabble player.By Kristen Sackley. DailyIllini.com (February 28, 2007). "[Mark] Richards, a graduate student, took a class with computer science Professor Eyal Amir, called Decision-Making Under Uncertainty (CS 598), and by doing a project on probability, he became interested in the strategy behind the game of Scrabble."I read about a previous Scrabble program that had been written, that had been 10 to 15 years ago," Richards said. He said he wanted to look into making a computer program better at winning the game of Scrabble by creating code that was better able to predict the letters the opponent had. ... Richards came up with the idea of opponent modeling which is actually already used in many variations today, Amir said. ... Inference Player ended up being such a successful program that it beat the computer world champion of Scrabble by an average of five points per game."

Computer Playing of Scrabble. By Kenneth Tam. 1998. A detailed description of a senior undergraduate computer science programming project at the University of Waterloo, Ontario, Canada.

Readings Online

Computers, Games and the Real World. By Matthew L. Ginsberg. Scientific American (special issue: Exploring Intelligence - Winter 1998). "More than just competing with people, game-playing machines complement human thinking by offering alternative methods to solving problems."

Do not pass Go. Computers can beat the world's best chess players but have yet to master other classic games like Go. By David Levy. The Guardian (October 24, 2002). "Ever since Garry Kasparov's sensational 1997 loss to the IBM chess monster Deep Blue, the chess world has thirsted for revenge. But the first opportunity ended in failure in Bahrain on Saturday, when Kasparov's former pupil and successor as World Champion, Vladimir Kramnik, could only draw an 8-game match against one of the world's leading chess engines, Fritz. But this was just the latest in a long series of human versus computer encounters that illustrate the inexorable march of artificial intelligence (AI). It's a story that began at a Dartmouth University conference in 1956, when several of the founding fathers of AI defined the goals of that infant science. One of them was to create a computer program that could defeat the world chess champion. Success would, those scientists believed, reach to the very core of human intellectual endeavour. By the early 1990s, due in no small part to the successes achieved in computer chess, the interest of the AI community had spread to many other games of skill, including backgammon, bridge, Go and Scrabble. Where exactly are we now in this fascinating struggle?"

A Gamut of Games. By Jonathan Schaeffer. AI Magazine 22(3): Fall 2001, 29-46. "The first documented Scrabble program appears to have been written by Stuart Shapiro and Howard Smith and was published in 1977 (Shapiro and Smith 1977). In the 1980s, a number of Scrabble programming efforts emerged, and by the end of the decade, it was apparent that these programs were strong players. ... At the first Computer Olympiad in 1989, the Scrabble winner was CRABwritten by Andrew Appel, Guy Jacobson, and Graeme Thomas (Leavy and Beal 1989). Second was TYLERwritten by Alan Frank. Subsequent Olympiads saw the emergence of TSP (Jim Homan), which edged out TYLER in the second and third Olympiads. All these programs were very good and quite possibly strong enough to be a serious test for the best players in the world. Part of their success was a result of the fast, compact Scrabble move generator developed by Andrew Appel (Appel and Jacobson 1988). Steven Gordon (1994) subsequently developed a move generator that was twice as fast but used five times as much storage. Brian Sheppard began working on a Scrabble program in 1983 and started developing MAVEN in 1986. ... In July 1998, MAVEN played another exhibition match against Adam Logan (at AAAI-98), scoring nine wins to five."

World-championship-caliber Scrabble. By Brian Sheppard. In Artificial Intelligence, January 2002 (Volume: 134, Issue: 1-2). Abstract excerpt: "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."

Mastering Scrabble. By Brian Sheppard. This is one of the essays from the collection: Playing with AI. IEEE Intelligent Systems, November/December 1999.

Related Web Sites

Quackle, an open source project available from SourceForge.com. "Quackle is a world-class crossword game artificial intelligence and analysis tool. It includes a move generator, simulator, and Qt-based user interface and can be used with any board layout, alphabet, lexicon, and tile distribution." Project administrators are Jason Katz-Brown and John O'Laughlin. (Also see theirQuackle page with competition results and more!)

Scrabble - source code, a resource of the wordgame-programmers@egroups.com mailing list. "There are no downloadable executables here and no interactive web games. What we have on our archive are only the sources of computer programs for academic study."

Related AI Topics Pages

• Overview
• Bridge
• Checkers
• Chess
• Crossword Puzzles
• Go
• Othello
• Poker
• Traveling Salesperson & NP-Complete Problems
• More Games & Puzzles

More Readings

Appel, A. W. and G. J. Jacobson. 1988. The World's Fastest Scrabble Program. Communications of the ACM 31(5): 572-578+.

Bramer, M. A., editor. 1983. Computer Game-Playing: Theory and Practice. Chichester, UK: Ellis Horwood. See the essays on Scrabble: A Scrabble Crossword Game-Playing Program by S. C. Shapiro; and, A Competitive Scrabble Program by P. J. Turcan.