I ran across a game called “Words With Friends” these days on the IPhone. It is very fun to play. After playing several games, being a computer scientist, I automatically think about developing and artificial intelligence program for the game. It is pretty challenging as there are a lot of words, and so many possible combinations to check, and for different directions. I first implemented an exhaustive search, testing every word in the dictionary for every cell. The result was miserable, one hour goes by and the computer only tested 20% of the words.
Admitted I was stomped. There has to be a better way. I have to add heuristics to the search algorithm. So I mapped out an efficient and clear thought process, and implemented it again. This time the results are better, took 10 minutes to go through all the words. Of course, in computer science there are ways to cut processing time with increase in the use of memory. So after a couple hacks, it can run on reasonable times.
Testing the AI against some opponents, I kept on improving it with some simple strategies such as sacrificing points to reduce exposure to Double or Triple risks. I think the AI is pretty good now. I must say it was a fun project.
Click Here to use my Words With Friends Cheat