Procedural Generation of Word Game Boards

Bent Vector Studios has been working on a new word game, Word Portal for about 10 months now. This is our first project using the Unity engine, so unsurprisingly there was a learning curve and we've had a lot of re-work as a result. We're now approaching the final stages of development and expect to ship the game very (very!) soon.

Part of this finalization process has been play-testing with a broader base of players. One of the biggest things that almost immediately jumped out of this new testing was that some levels of the game are not balanced with respect to their assigned level of difficulty. Players had a really hard time with some of the early levels and weren't able to advance as quickly as we had expected.

Word Portal is a simple word game wherein players are given a 5x5 (25) board of letters from which they must create words. The rules for creating words are simple:

1. Must be 3-12 letters long.

2. Must use the middle letter last.

3. Once you've used a letter from the "inner" ring, you cannot use letters from the "outer" ring (i.e.: the progression goes from outer->inner->middle).

4. Letters do not need to be touching (unlike, for example, Wordament)

5. No proper nouns or "curse" words.

Players get more points for creating long words and for using letters like Q, X and Z in words. No time limits are set on each round (no rewards for faster play). Every player gets the same set of letters for each round and are ranked on a per-round "ladder" online. Rounds can be replayed to improve player scores.

There are many, many ways to implement a word game. We tried 3 different permutations on the 5x5 board theme:

Option 1 was in place since the beginning days of Word Portal. This option "felt" right to the designer. To accommodate this, a procedural board generator was developed. For each round, players are allowed to create between 5 and 15 words of between 3 and 12 letters. That means that at most 15*12 letters would ever be used in a round. However, since letters can be discarded by the game engine for various rules (e.g.: words cannot end in Q or J) we generated 300 letters for each round using the following process:

Some of these same rules were applied during gameplay as letters used to create words were replaced:

In addition, the procedural generation tool was coded to validate the letter boards it generated. We used a list of the most common 5000 English words and counted how many 4, 5 and 6-letter words could be generated from each board. The algorithms took into account the board structure and the required use of inner, outer and middle letters on the board. Any boards that had less than 200 words in them were rejected - not sure where 200 came from, it just seemed like a reasonable cut-off.

Despite all of this work, as I mentioned above, play-testing was problematic. Some boards played easily at the start and became too hard after 3-4 words were played. Other boards started too hard and stayed that way.

Our first attempt was to create a new algorithm for option 1. Instead of using random letters, we tried building the board from random, common words:

This implementation guarantees that there will be at least a few "common" words on each board but didn't provide a better experience for play-testers. Players rarely found the first word added to the board (we kept track of them!) and often failed to complete rounds. The boards were still too difficult.

At this point, we started looking at building boards by hand. This meant that we could no longer use option 1 but needed to use either option 2 or option 3. Option 2 requires approximately 10 times as many boards as option 3 but we evaluated both. Players preferred option 3 because they were able to find more words in a shorter time. Completely refreshing the board after each word (option 2) resets the player's ability to find new words by an average of 1 minute. This is because the middle letter must be used to end each word, so players need to think of new words in reverse - or at least find common word endings (-ed, -ing, -ine, -ent, etc.) and try to build on those.

Moving to the manual board design and option 3 had several major benefits:

The custom level builder is probably the most exciting benefit (though special boards is also pretty cool)! We decided to make the level builder available in a future release of Word Portal. Players will be able to design boards to share online with their friends or the entire Word Portal community. It will be very interesting to see how this gets used and how many great and challenging levels players can come up with.

In the end, we were able to get procedural level generation working for Word Portal by taking some advice from Jason Cahill of the Wordament team: look at what you do to manually create your best boards and reproduce that with computer code. This was much easier said than done, but going back to the drawing board, we came up with a set of rules:
1. Create a list of common word endings (ing, ed, est, ene, ese, etc.).
2. Pseudo-randomly pick one (we actually duplicate the most popular ones to weight them heavier)
3. Put the last letter of this in the center and the remaining letter(s) in random positions in the inner ring.
4. Find words in the "common" dictionary (a dictionary of the most frequently-used English words - we picked 5000 of them with 3-12 letters) and add them to the board as follows:
  a. Test the word to (a) ensure it wasn't already used and (b) doesn't end up putting too many repeated letters on the board (e.g.: more than 4 letter "E")
  b. Truncate to remove the suffix already on the board
  c. Put roughly 1/3 of the letters in the inner ring and the remaining letters in the outer ring.
5. Repeat until 3 or less letter spots remain.
6. Fill the remaining spots with letters not in use or least frequent (1x usually).
7. If a Q is being added to the board, it MUST go in the outer ring and a U is added at the same time.
8. Rare letters like Q, X, Z, J, etc. can only appear once in the board.

There are a few other rules, but that the gist of it. In order to validate our letter boards, we test each one on completion using code that knows nothing about the words in the board that was just created. This takes significantly longer than the board creation process due to the way words are constructed in Word Portal. However, we are able to hand-pick the best boards from this procedural generation process to ensure that they have at least 200 words 3-12 letters in length, at least one word 9-12 letters long and more than ten 100+ point words.