Algorithm for generating a course for the game Scrabble

Good day, Habr!

In this article I will talk about how I created artificial intelligence for the game Scrabble. Details under the cut.

Scrabble

Erudite is a domestic analogue of the world-famous game Scrabble - a board game that can be played by 2 to 4 people by laying out words from the letters they have in the playing field. The playing field consists of 15 x 15, that is, 225 cells in which participants in the game make up words. Each composed word brings points depending on the value of the letters and cells used.
')
The field for the game Scrabble looks like this:


Figure 1. Playground

Fundamental rules

Usually the rules are negotiated by players before the game starts, but there are some generally accepted rules of the game:

• At the beginning of the game, each player is given seven chips. In one move, you can put a few words. Each new word must be in contact (have a common letter or letters) with previously laid out words. Words are read only horizontally from left to right and vertically from top to bottom.
• If a player does not want or can not lay out a single word, he has the right to change any number of his letters, having missed the move.
• If the player has used all seven chips during the turn, then he receives an additional 15 points.
• The sum of the points of each move consists of the sum of the points made up of letters, as well as the bonuses received for placing letters on the bonus cells.
• Bonus cells for letters: the points of a letter located on a green cell doubled, on a yellow one they triple.
• Bonus cells for words: if one of the letters of the word is located on the blue cell, the sum of the points of the whole word doubles, on the red one it is tripled.

The first steps

Before developing an algorithm for generating a move, it is necessary to figure out which words and where can be placed on the field. To do this, it suffices to find how to construct all possible words horizontally in the field — the construction along the vertical is obtained in the same way.

We introduce two definitions:
The prefix of a word is any successive set of letters of a word, starting with the first letter of the word, but not including the last.

A word suffix is any consecutive set of letters of a word, ending in the last letter of a word, but not including the first.

Anchor points

Figure 2. The row under consideration

Consider the series shown in the figure above. It is necessary to find all the words that can be built in this series. According to the rules of the game, any word must include an existing letter from a number. Then the places where you can form a word are empty cells adjacent to already occupied cells. We call these cells points of attachment (English acnhor ). There are five anchor points in this row, which are highlighted in red in the figure below.


Figure 3. Anchor points

Once all the anchor points are found, it is necessary to find the possible number of prefix letters for the anchor points that will form the word. If the cell adjacent to the left of the anchor point is occupied, then it is used as part of the prefix of the word being composed. In this case, the possible number of letters of the prefix is ​​fixed. If this cell is empty, the prefix is ​​formed from the letters of the player and then the number of letters of the prefix is ​​limited by the distance to the nearest non-empty one or the cell's anchor point.


Figure 4. Possible number of prefix letters

Algorithm for finding words in a row

For each cell that is an anchor point, we search for all possible words as follows:

1. Find all possible prefixes associated with a given anchor point and satisfying the possible prefix length specified for the anchor point.
2. For each prefix found in the paragraph above, find all suitable suffixes that will form together with the prefix a word from the dictionary. Suffixes are built using the letters of the player or the letters already on the field.

The word prefix will contain either cells from the player’s hand or cells already placed on the board, but not simultaneously.

Now, having a way to find all the words on the field, you can go directly to the description of the algorithms for generating a turn.

Algorithms for generating progress

I chose three algorithms for generating a move: the algorithm for selecting the maximum value, the brute force method, the alpha-beta cut-off method.

Algorithm for choosing the maximum value

At each iteration of the method, a word is searched that will bring in more points than the others. After finding this word, it is laid out on the field and the search is performed again for a new position and a new set of letters in the hand until at some step the set of found words is empty.

The main problem of this algorithm is that the resulting set of words will not necessarily be the best move in this position in terms of the number of points it will bring.

Brute force method

The second method of generating a move is a complete bust. Brute force - a method of finding a solution by exhausting all sorts of options. First, all the words that can be composed on the field in this position are searched. Then, for each new position and new letters in the hand, obtained by placing this word on the field, the previous actions are repeated. This continues until the set of words to be composed is empty.
As a result of the method, all possible moves that can be made by a player in a given position will be considered. Among these moves, the one that gives the most points is chosen.

The main problem of the method is speed. In order to increase the speed of the method, it is possible to memorize the positions and letters recurring during the placement of words on the hand, that is, to use dynamic programming.

Alpha-beta clipping method

Minimax is a decision rule for minimizing potential losses that cannot be prevented during the worst case scenario for a player. An improvement of this method is its modification - the alpha-beta cut-off method. The alpha-beta cut-off method is based on the idea that the evaluation of the branch of the search tree can be terminated early if it was found that for this branch the value of the estimating function is in any case worse than that calculated for the previous branch.

The algorithm of the method is as follows: first, all possible moves in a given position are searched. Then, for the resulting positions, all possible moves are searched by the opponent in the new position. These actions are repeated exactly as many times as the depth of the analysis of the initial position. In the resulting position tree, a move is sought such that the difference in points between the player and the opponent will be maximized.

The main disadvantage of this method lies in the fact that throughout almost the entire game the letters of the opponent are unknown. Therefore, it makes sense to use this algorithm only at the end of the game - when all the letters are used, except for the letters in the hands of the players.

results

For implementation, I used the Java programming language. The dictionary consisted of 12 thousand words, the program was presented in the form of the usual Set'a.

The average generation time is shown in the diagram below:

Figure 5. Generation timeline

The research sample included 100 different sequences of the appearance of letters issued to players (according to the stack principle). As a result, about 1500 different combinations of letters on the hand and positions were considered.

However, the gain in generation time led to a loss on points: the algorithm for choosing the maximum value on average brings the player about 30 points, while the other methods - about 60 points.

Todo

Unfortunately, the following points were excluded from consideration:

• Analysis of combinations with rare letters
• Analysis of letters remaining after the move
• Analysis of further actions of the enemy
• Letters that should be changed when skipping a move

Basically, the first two points rely on the use of rare letters, such as “ E ” and “ Kommersant ”, as well as the balance between vowels and consonants in the hands of the player. Analysis of the actions of the enemy includes attempts to prevent moves that pass through bonus cells. The study of the above points should improve the operation of the algorithm.

Literature

• Lecture by Peter Norvig on the game Scrabble. From this source borrowed the most ideas.
• Game rules
• Brute force wiki
• The Great Thomas Kormen: Algorithms. Construction and analysis.
• Alpha beta cut

Thanks for attention!