HARD SCRABBLE

Dick Pountain/15 November 2006/13:47/Idealog 148

Most professions have their own dirty secret, skeleton in closet, what people nowadays like to call the "elephant in the room". For doctors it might be the widespread prescription of placebos (let's leave euthanasia aside); for lawyers it's defending people they believe to be guilty; for the IT industry it's the fact that most progress in PC hardware design is actually driven by game playing. At this professional magazine we have regular debates about how relevant 3D graphics performance is when reviewing laptops, but in the end we know we have to review what people want to buy. I'm not such a curmudgeon as to object to this fact: it's impossible not to be impressed by modern £200 graphics cards that easily outperform Silicon Graphics' $100,000 Reality Engine of a decade ago. And in the fullness of time someone, somewhere will find a way to exploit 3D to improve the user-interface in a way so significant that even businessmen can't ignore it (though Vista isn't it, as Microsoft will soon find out).

I'm not a fanatical game player myself, though I did finish both Doom and Quake 1 before becoming bored with the whole genre. However there are two computer-based games to which I'm not ashamed to admit being completely addicted, neither of which requires much 3D performance (and precious little 2D). They are FreeCell and Scrabble. I'm not alone in either addiction: at least one other Real Worlder is hooked on FreeCell (you know who you are), while Scrabble is coming up almost as fast as Poker on the world stage.

I was a little surprised at becoming hooked on FreeCell because I'd always regarded Solitaire as a pointless and staggeringly boring activity, but those four little empty cells transform the game entirely. In regular Solitaire the vast majority of games don't come out whereas in FreeCell almost every game does, but only after a hugely variable number of moves. In fact, as I discovered a few years back, a bunch of mathematicians have not only completely analysed the game but have written a full solver for it which you can get in the freeware program FreeCell Pro from www.solitairelaboratory.com. They discovered that only one deal out of the 8 billion plus possible doesn't come out at all, which means that whenever you lose a game it's because you didn't play it right (unless it was deal 11982, the impossible one), not because of the lay of the cards. This totally transforms the skill required and its addictive nature: mostly I win games at the first try but occasionally I might have to play the same game twice, even four or five times before getting it out.

Many people don't think of Scrabble as a computer game but I love playing it four-handed against three computer opponents. It's a game that computers are devastatingly good at because they can search the whole dictionary in milliseconds before every move, so it's really good practice - I win barely once in five games. However I much prefer to play against the computer than most of my Scrabble-playing human friends, who tend to be obscenely competitive and who know the dictionary of two-letter words by heart (how sad is that? Answer: almost as sad as playing FreeCell). Playing four-handed the winning score is usually just over 200, and the biggest score I've ever had is 290.

That set me to thinking about what is the biggest possible score in Scrabble and to my surprise realised that it's not only a non-trivial question, but actually very difficult indeed. A bit of Googling established that the world's highest Scrabble score to date is 830, by a carpenter named Michael Cresta in Lexington Massachusetts this October. That would square with my four-handed games scoring around 200 per head with evenly-matched competitors. So how would you go about writing a computer program to establish the theoretical maximum score? First of all, is there in fact a maximum? Clearly yes, because the board is of finite size (15x15), there's a finite number of letter tiles (100), and there's a finite number of words in whatever language you're playing in assuming you choose some dictionary as your arbiter. Therefore there exists one (or maybe more) placement of all the letters on the board that cannot be beaten, for a particular language and dictionary.

But how on earth would you go about finding it? Plodding through every possible letter combination might take a while even on a 2GHz dual-core: with 10^318 (26^225) combinations it might take longer than the universe has left to run. Special placings, like putting the highest scoring letters Z, X, Q on Triple Letter Scores, is no better because you're constrained to make real words. Finding the maximum Scrabble score looks to me like a particularly horrendous member of the class of decision problems like map colouring, the knapsack problem, even protein folding, that algorithmicians call 'NP-complete' and which can't be solved in reasonable time. It's almost impossible to think of any opening move better than what you'd do in a real Scrabble game - make the best word you can with your tiles - so the only approach may be just to play trillions of computer v computer games and record the highest score obtained. Even that would take an awful lot of processing power - perhaps some of the spare power to be had from the latest graphics cards (see reviews on p72). Which brings me back to where I came in...