Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Words With Friends Algorithm

by Limbic~Region (Chancellor)
on Nov 12, 2012 at 18:24 UTC ( #1003487=perlmeditation: print w/ replies, xml ) Need Help??

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:

  • Saving high value letters for premium squares
  • Avoiding moves that open up premium squares to your opponent
  • Considering which tiles remain
  • Intentionally opening premium squares to your oponent which will in turn open even higher premium squares to you
  • Determining the best place to pass or swap tiles
  • Keeping a proper balance of vowels and consonants in your rack
  • etc

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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://1003487]
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (7)
As of 2014-12-21 21:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (108 votes), past polls