I have gotten an assignment in school to make Scrabble in C++-builder. The problem is you''re supposed to able to play against the computer and the teacher said that he would like the comuter player to have some AI(well sort of). Making the computer play the game isn''t a problem but how do I make it at least a little bit intelligent? The only way I can think of to make the computer play is to make it search through a dictionary and lay the word with the highest score, that''s the best strategy or is it??????

Ok Jon, first of all I''m very tired, so I wonder what Scrabble is. Then I wonder what school you go to, cause I live in Sweden to and want to know what schools gives you that kind of assignments. Now I''m going to try and answer you''re question.

...Wait a minute, I need to know what scrabble is first, won''t I?

Scrabble==Alfapet

I''ll write this in English so everyone else doesn''t feel left out. I attend Kth in Haninge, 120-p Data

Aha, ok

...hmmm...

yes, I think making a dictionary is one of the best choises.

That was a hard task, sorry I can''t help you anymore, cause I''m not to familiar with the game

(Excuse my spelling)

Using a dictionary seems to be the best choices for this project. You could introduce multiple difficulty levels based on how many words the program uses in the dictionary.

Gary

have maybe three intelligence levels with different score goals (easy: 5-10 pts, moderate: 5-20 pts, hard: 5-maximum pts). when its the computers turn, have it go thru the dictionary file and find a word. if it is in the given point bracket, play it, if it is a small word, see if it can find a better one. if it is on easy and it can only find a word that scores 50 points, have it pass (get new tiles or whatever). sorry that i can''t supply any code. there''s an open source scrabble game (Xscrabble i believe) that you could look at for ideas.

-destroid



"can't waste the day when the night brings a hearse"

Another thought is to have the AI rank lower words that are sub-strings of other words. i.e. rank lower cow because moocow is also a word.

I''ve thought of those solutions already but thanks anyway. I''ve already got a dictionary stored as a database and plan to use those ideas to set the difficulty to an easier level but at the hardest level (when the computer knows all the words) how can I make it even more difficult? Is it possible for the computer to lay its tiles so that it blocks the human player? Or is the ultimate strategy to score as many points as possible?

Don''t forget you''ve also got double and triple letter/word multipliers to take into account, although I''m sure you know the rules.

The basic problem you''ve got here is that of performing a state space search, i.e. using the current world state and a constrained number of possible moves to create a new world state.
Unfortunately you''re missing one of the important components of a state space search, the answer, which makes it less constrained and more computationally expensive to find the best solution.
This is because, however good your best answer to-date is, there may always be another way to place the pieces which would get a better answer.

To guarentee a perfect answer you would have to work your way through every possible permutation of letter orderings in every possible position on the board.
Seeing as scrabble is not a graphically intensive game this may be possible without day long moves from the AI.
If you got this to work you could then easily change difficulty levels by having a gate for the maximum number of permutations tried by the AI.
So how to perform the state space search?
There''s probably more than one way of doing this, but here''s my £0.02.

For every word in the dictionary
Disregard if it cannot be made by the current letters on the board combined with the letters in your hand (or on that little wooden seat thing)
Disregard if there are any letters on the board and none of those letters are in the word (because you have to place the word on an already existing word, unless it''s the begining of the game).
Find the letters which are not in your hand (and so _have_ to be on the board in order)
Find all instances on the board of those letters in order which
a) Are not already in a complete instantiation of the word b) Are not inside a word with non-viable letters
c) Can fit the remainder of the letters in the word without going off the board.
For all these instances, place the letters down and see what other words they touch, if they create any invalid words, disregard.
For all valid formations of this word, find the number of points and store if it is the highest number of points found.
Take the overall best score found.

You can make the AI stupider (because this will find the perfect answer you''re going to have to) by ignoring a percentage of words given matches in the dictionary and a percentage of the possible positions found on the board for valid answers.

Alternatively try every premutation of placing the letters on the board in any position and check for validity (but you might need Deep Blue for that one)

Hope I helped.

Mike

First off, I would suggest looking at a few of the scrabble fan sites on the web. Since scrabble is played for serious competition (and money!), I highly suspect that you will be able to find some strategy pointers (for humans) on those boards.

Sine I''m just a recreational player, I''ll give you a few ideas:

(1) Make sure the computer tries to find words in good spots, not just randomly. Precompute the number of good potential word locations that go through nice bonus tiles (2xW,3xW,2xL,3xL, etc..) Look for words in that set first.
Also, if you have a high letter, make sure you trie for words where that specific letter will be on the 2xL,3xL tiles.

(2) Make sure the computer tries to make multiple words in one pass. This is how good players do so well. If you can make 2 or 3 words in one play, at least one of which is fairly long, your going to do well. Even if you play perfectly, but ignore this facet, I suspect a good human player would cream your program.

(3) Make sure you don''t leave any glaring openings for the opponent after your turn. Like playing a word that leaves a 3xW wide open..I''d suggest computing the number of good spots again after you''ve laid your word down. If the ease of scoring has increased, you''ve given your opponent an opportunity.

This leads itself to chess style expressions -- create a tree of these positions, having the computer search n-ply on each move. At each position, try to play the highest possible combination of words while leaving the environment target poor for the next player. Then, guess what the player might play, how the computer could react, etc etc.. Its all min/max, alpha-pruning, etc.

Anyway, all this sounds pretty hard for a class project :}


Notwen