Notebook

Peter Norvig
29 December 2015

Refactoring a Crossword Game Program¶

In my CS 212 class on Udacity, the most complex lesson involved a crossword game program (for games such as Scrabble® and Words with Friends®). The program was developed incrementally. First I asked "what words can be made with a rack of seven letters, reagardless of the board?" Then I asked "how can you place words onto a single row of the board?" Finally, I, with the help of the students, developed a program to find the highest scoring play anywhere on the board. This approach made for a good sequence of exercises, each building on the previous one. But the code ended up being overly complicated—it accumlated technical debt—because it kept around old ideas from each iteration.

In this notebook I will refactor the program to pay off the technical debt.

Vocabulary¶

Our program uses these concepts:

Dictionary: A set of all legal words. Each word has only the letters A-Z.
Word: a string of uppercase letters.
Tile: a letter (or a blank) that can be played on the board to form words.
Blank: a tile with no letter on it; the player who places it on the board gets to choose which letter it will represent.
Rack: a collection of up to seven tiles that a player uses to make words.
Board: a grid of squares onto which players play tiles to make words.
Square: a location on the board; a square can hold one tile. (In the code, the variable name s always stands for a square number, and sq for the contents of a square, which can be a tile or empty.)
Bonus: some squares give you bonus scores: double or triple letter or word scores.
Play: a play consists of placing some tiles on the board to form a continuous string of letters in one direction (across or down), such that only valid dictionary words are formed, and such that one of the letters is placed on an anchor square.
Anchor square: Every play must place a letter on an anchor square: either the center start square or a square that is adjacent to a tile previously played on the board.
Direction: Every play must be in either the across or down direction. (The variable dir always stands for a direction.)
Cross word: a word formed in the other direction from a play. For example, a play forms a word in the across direction, and in doing so, places a letter that extends a word in the down direction. Any new extended cross word must be in the dictionary.
Score: the points awarded for a play, consisting of the sum of the word scores for each word created (the main word and possibly any cross words), plus a bingo bonus if all seven letters are used.
Word score: Each word scores the sum of the letter scores for each tile (either placed by the player or already on the board but part of the word) times the word bonus score. The word bonus score starts at 1, and is multiplied by 2 for each double word square and 3 for each triple word square covered by a tile on this play.
Letter score: The letter score is the value on the letter tile (for example, 1 for A and 10 for Q) times the letter bonus score. The letter bonus is 2 when a tile is first placed on a double letter square (or the center star) and 3 when first placed on a triple letter square; it is 1 for a tile already on the board, or for a new tile played on a non-letter-bonus square. The letter score for a blank tile is always zero.
Bingo: a bonus gained by using all seven tiles in one play. In Words with Friends® the bingo bonus is 35; in Scrabble® it is 50.
Game: players take turns making plays until one player has no more tiles. After making a play, the player's

rack is replenished with tiles until the player has 7 tiles or until the bag of tiles is empty.

Prefix: a string of zero or more letters that starts some word in the dictionary. Not a concept that has to do

with the rules of the game; it will be important in our algorithm that finds valid plays.

HTML display: a (hopefully) pretty display of the board.

This notebook uses these imports:

In [1]:

from collections     import defaultdict, namedtuple
from statistics      import mean, median
from IPython.display import HTML, display
import random

Dictionary and Words¶

We will represent the dictionary as a set of words. A word is an uppercase string of letters, like 'WORD'. There are several standard dictionaries used by different communities of players; we will use the ENABLE dictionary—we can cache a local copy with this shell command:

In [2]:

! [ -e enable1.txt ] || curl -O http://norvig.com/ngrams/enable1.txt

Now we can define what words are, load the dictionary, and show how the dictionary works:

In [3]:

def Word(w) -> str: return w.strip().upper()

DICTIONARY = {Word(w) for w in open('enable1.txt')}

In [4]:

len(DICTIONARY)

Out[4]:

In [5]:

random.sample(DICTIONARY, 10)

Out[5]:

['MUTUALITY',
 'HYPERIMMUNIZE',
 'MULISH',
 'AIRSICK',
 'PERSISTS',
 'UNRIDABLE',
 'DECANES',
 'UNSETTLEDNESS',
 'PIANISSIMI',
 'IRENICS']

In [6]:

'HELLO' in DICTIONARY

Out[6]:

True

Tiles, Blanks, and Racks¶

We'll represent a tile as a one-character string, like 'W'. We'll represent a rack as a string of tiles, usually of length 7, such as 'EELRTTS'. (I also considered a collections.Counter to represent a rack, but felt that str was simpler, and with the rack size limited to 7, efficiency was not a major issue.)

The blank tile causes some complications. We'll represent a blank in a player's rack as the underscore character, '_'. But once the blank is played on the board, it must be used as if it was a specific letter. However, it doesn't score the points of the letter. I chose to use the lowercase version of the letter to represent this. That way, we know what letter the blank is standing for, and we can distinguish between scoring and non-scoring tiles. For example, 'EELRTT_' is a rack that contains a blank; and 'LETTERs' is a word played on the board that uses the blank to stand for the letter S.

We'll define letters(rack) to give all the distinct letters that can be made by a rack, and is_word to test if a word is in the dictionary. The dict POINTS tells how many points each letter is worth.

In [7]:

BLANK    = '_'     # The blank tile (as it appears in the rack)
cat      = ''.join # Function to concatenate strings

def letters(rack) -> str:
    "All the distinct letters in a rack (including lowercase if there is a blank)."
    return cat(set(rack.replace(BLANK, 'abcdefghijklmnopqrstuvwxyz')))
    
def is_word(word) -> bool: 
    "Is this a legal word in the dictionary?"
    return word.upper() in DICTIONARY

POINTS = defaultdict(int, 
         A=1, B=3, C=3, D=2,  E=1, F=4, G=2, H=4, I=1, J=8, K=5, L=1, M=3, 
         N=1, O=1, P=3, Q=10, R=1, S=1, T=1, U=1, V=4, W=4, X=8, Y=4, Z=10)

In [8]:

is_word('LETTERs')

Out[8]:

True

In [9]:

letters('RRAACCK')

Out[9]:

'KCAR'

In [10]:

letters('EELRTT_')

Out[10]:

'rzvEbTathwfodRjLecgpixsymqlkun'

In [11]:

POINTS['Q']

Out[11]:

The Board, Squares, Directions, and Bonus Squares¶

In the previous version of this program, the board was a two-dimensional matrix, and a square on the board was denoted by a (row, col) pair of indexes. There's nothing wrong with that representation, but for this version we will choose a different representation that is simpler in most ways:

The board is represented as a one-dimensional list of squares.
The standard board is 15×15 squares, but

we will include a border around the outside, making the board size 17×17.

Squares are denoted by integer indexes, from 0 to 288.
To move in the ACROSS direction from one square to the next, increment the square index by 1.
To move in the DOWN direction from one square to the next, increment the square index by 17.
The border squares are filled with a symbol, OFF, indicating that they are off the board.

The advantage of the border is that the code never has to check if it is at the edge of the board; it can always look at the neighboring square without fear of indexing off the end of the board.

Each square on the board is initially filled by a symbol indicating the bonus value of the square: 1/2/3-dot characters for single/double/triple letter score; 2/3-dash characters for double and triple word score; and a star for the center starting position. When a tile is placed on a square,

the tile replaces the bonus value.

How will we implement this? We'll define Board as a subclass of list and give it three additional attributes:

down: the increment to move in the down direction; 17 for a standard board.
directions: the four increments to move to any neighboring square; (1, 17, -1, -17) in a standard board.
bingo: the number of points you get for using all 7 letters.

Jupyter/Ipython notebooks have a special convention for displaying objects in HTML. We will adopt it as a method of Board:

_repr_html_: return a string of HTML that displays the board as a table.

In [12]:

ACROSS = 1   # The 'across' direction; 'down' depends on the size of the board
OFF    = '█' # A square that is off the board
(SL,  DL,  TL,  DW,  TW,  STAR) = EMPTY = ( # Single/double/triple letter; double/triple word; star
 '.', ':', '∴', '=', '≡', '*') 

Square    = int # Squares are implemented as integer indexes.
Direction = int # Directions are implemented as integer increments

class Board(list):
    """A Board is a (linear) list of squares, each a single character.
    Note that board[s + down] is directly below board[s]."""

    def __init__(self, squares, bingo=None):
        list.__init__(self, squares)
        self.bingo = bingo or squares.bingo
        down = int(len(squares)**0.5)
        self.down = down
        self.directions = (ACROSS, down, -ACROSS, -down)
        
    def _repr_html_(self) -> str: return board_html(self)

HTML Display of the Board¶

I want to diaplay the board in HTML, as a table with different background colors for the bonus squares; and gold-colored letter tiles.

In [13]:

def board_html(board) -> str:
    "An HTML representation of the board."
    size = board.down - 2
    squares = [square_html(sq) for sq in board if sq != OFF]
    row = ('<tr>' + size * '{}')
    return ('<table>' +  (size * row) + '</table>').format(*squares)
    
def square_html(sq) -> str:
    "An HTML representation of a square."
    color, size, text = (bonus_colors[sq] if sq in EMPTY else ('gold', 120, sq))
    return ('''<td style="width:25px; height:25px; text-align:center; padding:0px;background-color:{};
            font-size:{}%; border: 1px solid grey;"><b>{}</b><sub style="font-size:60%">{}</sub>'''
            .format(color, size, text, POINTS[text] or ''))

bonus_colors = {
     DL: ('lightblue',  66, 'DL'),
     TL: ('lightgreen', 66, 'TL'),
     DW: ('lightcoral', 66, 'DW'),
     TW: ('orange',     66, 'TW'),
     SL: ('whitesmoke', 66, ''),
     STAR: ('violet',   99, '&#10029;')}

We'll define the standard boards for Words with Friends® and Scrabble®:

In [14]:

WWF = Board("""
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ . . . ≡ . . ∴ . ∴ . . ≡ . . . █
█ . . : . . = . . . = . . : . . █
█ . : . . : . . . . . : . . : . █
█ ≡ . . ∴ . . . = . . . ∴ . . ≡ █
█ . . : . . . : . : . . . : . . █
█ . = . . . ∴ . . . ∴ . . . = . █
█ ∴ . . . : . . . . . : . . . ∴ █
█ . . . = . . . * . . . = . . . █
█ ∴ . . . : . . . . . : . . . ∴ █
█ . = . . . ∴ . . . ∴ . . . = . █
█ . . : . . . : . : . . . : . . █
█ ≡ . . ∴ . . . = . . . ∴ . . ≡ █
█ . : . . : . . . . . : . . : . █
█ . . : . . = . . . = . . : . . █
█ . . . ≡ . . ∴ . ∴ . . ≡ . . . █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
""".split(), bingo=35)

WWF

Out[14]:

✭

In [15]:

SCRABBLE = Board("""
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ ≡ . . : . . . ≡ . . . : . . ≡ █
█ . = . . . ∴ . . . ∴ . . . = . █
█ . . = . . . : . : . . . = . . █
█ : . . = . . . : . . . = . . : █
█ . . . . = . . . . . = . . . . █
█ . ∴ . . . ∴ . . . ∴ . . . ∴ . █
█ . . : . . . : . : . . . : . . █
█ ≡ . . : . . . * . . . : . . ≡ █
█ . . : . . . : . : . . . : . . █
█ . ∴ . . . ∴ . . . ∴ . . . ∴ . █
█ . . . . = . . . . . = . . . . █
█ : . . = . . . : . . . = . . : █
█ . . = . . . : . : . . . = . . █
█ . = . . . ∴ . . . ∴ . . . = . █
█ ≡ . . : . . . ≡ . . . : . . ≡ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
""".split(), bingo=50)

SCRABBLE

Out[15]:

✭

Plays¶

A Play describes the placement of tiles on the board. We will implement Play as a named tuple of four components:

start: the index number of the square that holds the first letter in the word.
dir: the direction, with 1 indicating ACROSS and board.down (normally, 17) indicating DOWN.
letters: the letters of the word, in order, as a str. Blanks are lowercase. Some letters are from the rack; some may have been on the board.
rack: the letters that would remain in the player's rack after making this play. Not strictly necessary as part of the play, but useful information.

The function make_play returns a new board with the play made on it. It does not do any checking to see if the play is legal.

In [16]:

Play = namedtuple('Play', 'start, dir, letters, rack')

def make_play(board, play) -> Board:
    "Make the play on a copy of board and return the copy."
    copy = Board(board)
    end = play.start + len(play.letters) * play.dir
    copy[play.start:end:play.dir] = play.letters
    return copy

Example Board¶

Let's test out what we've done so far. I'll take some words from a previous game and put them on board:

In [17]:

DOWN = WWF.down
plays = {Play(145, DOWN,   'ENTER', ''),
         Play(144, ACROSS, 'BE', ''),
         Play(138, DOWN,   'GAVE', ''),
         Play(158, DOWN,   'MUSES', ''),
         Play(172, ACROSS, 'VIRULeNT', ''),
         Play(213, ACROSS, 'RED', ''),
         Play(147, DOWN,   'CHILDREN', ''),
         Play(164, ACROSS, 'HEARD', ''),
         Play(117, DOWN,   'BRIDLES', ''),
         Play(131, ACROSS, 'TOUR', '')}

board = Board(WWF)
for play in plays:
    board = make_play(board, play)
board

Out[17]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

E₁

C₃

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

Strategy for Finding All Legal Plays¶

This is our strategy for finding all possible legal plays on a board:

Find all anchor squares on the board. An anchor square is an empty square that is adjacent to a letter on the board—every legal move must place a letter on an anchor square. (One exception: on the game's first play, there are no letters on the board, and the STAR square in the center counts as the only anchor square.)
Using just the letters in the rack, find all prefixes of words in the dictionary. For example, with the rack ABC, we find that B, BA, and BAC are all prefixes of the word BACK (and the rack contains other prefixes of other words as well, such as CA and CAB).
For each anchor square and for both directions (across and down):

Try each prefix before the anchor (that is, to the left or above the anchor). Don't allow a prefix to extend to another anchor or off the board. That means we won't have to worry about cross words for the prefix. If there are already letters on the board before the anchor point, use them as the (only possible) prefix rather than using the prefixes from the rack. For each prefix that fits:
- Starting at the anchor, march across (or down) one square at a time, trying to fill empty squares with each possible letter from the rack that forms a valid prefix of a word in the dictionary. If the march hits letters that are already on the board, make sure they form a valid prefix too. Also check that any cross words are valid words. When we make a complete word (with an empty or OFF square ahead), yield the play that made the word.

So, each legal play will have zero or more prefix letters (which either all come from the rack or all were already on the board), followed by one letter from the rack covering an anchor square, followed by zero or more additional letters (which can be a mix of letters from the rack and letters already on the board). A legal play must be proceeded and followed by either an empty or OFF square.

Anchor Squares¶

An anchor square is either the star in the middle of the board, or an empty square that is adjacent to a letter:

In [18]:

def is_anchor(board, s) -> bool:
    "Is this square next to a letter already on the board? (Or is it a '*')?"
    return (board[s] == STAR or
            board[s] in EMPTY and any(board[s + d].isalpha() for d in board.directions))

def all_anchors(board) -> list:
    "A list of all anchor squares on the board."
    return [s for s in range(len(board)) if is_anchor(board, s)]

In [19]:

# The only anchor on an empty board is the star in the middle
all_anchors(WWF) 

Out[19]:

[144]

Prefixes¶

Here we define the set of all prefixes of all words in the dictionary, and investigate the set:

In [20]:

def dict_prefixes(dictionary) -> set:
    "The set of all prefixes of each word in a dictionary."
    return {word[:i] for word in dictionary for i in range(len(word))}

PREFIXES = dict_prefixes(DICTIONARY)

In [21]:

len(PREFIXES)

Out[21]:

In [22]:

random.sample(PREFIXES, 10)

Out[22]:

['REDRAWER',
 'TRIVE',
 'MENT',
 'CORPO',
 'TALESME',
 'DAVENPO',
 'TEMPORIZATIO',
 'PLURA',
 'CRUP',
 'SPOOR']

Here are all the prefixes from a tiny dictionary of three words. Note that the empty string is a prefix, and HELP is included because it is a prefix of HELPER, but HELPER is not included because there is no letter we can add to HELPER to make a word in this dictionary:

In [23]:

dict_prefixes({'HELLO', 'HELP', 'HELPER'})

Out[23]:

{'', 'H', 'HE', 'HEL', 'HELL', 'HELP', 'HELPE'}

The function rack_prefixes gives the set of prefixes that can be made just from the letters in the rack (returning them in shortest-first order). Most of the work is done by extend_prefixes, which accumulates a set of prefixes into results. The function remove(tiles, rack) removes letters from a rack (after they have been played).

In [24]:

def rack_prefixes(rack) -> set: 
    "All word prefixes that can be made by the rack."
    return sorted(set(extend_prefixes('', rack, set())), key=len)

def extend_prefixes(prefix, rack, results) -> set:
    "Add possible prefixes to `results`."
    if prefix.upper() in PREFIXES:
        results.add(prefix)
        for L in letters(rack):
            extend_prefixes(prefix+L, remove(L, rack), results)
    return results

def remove(tiles, rack) -> str:
    "Return a copy of rack with the given tile(s) removed."
    for tile in tiles:
        if tile.islower(): tile = BLANK
        rack = rack.replace(tile, '', 1)
    return rack

In [25]:

rack = 'ABC'
rack_prefixes(rack)

Out[25]:

['', 'A', 'B', 'C', 'BA', 'AB', 'CA', 'AC', 'CAB', 'BAC']

The number of prefixes in a rack is usually on the order of a hundred or two:

In [26]:

len(rack_prefixes('LETTERS'))

Out[26]:

In [27]:

len(rack_prefixes('ERYINNA'))

Out[27]:

In [28]:

len(rack_prefixes('XNMNAIE'))

Out[28]:

Unless there is a blank in the rack, in which case it is more like a thousand or two:

In [29]:

len(rack_prefixes('LETTER_'))

Out[29]:

In [30]:

len(rack_prefixes('ERYINN_'))

Out[30]:

Plays on Example Board¶

Let's work through the process of finding plays on the example board. First, we'll find all the anchors:

In [31]:

anchors = all_anchors(board)
len(anchors)

Out[31]:

To visualize these anchors, we'll make each one be a star, on a copy of board:

In [32]:

board2 = Board(board)
for a in anchors:
    board2[a] = STAR
    
board2

Out[32]:

✭

B₃

✭

T₁

O₁

U₁

R₁

✭

G₂

✭

B₃

E₁

✭

C₃

✭

I₁

✭

A₁

✭

M₃

✭

N₁

✭

H₄

E₁

A₁

R₁

D₂

✭

V₄

I₁

R₁

U₁

L₁

N₁

T₁

✭

I₁

✭

L₁

✭

E₁

✭

S₁

✭

E₁

✭

L₁

✭

E₁

✭

E₁

✭

R₁

E₁

D₂

✭

S₁

✭

S₁

✭

R₁

✭

E₁

✭

N₁

✭

Now we'll define a rack, and find all the prefixes for the rack:

In [33]:

rack = 'ABCHKNQ'

prefixes = rack_prefixes(rack)
len(prefixes)

Out[33]:

In [34]:

' '.join(prefixes)

Out[34]:

' C H Q K A B N BA CA BH KH CN KB KA KN AB AQ CH NA AC HA AN AH AK QA CHA KAC KAN HAK KNA KAB BAH BHA CAB ANK AHC ABH HAC ANC KBA KAH CAK CAH NAC ACQ BAK ACN KHA NAK BAC CAN HAN ANH ACK NAB HAB ABN QAN BAN ACH ACKN HANK BANC KANB CHAN CHAK CANK NACH KACH BACH KNAC HANC KHAN HACK BACK BHAN ANCH ANKH CHAB BANQ BANK CHAQ BHAK HACKB BANKC BACKH HACKN'

We won't go through all the anchor/prefix combinations; we'll just pick one: the anchor above the M in MUSES:

In [35]:

board3 = Board(board)
anchor = 141
board3[anchor] = STAR
board3

Out[35]:

B₃

T₁

O₁

U₁

R₁

G₂

✭

B₃

E₁

C₃

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

There's only room for prefixes of length 0 or 1, because anything longer than that would hit the anchor to the right of the G in GAVE; to avoid duplication of effort, we only allow words to run into other anchors on the right, not the left. Let's try the 1-letter prefix B first:

In [36]:

board3[140] = 'B'
board3

Out[36]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

✭

B₃

E₁

C₃

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

Now we can start to march forward. On the anchor square we can place any letter from the rack that makes a valid prefix, and that also turns ".MUSES" into a valid word. There's only one such letter, A:

In [37]:

board3[141] = 'A'
assert 'BA' in PREFIXES and is_word('A' + 'MUSES')
board3

Out[37]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

A₁

B₃

E₁

C₃

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

We can continue marching forward, trying letters from the rack that form valid prefixes. Let's try the combination CK:

In [38]:

board3[142:144] = 'CK'
assert 'BACKBE' in PREFIXES
board3

Out[38]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

A₁

C₃

K₅

B₃

E₁

C₃

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

We've spelled the word BACK, but we can't count it as a legal play, because there isn't an empty square to the right of BACK; there are two existing letters, BE. Fortunately, BACKBE is a valid prefix, so we can continue to the next empty square, where we can choose an N:

In [39]:

board3[146] = 'N'
assert 'BACKBENC' in PREFIXES
board3

Out[39]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

A₁

C₃

K₅

B₃

E₁

N₁

C₃

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

We continue to the next square (a double word square), and place an H, which completes a word, BACKBENCH (with an empty square to the right), and simultaneously makes a cross word, THE:

In [40]:

board3[148] = 'H'
assert is_word('BACKBENCH') and is_word('THE')
board3

Out[40]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

A₁

C₃

K₅

B₃

E₁

N₁

C₃

H₄

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

We've found a valid play; we can now backtrack to consider other letters for this and other prefix/anchor combinations. Now let's code this up!

Code for Finding All Plays¶

The function all_plays generates all legal plays by looking at every anchor square, trying all prefix plays, and then trying to extend each one, one letter at a time. (Note that it also generates the empty play, because a player always has the option of passing.)

In [41]:

def all_plays(board, rack):
    """Generate all plays that can be played on board with this rack.
    Try placing every possible prefix before every anchor point; 
    then extend one letter at a time, looking for valid plays."""
    yield Play(0, ACROSS, '', rack) # The empty play (no letters, no points)
    prefixes = rack_prefixes(rack)
    for anchor in all_anchors(board):
        for dir in (ACROSS, board.down):
            for play in prefix_plays(prefixes, board, anchor, dir, rack):
                yield from extend_play(board, play)

Now for the function prefix_plays, which returns a list of all partial plays consisting of a prefix placed before the anchor. Note that these are not legal plays; they are partial plays, some of which will end up being extended into legal plays.

There are two cases: if there are letters on the board immediately before the anchor, then those letters form the only allowable prefix. If not, we can use any prefix from the rack up to maxlen, which is the number of empty squares that do not run into another anchor, nor off the board.

In [42]:

def prefix_plays(prefixes, board, anchor, dir, rack):
    "Return all Plays of a prefix to the left/above anchor."
    if board[anchor-dir].isalpha(): # Prefix already on the board; only 1 prefix
        start = scan_letters(board, anchor, -dir)
        yield Play(start, dir, cat(board[start:anchor:dir]), rack)
    else: # Prefixes from rack fit in space before anchor
        maxlen = (anchor - scan_to_anchor(board, anchor, -dir)) // dir
        for prefix in prefixes:
            if len(prefix) > maxlen:
                return
            yield Play(anchor - len(prefix) * dir, dir, prefix, remove(prefix, rack))

Now extend_play takes a partial play, determines the square, s, that is one square past the end of the play, and tries all possible letters there. If adding a letter forms a valid prefix (and also does not form an invalid cross word), then we continue on (by calling extend_play recursively). If adding the letter forms a valid word, we yield the play.

In [43]:

def extend_play(board, play):
    "Explore all ways of adding to end of play; return ones that form full words."
    s = play.start + play.dir * len(play.letters)
    if board[s] == OFF: return
    cword = crossword(board, s, play.dir)
    possible_letters = board[s].upper() if board[s].isalpha() else letters(play.rack)
    for L in possible_letters:
        prefix2 = play.letters + L
        if prefix2.upper() in PREFIXES and valid_crossword(cword, L):
            rack2 = play.rack if board[s].isalpha() else remove(L, play.rack)
            play2 = Play(play.start, play.dir, prefix2, rack2)
            if is_word(prefix2) and not board[s + play.dir].isalpha():
                yield play2
            yield from extend_play(board, play2)

def scan_letters(board, s, dir) -> Square:
    "Return the last square number going from s in dir that is a letter."
    while board[s + dir].isalpha():
        s += dir
    return s

def scan_to_anchor(board, s, dir) -> Square:
    "Return the last square number going from s in dir that is not an anchor nor off board."
    while board[s + dir] != OFF and not is_anchor(board, s + dir):
        s += dir
    return s

Crosswords¶

If adding a letter in, say, the ACROSS direction also adds on to a word in the DOWN direction, then we need to make sure that this cross word is also valid. The function crossword finds the cross word at square s and returns it with a '.' indicating the empty square where the new letter will be placed, so we would get '.MUSES' and 'T.E' for the two crosswords in the 'BACKBENCH' play.

In [44]:

def crossword(board, s, dir) -> str:
    """The word that intersects s in the other direction from dir.
    Use '.' for the one square that is missing a letter."""
    def canonical(L): return L if L.isalpha() else '.'
    d = other(dir, board)
    start = scan_letters(board, s, -d)
    end = scan_letters(board, s, d)
    return cat(canonical(board[s]) for s in range(start, end+d, d))

def valid_crossword(cword, L) -> bool:
    "Is placing letter L valid (with respective to the crossword)?"
    return len(cword) == 1 or is_word(cword.replace('.', L))

def other(dir, board) -> Direction:
    "The other direction (across/down) on the board."
    return board.down if dir == ACROSS else ACROSS

In [45]:

crossword(board, 141, ACROSS)

Out[45]:

'.MUSES'

In [46]:

crossword(board, 148, ACROSS)

Out[46]:

'T.E'

The function valid_crossword checks if replacing the empty square with a specific letter will form a valid word:

In [47]:

valid_crossword('.MUSES', 'A')

Out[47]:

True

We can now see all the prefix plays for the anchor at 141 (just above MUSES):

In [48]:

set(prefix_plays(rack_prefixes(rack), board, 141, 1, rack))

Out[48]:

{Play(start=140, dir=1, letters='A', rack='BCHKNQ'),
 Play(start=140, dir=1, letters='B', rack='ACHKNQ'),
 Play(start=140, dir=1, letters='C', rack='ABHKNQ'),
 Play(start=140, dir=1, letters='H', rack='ABCKNQ'),
 Play(start=140, dir=1, letters='K', rack='ABCHNQ'),
 Play(start=140, dir=1, letters='N', rack='ABCHKQ'),
 Play(start=140, dir=1, letters='Q', rack='ABCHKN'),
 Play(start=141, dir=1, letters='', rack='ABCHKNQ')}

And we can see all the ways to extend the play of 'B' there:

In [49]:

set(extend_play(board, Play(start=140, dir=1, letters='B', rack='ACHKNQ')))

Out[49]:

{Play(start=140, dir=1, letters='BA', rack='CHKNQ'),
 Play(start=140, dir=1, letters='BACKBENCH', rack='Q'),
 Play(start=140, dir=1, letters='BAH', rack='CKNQ'),
 Play(start=140, dir=1, letters='BAN', rack='CHKQ')}

Scoring¶

Now we'll show how to count up the points made by a play. The score is the sum of the word score for the play, plus the sum of the word scores for any cross words, plus a bingo score if all seven letters are used. The word score is the sum of the letter scores (where each letter score may be doubled or tripled by a bonus square when the letter is first played on the square), all multiplied by any word bonus(es) encountered by the newly-placed letters.

In [50]:

def score(board, play) -> int:
    "The number of points scored by making this play on the board."
    return (word_score(board, play) 
            + bingo(board, play) 
            + sum(word_score(board, cplay) 
                  for cplay in cross_plays(board, play)))

def word_score(board, play) -> int:
    "Points for a single word, counting word- and letter-bonuses."
    total, word_bonus = 0, 1
    for (s, L) in enumerate_play(play):
        sq = board[s]
        word_bonus *= (3 if sq == TW else 2 if sq == DW else 1)
        total += POINTS[L] * (3 if sq == TL else 2 if sq == DL else 1)
    return word_bonus * total

def bingo(board, play) -> int:
    "A bonus for using 7 letters from the rack."
    return (board.bingo if (play.rack == '' and letters_played(board, play) == 7) 
            else 0)

Here are the various helper functions:

In [51]:

def letters_played(board, play) -> int:
    "The number of letters played from the rack."
    return sum(board[s] in EMPTY for (s, L) in enumerate_play(play))
    
def enumerate_play(play) -> list:
    "List (square_number, letter) pairs for each tile in the play."
    return [(play.start + i * play.dir, play.letters[i]) 
            for i in range(len(play.letters))]
            
def cross_plays(board, play):
    "Generate all plays for words that cross this play."
    cross = other(play.dir, board)
    for (s, L) in enumerate_play(play):
        if board[s] in EMPTY and (board[s-cross].isalpha() or board[s+cross].isalpha()):
            start, end = scan_letters(board, s, -cross), scan_letters(board, s, cross)
            before, after = cat(board[start:s:cross]), cat(board[s+cross:end+cross:cross])
            yield Play(start, cross, before + L + after, play.rack)

What should the BACKBENCH play score? The word covers two double-word bonuses, but no letter bonuses. The sum of the letter point values is 3+1+3+5+3+1+1+3+4 = 24, and 24×2×2 = 96. The cross word AMUSES scores 8, and THE is on a double word bonus, so it scores 6×2 = 12. There is one letter remaining in the rack, so no bingo, just a total score of 96 + 8 + 12 = 116.

In [52]:

score(board, Play(start=140, dir=1, letters='BACKBENCH', rack='Q'))

Out[52]:

We can find the highest scoring play by enumerating all plays and taking the one with the maximum score:

In [53]:

def highest_scoring_play(board, rack) -> Play: 
    "Return the Play that gives the most points."
    return max(all_plays(board, rack), key=lambda play: score(board, play))

In [54]:

highest_scoring_play(board, rack)

Out[54]:

Play(start=140, dir=1, letters='BACKBENCH', rack='Q')

In [55]:

make_play(board, Play(start=140, dir=1, letters='BACKBENCH', rack='Q'))

Out[55]:

B₃

T₁

O₁

U₁

R₁

G₂

B₃

A₁

C₃

K₅

B₃

E₁

N₁

C₃

H₄

I₁

A₁

M₃

N₁

H₄

E₁

A₁

R₁

D₂

V₄

I₁

R₁

U₁

L₁

N₁

T₁

I₁

L₁

E₁

S₁

E₁

L₁

E₁

R₁

E₁

D₂

S₁

R₁

E₁

N₁

Playing a Game¶

Now let's play a complete game. We start with a bag of tiles with the official Scrabble® distribution:

In [56]:

BAG = 9*'A' + 12*'E' + 9*'I' + 8*'O' + 'BBCCDDDDFFGGGHHJKLLLLMMNNNNNNPPQRRRRRRSSSSTTTTTTUUUUVVWWXYYZ__'

Then the function play_game will take a list of player strategies as input, and play those strategies against each other over the course of a game. A strategy is a function that takes a board and a rack as input and returns a play. For example, highest_scoring_play is a strategy. If the optional argument verbose is true, then the board is displayed after each play.

In [57]:

def play_game(strategies=[highest_scoring_play, highest_scoring_play], 
              board=WWF, verbose=True) -> list:
    "A number of players play a game; return a list of their scores."
    board = Board(board)
    bag = list(BAG)
    random.shuffle(bag)
    scores = [0 for _ in strategies]
    racks = [replenish('', bag) for _ in strategies]
    while True:
        old_board = board
        for (p, strategy) in enumerate(strategies):
            board = make_one_play(board, p, strategy, scores, racks, bag, verbose)
            if racks[p] == '':
                # Player p has gone out; game over
                return subtract_remaining_tiles(racks, scores, p)
        if old_board == board:
            # No player has a move; game over
            return scores

def make_one_play(board, p, strategy, scores, racks, bag, verbose) -> Board:
    """One player, player p, chooses a move according to the strategy.
    We make the move, replenish the rack, update scores, and return the new Board."""
    rack     = racks[p]
    play     = strategy(board, racks[p])
    racks[p] = replenish(play.rack, bag)
    points   = score(board, play)
    is_bingo = ('(BINGO!)' if bingo(board, play) else '')
    scores[p]+= points
    board    = make_play(board, play)
    if verbose:
        display(HTML('Player {} with rack {} makes {}<br>for {} points {}; draws: {}; scores: {}'
                     .format(p, rack, play, points, is_bingo, racks[p], scores)),
                board)
    return board

def subtract_remaining_tiles(racks, scores, p) -> list:
    "Subtract point values from each player and give them to player p."
    for i in range(len(racks)):
        points = sum(POINTS[L] for L in racks[i])
        scores[i] -= points
        scores[p] += points
    return scores

def replenish(rack, bag) -> str:
    "Fill rack with 7 letters (as long as there are letters left in the bag)."
    while len(rack) < 7 and bag:
        rack += bag.pop()
    return rack

In [58]:

%%javascript
IPython.OutputArea.auto_scroll_threshold = 9999;

In [59]:

play_game()

Player 0 with rack EDOSOLB makes Play(start=144, dir=1, letters='BOODLE', rack='S')
for 18 points ; draws: STOYNRR; scores: [18, 0]

B₃

O₁

D₂

L₁

E₁

Player 1 with rack IUSI_IT makes Play(start=146, dir=17, letters='OUISTItI', rack='')
for 53 points (BINGO!); draws: OHAKAQL; scores: [18, 53]

B₃

O₁

D₂

L₁

E₁

U₁

I₁

S₁

T₁

I₁

Player 0 with rack STOYNRR makes Play(start=264, dir=1, letters='YIRR', rack='STON')
for 45 points ; draws: STONONE; scores: [63, 53]

B₃

O₁

D₂

L₁

E₁

U₁

I₁

S₁

T₁

I₁

Y₄

I₁

R₁

Player 1 with rack OHAKAQL makes Play(start=212, dir=1, letters='LOTAH', rack='KAQ')
for 32 points ; draws: KAQDEWU; scores: [63, 85]

B₃

O₁

D₂

L₁

E₁

U₁

I₁

S₁

L₁

O₁

T₁

A₁

H₄

I₁

Y₄

I₁

R₁

Player 0 with rack STONONE makes Play(start=116, dir=17, letters='ONSET', rack='ON')
for 30 points ; draws: ONROBEM; scores: [93, 85]

O₁

N₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

I₁

T₁

S₁

L₁

O₁

T₁

A₁

H₄

I₁

Y₄

I₁

R₁

Player 1 with rack KAQDEWU makes Play(start=168, dir=17, letters='DAWK', rack='QEU')
for 57 points ; draws: QEURLVI; scores: [93, 142]

O₁

N₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

D₂

I₁

T₁

A₁

S₁

W₄

L₁

O₁

T₁

A₁

H₄

K₅

I₁

Y₄

I₁

R₁

Player 0 with rack ONROBEM makes Play(start=66, dir=17, letters='BROMO', rack='NE')
for 41 points ; draws: NEETN_A; scores: [134, 142]

B₃

R₁

O₁

M₃

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

D₂

I₁

T₁

A₁

S₁

W₄

L₁

O₁

T₁

A₁

H₄

K₅

I₁

Y₄

I₁

R₁

Player 1 with rack QEURLVI makes Play(start=80, dir=17, letters='QUELL', rack='RVI')
for 34 points ; draws: RVIDTHA; scores: [134, 176]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

D₂

I₁

T₁

A₁

S₁

W₄

L₁

O₁

T₁

A₁

H₄

K₅

I₁

Y₄

I₁

R₁

Player 0 with rack NEETN_A makes Play(start=190, dir=1, letters='NEATNEsS', rack='')
for 47 points (BINGO!); draws: VEXEPIL; scores: [181, 176]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

L₁

O₁

T₁

A₁

H₄

K₅

I₁

Y₄

I₁

R₁

Player 1 with rack RVIDTHA makes Play(start=174, dir=17, letters='DEARTH', rack='VI')
for 36 points ; draws: VINESTI; scores: [181, 212]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

A₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

I₁

T₁

H₄

Y₄

I₁

R₁

Player 0 with rack VEXEPIL makes Play(start=230, dir=1, letters='PIXIE', rack='VEL')
for 48 points ; draws: VELUCUI; scores: [229, 212]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

A₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

P₃

I₁

X₈

I₁

E₁

T₁

H₄

Y₄

I₁

R₁

Player 1 with rack VINESTI makes Play(start=165, dir=1, letters='SNED', rack='VIETI')
for 22 points ; draws: VIETIAA; scores: [229, 234]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

A₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

P₃

I₁

X₈

I₁

E₁

T₁

H₄

Y₄

I₁

R₁

Player 0 with rack VELUCUI makes Play(start=205, dir=1, letters='UVEA', rack='LCUI')
for 23 points ; draws: LCUIEIF; scores: [252, 234]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

P₃

I₁

X₈

I₁

E₁

T₁

H₄

Y₄

I₁

R₁

Player 1 with rack VIETIAA makes Play(start=159, dir=17, letters='VITIATE', rack='A')
for 24 points ; draws: AZEOIMG; scores: [252, 258]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

H₄

E₁

Y₄

I₁

R₁

Player 0 with rack LCUIEIF makes Play(start=245, dir=17, letters='IF', rack='LCUEI')
for 28 points ; draws: LCUEIGD; scores: [280, 258]

B₃

Q₁₀

R₁

U₁

O₁

E₁

O₁

M₃

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 1 with rack AZEOIMG makes Play(start=76, dir=17, letters='GAZEBO', rack='IM')
for 36 points ; draws: IMGRORY; scores: [280, 294]

B₃

G₂

Q₁₀

R₁

A₁

U₁

O₁

Z₁₀

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 0 with rack LCUEIGD makes Play(start=110, dir=1, letters='ZIG', rack='LCUED')
for 17 points ; draws: LCUEDEA; scores: [297, 294]

B₃

G₂

Q₁₀

R₁

A₁

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 1 with rack IMGRORY makes Play(start=92, dir=1, letters='YAM', rack='IGROR')
for 22 points ; draws: IGRORNJ; scores: [297, 316]

B₃

G₂

Q₁₀

R₁

Y₄

A₁

M₃

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 0 with rack LCUEDEA makes Play(start=24, dir=17, letters='DECAY', rack='LUE')
for 18 points ; draws: LUETSAW; scores: [315, 316]

D₂

E₁

C₃

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 1 with rack IGRORNJ makes Play(start=40, dir=1, letters='REJOIN', rack='GR')
for 52 points ; draws: GRNPFEC; scores: [315, 368]

D₂

R₁

E₁

J₈

O₁

I₁

N₁

C₃

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 0 with rack LUETSAW makes Play(start=26, dir=1, letters='WAES', rack='LUT')
for 62 points ; draws: LUTA; scores: [377, 368]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 1 with rack GRNPFEC makes Play(start=60, dir=1, letters='ENG', rack='RPFC')
for 21 points ; draws: RPFC; scores: [377, 389]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

E₁

N₁

G₂

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 0 with rack LUTA makes Play(start=172, dir=1, letters='TAD', rack='LU')
for 11 points ; draws: LU; scores: [388, 389]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

E₁

N₁

G₂

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

U₁

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

T₁

A₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 1 with rack RPFC makes Play(start=96, dir=1, letters='CUP', rack='RF')
for 10 points ; draws: RF; scores: [388, 399]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

E₁

N₁

G₂

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

C₃

U₁

P₃

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

T₁

A₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 0 with rack LU makes Play(start=127, dir=1, letters='EL', rack='U')
for 8 points ; draws: U; scores: [396, 399]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

E₁

N₁

G₂

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

C₃

U₁

P₃

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

T₁

A₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

H₄

E₁

F₄

Y₄

I₁

R₁

Player 1 with rack RF makes Play(start=234, dir=17, letters='EF', rack='R')
for 9 points ; draws: R; scores: [396, 408]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

E₁

N₁

G₂

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

C₃

U₁

P₃

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

T₁

A₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

F₄

H₄

E₁

F₄

Y₄

I₁

R₁

Player 0 with rack U makes Play(start=258, dir=1, letters='UH', rack='')
for 5 points ; draws: ; scores: [401, 408]

D₂

W₄

A₁

E₁

S₁

R₁

E₁

J₈

O₁

I₁

N₁

C₃

E₁

N₁

G₂

B₃

A₁

G₂

Q₁₀

R₁

Y₄

A₁

M₃

C₃

U₁

P₃

O₁

Z₁₀

I₁

G₂

E₁

O₁

M₃

E₁

L₁

N₁

O₁

B₃

O₁

D₂

L₁

E₁

S₁

V₄

O₁

U₁

S₁

N₁

E₁

D₂

T₁

A₁

D₂

I₁

T₁

A₁

N₁

E₁

A₁

T₁

N₁

E₁

S₁

W₄

U₁

V₄

E₁

A₁

I₁

L₁

O₁

T₁

A₁

H₄

K₅

R₁

A₁

P₃

I₁

X₈

I₁

E₁

T₁

I₁

F₄

U₁

H₄

E₁

F₄

Y₄

I₁

R₁

Out[59]:

[402, 407]

That was an exciting high-scoring game, but it was just one game. Let's get statistics for both players over, say, 10 games:

In [60]:

%%time

games = 10

scores = [score for game in range(games) 
                for score in play_game(verbose=False)]

print('min: {}, median: {}, mean: {}, max: {}'.format(
    min(scores), median(scores), mean(scores), max(scores)))

min: 307, median: 373.5, mean: 382.8, max: 459
CPU times: user 33.2 s, sys: 324 ms, total: 33.5 s
Wall time: 36.2 s

Tests¶

I should have a complete test suite. Instead, all I have this minimal suite, plus the confidence I gained from seeing the game play.

In [61]:

def sames(A, B): return sorted(A) == sorted(B)

def test():
    "Unit tests."
    assert is_word('WORD')
    assert is_word('LETTERs')
    assert is_word('ETHyLENEDIAMINETETRAACETATES')
    assert not is_word('ALFABET')
    
    rack = 'ABCHKNQ'
    
    assert sames(letters(rack), rack)
    assert sames(letters('ABAC_'), 'ABCabcdefghijklmnopqrstuvwxyz')
    
    assert dict_prefixes({'HELLO', 'HELP', 'HELPER'}) == {
        '', 'H', 'HE', 'HEL', 'HELL', 'HELP', 'HELPE'}
    
    assert set(rack_prefixes('ABC')) == {'', 'C', 'B', 'A', 'AB', 'CA', 'AC', 'BA', 'BAC', 'CAB'}
    assert len(rack_prefixes('LETTERS')) == 155
    assert len(rack_prefixes('LETTER_')) == 1590
    
    assert remove('SET', 'EELRTTS') == 'ELRT'
    remove('TREaT', 'EELRTT_') == 'EL'
    
    assert len(WWF) == len(SCRABBLE) == 17 * 17
    assert all(sq in EMPTY or sq == OFF for sq in WWF + SCRABBLE)
    
    DOWN = WWF.down
    plays = {
         Play(145, DOWN,   'ENTER', ''),
         Play(144, ACROSS, 'BE', ''),
         Play(138, DOWN,   'GAVE', ''),
         Play(158, DOWN,   'MUSES', ''),
         Play(172, ACROSS, 'VIRULeNT', ''),
         Play(213, ACROSS, 'RED', ''),
         Play(147, DOWN,   'CHILDREN', ''),
         Play(164, ACROSS, 'HEARD', ''),
         Play(117, DOWN,   'BRIDLES', ''),
         Play(131, ACROSS, 'TOUR', '')}

    board = Board(WWF)
    for play in plays:
        board = make_play(board, play)
        
    assert len(WWF) == len(board) == 17 * 17
    assert all_anchors(WWF) == [144]
    assert all_anchors(board) == [
        100, 114, 115, 116, 121, 127, 128, 130, 137, 139, 141, 143, 
        146, 148, 149, 150, 154, 156, 157, 159, 160, 161, 163, 171, 
        180, 182, 183, 184, 188, 190, 191, 193, 194, 195, 197, 199, 
        201, 206, 208, 210, 212, 216, 218, 225, 227, 230, 231, 233, 
        236, 243, 248, 250, 265, 267]
    
    assert crossword(board, 141, ACROSS) == '.MUSES'
    assert crossword(board, 148, ACROSS) == 'T.E'
    assert valid_crossword('.MUSES', 'A')
    assert not valid_crossword('.MUSES', 'B')
    
    assert sames(prefix_plays(rack_prefixes(rack), board, 141, 1, rack),
                 [Play(start=141, dir=1, letters='', rack='ABCHKNQ'),
                  Play(start=140, dir=1, letters='C', rack='ABHKNQ'),
                  Play(start=140, dir=1, letters='K', rack='ABCHNQ'),
                  Play(start=140, dir=1, letters='B', rack='ACHKNQ'),
                  Play(start=140, dir=1, letters='A', rack='BCHKNQ'),
                  Play(start=140, dir=1, letters='H', rack='ABCKNQ'),
                  Play(start=140, dir=1, letters='N', rack='ABCHKQ'),
                  Play(start=140, dir=1, letters='Q', rack='ABCHKN')])
    
    assert sames(extend_play(board, Play(start=140, dir=1, letters='B', rack='ACHKNQ')),
                 {Play(start=140, dir=1, letters='BA', rack='CHKNQ'),
                  Play(start=140, dir=1, letters='BACKBENCH', rack='Q'),
                  Play(start=140, dir=1, letters='BAH', rack='CKNQ'),
                  Play(start=140, dir=1, letters='BAN', rack='CHKQ')})

    assert len(BAG) == 100
    
    assert replenish('RACK', ['X', 'B', 'A', 'G']) == 'RACKGAB'
    assert replenish('RACK', []) == 'RACK'
    assert replenish('RACK', ['A', 'B']) == 'RACKBA'
    
    assert score(WWF, Play(144, ACROSS, 'BE', '')) == (3 + 1)
    assert score(board, Play(140, ACROSS, 'BACKBENCH', 'Q')) == 116
    
    return 'ok'

test()

Out[61]:

'ok'

Conclusion: How Did We Do?¶

We can break that into four questions:

Is the code easy to follow?

I'm biased, but I think this code is easy to understand, test, and modify.

Does the strategy score well?

Yes: the mean and median scores are both over 350, which is enough for the elite club of high scorers.
No: this is not quite world-champion caliber.

Is the code fast enough?

It takes less than 3 seconds to play a complete game for both players; that's fast enough for me. If desired, the code could be made about 100 times faster, by using multiprocessing, by caching more information, by not building explicit lists for intermediate results (although those intermediate results make the code easier to test), by using PyPy or Cython, or by porting to another language.

What's left to do?
- We could give players the option of trading in tiles.
- We could explore better strategies. A better strategy might:
  - Plan ahead to use high-scoring letters only with bonuses.
  - Use blank tiles strategically, not greedily.
  - Manage letters to increase the chance of a bingo.
  - Play defensively to avoid giving the opponent good chances at high scores.
  - Think ahead in the end game to go out before the opponent (or at least avoid being stuck with high-scoring letters in the rack).
  - In the end game, know which tiles have not been played and thus which ones the opponent could have.
- The game could be interfaced to an online game server.
- More complete unit tests would be great.
- We could compare this program to those of the giants whose shoulders we stood upon.

Thanks to Markus Dobler for correcting one bug and making another useful suggestion.

*[Peter Norvig](http://norvig.com)*