Here's the outline of my 29 May talk to Portland State
University's CS 442/542: Combinatorial Games. Thorough credit
was given to Maven and Quackle, from which most of the ideas
were lifted. (The end of the handout gave excerpts from three
of Quackle's data files.)

I'm posting in case it's a useful start for anyone wanting to
give a comparable talk, and especially to encourage anyone else
to post a summary of their own talk.

Steven Alexander
Portland, OR, USA
sa433@...
<http://home.teleport.com/~stevena/scrabble/faq.html>


For Portland State Univ Prof. Massey CS542: Combinatorial Games, Spring 2007
Steven Alexander*
* 5th-ranked OR player (90th N.Am.); 21st all-time-high rtg; NSA Rtg Cmte. A.B.
Princeton, J.D. Columbia, C.S. grad work, UC Berkeley.
I. What’s known about Scrabble
a. Unless doing Scrabble in particular, how would you find out this kind of
thing?
II. Modeling simplifications (both computer & human)
a. Linear insights were major advances; worth of more effort subject to measure
i. Unless essence of game, hunch may be wrong
b. Essence of game:
i. move finding
ii. score as proxy for winningness
III. Move-generation
a. Per line -- uniform structure
b. cross-checks
i. avoid reevaluation outside next move’s neighborhood
c. trie structure (Boyer-Moore string search)
i. GADDAG improvement [Gordon]
1. new lexicon, same structure
2. FADGE# ADGE#F DGE#FA GE#FAD E#FADG
d. Alternatives: permute letters of rack & fit (ultra-small memory)
IV. Static move evaluation
a. Goal = max(E[score])
i. Score + leave + board -- we’re done
b. Value of leave
i. Turnover
1. humans used: "@tile played worth 2pts"
2. now situational: #played * avg_val(tiles_in_bag) -- val(tiles_played)
3. captured in volatility
ii. Tiles
1. Rules of thumb .. captures large effects: ? Q S E largest deviants
2. pre-generate using contribution of tile-on-rack to next score
3. average value of all tiles = 0?
iii. improvements
1. longer leave sets (Quackle)
2. vowel-consonant balance
c. Value of board
i. simulation showed +-3pt, esp. access to TWS
1. generally not modeled by Maven, emotional to players
d. Goal = win(E[win])
i. then we’re not done
ii. 2 vs. 3 vs. 4 points probably linear -- players’ scoring as bell-curve
process
V. Simulations & dynamics
a. How dependent on static/dynamic/quality of later moves?
i. play out should introduce less error than difference between moves
ii. next-play greedy overall excellent
1. some positions not
b. How many initial moves to consider?
i. all, let moves incrementally eliminate themselves (Quackle)
c. Non-linearity of score
i. fast/slow
1. win% based on (score_diff,tiles_in_bag)
d. Pre-endgame
i. Especially 1..2-in-bag
1. simulation
2. opponent-holding inferences
e. Endgame -- still not perfect
VI. Opponent modeling
a. Opponent’s secret information = tiles
i. last play
ii. tile exchange
b. Opponent’s plan?
i. in human play, can alert to weird opportunity opponent pins hope on
VII. Other
a. Computer versions educate humans
i. top UK player plays according to max(equity_calc)
b. General insight to modeling approach
i. imperfect human knowledge & linear approach: value of word = -"opportunity
cost"
c. Data structure techniques for human memory
i. multi-champion Canadian music prof. uses linked list of linked lists to
recall 7s & 8s
VIII. Closing
a. Study game closely
i. enlist at least one communicative expert
b. Payback for the expert(s)

Terminology
1. Board structure
a. cross-check
b. trie, dawg
c. gaddag
2. Heuristics, simulation terminology
a. Equity
b. Ply
3. Human terminology
a. Extension -- (different feel for human, routine for computer)

References:
* Quackle {2005+}, <http://www.quackle.org/doc/how_quackle_plays_scrabble.html>,
Jason Katz-Brown and John O’Laughlin
- released 2005; un-configured for Scrabble 2006
-- open source but not yet well-documented
* Maven {1987+}, <http://wiki.cs.pdx.edu/cs542/papers/maven.pdf>, Towards
Perfect Play of Scrabble, Brian Sheppard, 2002 (dissertation, U. Maastricht
Press)
- early version played tournament 1987; distributed ~1992-95; sold to Hasbro
-- well-documented, no source
* A Faster Scrabble Move Generation Algorithm, Steven A. Gordon, Software
Practice & Experience, 24:2, Feb 1994, 219-232
* The World's Fastest Scrabble Program, Andrew W. Appel and Guy J. Jacobson,
Communications of the A.C.M., 31:5, May 1988, 572-578, 585

{Quackle}/source/quackle-0.93/data/strategy/twl06
bogowin
-1 91 0.572342
-1 92 0.571746
-1 93 0.57116
0 1 0.785018
0 2 0.777264
0 3 0.769868
syn2
AA -3.82
AB 0.39
AC 0.32
AD -0.45
worths
A 0.852
B -1.8632
C 0.737
D 0.5776
E 1.0925
F -2.0915
G -2.8469
H 1.0314
I -0.4633
J -2.5068
K -0.9184
L -0.3699
M 0.6313
N -0.1618
O -0.5529
P -0.575
Q -7.5409
R 0.5145
S 6.7782
T -0.2042
U -3.0467
V -5.1075
W -3.9051
X 3.102
Y -0.9842
Z 4.8172
? 21.7777

[Non-text portions of this message have been removed]