Brian Sheppard talks about Maven
My first Maven dates from 1983. I had a summer job as an intern at a
technology company, but my boss was ill the entire summer. They literally
told me to keep busy until he came back, which was expected to occur "next
week." Idle hands make devil's work, you know.
Maven's first version was better than anything that had been published in
the computer literature, but it was nothing special. Figure 1200 rating or
so. It didn't have the full OSPD (Official Scrabble Player's Dictionary)
In 1986 I wrote a version that had the full OSPD. (Or as close as I could
come using manual text entry. In truth, the dictionary wasn't fully accurate
until 4 years later.) I invented a method of prioritizing moves that
superseded the methods employed by human masters. That version was probably
a little better than human champions.
In the years after 1986, Maven got various upgrades to its move evaluation
logic. One of the first improvements was the Perfect level, but computers
of that era weren't fast enough to execute the process in real time. So,
while the Perfect level was implemented early, it didn't appear in actual
games until 1996. In 1990, Maven got an endgame player, which handled
positions where the bag was empty (so Maven could calculate which tiles the
opponent has, and plan accordingly). Even though this improved Maven by over
10 points per game, Maven still was only a little better than human
champions. Humans learned how to evaluate moves by watching what Maven does,
so they improved a lot between 1986 and 1995.
1996 was the first year that Maven was able to play the Perfect level at
over-the-board time controls. This marked the advent of genuinely
superhuman play by a computer program. By 1998, Maven had very good methods
of controlling CPU utilization so that it could play at interactive speeds.
For this product, the Perfect level learned how to share the CPU with a user
interface. This is the first commercial product that has a Perfect level.
The Perfect level plays very, very well. It is hard to know exactly how well
because there is nothing to compare it to. I have some statistical evidence
that suggests that its errors total under 1 point per game. Maybe it isn't
perfect, but it's pretty close. It beats human champions about 60% of the
time. Maven's Champion level is probably stronger than human champions, but
the edge isn't particularly large; maybe a few percent.
One of the challenges of programming Maven was to produce realistic play at
the weak levels. Maven has a common-word dictionary that it employs at
levels below Champion, and move generation strategies that result in low
average scores without resorting to frequent exchanges. Such methods keep
Maven's play entertaining down to the lowest levels.
Maven can play Scrabble in 4 languages at present, or 5 if you consider the
dialect of English used in the United Kingdom to be a different language.
:-) While Maven is likely to need occasional upgrades, extensions, and bug
fixes, most of the work now and in the future is in three areas. First, I
would like to simplify Maven's development model. As you can imagine, a code
base that has undergone 3 platform changes, 3 language changes, 5 compiler
upgrades, and 3 complete rewrites over a 20-year time frame will need a
certain amount of cleanup. Second, I want to create features that make
expert thought processes accessible to aspiring human users (like Hint,
Shuffle, and Definitions from this product). Third, I will often use Maven
to explore or test various theories about the game.
The entire code base is surprisingly small; maybe 10,000 lines of code if I
trim it down to essentials.
Brian