Thread: Scrabble - find all possible plays

  1. #1
    Registered User
    Join Date
    Jun 2004
    Posts
    722

    Scrabble - find all possible plays

    I need extrem and urgent help: I currently developing a scrabble game in prolog, and I need to make the computer play, but I'm completly lost! Don't have the smallest clue how to analyse the board and find a play. This is for a work assignemt to be presented tomorrow, monday, and I'm desperate for help. So I'd like you to post here link to websites where I can find info on these algorithms. Thankx on advance

    EDIT: algorithms to analyse the board and determine valid plays.
    Last edited by xErath; 11-14-2004 at 11:16 AM.

  2. #2
    Mayor of Awesometown Govtcheez's Avatar
    Join Date
    Aug 2001
    Location
    MI
    Posts
    8,823
    Your work is requiring you to present a scrabble program?

    I don't mean to call you a liar, but you're a liar.

  3. #3
    It's full of stars adrianxw's Avatar
    Join Date
    Aug 2001
    Posts
    4,829
    I would have thought a bigger problem would be getting a list of all valid words.
    Wave upon wave of demented avengers march cheerfully out of obscurity unto the dream.

  4. #4
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Liar why??
    The UI is implemented, so as predicats to verify valid plays, a dictionary of about 25k words. Now the big objective of this crap, using by logic methods (prolog, duh!!), is to make the computer play the damn game.
    Oh.. and yes It's homework, but I'm not asking anyone for any source.. Only directions for algorithms.. thank you by your consideration.

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Liar why??
    Because in the span of two posts you completely changed your story.
    This is for a work assignemt
    Oh.. and yes It's homework
    Oh and in response to
    to be presented tomorrow
    Failure to prepare on your part doesn't constute an emergency on my part.

    And again you posted the question on the wrong freaking board!

  6. #6
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Huh! Sorry, may C board is nice for prolog questions...
    Last edited by xErath; 11-14-2004 at 12:22 PM.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > I need extrem and urgent help
    http://www.catb.org/~esr/faqs/smart-...ns.html#urgent

    > Don't have the smallest clue how to analyse the board and find a play.
    Lets see, there's
    - the set of possible moves
    - the set of valid moves (intersects one or more letters already on the board?)
    - the set of all possible words (eg hygmpf)
    - the set of words in the dictionary (eg hello)

    For all the valid words which are valid plays, find the one with the highest score.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > may C board is nice for prolog questions
    Nope - that's what the tech board is for
    Which is where this thread now is

  9. #9
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Well, I admit I've explained my situation in a wrong way.
    The game's interface is up and running. The board and a set of functions relative to it are also implemented.
    The problem is to find valid plays.
    I already have predicates to determine all possible words in the dictionary that can be written with the set of pieces each player has. Then after finding all possible plays choosing the best is very trivial.
    I'd asked you to place here some links where I can find valid info on algorithms.

    And Thantos, it's your decision to help or not. Am I forcing you to anything?

  10. #10
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I'm helping by keeping you honest and letting you know when you screw up.

  11. #11
    Toaster Zach L.'s Avatar
    Join Date
    Aug 2001
    Posts
    2,686
    The underlying logic is fairly simple (at least for a simple algorithm):
    - you know (or can find) the set of intersections (that is, the set of possible continuations on the board)
    -- e.g. ???a??? (where ? is a variable letter) is the 7-letter string with a in the middle (obviously, the case of running a word parallel to another requires some care)
    - you can find the elements in the dictionary that match the patterns you found in the previous step (this could be rather time consuming with a large dictionary)
    - find the intersection of the above set with the set of words that can be made from the players letters (taking into account the fact that the matched letters are already on the board

    It may be a bit time consuming to implement this, though (as would probably any solution)
    The word rap as it applies to music is the result of a peculiar phonological rule which has stripped the word of its initial voiceless velar stop.

  12. #12
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    i though about that, but then I would have for each space in the board to search vertically and horizontaly for matches from size 2 to (what?) 15. time consuming indeed...

  13. #13
    Bob Dole for '08 B0bDole's Avatar
    Join Date
    Sep 2004
    Posts
    618
    >time consuming indeed...

    That's why creating a good algorithm is key to any good program.\

    GLHF
    Hmm

  14. #14
    Bob Dole for '08 B0bDole's Avatar
    Join Date
    Sep 2004
    Posts
    618
    OH, by the way, try google some time.

    http://www.cs.ubc.ca/local/reading/p...ue2/spe880.pdf
    Hmm

  15. #15
    Registered User
    Join Date
    Jun 2004
    Posts
    722
    Thank you!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem building Quake source
    By Silvercord in forum Game Programming
    Replies: 16
    Last Post: 07-11-2010, 09:13 AM
  2. could not find -lwsock32.lib
    By thomas_joyee in forum C++ Programming
    Replies: 8
    Last Post: 07-14-2008, 12:28 PM
  3. How to find O of threads ?
    By jabka in forum C Programming
    Replies: 3
    Last Post: 03-11-2008, 12:25 PM
  4. how do u find 2nd largest number??
    By juancardenas in forum C Programming
    Replies: 8
    Last Post: 02-14-2003, 08:28 AM
  5. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09:28 AM