Scrabble AI

This is a discussion on Scrabble AI within the C Programming forums, part of the General Programming Boards category; I want to implement a computer play option with AI in my Scrabble game. I came across Appel-Jacobsen Move Generation, ...

  1. #1
    Registered User
    Join Date
    Mar 2004
    Posts
    16

    Scrabble AI

    I want to implement a computer play option with AI in my Scrabble game. I came across Appel-Jacobsen Move Generation, Maven and Gordon Move but they were to advanced for me as a beginner to write. Where can I find these algorithm ready to be used? Also what's the easiest way to just make up a word in Scrabble neglecting best word or anything? Or if u guys are familiar with anyother high score playing algorithm I am all year.

    Helix

  2. #2
    Jez
    Jez is offline
    The C-er
    Join Date
    Mar 2004
    Posts
    192
    That sounds like very advanced stuff. I don't know about scrabble algorithms as such, but I guess it's similar to doing a crossword. And I do know (part of) a crossword algorithm which may help.

    Actually, I'm blagging it. I did read something years ago, and I'm making it up as I go along.

    You can go out and buy such things as crossword dictionaries, (can be used for anagrams too) these have entries arranged in orders of their individual letters. Perhaps an example would help.

    Heres my dictionary. To keep it simple it only consists of the words:

    aardvark
    badger
    dog
    stoat
    toast
    weasel

    in the crossword dictionary it would be listed thus:

    aaadkrrv -> aardvark
    abdegr -> badger
    aeelsw -> weasel
    aostt -> stoat, toast
    dgo -> dog

    I've got a feeling that the shorter words are listed first, too. I expect you can research that.

    You might find such a dictionary on the web. Or you could download an ordinary dictionary and sort it with another C program.

    So you arrange the tiles on your rack into alphabetical order and then search the modified dictionary for the longest word that fits.

    Somehow you have to factor in the tiles that have already been laid too.

    I guess that would be a starting point though. Don't ask me for any code as I'm just learning C myself...

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    16
    Wow. That's actually not bad. Really simple to design and find words thx!!

    But, here's the thing that's bothering me. How do I play new new letters on the existing words? Isn't the algorithm u defined only for making new WORDS from your tiles? What about using only your letters to form new words on the board?

  4. #4
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317

    I am not sure if this would work.

    Just an idea. If you have letters on the board both vertical and horizontal you can take each row of letters or column

    Code:
    ___________________________________________
    ____|____|____|__A__|____|____|__R__|____|
                      A    D    O    R     E
    list of letters: deo
    adeor

    And use the distance between them as an offset
    so you first add the letters a and r to your list of letters and then after you get a list of words that contain all the letters load each word into an array one at a time then scann until you find the first letter on the board here which is an A counting each letter from the beginning of the word. Then get the distance from the edge of the board to A in the row and compare that with the count of letters to make sure you have enough room. Then add the distance between A and R to the pointer and test for R in the word to see if the word will match the spacing of letters. Then take the difference between R and the edge of the board and see if that is greater then the distance beween R and the end of the word so you know there is enough room.
    Last edited by manofsteel972; 03-20-2004 at 01:02 AM.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  5. #5
    Jez
    Jez is offline
    The C-er
    Join Date
    Mar 2004
    Posts
    192
    That sounds like a plan manofsteel972. The devil is in the detail though.

    I know what happens next, you spend months figuring out all the bugs and wrinkles, and at the end you have an algorithm that works.

    Then you realise it's the same as Appel-Jacobsen Move Generation (or whatever), the only difference is that you understand your way - because it's so simple. Then you write a learned thesis on it - which nobody can understand!

    Most problems aren't difficult once you understand them

  6. #6
    Registered User manofsteel972's Avatar
    Join Date
    Mar 2004
    Posts
    317

    Appel Who?

    Well I am not much for algorithm theory or anything. I am not even taking any college classes. I am just figuring out stuff on my own. I just took a stab at the problem. I have no idea if it will work. I am flattered by your response though. Maybe I should take some classes.
    "Knowledge is proud that she knows so much; Wisdom is humble that she knows no more."
    -- Cowper

    Operating Systems=Slackware Linux 9.1,Windows 98/Xp
    Compilers=gcc 3.2.3, Visual C++ 6.0, DevC++(Mingw)

    You may teach a person from now until doom's day, but that person will only know what he learns himself.

    Now I know what doesn't work.

    A problem is understood by solving it, not by pondering it.

    For a bit of humor check out xkcd web comic http://xkcd.com/235/

  7. #7
    Registered User
    Join Date
    Mar 2004
    Posts
    16

    Cool Brainstorming some ideas for scrabble AI

    Hi,

    I have successfully completed the human vs. human part for my program (some minor bugs remain ). I couldn't have done it without you guys. I greatly appreciate your help.

    I think I am ready to work the computer AI part. I really don't care about efficiency and how long it takes to run... just wanna create some high scoring words.. thinking probably elimination is the way to go for a beginner.

    One of the members, Jez, mentioned to use crossword/jumble like search to find new words. But that search will only find words in the rack. In scrabble you have to use atleast one tile from the board to create a new word. Using more tiles from the board may or may not be beneficial. Is there a way through elimination to check all letters on the board, 1 by 1, against your tiles to find the highest scoring word possible? You can always create two words with a single tile.. but lets not worry about.. probably too advanced for me.

    Helix

  8. #8
    Registered User joed's Avatar
    Join Date
    Mar 2004
    Posts
    59
    Seems easiest to take regular words:

    tree
    car
    house

    say this is the board:

    Code:
    ........
    ..h....
    ..i.....
    ........
    The computer hits the 'h' and then looks left and right. There are a few possible patterns to match:
    a.) 2-3-letter words ending in 'h'.
    b.) 2-5 letter words beginning with 'h'.
    c.) 3-6 letter words with 'h' for second letter.

    I think I got them all. Now that it's all broken down, testing the possibilities "should" be easier. If you don't find anything horizontally, then it can test vertically. When multiples are found, it just picks the highest scoring word to use.

    It gets more complicated when crossing more letters, but as long as the "possibility tester" does a good job of breaking things down, matching the patterns is easier.

    The other caveats: Game has to test to make sure placed words don't produce illegal words in other places. Human player is limited to words in the dictionary, obviously.

    AI is hard, I once wrote a "GO" game without researching it very much. I did all the gfx, and nearly the entire game and then found out that making a computer play "GO" is one of the most challenging computer science problems and was way over my head. I still learned some stuff, but "check yourself before you wreck yourself" was the resounding theme in my head for awhile.

    -Joe

  9. #9
    Jez
    Jez is offline
    The C-er
    Join Date
    Mar 2004
    Posts
    192

    AI is hard, I once wrote a "GO" game without researching it very much. I did all the gfx, and nearly the entire game and then found out that making a computer play "GO" is one of the most challenging computer science problems and was way over my head. I still learned some stuff, but "check yourself before you wreck yourself" was the resounding theme in my head for awhile.
    Yes, I would say scrabble is in the same league as Go when it comes to AI. But since you've got this far, vex_helix, I would stick with it. Your idea for elimination could be worth considering.

    I've got an idea for a way forward, I'll give it some thought and post it back.

  10. #10
    Registered User
    Join Date
    Mar 2004
    Posts
    16
    Quote Originally Posted by Jez
    Yes, I would say scrabble is in the same league as Go when it comes to AI. But since you've got this far, vex_helix, I would stick with it. Your idea for elimination could be worth considering.

    I've got an idea for a way forward, I'll give it some thought and post it back.
    Thx jez. Making words by integrating yr tiles and tiles on board is a little troublesome.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple space combat AI
    By VirtualAce in forum Game Programming
    Replies: 5
    Last Post: 01-05-2009, 11:54 PM
  2. chess ai contest
    By Raven Arkadon in forum Contests Board
    Replies: 7
    Last Post: 07-09-2005, 06:38 AM
  3. AI Contest Proposal
    By MadCow257 in forum Contests Board
    Replies: 4
    Last Post: 03-13-2005, 02:27 PM
  4. Game Design Topic #1 - AI Behavior
    By TechWins in forum Game Programming
    Replies: 13
    Last Post: 10-11-2002, 10:35 AM
  5. Technique of all board-like games?
    By Nutshell in forum Game Programming
    Replies: 28
    Last Post: 04-24-2002, 08:19 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21