wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Highest Scrabble Score
        
(Message started by: John_Gaughan on Dec 18^th, 2003, 1:47pm)

Title: Highest Scrabble Score
Post by John_Gaughan on Dec 18^th, 2003, 1:47pm

My wife and I play Scrabble every day. We find it is a fun way to learn more about words (we play with an open dictionary instead of the normal word challenge rules). Me, being the geek that I am, will take an extra five minutes to find a way to put that Z or Q on a double letter score *and* hit the triple word score. In my quest to earn the highest score I can, I asked myself, what is the highest score possible?

Assume:

1. A normal Scrabble board and letters

2. You have access to all letters, i.e. they are all face up and on your letter rack.

3. You can place anywhere from one to seven letters at a time.

4. There is nobody else in the game -- this is solitaire Scrabble.

5. Liberal selection of words. Anything but proper names and abbreviations are fair game, assuming it can be spelled without punctuation. As long as you find the word in a dictionary, no particular one, it is valid. It doesn't have to be the official Scrabble Players' Dictionary.

What is the highest score possible? How would one go about developing an algorithm to calculate this? I imagine my Athlon XP wouldn't be able to crunch these numbers in my lifetime, but I am still curious as to the algorithm that could solve this.

Any ideas?

Title: Re: Highest Scrabble Score
Post by towr on Dec 19^th, 2003, 1:56am

on 12/18/03 at 13:47:57, John_Gaughan wrote:

Assume:
1. A normal Scrabble board and letters

American version? (if so letter frequencies and scores would be appreciated, the board is probably the same I think..)

Quote:

2. You have access to all letters, i.e. they are all face up and on your letter rack.

Blanks as well?

Quote:

What is the highest score possible?

over 1300, I think.. Someone mentioned to me that's the highest recorded in the guinness book of records..

Playing solitair it would probably be best to allways start with small words that can be extended, unless you get plenty of bonus points for laying down 7 letters at once (I don't know what the official rules are, but at home we got 50 points extra if we cleared our letter rack)

Title: Re: Highest Scrabble Score
Post by THUDandBLUNDER on Dec 19^th, 2003, 11:27am

Quote:

...what is the highest score possible?

See http://rec-puzzles.org/sol.pl/competition/games/scrabble

(My highest Scrabble score is 399.)

Title: Re: Highest Scrabble Score
Post by John_Gaughan on Dec 19^th, 2003, 12:57pm

towr:

Yes, the U.S. version (see the U.S. flag to the left? ;-) ) Yes, including blanks, they are part of the tiles in the box.

THUDandBLUNDER:

Thank you for the link, it is a good page. I was thinking more theoretical, not sample games (although they do give a good idea of what is practical).

There are 15 squares to a side, so 225 squares total on the board. There are 100 letter tiles, including blanks. Given the number of obscure two-letter words (including colloquisms, greek letters, symbols of elements from the periodic table, etc), it is not difficult to use any weird leftovers, so it is very practical to assume the player can use all 100 tiles.

100 tiles, 125 unused squares, 225 total. The number of permutations is obviously less than 225!, since some elements in the set are equivalent. Taking into account the frequency of unused tiles, each letter in order, and blanks, we have:

permutations = 225!/(125!9!2!4!12!2!3!2!9!1!1!4!2!6!8!2!1!6!4!6!4!2!2!1!2!1!2!)

permutations = 225!/(125! * 8928874352780446688870400000)

permutations ~= 7.492e195

That is a *very* large number. Assuming a computer can brute force one billion solutions per second, and there is a cluster of 1,024 computers, it will take about 2.320e176 years to compute them all. Assuming that, on average, the solution is found after one-half of the solution space is explored, it will take about 2.900e166 times the age of the universe to find the solution.

Brute-forcing this on my Athlon XP is an option, but a stupid one. That is why I am looking for an algorithm, not the solution.

Title: Re: Highest Scrabble Score
Post by Sir Col on Dec 19^th, 2003, 5:19pm

Greetings John and welcome to the forum.

I found another link that presents the highest score in one turn (mentioned in the link that T&B posted) more explicitly:
http://www.fun-with-words.com/scrabble_1962.html

I know you're after a theoretical maximum, and I'm no scrabble player, but doing research on the internet seems to indicate that no one has found a theoretical maximum. I suspect it is for the reasons that you mentioned: the sheer magnitude of a brute-force search.

It seems that some of the words in the 1962 solution, however, are not in the Official Scrabble Players' Dictionary. This website addresses the theoretical maximum using accepted wordlists, but I don't know how 'official' the maximums are?
http://www.teleport.com/~stevena/scrabble/faqtext.html#Theoretical

With regards algorithms, I guess working backwards would be the most efficient:

Rank maximum lines (utilising double/triple letter/word scores) in descending order
Obtain separate wordlists of optimum word candidates for each line in descending order.

Then in descending order of maximum lines, attempt to place/overlap candidates recursively (in descending order) until no more words can be added.

The challenge would be whether or not the wordlist of maximum candidates really provides the maximum possible score? It could be that starting with a fairly average word on the maximum line leads to the optimum score.

Title: Re: Highest Scrabble Score
Post by John_Gaughan on Dec 20^th, 2003, 12:29am

Despite the staggeringly huge number of possibilities, it is quite possible to narrow the search field down quite a bit. Tiles must be adjacent, which eliminates a large chunk of the possibilities. Certain spaces are favored over others, some of which would never be used ("normal" spaces not close to a score space).

Maximizing score, as any good Scrabble player knows, involves big letters on big spaces -- the Z on the double word score between two triple word scores, then using both triple word scores. That alone gives 180 points. Using all three triple word scores along a side while using seven tiles at once gives 27 times the score +50. Combined with a few high scoring tiles, it is clear that scoring over 1,000 in a single turn is feasible.

The point is, we can figure out that a lot of the combinations are either invalid or produce low scores -- putting the Q and Z on a normal square, and putting an A or E on a triple letter score, for example.

Maybe bending the rules and making a subset of the larger problem, i.e. the highest-scoring single turn, would be more feasible to solve. Then do it a second time, taking board state and letters used into account. Maybe by working backwards the puzzle is solveable?

Well I just tried backspacing over a mistake and missed the backspace key, falling asleep with my finger on the "/" key, so I think it's bed time...

Title: Re: Highest Scrabble Score
Post by Sir Col on Dec 20^th, 2003, 3:47am

The problem with localised optimisation strategies is that we can occasionally miss the global optimisation. For example, rejecting, as part of your algorithm, the chance of putting an A or E on a triple letter square could reduce the potential to maximise at another stage. The Q and Z score highly because they reduce the chance of other words running through them.

I suspect there is no stategy which narrows the search on a localised level, as the result of an earlier decision will have an unknown conseqeunce on a later decision; confer chess.