New games every week!
Scrabble Solving Methodology Blog
4th May 2019

Alan asks..

What's the general outline of your current approach?


The general method is as such.

1. The AI randomly picks a spot on the board, and scans to check that a word will fit in the space provided. It looks for a space that will fit about 3 or 4 letters and will connect to at least one other tile on the board.

-=-=-

2. It gathers up "letters in the way" to add to an anagram shuffle.

3. It searches for anagrams with the full rack of letters, plus any letters "in the way".
It repeats this task, using fewer and fewer random letters from the rack, until it finds a nice anagram or two that might fit into the space.

4. It places the letters down onto the "Playing" array, making sure the "Letters in the way" fit correctly, and then the default word checker hecks and scores. Thus far, I haven't scanned for adjacent tiles, so the word checker is the part that does that part of the checking.

5. Assuming it's a valid placement, the score is used to determine the "Best word so far", and the placement is stored into the "Best word placement array".

6. We repeat this over and over, once per frame, over a maximum of 300 frames. In the video I posted last night, you should be able to see the lower left four values, one for each AI, which say how many frames it's taken for that player to pick a word.
If the counter reaches >300, then it gives up trying and swaps a few letters.

..I haven't yet added a "This player gave up and swapped some letters" notification!!

This isn't "The best" Scrabble Solver method, since it doesn't yet account for Premium Tiles, but I should be able to add those fairly easy I think.

But it is fairly simplistic in its methodology, and Javascript appears to be coping alright with it. The fan can kick up if the computer takes too long. This is why I've added the 300-frame limit. It can also get a bit tetchy when all four players are AI, so I might try to add some kind of "Player played X word" delay after a play, to allow the system a moment or two to relax.

But .. It works, and that's alright by me!

Alan Continues..

Have you read up on ''Trie''s?

When I first created Stringy Things (May 2003!) the addition of the Blank Tile made everything much harder than it should've, as far as quick word-checking was concerned.
Add to that, the fact that BlitzBasic was "a bit pants" at string comparisons, and everything chugged to a halt when attempting such things.
Back then, I did attempt to work with Binary Trees and the like, to help speed things up, but in the end, I found it was much better to simply scan the entire list, each and every time, simply because of those Blanks.
The blanks really do break all manner of Binary Trees.

In addition, I changed the entire wordlist from being words, to being numbers. BlitzBasic could compare two sets of numbers infinitely quicker than it could two sets of words.
I considered adding that to this framework, too, but couldn't think of a simple way to store those numbers, without the file growing exponentially.
In Blitz it was raw data, but many browsers have security issues with accessing raw data, so the alternative would be plonking thousands of great big numerical values into a giant script.
*sigh*
It's one issue after another.

Suffice to say, this method does at least work, and it seems to be handling it rather well. .. I think!!

I should probably have another look at Tree Stuff, though. It HAS been a long time since I last did that!
Views 153, Upvotes 17  
Shoebox , Scrabble
New games every week!
Site credits : Jayenkai
(c) Jayenkai 2023 and onwards, RSS feed

Blog - Scrabble Solving Methodology - AGameAWeek