Subject: Problem w/ Dictionary Encoding

From: [email-masked] (Steve Hodsdon)
Date: Tue, 01 Nov 1994 22:41:35 -0000 (GMT)

Hello all,

     I am currently designing a program that plays Boggle, the word 
search game.  One of the first design problems that I have hit upon is 
an algorithm that can fill in the 4X4 matrix with a good mix of letters.  
What I mean is, I want the player to be able to find valid words on the 
board, not just some randomly placed letters.  (You see, I wanted to be 
able to generate each board as the game is being played, not have some 
"board data base" that has a mass of pre-generated boards.  However, if 
I can't come up with a fast way to generate a board on the fly, I'll 
have to go the pre-generated route.)

     The first step in creating the boards is finding how the letters of 
each word in the dictionary relate to each other.  I have the Scientific 
American (December '83) Computer Recreations column on "A progress 
report on the fine art of turning literature into drivel."  Brian Hayes 
(BH) writes: "The conversion of literature into gibberish is done in two 
stages.  First a text is 'read' by the program, and certain statistical 
properties are extracted and recorded.  The statistics define the 
probability that any given letter of the alphabet follows another 
letter, or another sequence of letters in the source text."

     Well, so far, so good.  This is exactly what I want to do.  I need 
to find a method that will show the probability of one letter following 
another.  BH writes: "The root of the idea is that a letter's 
probability of appearing at a given point in written english depends 
strongly on the preceding letters.  ...  The procedure, then, is to set 
up a separate frequency table, for each symbol in the character set.  
The frequencies are recorded in a two-dimensional array with 28 rows and 
28 columns, for a total of 784 elements."  (He uses the 26 alphabetic 
characters, the space, and the apostrophe.)  This is referred to as 
"second-order random text."

     More refinement is needed.  I'm assuming that I'm looking at the 
first two letters of each word.  Is this frequency table valid for the 
"middle" of the words?  No, I can see letter pairs in the middle of 
words that can not be at the start of any words.  What am I to do?

     BH writes: "The next step should be obvious.  A third-order 
algorithm chooses each letter in the random text according to 
probabilities determined by the two preceding letters.  This calls for a 
three-dimensional array with 28 planes, each plane being made up of 28 
rows of 28 columns."

     Brian then goes on to describe even higher orders of approximation 
along with storage requirements.  A fourth order table will require more 
than 600K of memory.  There must be a way to compress this storage 
requirement.

     I have a paper by Steven Gordon entitled:  _A Comparison Between 
Probabilistic Search and Weighted Heuristics in a Game With Incomplete 
Information_, (Published in _Games: Planning & Learning_, published by 
the AAAI Press.)  This is an interesting paper on Scrabble strategies.  
Also included in it is a couple of references to papers on "a compact 
representation for a large lexicon and a fast algorithm for each 
possible move in a given Scrabble position."

     One reference is:  A. Appel and G. Jacobson, 'The world's fastest 
Scrabble program', Commun. ACM, 31,(5), 572-578, 585 (May 1988).  (This 
is the reference to a paper that I was looking for in a previous post.) 
(As an aside, can anyone help me get a copy of this paper?  I can't get 
access to any of the "old" Communications of the ACM.)

     The other reference is to a yet un-published paper (by S Gordon) 
entitled: 'A faster Scrabble move generation algorithm', submitted back 
on 3/93.  (Has this been published yet?  If so, where?)

     Well, this was a long-winded introduction to my main question.  I 
*think* that having a compact way to represent the dictionary in memory 
and being able to encode the frequency tables should be related.  Does 
the Appel & Jacobson paper describe how the encode the Scrabble 
dictionary in enough detail for me to program it?  Does anyone know of a 
program that does this sort of analysis work that I want to do?

Many thanks in advance,

Steve

-----------------------------------------------------------------------------
: It's me that's been dogging your shadow,    |  [email-masked]      :
: It's me that's been a shadowing your dog... |   Pragmatic Designs         :
:                                        10cc |  I *AM* the company!        :
-----------------------------------------------------------------------------