Quackle and game complexity

[Martin Gardner]

I don't know if you're all familiar with Quackle. In fact I know you're not. Basically it's a Scrabble program largely inspired by Maven that in theory comes up with the best move every time. It's probably the best Scrabble program in the world, I admit, I just get slightly annoyed when people quote Quackle and thing it always gives the best play, Q.E.D. I admit it's brilliant and very likely the best ever, but it's not flawless either.

Basically it was the chess thread that made me think of it. I'm sure Maven was inspired by those sort of chess programs, because it basically uses 'brute force' to come up with its solutions. It proposes about 10 moves and then simulates the game after each one of these moves, to see what the final scores are. Obviously Scrabble is a lot more complicated than chess. Scrabble uses a 15-by-15 board, whereas for chess its 8-by-8. And there are 27 'letters' for Scrabble (a-to-z and the blank) whereas in chess there are just 7.

I suppose ideally, you'd just work out every single combination of moves following each move and that would give you a pretty convincing answer. But that's an enormous number! So it just simulates until you stop it, and it tells you which is the best at that point.

I think one famous example of this going 'a bit wrong' was when using Maven, someone changed OE on their first rack. And because he didn't change the letters in alphabetical order, it simulated CHANGE OE against CHANGE EO and oddly enough, one of them turned out to be quite a lot better than the other! Indeed Pete Finley repeated it, and also found that one of them was a fair bit better than the other.

Also, it assumes perfect play, so if it picks out a bingo it will always play it, while a human player might miss it. I remember the first Can-Am Scrabble book used the word 'super-optimal' - a play that might induce an error from the opponent, even though Quackle or Maven doesn't rate it as the best play.

[Jon O'Neill]

Obviously Scrabble is a lot more complicated than chess. Scrabble uses a 15-by-15 board, whereas for chess its 8-by-8. And there are 27 'letters' for Scrabble (a-to-z and the blank) whereas in chess there are just 7.

Never. From a computational perspective, Scrabble is nothing compared to chess. Am I right, computer geeks??

[Charlie Reams]

Obviously Scrabble is a lot more complicated than chess. Scrabble uses a 15-by-15 board, whereas for chess its 8-by-8. And there are 27 'letters' for Scrabble (a-to-z and the blank) whereas in chess there are just 7.

Never. From a computational perspective, Scrabble is nothing compared to chess. Am I right, computer geeks??

Computationally, Scrabble is much more "difficult" than chess. What really bites you in Scrabble is 1) you have a ridiculous number of moves available on every turn, if you consider every possible change, every 1 tile play and so on; 2) the random element, which means you can't "look ahead" in anything like the way that you can in chess; 3) the hidden information (your opponent knows his rack which you don't, and vice versa, and he knows you don't know, etc.), which again has no analogue in chess.

The main reason that computer Scrabble programs are currently better than humans is that they know every word and spot every available play. In tactical terms humans are probably still better.[citation needed] Compare that to chess, where obviously a human has no problem generating all possible moves; the difficult bit is deciding which one to play.

Playing "perfect" Scrabble is pretty much impossible (quantum computing notwithstanding.) Perfect chess is tough but could happen in our lifetimes.

Martin makes a good point about super-optimality, but the same phenomenon exists in chess. A computer may see that one move leads theoretically to a loss, while another leads theoretically to a draw, and hence the optimal play is obviously the latter, assuming best player from the opponent. However a "super-optimal" player may observe that the winning sequence from the first move is extremely difficult to notice and execute (maybe hundreds of moves long), so that a human player will probably miss it; and, if the other outcomes of that move are all wins for the computer, then arguably that move is superior. However I've used words like "human" and "probably" here, which are not well-defined, so it's questionable whether this idea of super-optimality is really meaningful.

Oh yes, and Quackle is awesome, but anyone that says it is perfect needs to look more carefully at the sort of assumptions (hi Kirk!) and heuristics it uses. However it does play optimally in the endgame (when there are no tiles left in the bag), which is pretty cool.

[Jon O'Neill]

Fair enough, but doesn't point 2 on your list go in favour of Chess being more difficult, in that you have to calculate a load of moves ahead, with the number of possibilities exponentially increasing, to work out the best play?

[Charlie Reams]

Fair enough, but doesn't point 2 on your list go in favour of Chess being more difficult, in that you have to calculate a load of moves ahead, with the number of possibilities exponentially increasing, to work out the best play?

For optimal play you need to do that in Scrabble too, then weight it according to how likely the different tile draws are, but obviously that's just stupidly difficult to compute. When Quackle does a "simulation", it randomly picks a few of the possible racks that can be drawn (a pathetically small number compared to the space of all possible racks) and follows them through to compute an approximate average, which works most of the time, but is a long way from optimal.

[Martin Gardner]

Well, with Scrabble you have no idea what letters are going to come later, other than not the ones that are already on the board. There's no equivalent of this in chess. You can't suddenly have an unexpected piece appear. As pointed out, the only time there's absolute certainty is when there are no more letters to drawn, so whichever letters you don't have and aren't on the board, your opponent has them! Although I've heard stories of players "dropping" a letter on the floor or on their lap. Alright two stories come to mind, there.

[Gary Male]

Well, with Scrabble you have no idea what letters are going to come later, other than not the ones that are already on the board. There's no equivalent of this in chess. You can't suddenly have an unexpected piece appear.

Oh I don't know. In "How to Cheat at Chess: Everything You Always Wanted to Know About Chess, but Were Afraid to Ask" Bill Hartson recounts the (hopefully not apocryphal) tale of a crowded chess club where a player absent-mindedly grabbed a rook off the adjoining board to give check. His opponent applauded the move as he hadn't seen it coming. Much later the players at the other board wondered where the missing rook was, and reckoned it must have been lost in the complex midgame.

The discrpenecy between Change EO and Change OE is explained by not having a big enough sample, or at least not using the same random seed to start each search in the small sample.

[Martin Gardner]

Well, with Scrabble you have no idea what letters are going to come later, other than not the ones that are already on the board. There's no equivalent of this in chess. You can't suddenly have an unexpected piece appear. As pointed out, the only time there's absolute certainty is when there are no more letters to drawn, so whichever letters you don't have and aren't on the board, your opponent has them! Although I've heard stories of players "dropping" a letter on the floor or on their lap. Alright two stories come to mind, there.

I might as well tell'em now. One is something I read on the Internet, about Joyce Cansfield losing a game by a couple of points and then they found a letter on the floor. The second one is a bit more sinister. When I was in Vaujany, in France we had a tournament and one player accused another of concealing a letter or letters in his hand when he was going to pick out new letters, and doing an "illegal exchange". To illustrate, say he's got AEHNQST, he can play HA but then he conceals the Q in his hand and picks up three new letters. She didn't inform the director - unfortunately with the dominance of duplicate in French-speaking countries, they have an appalling grasp of the rules. Even at World Championship level.

[Gavin Chipper]

I would have thought that it would be much "easier" to make a brilliant Scrabble program than a chess one. With Scrabble, while one might like to look ahead, surely the here and now has much more weight than it does in a game of chess. The program could just look at what would score the best in that one round and perhaps also look one or two rounds ahead, and would already be pretty decent. But with chess, you don't score points for an individual move so any decent program would be compelled to look quite far ahead to be any good.

While an "optimal" Scrabble program might be more of a challenge, I would have thought that by cutting a lot of corners you'd lose very little when compared to a chess program. Would this be right?

[Charlie Reams]

I would have thought that it would be much "easier" to make a brilliant Scrabble program than a chess one. With Scrabble, while one might like to look ahead, surely the here and now has much more weight than it does in a game of chess. The program could just look at what would score the best in that one round and perhaps also look one or two rounds ahead, and would already be pretty decent. But with chess, you don't score points for an individual move so any decent program would be compelled to look quite far ahead to be any good.

While an "optimal" Scrabble program might be more of a challenge, I would have thought that by cutting a lot of corners you'd lose very little when compared to a chess program. Would this be right?

Yep.

[Martin Gardner]

I would have thought that it would be much "easier" to make a brilliant Scrabble program than a chess one. With Scrabble, while one might like to look ahead, surely the here and now has much more weight than it does in a game of chess. The program could just look at what would score the best in that one round and perhaps also look one or two rounds ahead, and would already be pretty decent. But with chess, you don't score points for an individual move so any decent program would be compelled to look quite far ahead to be any good.

While an "optimal" Scrabble program might be more of a challenge, I would have thought that by cutting a lot of corners you'd lose very little when compared to a chess program. Would this be right?

We tend to talk about "score and leave"

Score - pretty self-explanatory
Leave - the letters left after the word you've played, so QVH is not very good, but ERS is good because you've got a very good chance of getting a 50 point bonus next turn. Quackle for instance, given the rack AAEINRT on the first move will do CHANGE A and keep RETAIN and wait for a bonus letter (virtually every letter, apart from Q, V, X and Y, oh and another A).

[Adam Dexter]

And there are 27 'letters' for Scrabble (a-to-z and the blank) whereas in chess there are just 7.

You missed out letters bcdefghijklmnpqrsuvwxy...