[I got into playing Words With Friends on Facebook and my mobile phone back in 2012, and started writing a lengthy article on designing an AI to play scrabble-like games in a manner that convincingly simulates a learning human. This weekend, several years later, I’m a spectator at a local Scrabble tournament, and decided to finally finish up my thoughts.]
Designing AI for Scrabble-like games
I’ve been playing the Zynga game Words with Friends with various people for a few weeks, and have gotten progressively better at the game. After looking back and reflecting on the evolution of my play, and the development of my strategy, I became inspired by the idea of a convincingly human-like AI that embodied the various stages of my development as a player.
While actually programming it is a little more effort than I want to put into it, even just thinking about the design for such an AI is interesting.
Note: There is a very well-done Words With Friends Cheat at blogmybrain.com which I borrow some concepts and inspiration from. (Now that my human opponents will be reading this, they’ll probably accuse me of cheating against them. (Maybe I was at times!) Actually, I learned quite a bit from using the cheater, but I learned even more by playing players who are better than me repeatedly, and watching how they would beat me, and the more I improved, the less helpful I found the cheater.)
The move picking rules from this cheat would potentially make an excellent starting point for an AI that directly plays the game. The cheat doesn’t go as far as making moves for you in the game, or reading the game data directly, so the cheater has to convey data between the game and the cheat.
This cheater is technologically fascinating, although I haven’t begun to try to understand it yet, but it isn’t quite what I’m thinking of in terms of an AI, as its goal is to play at a high level of play consistently for a simulated player of a given educational level. A more human-like AI would be a little less consistent, and perhaps might employ a bit deeper strategy.
If I were very serious about doing a good job of creating a humanlike AI — like, if someone were paying me to do it — I would want to study a wide variety of players to get a feel for different styles of play beyond my own. The best way to do that would be to record every game played by the game in production, and create statistical models of that data. This data model would be somewhat suspect, due to the possibility of bots and cheaters, but it would contain a great amount of useful data, and I’d imagine it’d be possible to filter out the more egregious suspect data through clever analysis. Every player has their own style and skill level, and I’d like to learn not just how I play, but how lots of people play.
I don’t have the resources to do that, myself, so I can only model my AI design on my own insights about my own play, and maybe a little of what I glean from my opponents. I noticed as time went on as I played, I went through several phases of development as I learned to play better. Each of these phases could be taken to be a basis for a distinct AI personality.
There are certainly other approaches to play possible that I have not considered, so I don’t mean to suggest that these “personalities” are exhaustive.
Elements to strategy
I assume people are familiar enough with Scrabble-like games that I don’t need to go into a lot of detail about the way the game is played. However, it is still worthwhile to identify game elements that influence strategy. The game has a number of features to it which can contribute information to the player’s strategy.
Letter point value
Every letter has a predefined point value, based on the rarity of the letter in English words. Playing higher-point value letters is generally a good thing. However, a smarter player will try to position the high letters in words that allow them to multiply their value (see below).
Generally, the more letters you play, the more points you score.
However, it would be an extremely naïve strategy to try to play the longest possible word that you can make with your rack. Long words expose a lot of surface area, which your opponent can exploit on the next turn. We’ll discuss this in more detail under Board Position.
Using all 7 letters in your rack is called a “Bingo”. Playing a bingo gives a large bonus to the score that turn. These are rare occurrences, normally, although a player can help influence their odds of getting tiles that can result in a bingo. Through clever rack management, a player can hold common suffix and prefix letters (ING, LY, ATE, OUS, RE, PRE, DE, TION, etc.) and then wait for a common three or four letter word to combine them with, to use all 7 tiles.
Playing a bingo opens the player to some liability, due to the amount of surface area they usually expose and the number of attachment points that grant access to hot spots. If a human player recognizes that they have a Bingo in their rack, they are normally very likely to play it. Some players may opt not to play a bingo in the early game if it presents an opportunity for the opponent’s next move to be a big score, although they are a powerful and intimidating opening move. Bingos are very powerful in the mid-game, when the board has less open space, and fitting a 7-tile play into the remaining open space can close more of the board, and put up big points.
It may be somewhat common for a human player to fail to recognize the Bingo they have in their rack. Being able to anagram quickly is not an easy skill for most people. Some are naturally good at it, and we can expect such people to have greater ease with identifying a Bingo. I suspect that many players don’t look very hard for words that have more than 4-5 letters to play, whether due to being of lower skill, or due to playing a strategy that does not depend strongly on playing Bingos.
Playing the board, or focusing on board position pays off more than playing longer words does. So this is not just a matter of intelligence or laziness on the part of the player – it’s also reasonable to say it’s good strategy not to spend a lot of time/effort looking for 6 and 7 letter plays.
Certain tiles on the playing board give a multiplier to the letter or the entire word played.
It is desirable to play words that land on these tiles.
Word multipliers are usually more valuable than Letter multipliers. But if you can play a letter multiplier as a corner of two words, it can be very powerful (cf “Compound bonuses”). Playing a high letter on a letter multiplier may be a better move than playing a multiplied word that nets fewer points. Often times there will be situations where a longer word is possible, but the high-value letter in that word would get shifted off of a letter multiple, resulting in a lower score for a larger word.
It is especially desirable to play moves that land on multiple bonus squares. A high letter on a letter multiplier in a word that touches a word multiplier is one of the best moves in the game. The Words With Friends board is a modified Scrabble design, intended to foil copyright lawsuits and to allow greater opportunity for compound bonus moves. DWxDW and DWxTW and even TWxTW are possible, though pretty rare. DL/TLxDW and DL/TLxTW are relatively common and can score very high.
Knowing how many tiles remain can influence decisions made during the game. Some moves are more advantageous earlier in the game than later. This is subtle enough that I’m not entirely sure how to define it; this is currently an area of my strategy that I am still developing.
By knowing the distribution of tiles, and tracking the tiles in your rack and on the board, it’s possible to know which letters remain and how many of each letter, which can help you know the odds that you have of drawing a specific letter.
Generally I have found that a strategy of drawing tiles, hoping for a specific letter is almost never a good way to play, due to the low likelihood of actually drawing the desired tile, the rapidly shifting board positions, and loss of real opportunity while the hoped-for one never materializes.
Current Board Position
Based on the current state of the board (when it is your turn), you have a variety of options. Learning to see the board is important to playing effectively. A more experienced player can quickly assess the board position and determine
- “dead zones” where letters cannot be played.
- “attachment points” where new words can be played easily.
- “hot zones” where bonus tiles are open to play on in the current turn.
- “partials” where words already in play may be extended through adding a prefix or suffix.
- “corners” where letters can be played to make a word in both the vertical and horizontal axis, effectively doubling the corner letter.
Beyond the obvious board position, a master player will be looking for more subtle positional cues:
- “parallels” where two words may be played adjacent, and parallel, creating a long word and a series of perpendicular words.
- “obscure” attachment points, where a crowded part of the board is still open for play for certain letters. Making a “obscure” play is not always a high scoring play, but may be advantageous for defense, as filling in the hole avoids opening more of the board, limiting the opponent’s opportunity to play on a hot zone. It can also be intimidating to a human opponent who is impressed by the player’s ability to see the hidden opportunities on the board.
- “ladders” and “boxes”. Some players may have a preference for trying to create a bridge between two separate parallel words, or create an enclosed area of the board. These moves do not score higher, and I don’t see much of a defensive advantage to playing these types of moves, but may be played due to the player’s aesthetic bias, or may simply be noted as being somewhat uncommon board situations.
Future Board Position
Like in chess, it’s good to try to see a few moves ahead in the game.
It’s not hard at all to see what the board you’ll be leaving your opponent with a move you are considering – what the board will look like after you play the move you’re considering, before you actually play it.
It’s virtually impossible to know exactly what your opponent will do next, absent knowledge of what tiles are in their rack. Depending on what letters they have, their vocabulary, how well they perceive board position factors, they might do anything.
If you are playing against good opponent, they’ll likely try to use an attachment point that allows them to take advantage of a hot spot, in order of value, assuming they have letters that will allow them to. A good opponent will also try to make plays that limit your opportunities to make a play on a hot spot in the next move.
There’s too much hidden information to be able to project more than the next move ahead. Too much can change with each turn, making a very forward looking strategy all but impossible – Scrabble-like games are more entropic than chess, where you can try to play out several moves ahead of the current turn. But you can and should anticipate the way your opponent will likely play the board you’re about to leave him/her. This is simply a matter of considering the attachment points and hotspots of the new board position created by your move.
Advanced strategies take into consideration future board position. This might be called “playing defensively”. Rather than simply playing the highest valued move that you possibly can make in the current turn, it’s necessary to weight that score by a factor of the future board position. This is not too difficult to do, mathematically speaking. Take the points scored by the move under consideration, and subtract a guesstimated value based on the number of attachment points, the value of the open hot spots, and the high value letters already in play which are attachable. It’s a tricky thing to know precisely how to value these things, but as long as we do so consistently, and weight them relatively to their true value in play, it will give much more useful results.
Less sophisticated players don’t look at board position and don’t play defensively. So certain AI personalities shouldn’t employ this in their strategy, or should dial it down somehow, perhaps by weighting the model differently, or by applying it less consistently.
The Game Dictionary
No human knows the entire game dictionary; neither should a humanlike AI. The game program needs to know the entire dictionary, in order to know what plays are legal. But this information should not automatically be known to an AI player. The AI designer should weed through the dictionary and flag every word with a “vocabulary” level, and then design AI personalities with differing vocabularies. By ranking vocabulary words from Common to Educated to Exotic, we should determine a relatively likelihood of the AI knowing the words in the dictionary.
Borrowing from the blogmybrian.com cheater, we might use categories like:
- Middle School and lower
- High School
- World Champion
Depending on the AI’s vocabulary score, it might know a certain percentages of words from the dictionary belonging to each category. Real people don’t know 100% of the words even at the Middle School and lower level, or at least don’t always have the presence of mind to see them when they have the opportunity to play them. So a humanlike AI should not know 100% of the dictionary, even of the words designated as belonging to lower vocabulary rankings. Obviously, it’d be weird for any humanlike AI not to know very common words like THE, MOM, or BOY, so there should be a class of ultra-common words that ought to belong to a base dictionary that all AI would start with.
Unique AI’s vocabularies could be generated automatically by randomly picking N% of the words from each category, diminishing N for each increasing vocabulary category, and using that as the AI’s starting dictionary.
The AI could be made to learn by observing games that it plays, adding to its dictionary new words as it encounters them in play, and possibly also forgetting learned words that it has not seen or used in some time. This time might be gauged by number of turns since last seen, number of games since last seen, or even actual elapsed time since last seen. Forgetting might be randomized so that there is a percentage chance of forgetting a word after enough time has passed, and this chance might be weighted based on the point value of the word (if the AI has a competitive “personality”) and the vocabulary ranking (common words are less likely to be forgotten, but then so are “interesting” or “prestigious” words.) Feeling this out would be tricky for the AI designer, but the best thing to do here would be to put dials on it that could be adjusted easily, or set randomly, or set programmatically according to some learning algorithm.
A more sophisticated learning AI might also rank the words in its dictionary by their base point value. In play, point value can change a great deal depending on placement on bonus tiles. But lesser-skilled humans often think of the word value independent of the position that the word is actually played on.
For example: A lesser skilled player might choose to play CROWS when COWS would be better because the C in COWS would end up on a TL for 12 points, while CROWS puts a 3-point R in its place. But CROWS must be the better word, since it has more letters, and adding their values you get a higher word score, right? A computer wouldn’t make this mistake, but a human of lesser skill often does.
Vocabulary and personality
A more humanlike AI might have certain words that it favors, especially “cool” words. Some human players will play a “prestigious” word to show off their vocabulary, just because they like the word, even if it’s not the highest possible play or the best defensive play. A flirty AI might even favor sexually suggestive words and double entendres to affect a more humanlike style of play. An AI might have its dictionary influenced by interests or mood. Good competitive players tend to be less influenced by the meaning of a word, and more by the point values, but even so the words a player is most familiar with, and has on their mind, will be more likely to pop out at them when their letters appear in the rack than would less familiar words.
Just because an AI happens to have a word in its vocabulary, does not mean that a humanlike AI should always have presence of mind to see that they can play every word in their vocabulary – people sometimes miss things and make mistakes by rushing or overlooking or fixating on something else.
The Tactician’s Dictionary
Once a player becomes serious about playing competitively, they will necessarily begin to look at the dictionary, to enable them to have a tactical advantage with certain letters. Tacticians will play words that are not part of the usual vocabulary of most people, but are well known to other tacticians. Serious players will know most if not all of the 2 and 3 letter words. Many players focus on memorizing words that use the letters Z, Q, J, X, and to a lesser extent, V, P, M, B, C, K. ZQJX are difficult to play without a little bit of vocabulary training to increase opportunities to play known words. Beginner players are often at a disadvantage playing with these tiles, because they only know a few legal words that can use them, miss opportunities with words they don’t know, and hold on to them for too long waiting for the letters they need in order to make a play with them.
Experimentation and “Bullshit” words
In Scrabble-like games, you can play a word you don’t know by guessing it, or bluffing. The opponent may challenge, and if the word is not an official dictionary word, the play is struck and the player loses their turn. This discourages experimentation.
In Words With Friends, you can try anything, and if it’s not a valid word, the game simply doesn’t allow you to play and allows you to make another attempt. You have an unlimited number of attempts. So occasionally you might play words by trying random combinations, hit upon something that works, and maybe even score a lot of points.
Oftentimes you end up with some “bullshit” word that no real person uses or knows, but is in the dictionary anyway. Exotic or archaic or possibly complete fabrications that happen to be in the official dictionary for some reason, playing these words does not feel very humanlike. These moves really feel more like a computer AI employing a brute force technique to find high value plays.
Humans are slower at it, of course, but some players I’ve played with do claim to do this. I say “claim” because it’s a very common response to accusations of cheating, especially if you ask the opponent what the word means and they don’t know.
Thus, an AI attempting to be humanlike should play words like this very sparingly, if ever. A good rule of thumb would be for these words to only be used if the human opponent plays them first, giving the AI the excuse that they “learned” the word from watching the human.
A human will recognize when it should not play a certain move. For example, I was just playing a game where I decided to play EM on a DW, in a corner move that enabled me to use the DW twice, once for each word I made (the other one was EH). I had a U in my rack, so I could have played EMU. But I chose not to. Why?
Because U is more valuable than to be thrown out for an extra four points. It’s early in the game, and if I happen to pick up a Q in the next few moves, I’ll be glad I kept the U. So, the more general rule to extrapolate from this is to look for letters that pair well with more valuable letters, if they are still available, and give a preference to holding them unless the opportunity to use them is too great to pass up. So too, with other “helper” letters that pair well with other letters: C+H, C+K, T+H, T+H+R, S+T+R, L+Y, L+E, vowel dipthong combos, etc.
Also, there’s a defensive aspect to consider. In this board position, if I were to put the U down, it opens up the board to my opponent to play on the two DW tiles on the right side of the board, possibly hitting both for a 4x word multiplier if they happen to have a 5-letter play that can reach both of them. My opponent can still hit the DW’s, but only if they have something they can stick on EM to extend it, which would be U or S. If I put the U there for them, it’s easier for them to play some word that can take advantage of the U. Putting the U there also gives them the potential to reach the two TL’s that are even closer, by adding S to the end of EMU to make EMUS and running a word vertically from there.
Humanlike AI should be capable of making these judgment calls, as well. This is bound to be very tricky, but consistently playing a higher point play while consistently leaving the future position more exposed to high point plays by the opponent is something only a mediocre player would do for a long time without learning from it and introducing some restraint.
S and blank are similarly valuable, despite being worth only 1 point by itself. S is a powerful letter because it can be used to pluralized a great many words, making it very easy to attach to words, usually creating a corner which allows the player to make two words in one move, which is a key way to score a lot of points. Good players recognize this value and will hold onto S’s, using them to maximum advantage.
The blank tiles are similarly valuable due to their versatility. A good player will hold onto them, attempting to use them in situations when they enable a big score. A tournament scrabble player I asked about how to use Blanks is to hold them unless your next best move would be 25 points less than the move you could make with a Blank.
Sometimes a play will be motivated by spite, or desire for revenge.
- Playing a word in such a way that it makes a bonus tile inaccessible. This is a defensive move, known as a block, as in blocking the opponent from being able to play on the bonus tile. This is not necessarily purely spiteful, but simply sound strategy
- Playing off an opponent’s play, particularly immediately after they play a 10pt letter, to try to get something back for it. Especially if the play nets more points than the original word (which is likely unless the original word used a bonus tile). Say you lay down the Q, and your opponent comes back and plays their next move off the Q, and manages to score more points with it than you did. That’s a spite move.
In some cases, spite moves are not optimal from a scoring or defense standpoint, but are played anyway because the player’s spite is such that they are blinded to the other plays they could make, or don’t care about them.
Good players try to make effective use of their letters.
One way of evaluating the value of a move is to look at the ratio of the face value of the letters used compared to the score value of the play. If you play a 20 point word, using 18 points worth of letters, it’s less efficient than a 20 point word that uses 5 points of letters.
Another way of evaluating the value of a move is to look at the ratio of the points scored, against the points scored by the opponent’s next move.
Still another way to evaluate the efficiency of a move is to count re-use of already-played tiles. If a player builds up AX, AXE, TAXED, over the course of several turns, they’ve used the X three times, multiplying its effective value.
Looking at efficiency is a better way to evaluate a move than looking at just the raw point value of the play.
Any AI worthy of the adjective humanlike ought to be sophisticated. A highly sophisticated AI should learn to play better by watching how its opponents play, and noting particularly effective moves, learning new vocabulary words, and even tracking the style of play of the same opponent over a series of games. An AI could simulate learning by arranging the strategic rules in a hierarchy from beginner to advanced, and gradually allowing access to the more advanced branches of the tree over time, and after the AI observes an opponent player making use of the strategy. A true learning AI would need to be able to extrapolate its own strategies, inferring rules from actual play.
A Humanlike AI should not
- Have omniscience.
- Know how which tiles remain in the pile. Knowing how many tiles remain in the pile is a given. But knowing which tiles remain in the pile is not humanlike (unless the game tracks those for the player automatically, as a playing aid). A highly advanced competitive player might well know the distribution of letters in the game, and could know how which letters have not yet been played by keeping tallies of the letters that have been played, and subtracting that count from the known totals for each letter. This is obsessive and no casual human player would do this, apart from serious competitive players.
- Know which tiles are in the opponent’s rack. No human player would ever know which letters are in the opponent’s rack, except at the very end of the game, when it’s possible to infer this when there are 0 tiles remaining in the pile, you can count all letters in play, plus what’s in your rack, to know how many letters your opponent has left, and even what letters they must be.
Of course, there’s nothing stopping a human from looking up the letter distribution counts and tracking the usage of the letters during play to have some good idea of what’s left in the pile and what may be in the opponent’s rack, and there’s even an in-game purchase to automate this. But practically speaking, no one plays like that unless they’re obsessed or very competitive. There is advantage in letter counting confers, but it is probably relatively slight compared to other things a person can do with their brain during the game. This is especially so since letter selection is random.
One area which letter counts might be useful is for players who are using a “holding strategy” – that is, given a certain board position or certain letters in their rack, they see an opportunity for a high scoring play, if only they hold the letters they need and wait for random luck to draw the remaining tile that they need. Knowing the counts would allow a player to know whether the letter they need remains in the pile, and calculate the odds based on the number of occurrences of that letter divided by the size of the pile.
In my personal strategy, I use “holding” very, very little, and so do not value these counts very much. But other players may use “holding” more. The main reason, I don’t use it, apart from it requiring too much effort for the expected benefit, is that board position changes rapidly, and counting on a part of the board to remain open longer than the next two turns is very unreliable – particularly against a strong player who has a good sense of position and identifying hot spots. There is so much opportunity cost in tying up letters – particularly the high value letters that you most often would want to hold if you were going to employ a strategy that uses holding tactics. When I do hold, I never hold more than 2 tiles, and never for more than 2-3 turns at the very most. Any more than that, and my psychology is to feel “stuck” with the letter, that I have nowhere to play it.
Since we’re going for humanlike AI, we won’t bother with using these approaches to build the AI’s strategy.
Passing and Exchanging
A good player will only pass when they cannot make a move and there are no tiles to exchange. Occasionally a good player will pass on the opening move when they have high value letters, but no good words to make with them, in the hopes that the opponent’s opening move will give them better possibilities.
Less-able players will pass more often, because they miss opportunities on the board, and due to having a smaller working vocabulary.
When you make a play, the tiles you use to form your word are called the “lay” and the tiles you have left in your rack are called the “leave”. It’s important to manage your leave so that you will be more likely to have a good selection of tiles left to create your move with in your next turn. If you have a choice between two lays, sometimes it can be better to lay a word that scores you less points, but gives you a better leave. If you give yourself a bad leave, it can put you in a bad position, force you to “dump” or exchange tiles, wasting a move.
As well, it’s often the case when you pick up a high-value tile, Z, Q, J, X, K, V, you will want to hold it for a while until you have a good opportunity to use it effectively. An human-like AI should not immediately play a Z or Q just because it can, and that happens to be the highest point value lay they can make in the immediate turn. A good player will try to hold their high value tiles until an opportunity presents itself to use it on a TL or TW, DLxDW, TLxTW, TLxDW, or DLxTW, or use a cornering move to make a more efficient play. Even an unsophisticated player will try to at least get a x2 multiplier when they lay their high value tile, and choose to hold a high value tile when there is nothing better than a single-efficiency prospect.
Another important aspect to the Leave is that you want to give yourself good letters for the next turn. A play that leaves you with 4 I’s, is a bad leave. A good player may choose a slightly lower scoring move with a word that uses one of those I’s. Generally, the player will want to favor a leave that gives them a balance of vowels and consonants, and letters that work well together in many common words, or that can boost a 3-4-5 letter word into a 7-letter Bingo.
When you have a bad rack, it’s a good idea to consider Exchanging. A bad rack is contextual — sometimes good (high value) letters can be a problem (if there’s nowhere to play them). A good player’s decision to exchange letters will be influenced on what tiles remain in the bag. There’s no sense swapping if the tile you’re hoping for isn’t in the bag. Bad players don’t keep track of what’s in the bag.
Time Between Plays
A computer can compute the next move it will make in a fraction of a second. But playing immediately each and every turn is not very humanlike. It’s certainly very possible for a human to play quickly, particularly if they are analyzing the board while the opponent considers their move, and are ready to play one or more possible moves as soon as the opponent plays their move, depending on what the opponent plays. A human player who isn’t particularly concerned with winning, or playing competitively, may take less time to consider other possible moves and strategy issues, and just play the first thing they see, or the first word that they can form that they “like” for whatever reason. Real humans also do other stuff – they play asynchronously, taking breaks from the game lasting hours or even days as they go about their lives.
A humanlike AI should have some kind of delay when its turn comes up. Perhaps just a few seconds, 5-15. Or perhaps several minutes. There is a great deal of opportunity for simulated humanness here. In addition to all the external factors that may delay a person from making their next move, delay can add significance or drama to a move. Generally, an AI should not delay to such a length that it becomes annoying to the human opponent – perhaps it should be a configurable setting in the game to define the maximum amount of time the AI can wait before playing. But it’s OK if the delay is a little inconsistent. I’m not going to say that we need to go so far as to simulate the AI driving to work, hanging out at a night club, waiting at a restaurant or bank, or anything, but we might have times of day when the AI is more rapid and responsive, and other times of the day when its delayed or distracted, if we decide that’s within scope. This could perhaps be simulated best by datamining the response times of actual humans playing with each other, or by taking after the patterns of the particular human player that the AI is currently facing.
Generally, when a game is close, or when the board position has a larger number of hot spots, the AI should simulate a longer delay before playing its move, to simulate additional time spent thinking. Observing human players and the reasons they spend more time thinking.
I feel that it really is important to include these delays because a human player will fatigue when playing against an opponent who puts pressure on him to play his own moves more quickly, or intimidated by an AI that moves again instantly every time. There is a psychological factor at play which a good humanlike AI should strive to capture, even if it isn’t directly tied in with the calculations that drive picking what move to play.
AI chat is definitely well outside our core feature set for our AI, but some consideration might be given to how we might employ the Chat feature in the game to further round out the humanness of the AI. A cleverbot or Eliza chat bot would be easy to tie in to the AI.
Some further refinement could be added, however, such as whining and taunting, congratulating on good plays, and so on.
The AI could taunt when it makes a particularly good play, or when it senses that the opponent has made a weak play (either by a low score, or by opening a lot of attachment points and/or hot spots, or failing to take advantage of the most valuable hot spots).
The AI could whine when it has poor letter selection, when the opponent makes a particularly good play, or when the opponent plays in a position where the AI could have played a high scoring move.
Canned whines and taunts could be programmed in, or the AI could be programmed to learn them from other players that it faces.