5 ms·

The article claims there are just shy of 200,000 scrabble words. Why would it be so complex? The key is to use all 7 of your letters. The subset of valid words

by thret 12y ago

The article claims there are just shy of 200,000 scrabble words. Why would it be so complex? The key is to use all 7 of your letters. The subset of valid words containing all 7 letters you hold shouldn't be that large, surely the board can be exhaustively searched to fit them?

deleted 12y ago
[deleted]
adrianN 12y ago
You don't have to use all your letters for the same word, and there are strategic considerations regarding which spots you place your words, since that might enable the other player to use the score multiplier tiles for their next move.
vijayr 12y ago
200K words! I wonder how many does an average human know? 5k? 10k?
- taejo 12y ago
  IIRC 15k-20k is usual for monolingual adult speakers of English. Since different languages have different total vocabulary size -- English's is particularly high -- it probably varies quite a bit across languages. I believe bilinguals tend to have a smaller vocabulary in each language, but larger if both are counted. You can estimate your English vocabulary at http://testyourvocab.com/ http://testyourvocab.com/ (BTW, if anybody knows a site that does a similar test for other languages -- particularly German -- I'd be interested).
Strilanc 12y ago
You don't just want good words, you want to position yourself so your next move is also a good word. So you don't just have to iterate over the current board, you have to iterate over all possible upcoming boards. But it's even worse than that! You want to set up your opponent for a bad move, and vice versa, so you're trying to infer each others' tiles from past moves and bluffing starts to matter. So you also have to reason about counterfactual games where your opponent would have done the same thing, meaning you have to care about the entire game tree instead of just the sub-tree you're in... In the general case, solving games involving partial information requires super-exponential time. It's no picnic. (Of course in practice we use approximations, and those can work quite well.)
- thret 12y ago
  Good point regarding setting up for double/triple word scores, however I doubt there is much soul reading or bluffing in scrabble - I think the cost of making a sub-optimal move is too great, you'd need to be very sure that it hurt your opponent even more than yourself. Also although the remaining letters are known, your selection is random. I don't know how you could possibly choose between words to maximize your next move when you don't know what letters you will get?
  - icelancer 12y ago
    > I don't know how you could possibly choose between words to maximize your next move when you don't know what letters you will get? Your selection is random amongst a determined pool of tiles. You can easily maximize your move even if the move is not 100% deterministic. The fact that there is a random factor does not mean strategy is useless. This is trivially true in a lot of cases, but sticking with games: The dealer's concealed (hole) card in Blackjack is not known precisely but by counting cards, you can determine the best play even if the effect is small.

by thret 12y ago

deleted 12y ago

[deleted]

adrianN 12y ago

You don't have to use all your letters for the same word, and there are strategic considerations regarding which spots you place your words, since that might enable the other player to use the score multiplier tiles for their next move.

vijayr 12y ago

200K words! I wonder how many does an average human know? 5k? 10k?

taejo 12y ago
IIRC 15k-20k is usual for monolingual adult speakers of English. Since different languages have different total vocabulary size -- English's is particularly high -- it probably varies quite a bit across languages. I believe bilinguals tend to have a smaller vocabulary in each language, but larger if both are counted. You can estimate your English vocabulary at http://testyourvocab.com/ http://testyourvocab.com/ (BTW, if anybody knows a site that does a similar test for other languages -- particularly German -- I'd be interested).

Strilanc 12y ago

You don't just want good words, you want to position yourself so your next move is also a good word. So you don't just have to iterate over the current board, you have to iterate over all possible upcoming boards. But it's even worse than that! You want to set up your opponent for a bad move, and vice versa, so you're trying to infer each others' tiles from past moves and bluffing starts to matter. So you also have to reason about counterfactual games where your opponent would have done the same thing, meaning you have to care about the entire game tree instead of just the sub-tree you're in... In the general case, solving games involving partial information requires super-exponential time. It's no picnic. (Of course in practice we use approximations, and those can work quite well.)

thret 12y ago
Good point regarding setting up for double/triple word scores, however I doubt there is much soul reading or bluffing in scrabble - I think the cost of making a sub-optimal move is too great, you'd need to be very sure that it hurt your opponent even more than yourself. Also although the remaining letters are known, your selection is random. I don't know how you could possibly choose between words to maximize your next move when you don't know what letters you will get?
- icelancer 12y ago
  > I don't know how you could possibly choose between words to maximize your next move when you don't know what letters you will get? Your selection is random amongst a determined pool of tiles. You can easily maximize your move even if the move is not 100% deterministic. The fact that there is a random factor does not mean strategy is useless. This is trivially true in a lot of cases, but sticking with games: The dealer's concealed (hole) card in Blackjack is not known precisely but by counting cards, you can determine the best play even if the effect is small.