Scrabble AI

[vex_helix]

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

[Jez]

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...

[vex_helix]

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?

[manofsteel972]

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

___________________________________________
____|____|____|__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.

[Jez]

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

[manofsteel972]

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.

[vex_helix]

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

[joed]

Seems easiest to take regular words:

tree
car
house

say this is the board:

........
..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

[Jez]

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.

[vex_helix]

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.