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.
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:
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
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
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.
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.
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.