Scrabble AI

Started by
2 comments, last by vex_helix 20 years, 1 month ago
Hi guys, I want to create a computer play option in my C scrabble game. Are there any good algorithms out there for scrabble? Any suggestions for possible AIs? I am just learning C (after doing Java) and haven''t really done any AI in the past. Thanks for yr help, Helix
Advertisement
Hey. Though I have never writen a Scrabble AI player before, I was interested in doing so at one time and did a little bit of research online about it.

The basic strategy is to try making all possible words in all possible locations on the board on the computers turn, and then scoring each move in terms of the number of points it gets, what scoring tiles it opens up for the other players, and how useful the letters used to make that word are (the idea being to dump your most useless letters to save up and make the 7 letter bingos). This is actually much easier than it sounds if you set up your data structures right. The trick is to save your dictionary of words in memory as a DAWG (I forget what the D stands for, but the AWG is "acyclic word graph") and implement an IsPrefix function that will tell you if a string of characters is a prefix to any longer word in the DAWG.

It''s been a while since I''ve gone through this stuff. If you Google for DAWG you can find some good info. Also try Googling for "Maven" - it''s a hobbyist Scrabble-playing program. You can even find a textfile containing all the words in the Scrabble players dictionary (sorry, I don''t remember where I saw it).

Goodluck!

----------------------------------------
Let be be finale of seem, seems to me.
----------------------------------------

Coding:
http://www.stanford.edu/~jjshed/coding

Miscellany:
http://www.stanford.edu/~jjshed

Shedletsky's Bits: A Blog | ROBLOX | Twitter
Time held me green and dying
Though I sang in my chains like the sea...

You might get some ideas here...
http://www.gtoal.com/wordgames/scrabble.html
It may be a little outside the scope of what you''re doing, but the best Scrabble AI is Maven by Brian Sheppard. There is a fantastic article about it: Sheppard, B. (2002). "World-championship-caliber Srabble." Artificial Intelligence 134: 241-275. You can get the paper in PDF format here http://www.math-info.univ-paris5.fr/~bouzy/ProjetUE3/Scrabble.pdf.

-Kirk

This topic is closed to new replies.

Advertisement