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.
:O The concept of trying to make a completed scrabble is mind boggling!
ReplyDeleteAre the humans in question meant to be the best in that game? Otherwise the computer could win at anything in the same way that fish can't cut down trees and so the tree would win?
"Blog Post Week" - implying this is just for a week? Nuh uh.
ReplyDeleteNever really thought about it before, but yes, obviously Scrabble is harder to figure out because of the unknown and random elements - hence the need to try to minimise your opponents' potential for scoring, because you can't know for sure if they have a Q or not, or if they will draw one from the bag soon, or if you will.
In fact, surely there can be no perfect strategy in Scrabble, because no strategy can compensate for the possibility that you just have terrible luck drawing tiles from the bag? No matter how good a computer you are, you still can't get a high score with no consonants.
Whereas chess, the pieces always move the same, you can see all of them, there's no random element, so it's purely down to calculating power. I suppose that's why I prefer it.
Like I say, you can't solve Scrabble. A computer that knows the best move in every possible position may still lose individual games, but over a sufficiently large number of games would beat a sub-optimal machine more than 50% of the time.
ReplyDeleteLiffy: be on YouTube? So we can all make a collab channel or something?
Oh, you're on YouTube already.
ReplyDeleteSubscribed to yo' ass!
Hahahahahahahahahaha yeah I have a youtube account. Although I don't use it much and I'm hideously embarrassed by it all. I might upload other things but also maybe not :P
ReplyDelete