Can computers play scrabble?

[Captain Kremmen]

I have recently started playing a computer version of scrabble.
It is Ubisoft's scrabble interactive 2005.
Let me rush to tell you that it came free with a Sunday Newspaper, in case anyone should think me sad enough to buy it. (I am, but it was free anyway)


It's an entertaining game, but my impression is that computers must be very poor at the game.

According to this game, I am now supposedly a grandmaster, and in order to beat me the computer has to cheat by messing with the tile selection. This seems to be the method that it uses, rather than increasing its vocabulary.
As you advance against a particular level, it gives you poorer and poorer tiles.

It would be flattering to think that I am at world champion level after a few weeks, but it is more probable that computers cannot cope with more than basic levels of play, given the size of the board and the number of possibilities available.

Anyone else played this game.
Any other observations on scrabble welcome.

[Captain Kremmen]

Clearly no-one has played this computer game.
No wonder it was free.


If for some reason I had to be a genius at a game, I would prefer it to be something useful like poker.

[Enmos]

I don't see why not.
How hard could it be to program it ?

[Steve100]

I don't see why not.
How hard could it be to program it ?

It's not just about making the best words, it's about board covering tactics, that's why.

[Enmos]

It's not just about making the best words, it's about board covering tactics, that's why.

Is that fundamentally different than chess tactics ?

[Steve100]

Is that fundamentally different than chess tactics ?

I don't know. But what I can make a good guess at is that people have not been developing Scrabble computers anywhere near as much as chess ones.

[Enmos]

I don't know. But what I can make a good guess at is that people have not been developing Scrabble computers anywhere near as much as chess ones.

True.

[Fraggle Rocker]

I don't know. But what I can make a good guess at is that people have not been developing Scrabble computers anywhere near as much as chess ones.I agree. As a former software geek, Scrabble looks like an easy game to program. All you need is a Scrabble-approved unabridged word list (which will easily fit in today's memory chips) and that puts you in the league with the world's best human players, who can't possibly know every legal word. Sure there's some strategy but you don't have to read ahead more than a couple of moves.

Chess requires reading ahead as far as you can go in the allotted time. And doing some incredibly complex position analyses to figure out which sequence of moves is the most advantageous. I think these days chess programmers have to actually analyze the game in a different way from human players. I doubt that this is the case with Scrabble.

People were working on chess programs back in my day in the 1960s, so they've had quite a head start on the other games. Scrabble wouldn't have been practical then; the word list would probably not fit on a 1960s-era hard disk, much less directly in RAM.

Go programming has also been very slow to develop. In the 1960s when I learned the game a Taiwanese businessman offered a huge award to the first program that could merely understand the rules: Making only legal moves, not putting itself in atari, recognizing a two-eye shape, filling in the dame at the end of the game, and passing when it was obviously over. That didn't happen until around 1990, and it's only been the last few years that programs can play go at my (rather modest) level and don't need me to give them a six-stone handicap.

Twenty years ago a chess computer from the mall could beat me, and today they play at the grandmaster level.

[rpenner]

8 hours of programming time should suffice to make a Scrabble game that is capable of making the greedy-best-possible move, maintain a pool of letters, challenge player-entered words and playing to exhaustion. Since Scrabble is a game of incomplete knowledge, a smart game that reasons about what moves its opponent could make would probably take 12 more hours to implement a metric like my_move - E(max(their_moves)) + E(my_next_move) - E(max(their_next_move)) and multithreaded logic to terminate calculations in a reasonable time. And for production purposes you probably want to spend about 8 hours on optimization (indexing the dictionary, improving the is_legal_move check) and an unknown amount of time for UI design (handling of blank tiles, "advice" like "aw, with those letters you could have played here for double word score....").

(Estimates are for a low-level language like C or C++ with no pre-existing Scrabble- or Game- specific programming. There may in fact be off-the-shelf shortcuts that will greatly speed the backend development. In high-level languages, there almost certainly are such shortcuts.)

[Captain Kremmen]

I've read a few reviews of the ds version, and a common comment is that this version of computer scrabble is not hard for a good player to beat.
Most people seem to enjoy the gameplay though.

I suppose the point is that ubisoft are in the entertainment business, and a game that thrashed you all the time wouldn't be entertaining.

It wouldn't be too difficult for a computer to look for every available "bingo", where a player plays all his 7 tiles at once, and rack up an unbeatable score in a few goes.
It would be frustrating though, as all your tactics and effort would be outperformed by what in a human would be cheating. ie, resorting to a computer anagram engine.


There do seem to be difficulties for programmers, however:
World-championship-caliber Scrabble. By Brian Sheppard. In Artificial Intelligence, January 2002
"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 uses a mathematical method called the b* algorithm.
In computer science, B* (pronounced "B star") is a best-first, graph search algorithm that finds the least-cost path from a given initial node to one goal node (out of one or more possible goals). First published by Hans Berliner in 1979, it is related to the A* search algorithm. It stores intervals for nodes of the tree as opposed to single point-valued estimates. Then, leaf nodes of the tree can be searched until one of the top level nodes has an interval which is clearly "best." (from wiki)

[Captain Kremmen]

The problem is possibly the task of creating a game with good gameplay which still can beat very good players.
I don't think that they've managed it yet.
And if they did so, it would be only a small percentage of people who would want that version of the game.
Those people would probably be better off playing other humans.

[Pete]

Quackle

[Captain Kremmen]

That is definitely not a word.
Is it?

[Pete]

Sorry.
Quackle (http://web.mit.edu/jasonkb/www/quackle/)

[funkstar]

8 hours of programming time should suffice to make a Scrabble game that is capable of making the greedy-best-possible move, maintain a pool of letters, challenge player-entered words and playing to exhaustion. Since Scrabble is a game of incomplete knowledge, a smart game that reasons about what moves its opponent could make would probably take 12 more hours to implement a metric like my_move - E(max(their_moves)) + E(my_next_move) - E(max(their_next_move)) and multithreaded logic to terminate calculations in a reasonable time. And for production purposes you probably want to spend about 8 hours on optimization (indexing the dictionary, improving the is_legal_move check) and an unknown amount of time for UI design (handling of blank tiles, "advice" like "aw, with those letters you could have played here for double word score....").

(Estimates are for a low-level language like C or C++ with no pre-existing Scrabble- or Game- specific programming. There may in fact be off-the-shelf shortcuts that will greatly speed the backend development. In high-level languages, there almost certainly are such shortcuts.)
I think those estimates are too low. Finding the possible moves looks to be quite a computation-intensive task, and estimating the opponents next move (or just possible moves) even more so. I also don't think multi-threading will get you much (a thread/process pr. core, but other than that just do breadth-first.)


I'm extremely tempted to actually try and program a scrabble-playing engine, now...

[Fraggle Rocker]

8 hours of programming time should suffice to make a Scrabble game that is capable of making the greedy-best-possible move, maintain a pool of letters, challenge player-entered words and playing to exhaustion.Devoting eight hours to this project would certainly be the state of the art in commercial and consumer software development, and you'd end up with a program about as reliable and user-friendly as Word or Outlook. Games are engineered rather than hacked and are thus built to much higher standards. Last time I looked at the statistics, the only software that came close to the quality of games was created by the Israeli military.

[domesticated om]

To be honest, I don't believe an AI is needed. Scrabble is simply one part luck, and one part pattern. Your application would simply run a script, and pass through a gauntlet of arguments to reveal the highest scoring move. The program doesn't need to use any strategy.

[Harro]

Yeah I would have thought the computer would have to be programed to deliberatly not always take the best option or highest scroring option to give the player a fighting chance.

[Fraggle Rocker]

To be honest, I don't believe an AI is needed. Scrabble is simply one part luck, and one part pattern. Your application would simply run a script, and pass through a gauntlet of arguments to reveal the highest scoring move. The program doesn't need to use any strategy.You try not to leave your opponent the opportunity to reach a Triple Word Score on his next move. If you are, you have to balance the payoff from your own move against that risk, and you might decide to settle for your second-best move. Similarly you might try to block it by sticking an X in front of it.Yeah I would have thought the computer would have to be programed to deliberatly not always take the best option or highest scroring option to give the player a fighting chance.I wouldn't be so certain that a top-notch human player can't play almost as well as a computer. It might take ten or twenty games to determine that the computer wins a little more often.

[S.A.M.]

iPhone has a great scrabble apps, but its easy to beat

[iceaura]

I do not share the confidence of some here that software capable of beating the best human players consistently would be all that easy to write.

Even more difficult would be software capable of outperforming the best human players in matched contests with lesser (or even random) human players.

The elements that some take as simplifying - the luck factor, the risk assessment, etc, - add considerable difficulty to a machine approach, IMHO.

The game is normally played at a fairly low level. High levels of play seem possible, to me, and involve the sort of programming difficulties that have proven unexpectedly troublesome routinely.

[Fraggle Rocker]

I do not share the confidence of some here that software capable of beating the best human players consistently would be all that easy to write. Even more difficult would be software capable of outperforming the best human players in matched contests with lesser (or even random) human players. The elements that some take as simplifying - the luck factor, the risk assessment, etc, - add considerable difficulty to a machine approach, IMHO.I don't believe that luck is an important factor in Scrabble. The game consists of enough draws that the law of averages rules. It's a rare game that the strongest player at the table does not win due to a once-in-a-lifetime run of bad draws. I suppose if everyone is an expert, then in any one game luck might determine the winner. But in the long run they would probably come out pretty close. If you kept a running score like bridge, you might find that after ten games or a hundred games, the strongest players' scores differ by a very small percentage.The game is normally played at a fairly low level. High levels of play seem possible. . . .Oh dude you'd better believe it! There are a lot of people who take this game VERY seriously. If you think you're hot because you always slaughter your whole family at Thanksgiving, or even perhaps were the champion of your college dormitory, you may still have no idea what top-end Scrabble is like.. . . . and involve the sort of programming difficulties that have proven unexpectedly troublesome routinely.Still, it's primarily a matter of:Good memory. Knowing a lot of words. Especially the two-letter words, all the words that have Q with no U, the words with Z in an unusual position, etc. Good eye. Spotting the exceptional opportunities, such as making multiple words for more points. Speed. Serious games are timed. You have to be able to do all that before your timer runs out.Computers excel at every one of these key tasks.

[Captain Kremmen]

Sorry.
Quackle (http://web.mit.edu/jasonkb/www/quackle/)

Have downloaded this, and on its highest level it plays a VERY strong game.
Too strong for me I think.
I'll try it on the lower levels and let you know if I can beat any.

It's a wonder one of the major manufacturers haven't brought out a version of it. It is definitely a more canny player than the ubisoft version, but could do with some bells and whistles.

You have to set it up as a standard scrabble board yourself, but that only takes a few minutes.
Nice link Pete !

[Captain Kremmen]

No way can I beat quackle, even on its lowest level.

rpenner is correct.
It is possible to make a computer version of scrabble which sees every possible play. It's called quackle.

If a person can beat it on its championship level, they will only do so through advanced tactical play.
It sees everything. Try it.

I think I'll go back to the ubisoft version, where I am playing a world champion called Terry.
I beat the sap nearly every time.

[one_raven]

It's an entertaining game, but my impression is that computers must be very poor at the game.

I think it's more likely that you just got a poorly written game.

[domesticated om]

You try not to leave your opponent the opportunity to reach a Triple Word Score on his next move. If you are, you have to balance the payoff from your own move against that risk, and you might decide to settle for your second-best move. Similarly you might try to block it by sticking an X in front of it.

Availability of "word score" tiles would also be written into the script in terms of being situations which merit specific actions, but it still wouldn't be strategy or require any decision making on the computer's part. It would simply be another "if - then" statement passed prior to placing the word.

Every situation you could run into with scrabble can be prioritized and nested into the script. Things like availability of word score tiles, multiple words created by placement of single words, rapid disposal of "X" and "Q", etc etc

Highest priority would be placing all 7 letters from tray
Elseif triple/double score is in range
Elseif current collection contains "X", or "Q" (with special case "Q" & "U")
Elseif space is available on board due to word containing an "S"
Elseif...........


So on and so forth. Assuming it doesn't trigger any of the elseifs then it ends with "place highest scoring word"

[Captain Kremmen]

Highest priority would be placing all 7 letters from tray



Quackle does this about every third or fourth play.

The ubisoft version is definitely dumbed down for entertainment value.
I think they have got the mix just about right.

Playing against quackle is like playing against big blue at chess.
Not very entertaining unless you are a grandmaster.

Club level players use quackle to analyse their games and see if they could have done better than they did.

If you have a set of tiles that looks very promising for a seven letter play, with a good spread of vowels and consonants, quackle is quite capable of instantly finding 10 or more ways of playing out those tiles whereas you may take 10 minutes to find just one.
With one such selection, I took 5 minutes to find a "bingo".
Quackle had over forty of them.

[Pete]

Recently on xkcd (http://www.xkcd.com)..
http://imgs.xkcd.com/comics/scrabble.png
What's the next best play on this set? (No fair if you've already seen the subtext!)

[Spud Emperor]

I don't believe that luck is an important factor in Scrabble.

I have to disagree on this one.
Spud Empress and I go through phases of playing.
We're evenly matched, we have different strengths and weaknesses.
Over time we would be close to 50/50 wins and losses.
Some games, one of us never gets going, never gets a chance, barely gets a decent tile or a chance to score heavily, gets stuck with six vowels for five turns, shit like that. Luck seems fairly important to me. There are of course, plenty of games where the luck is even and a good, tight game ensues but the luck can certainly run.

[RubiksMaster]

Every situation you could run into with scrabble can be prioritized and nested into the script. Things like availability of word score tiles, multiple words created by placement of single words, rapid disposal of "X" and "Q", etc etc

Highest priority would be placing all 7 letters from tray
Elseif triple/double score is in range
Elseif current collection contains "X", or "Q" (with special case "Q" & "U")
Elseif space is available on board due to word containing an "S"
Elseif...........


So on and so forth. Assuming it doesn't trigger any of the elseifs then it ends with "place highest scoring word"
What you call a script is actually a pretty complex algorithm. It might seem simple on the surface but I bet that algorithm grows way more complicated when you try to implement it. It's due to the fact that each word can be placed in multiple locations, and you have to consider not only the tiles in your rack, but the tiles already on the board. A low-scoring word placed over a double word score might score lower than some words played over normal grid squares. This is especially true when you consider adjacencies, and the fact that you can form multiple words with very few tile placements, depending on the words already in play. Your hierarchy of decisions starts to break down.

If you think you can implement a good scrabble player with a simple script, I would love to see it, but I think it's much more complex.

[Varda]

I'd make it as a self-teaching program that improves its strategy at every match, then it would become more difficult every time you play.