Thought I'd join in with Blog Post Week?
This:
http://www.xkcd.com/1002/
was interesting.
I think that the continuum presented here, from Easy to Hard, doesn't tell the whole story.
For example, glancing at this chart gives the impression that Scrabble has more chance of moving into the [SOLVED - computers can play perfectly] category than has chess. Scrabble is the next candidate for solving, as it were.
Except that you can't solve Scrabble. You can give a computer a game in progress, seven tiles and a dictionary and ask it to find you the highest possible score, and it will, quite easily, and will use this ability to thrash any human player.
But what happens if you get two of these highest-score-machines to play each other? Obviously, the result is a toss-up, 50-50, depending on what letters they each get.
You can tip the odds in favour of your machine by telling it to do certain things in certain situations. To play the percentages. Rather than always maximising its own score, you can tell it to maximise its own score to a certain extent while also minimising the potential for the opponent to score points. Don't put an I directly below a triple-letter square when they might conceivably have a Q, for example. (
http://en.wikipedia.org/wiki/Qi)
It's not theoretically impossible that a "solution" exists for Scrabble to the extent that, for any possible position, there is one single move that has the highest probability of leading to victory. It's probably impossible to
find that solution, because there would be no way of verifying that our machine's strategy would beat every other conceivable strategy. But even assuming it is possible, the complexity of Scrabble - and hence, the amount of calculating we'd have to do before we have the solution - is orders of magnitude of orders of magnitude (that wasn't a typo) greater than that of chess. There are more possible Scrabble positions than chess positions by a factor of 10 to the power Jesus Christ.
So do the top Scrabble-playing computers have a greater advantage, relative to humans, than the top chess-playing computers? Yes. But is chess closer to being in the SOLVED category than is Scrabble? Undoubtedly.
