I'm doing a simple scrabble game and I want to be able to play against the computer. The problem is that I can't figure out how to let the computer check all possible combinations of words :(

Any information about this topic is appreciated.
Posted on 2003-08-17 09:46:10 by Delight
What about checking against a huge dictionary of words? Maybe you would want to encrypt it so that the player would not peek into this dictionary :grin:
Posted on 2003-08-17 10:18:14 by roticv
Oops, a large piece of my message is gone (strange?!). Anyway, I already have a large textfile with all words in the dictionary, and what I'm searching for is an algorithm that finds the combination of seven given letters that give most points on the scrabble board.
Posted on 2003-08-17 10:24:47 by Delight
; calculate score for a word place on the board at X,Y

iScoreWord PROC pWord:DWORD, X:DWORD, Y:DWORD
iScoreWord ENDP ; EAX = value of word


; find the most valuable word including the letter at possition X,Y
iFindWord PROC pPlayer:DWORD, pWord:DWORD, X:DWORD, Y:DWORD
; search horizontal and vertical
iFindWord ENDP ; EAX = value of word, pWord = word

; note: might be better to retain a list of solutions allowing the difficulty
; of the game to be adjusted by selecting a non-optimal solution, or to
; program heuristics that work across multiple turns?

; transverse the board to find most valuable word
SolveBoard PROC pPlayer:DWORD
; since all words must connect to an existing letter, transverse the board
; by only checking each square where there is a letter tile.
WHILE There_are_more_letters_on_the_board
invoke iFindWord
ENDW
SolveBoard ENDP
Posted on 2003-08-17 11:42:03 by bitRAKE
i don't know how efficient this would be, but i think this might work as a solution (for English scrabble):

Sort comp's hand alphabetically.
Since all (English) words contain vowels (or at least a semi-vowel), segregate the vowels.
Count # of occurences of each vowel. In your word database, break it down into a similar grouping.

e.g. (in the db)
Group of all words /w 1 A, 0 Es, 0 Is, 0 Os, 0 Us.
Group of all words /w 2 A, 0 Es, 0 Is, 0 Os, 0 Us.
Group of all words /w 3 A, 0 Es, 0 Is, 0 Os, 0 Us.
etc.

Say the comp's holding is AAIBCFR
Then you can check the DB for the word list of words /w 1 A, 2 As, 2 As and an I, 0 As and an I, 1 A and an I. This should decrease the character search space.

The following is another method i thought could efficiently reduce the completely-brute-force search space. i don't see how a binary tree might be used to make the following search more efficient.

Alternately, you could load 4 MMX registers (4x8 bytes = 32 characters) /w the number of each character. Each byte within an 8-byte field contains the occurences of each letter. Using the byte-comparison, you can make sure that there are sufficient characters in the held hand to make the word in the dictionary.

To account for the piece on the table which will be used, you can add one to each hand-byte for comparison. Rough estimates of each compare:

main loop:
4 mmx register loads
4 compares
4 testings of the mmx registers

a conservative estimate would be 50 to 100 cycles/word. A one-million word dictionary would thus take a very short amount of time to process on even a modest processor by today's standards.

This should give build a complete list of words which can be formed from the characters in hand. i would expect that a list of no more than a thousand should be formed. Further pruning based on characters laid on the board should reduce the possible playable combinations to about 10-20. Score tests for each word should be easy to perform on this small set.
Posted on 2003-08-17 23:44:56 by jademtech
jademtech, in your algorithm how would you handle the cases where mulitple pieces from the board are going to be used?

Look at this Scrabble board: http://www.braunston.com/kevin/scrabble/wsc.html
Posted on 2003-08-18 02:01:48 by bitRAKE
Thanks guys, I think I have enough information to get started.
Posted on 2003-08-18 04:04:51 by Delight

jademtech, in your algorithm how would you handle the cases where mulitple pieces from the board are going to be used?

Look at this Scrabble board: http://www.braunston.com/kevin/scrabble/wsc.html


hm... you're right. i guess it could try word placement with each possible location on the board, but keeping a list of letter combinations that have been checked.

Brain muddled :) :confused:
Posted on 2003-08-18 16:28:37 by jademtech

Brain muddled :) :confused:
:) Well, this just means pruning the dictionary with the players hand does not help find an optimal word. You have some good ideas, but before going any deeper I would need some code or to write out the problem: listing all the parameters to ensure the correct game environment is created with the algorithm.

I've played Scrabble hundreds of times, but I'm not well versed is all the rules. I do know there is a set number of each letter availible; and there are different score markers on the board for both letter score multipliers and word score multipliers. My dad worked for a guy that played in Scrabble tournaments - I remember looking at his Scrabble dictionary: "Wow, all these words are valid!?" I like playing with a topic, and then we all vote if the word is valid in the topic - this is really cool.
Posted on 2003-08-18 19:58:19 by bitRAKE