undefined | Better HN

0 pointsjollyjerry14y ago0 comments

This reminds me of the documentary "Wordplay" about competitive crossword puzzle players. Without a formal proof, my guess is that scrabble is faster to solve that a hard crossword puzzle for a computer. It's amazing that the human mind can stitch together patterns like these and internalize that in a meaningful way. A cool extension of this project would be to write a scrabble tool that generates arbitrary strategies that would be useful for a human player. So instead of generating the best play for a move, the program would recognize that "when the board is like X, then try and use strategy Y"

Awesome project @zephod!

0 comments

3 comments · 1 top-level

shaggyfrog14y ago· 2 in thread

It depends what you mean by solve. Scrabble, as a two-player game, has a significant branching factor compounded by the fact that the tile drawing makes it both a stochastic game as well as one with hidden information. Maven http://en.wikipedia.org/wiki/Maven_(Scrabble) is an AI that can play Scrabble, and it's good, but it's certainly not "solved".

On the other hand, crossword puzzles are single-player games that use natural language wordplay to create a challenge. Some AI work has been done in this field, which can use a Web search engine (like Google) to try and determine the answer to each clue based on the clue (as well as any candidate words/letters already filled in). The hard part is understanding the clue. Look to systems like IBM's Watson to see how those kinds of problems can be solved.

"Solution" in a single player game, like a crossword puzzle, is solved in exactly one way: when all the rows and columns are filled with legal words (usually -- unless the author rigged it to allow clues to have multiple solutions, like the election day crossword in the NYT in 1996). A "solution" in a two-player game is when, no matter what move you make, your opponent knows perfect play. For example, checkers is solved: http://en.wikipedia.org/wiki/Chinook_(draughts_player)

zem14y ago

quackle [http://people.csail.mit.edu/jasonkb/quackle/] is an open-source scrabble ai that can currently play on par with all but the very best human players. which is not the same thing as scrabble being "solved" of course, but it does bode well for the state of the art.

shaggyfrog14y ago

I am pretty sure Maven was playing at the same level circa 2001, so not surprised to hear other AIs are doing just as well in 2011.

I guess it's kind of like chess: it's almost impossible to beat a computer, so it's effectively solved. Except when they play each other :)

j / k navigate · click thread line to collapse