All,
I have been rather distant from the Monastery for a year or more. My daughters are growing up and other hobbies consume more and more time. During a recent episode of The Big Bang Theory, I had an opportunity to be introduced to Words With Friends. This of course made me want to write an algorithm to play optimally which in turn made me think of the monks.

I am not interested in writing yet another cheater - there are plenty of them out there. I am interested in writing a platform where two computer algorithms can duel for bragging rights. There are plenty of strategies one might consider:

If I built the platform, would anyone be interested in writing a player? If so, what ideas do you have? If you are not interested in writing a player, what strategies do you think would work best (so I can steal them for my player)?

Update: I should clarify. If you are interested in writing a player, I am soliciting ideas for how game play should be done. In other words, a web interface, being able to play the same game twice (taking turns with who goes first), etc.

Cheers - L~R

Comment on Words With Friends Algorithm
Re: Words With Friends Algorithm
by zentara (Archbishop) on Nov 13, 2012 at 12:28 UTC
Re: Words With Friends Algorithm
by ColonelPanic (Friar) on Nov 13, 2012 at 13:49 UTC

    This is a significant AI problem. The generic solution would be running simulated future game outcomes for each potential move to see which one maximizes your probable point advantage. However, this will get expensive very quickly--each move involves scanning thousands of possible word/location combinations, and your opponents' tiles are not known. It would get very interesting if you restrict the amount of time the player can run and the size of the code.

    My suggestions:

    • Think hard about a good set of rules. To keep this fun, you want to require the players to be fairly simple, and you don't want the games to take forever.
    • To start out, just make a game module and post it here, along with a simplistic player that will give people a test opponent. Then people can download it and run it themselves with different players. If the idea draws interest, you can set up something more complex, like a web interface.


    • When's the last time you used duct tape on a duct? --Larry Wall
Re: Words With Friends Algorithm
by eyepopslikeamosquito (Canon) on Nov 13, 2012 at 18:56 UTC

      Currently the strongest Scrabble-playing program in the world is Quackle, which uses simulation as mentioned by ColonelPanic. It generally only simulates a few plies into the future, which is almost always good enough for a game like Scrabble with a significant random element. Also, Quackle's board is completely configurable so it should be able to play Words With Friends as well. The code is open-source and may be instructive. I don't know if this helps but I hope so!

      -- Mike

      --
      XML::Simpler does not require XML::Parser or a SAX parser. It does require File::Slurp.
      -- grantm, perldoc XML::Simpler

Re: Words With Friends Algorithm
by ambrus (Abbot) on Dec 22, 2012 at 23:32 UTC

    This is to note that tom7's Scribble is a similar word game that also allows for similar strategy questions. That game is cooperative, not competitive, that is, players try to help get the highest shared score instead of defeat each other.