Scrabble strategies ...

Lets post in this thread the strategies we used for the scrabble contest. I will post mine in an hour or so that the contest ends ...

It' only 15 minutes before the contest ends so ...

... I will try to explain both strategies I tried the best I can. My English are not perfect so forgive me if something doesn’t make sense :

Common part : Both strategies share some common parts so lets start here …

- First the script calculates the value of every word in the file and places it in an array in the format : $words[$name] = $value; I also save different tables for each word length. For example in the $words3 array I have all the words of length 3, in $words4 those of length 4 etc. Finally I sort all the arrays with the words in descending order by value (using arsort).

- I create an array called superwords which is a merge of words6, words5, words4, words3. Then I try to find as many overlaps as i can in a limited amount of time (ex. 10 secs). That means for each words3 I search if it is a substring of any of the words in words6, word5 or words4. For each words4 I search in word6 and words5. For each words5 I search in words6. When for example in the word ABAZER I find that includes the word BAZE, I change the value of ABAZER to ABAZER + BAZE (of course I calculate the scor from the original values). For small files (<1500 words) it searches for all possible overlaps. For larger files it searches for a percentage. Because of the order of the search it will find the most overlaps in the given time. This is because it is more likely for a word3 to exist in a word6 than it is for a word5 to exist in a word6. This gives me a more realistic array with values, even if it only searches for 15-20% of the possible overlaps.

Here it is, that the 2 strategies split.

Strategy 1 (the one that I didn’t finally use) :

- After this I am trying to fit the words with the highest values to the grid horizontally. I also give a bonus to words5 and words4, because I have a function that adds letters to the blank spots trying to create words3 creating more overlaps. The fills try to maximaze only the horizontal scor since …

- … I try as many combinations as I can (max 6! = 720) for 6 lines to be fitted in 6 places. This way I am trying to mazimize the vertical scor. The horizontal doesn’t change since I shuffle whole lines. Of course I keep the grid with the highest scor.


Strategy 2 (the one that I submitted) :

In this one I chose to do something different. I first place the word with the highest value vertically in the 1st column. Then I try to place words horizontally so that their 1st letter matches the one in the vertically placed word. Then I continue placing the word in the second column instead of the first. After one complete round is completed (I have placed the highest value word in all six colums) I continue to the second round with the next highest value word in each column etc. The script ends when the time limit passes and returns the grid that had the most points during this procedure. For each complete grid that I was testing I was also adding letters to the blank spots but this time also searching for vertical overlaps. It proved that this method was giving almost always better results (5%-10%) in the time limit of 30 seconds.

There are some more details but this is the basic idea. I hope you understood what I did and tell me what you think. Since I have seen the scores that other people are getting I don’t expect to win as I have much lower scores. But I am very interested to hear the strategies other people used.

OK, here was my strategy. Rather simple, and although I don't think it will win, it might have a chance...

I would take the wordlist, and load it into an array of "Word Objects", which contained a word's text, it's length, and it's point value.

This array was then sorted by the number of points for each word.

I then would take the highest 600 scoring words, and start running across the board starting in the upper left, horizontally, then vertically.

At each position, it would run through the list of words starting from the one with the highest points, until it found one it could play.

At the same time, if a word could not be played from the list, it was removed. When the wordlist reached below 1/8th of the original number of words, the top 600 were all placed in the list again.

It kept going, until it had tried vertical and horizontal positions in all blocks.

After filling the grid, it would do a search on the grid from the original full wordlist, just in case it accidentally had placed some words it didn't know about... ;-)

On xs0's balanced sets, on a Powerbook G3 400Mhz, I got around 4000 to 6000 points in 15 to 30 seconds.

If I'd had a bit more time, I'd have added some breath first searching to the code, instead of just a single depth first placement into the grid, which probably would have added another 1000 points or so per run...

As it was, I was lucky to enter, since I didn't notice Matt placed the the contest until four days before the deadline.

My strategy is exactly Fractalbit's first technique !

I optimized a lot my code to generate the highest number of possible 6 letters words in 10 seconds (I only retain the 80,000 best words, because of the 32Mb limit).
Due to the number of combinations, I used:
3+3 with no overlap
5+1 overlap
4+2 overlap
3+3 overlap

The second pass is simply to find the 6 words that have the biggest horizontal sum, and that obey the letters counting.
When such a set is found, the program tries the 720 possible combinations to get the highest score.
In general, the best solution is found within 10 seconds in the second pass.
In general, my program is able to put more than 25 words in a grid.

I previously tried another approach by setting the first and the last vertical words and trying to fill the grid with horizontal words, but had not much success.

JC

First, I reject impossible words: those with too many Z's or X's or K's...

Once I have the scores for each word, I look for the words that are within other words and add their points to the bigger, cause that is the score that it will obtain (almost allways) when put on the board. That is the score I use for sorting, also. Also when I put a word I put the ones contained in it.

My board starts as a 9x11 grid (on a string). Real board is a 6x6 section, 'floating' within. This is so you can put the first word horizontally at pos (3,5), and fit other words around it rather freely. When they occupy an area of 6x6 the board is fixed. It happens usually after 3 or 4 long words. Thus I avoid multiple tries for the first word.

I also keep a list of 'holes' within the board. It is used for 'fast rejecting' of words. A hole is a place where you can fit a 3,4,5 or 6-letter word. I keep them on an array of integers, where index correspond to word starting positions on the board.

In my several lists of word-scores, words-into-other- words, words-with-'AAA', 'AAB' 'AAC'... I use indexes for words, say word 0 is the first on the list and so. I also had lists of words with 'A','B'... and other of words with 'AA', 'AB'... but I hadn't use for them (They were intended for fast search o words fitting a place).

The list of words with 'AAA', 'AAB'... is used to fast finding the words contained in others, as they should have at least 3 common letters.

For each word, I call $board->add_first_try() that returns TRUE if word was fitted and FALSE in case it wasn't possible...

First I try to put it overlapping the ones already in the board by looking on the board for letters in the word. Also the word is rejected if it has an 'exhaust' letter and can't be fit using one already put.

Then I try to fit the word by brute-force...

As I wrote this, I have found various bugs around my code... too fast and nightly coding!

Try to explain me too...

1) function prepare()
in this function the script prepare the list of words:
preg_match_all to get in an array the words of len beetween 3 and 6 chars
walk in the array and transform the word in a format like "VVCCCCCC" where VV is the value of the word, 0 if invalid (for example 3 "Q"), "C" is the word, this array is called AR_WORDS
Contestually an associative array of "word" => "value" is created, this array is called AR_SWORD
Find all substrings in the word and re-arrange the value in AR_WORDS
order AR_SWORD with sort(), we willhave the better words first.

2a) function hard_try()
this function take the first few words and try *all* the combinations of them, it has two limitations:
- it can't use two time the same word
- it's cost is an exponent (k ** nword_to_try)
where k depend from the len of the words

2b) function hard_try2()
this function take the first words (more than the first one) and try to insert then starting from the better one (that surely apply becouse the square is empty and the words become from AR_WORDS), then I try to put again the same word, and again if it apply, if it not let's go to the next and so on. This function try to insert the word in place where it fill *less* spaces, in this way we leave space for other words.

3) function soft_try()
mantain the better result from the previuos function, continue to fill the square simply trying to put the word from the best one to the worst one, it use the same philosopy of hard_try2() but in a faster way.

4) fullfill the square with letters, it was not necessary but why not?

In addition to this there are functions that say to me if a string may be inserted, check the type of letters, this ones need to be *very* fast, for this the square is a string where the spaces are "x0", and it is an array of two string, horizontal and vertical, the size of each string is: max(square_len, 8) * square_len - (8 - square_len).
Where possible the string operations are translated in bitwise operation.

same stuff as gatopeich "As I wrote this, I have found various bugs around my code... too fast and nightly coding! "

I'm too lazy right now to post my strategy, but it's mostly similar to what everyone else has done. I didn't come up with anything too unique it seems like.

I just wanted to tip my hat to gatopeich for coming up with a very interesting solution for one of the problems I had: where to place that first word. By using the larger board internally, you can forget that problem and just start placing words where you like. Very smart!

Thanks Mr. mungk! :-)

I wonder if anybody else added the points of words included into another one in order to decide what is the best word.

Also I would have liked to have time to implement a better management of 'holes' for the words. I think a good implementation would have increased the speed a lot.

Perhaps the time for this contest has been a little short.

I toyed with the idea of looking for overlapping words but it took so long that I would exceed the timelimit without placing any words! I would've liked to do it, but I couldn't make it efficient enough.

The way I ended up coding it allowed for the search to find such things as it went rather than looking for overlaps at the beginning.

Well, it seems my strategy was much simpler.

First, I also read words, assign scores and sort them in reverse order. But then, instead of trying to fit them in some smart way, they're randomly placed on board.

Well, there are some optimizations. The first one was that some words are (randomly) skipped, because it turned out that using highest scoring words didn't lead to best results.

The second optimization is that from all the possible positions, only those are considered, that take least new letters, but still at least one new (with zero new, it's already there, so it's better to put it somewhere else).

Finally, each word is tried twice, so as to try to fit the better scoring words more than once.

The whole process is repeated from start, until the time runs out.

I tried several other strategies, but none worked better, so I submitted this..

It is actually like in Mario Benedetti's poem "Tactica y Estrategia".

I can't resist the temptation to quote him and try to translate the meaning...

My translation & comments:

My strategy was to take some code I'd written for the purposes of a previous codewalkers contest and fit it to this problem.

I didn't have the time to develop an algorithm for this contest and hoped the power of a genetic algorithm would find boards that would be hard to find any other way.

My code works by starting off with a "population" of almost random boards and modifying them over a number of generations. The next generation is taken from the most promising of the previous generation along with boards generated by the "breeding" of the high scoring boards, mutations of other boards and a totally random new board.

The challenge was to take this usually quite slow method and get it to produce decent results in 30 seconds (in php - which is not known for its performance).

To give the code some help the initial boards were not totally random. Instead I sorted the words by score (I used the "sub score" ("points of words included into another one" as gatopeich calls it)) and tried a very simple method of fitting them into the boards. These boards meant the algorithm started with some high scoring boards and performed much better as a result.

I've enjoyed trying to do something different although I am disappointed by the results compared to what others are claiming.

Much of my time on this contest was spent optimising the scoring algorithm. I started out with 3 or 4 separate functions and ended up with two simple for loops one nested in the other - what can I say I've been taught to make code easy to read and modular (I did manage to resist using objects though ;))

ps. I am no where near experienced in the techniques I'm using (as may be obvious) any advice would be appreciated.

About the scoring of a grid, here is how I coded it.

First, I initialized an array $SumArray like this:

$sum=0;
for($i=0;$i<strlen($word);++$i) $sum+=$LetterValue[$word{$i}];
$SumArray[$word]=$sum*$sum;

Thus, every word of the wordlist has an assigned value.

My grid was stored as follows:
$Grid=array();
$Grid[0]='ABCDEF'; // 6 characters !!!
$Grid[1]='ABCDEF';
$Grid[2]='ABCDEF';
$Grid[3]='ABCDEF';
$Grid[4]='ABCDEF';
$Grid[5]='ABCDEF';
(more convenient, because of my horizontal line algorithm).

Computing the score of a grid is done as follows:
function ComputeSum($w)
{
global $SumArray;
return $SumArray[substr($w,0,3)]+$SumArray[substr($w,1,3)]
+$SumArray[substr($w,2,3)]+$SumArray[substr($w,3,3)]
+$SumArray[substr($w,0,4)]+$SumArray[substr($w,1,4)]
+$SumArray[substr($w,2,4)]+$SumArray[substr($w,0,5)]
+$SumArray[substr($w,1,5)]+$SumArray[substr($w,0,6)];
}

$a=$Grid[0];
$a=$Grid[1];
$a=$Grid[2];
$a=$Grid[3];
$a=$Grid[4];
$a=$Grid[5];
$s=ComputeSum($a);
$s+=ComputeSum($b);
$s+=ComputeSum($c);
$s+=ComputeSum($d);
$s+=ComputeSum($e);
$s+=ComputeSum($f);
$s+=ComputeSum($a{0}.$b{0}.$c{0}.$d{0}.$e{0}.$f{0} );
$s+=ComputeSum($a{1}.$b{1}.$c{1}.$d{1}.$e{1}.$f{1} );
$s+=ComputeSum($a{2}.$b{2}.$c{2}.$d{2}.$e{2}.$f{2} );
$s+=ComputeSum($a{3}.$b{3}.$c{3}.$d{3}.$e{3}.$f{3} );
$s+=ComputeSum($a{4}.$b{4}.$c{4}.$d{4}.$e{4}.$f{4} );
$s+=ComputeSum($a{5}.$b{5}.$c{5}.$d{5}.$e{5}.$f{5} );
$s now contains the real score.

Did someone come up with a faster technique ?

JC

Hi everybody!
I wanted to show my strategy (which doesn't differ much from the ones seen previously).
-- When reading in words eliminate those whit 'too much of some letters'.
-- Sort them according to the 3 first letters, then length, and if the 2 are equal char comparisson (this initial is not so important).
-- Create an array with pointers to the begginings and the ends of the words in words array that start with every 3 letters, every 2 letters, and every letter. For example beg[3]['A']['B']['C'], beg[1]['G'], end[2]['Y']['B'], etc. This way you can see if some word is in the list more faster by first checking if the pointer with its first 3 letters is set. Then you start searching from it instead from the beggining. These pointers are one of the backbones of the script.
-- Create binary search function for this array of words. It extensivly uses the pointers mentioned above.
-- Calculate the values of all words. I do not do it by trying for every 2 words if one is in the other one because it takes n^2 time and so exceeds the time limit for larger n.
The more sophisticated way is to take one word, and try for every of its substrings the binary search function to see if the substring is in the wordlist. This way complexity is only n * log(n). For n=5000 it takes only about 2-3 seconds to check everything.
-- Create aditional array with pointers to the most valuable words.


::BEGIN::
With the first few most valuable words (3 loops) put them in the first three lines. Then try to fit in verticaly the words by using the pointers mentioned above. You have mostly 3 first letters so you can easely see if there can be found som word to fit in. If not put some 3 chars word in the rest of the current column.
Check the board for 'too much leters' by going in revers and if some letter is there too much times replace it with something else. Also all gaps are filled with letter here. Then check the score of the board (with binary search of every substring in the board).

My method was certainly simple compared to others' ideas. I sorted the words descending by score, and for each score ascending by length.

I then included in each word a link to the following word. This created a simple linked list.

I then started with an empty board and took the first word and created new layouts for all the positions the word could fit (breadth-first). Each new layout stored a reference to the word currently used.

After each level, the layouts are ordered by score, and only the top n proceed to the next level.

On the first word, only horizontal positions were tried, and for the first few levels, higher values of n were used.

This method got 6441 on JC's list. I made the first two levels create new layouts from the first three eligable words, and this resulted in 6710. If I let the program run on, it found good results, but in the 30 seconds it struggled.

Unfortunately, I had been busy and was unable to complete it in the time available. I still had to code the move display and find a good way to stop overruning the time.

If possible, I will post the code. I don't think you can post attachments, though.