Winning computer program created by graduate student beats world champion Scrabble player

ME Online

Strategy is used in almost every aspect of today's business world as well as simple things that take place in daily life. Although people may not always realize they use strategy in many ways, they often do, even when it comes to something as fun as a board game. And Mark Richards was interested in exactly that.

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 started using a Scrabble open-source program called Quackle to begin his work on opponent modeling. "Open source" means that there is some code available and anyone can use it, add to it or change it to create new programs.

"There are a lot of open source software projects out there and the nice thing about it is they encourage this kind of community. Anyone who is interested in Scrabble can work on it and make this program better," Richards said.

Richards explained that the biggest problem with most Scrabble programs is that they don't take into account what the opponent has.

"What normal programs do is they generate all the possible plays and they rank them not only according to how many points they score on the current turn but on the quality of the letters they leave behind," he said. "But what they often fail to take into consideration is what does my opponent have."

This is where Richards came up with the idea of opponent modeling which is actually already used in many variations today, Amir said.

Amir said that people are concerned with what their opponent is doing in the stock market, online bidding and even when buying houses.

"Usually in different competitive situations you try to understand what your opponent has," Amir said. "When you want to buy something on eBay you make some assumptions about (what) other people will pay for this and what is the probability that people will buy this."

Amir said that although this type of technology is being used in other applications today it is only in its infancy and there is much room for advancement, which is just what Richards said he plans to do.

In the program, the computer narrows down the possibilities that their opponent has by assuming that the tiles left on an opponent's rack after they make a move do not include any letters that could have been used to form higher-scoring words, Richards said. Amir helped Richards develop strategies for making a better program and leading him in the right direction of what ideas would actually work.

Richards said he was really only interested in developing his Scrabble program, Inference Player, but that he may work on other applications using the thought process of his program.

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. Richards is being noticed in programming publications for his success with the program and said he hopes to market the program publicly for all avid Scrabble gamers.