Bitboards in Word Games (such as Scrabble and Wordfeud)

Bitboards are datastructures heavily used in board games, most notably chess, to speed up move generation and board evaluation by using simple (and fast) low-level bit operations. It can, however, also be used for move generation in board word games such as Scrabble, Words with friends, Wordfeud and Angry Words.

This works because, during move generation, the actual characters are not important. We are simply interested in what moves are possible. Matching these with actual dictionary words comes later.

Board representation

The board can be broken into lines and each line represented by one machine word. Although the method is general, all the mentioned word games takes place on a 15x15 board. This board is represented by 15 16bit words where each bit is one position and the most significant bit (MSB) goes unused.

Each of the 16bit words representing one line has the corresponding bit set if the position is occupied by a tile, and clear if the position is clear.


Since a valid move can be placed anywhere on a line where it either incorporates existing tiles, as well as where it touches tiles on the lines above or below, the lines above and below must be taken into consideration.

We perform a OR on the line above and the line below the curent line, to get anchor bits for the current line. The anchor contains all positions where a tile would touch a tile on the line above or below. Obviously, the first line has no line above itself, and the last line has no line below.


anchors = map (fst .|. snd) (zip (0:tail board) (init board:0))


We define a move to be the contiguous tiles making up a new word. A move can therefore contain existing tiles on the board as well as the tiles to placed to form the word.

Since all moves must, except for the opening move, connect to a word already on the board, we can disregard moves of length 1 since 1-lenght moves in the horizontal direction will necessarily be represented by a multi-tile move in the vertical direction, and vice versa.

There are a total of 105 possible moves on any line. Of these we have 1 valid 15-tile move, two 14-tile moves, three 13-tile moves down to fourteen 2-tile moves. Here are the nine 7-tile moves as bitmaps and decimal values:

0111111100000000 32512
0011111110000000 16256
0001111111000000  8128
0000111111100000  4064
0000011111110000  2032
0000001111111000  1016
0000000111111100   508
0000000011111110   254
0000000001111111   127

All 105 possible moves as decimal values:

let allmoves = [3,..32767] :: Word16

Valid moves

Since a move can't be placed adjacent to any existing tiles, but must incorporate them, we can, for a given line, remove all moves not satisfying this criteria. We do this by expanding our move one bit to each side and then checking to see if the number of existing tiles present in the move changes. If it changes, it means we have engulfed an adjacent tile, and the move is illegal.

We call this operation a wiggle:

wiggle = shiftL 1 move .|. shiftR 1 move

Available tiles

Any move requiring more characters than we have available can't be done and can be removed. Since all the mentioned board games limit the player to 7 tiles at any one time, this is an important step dramatically reducing the number of possible moves.

We check for this constraint by finding the number of bits in the move which is not already part of the line.

Note that most modern microprocessors (2007+), such as Intel CPUs with SSE4.2 and AMD CPUs with SSE4a, have an assembly instruction (POPCNT) for calculating the number of bits set in an argument. This property is called the population count or Hamming Weight. Sadly, not all compilers of popular high-level languages will actually use this.

Precomputing moves

Before moving on, it is worth noting that while we have not yet used our anchors, meaning we have not yet moved outside of considering each individual line, it is at this point possible to build a lookup-table giving a list of just the possible moves (at this point) for each possible line. This lookup table will have one entry for each of the 32768 possible lines (all 15bit combinations), returning the moves for each. If we constrain ourselves to a maximum of 7 available characters, there will be 0 to 65 moves per entry with an average of 30 with a total of almost 1 million (16bit) moves in total.

Bringing it together

Given a line, its anchor, and the number of available characters, the valid moves are all moves satisfying
not adjacent to an existing tile (wiggle test)
not requiring more characters than we have available
incorporating at least one already present tile or an anchor

If we use the previously mentioned lookup table, and we have 7 characters available, the first two conditions has already been taken into consideration, leaving us with only the last. Needless to say, requiring only this simple test bodes for great performance.

We need to perform this for each line in the board as well as for each line of the rotated board, to account for left-right as well as top-down words. These moves can then be converted to patterns with actual characters, including constraints imposed by perpendicular words already on the board, and passed to dictionary match processing. The dictionary matching process can also be accelerated with other kinds of bitmaps, outside the scope of this article.