The first step was to build a program that allows humans to play Scrabble. I’m going to try to be as non-technical as possible, but I want to also try to cover some interesting details. Now that I’ve explained how WordSmith works, I’m going to explain how the algorithm was actually designed. This means a clever player can outmaneuver WordSmith even though WordSmith never fails to recognize the highest-scoring word. In technical terms, ignoring the timeout feature, WordSmith is statically-perfect, but not dynamically-perfect. Similarly, playing long words opens up more possible countermoves than defensive, compact playing. Leaving a triple-word score spot open is dangerous, but WordSmith is oblivious to this misstep. This omits some of the obvious rules of thumbs that human players actually use. Blanks and high-point letters (Q, Z, X and J) are incredibly valuable, so if WordSmith can’t find a good use for it in the first turn it finds one, it will wait. The only heuristic I’ve tested that has made it into the final build of WordSmith is one that is conservative when playing good tiles. I had started developing this capacity in the program, but there’s always the possibility of better heuristics, so this can give human players a strategic advantage. A heuristic is a fancy CS way of saying “rule of thumb”, meaning a simplified rule that will tend to increase performance when applied. Scrabble is a lot of luck and often the technically best word isn’t considerably higher scoring than one an advanced player would pick. I’ve beaten it roughly 10% of the time in the matches I’ve played. This doesn’t mean WordSmith is impossible to beat, however. I’ve built the AI to give up after 15 seconds (which is why the blue bar doesn’t always finish), but at least on my computer it does retrieve the highest possible scoring word over 95% of the time. What it is actually doing is trying every combination of letters it can play and keeping track of which moves are both valid and score enough points. When playing the AI, you’ll notice a blue progress bar as the AI “thinks”. It evaluates this not only based on how many points a particular move gives, but also by using heuristics to avoid technically higher-scoring moves which are probably detrimental in the long-run. WordSmith plays by searching the board for all possible tile placements and then chooses the best one. It was a fun project, not only because I enjoy Scrabble, but because the problem was interesting enough to require clever algorithmic tricks, but not so tricky I couldn’t do it part-time over three weeks while on vacation in Paris. Not only because then I could play a game I enjoy without needing a ready opponent, but also because a strong computer opponent would teach me more about the game. Even a perfect Scrabble player may still lose due to unfortunate letters or an unlikely countermove.īecause of this, I wanted to see if I could make a computer that plays Scrabble. Unlike chess, AI-researchers’ favorite game, luck and outside knowledge play a role. The game requires a mixture of vocabulary, strategy, pattern-recognition and luck. If CS or Scrabble don’t interest you at all, feel free to skip this article, as I’ll be back next week with my normal writing. While it’s not tremendously complex, it does show a little of the computer science knowledge I picked up through the MIT Challenge. Visit the download page to try it out.įor the rest of this article, I’m going to explain how the program works. I’ve made the project free and open-source, so anyone can play it and also see how it works. The result was WordSmith, a program that lets you play the game Scrabble against a computer. When I finished, I wanted to work on a small and fun project that would test some of the things I learned. While the challenge was exciting and educational, the tight deadline didn’t give me any time for extracurricular projects.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |