# What is the optimal strategy for the Dictionary Game?

In the Dictionary Game, players take turns saying English words. The first player starts by choosing any word, which splits the dictionary in two parts. The next player chooses a part and picks a word in that part which will split that part into two smaller parts. This continues until a player is no longer able to find a word.

Note that the players do not actually use a dictionary, they can only say words they know. Additionally, when a player says a word the other player doesn't know, the other players will learn the word and be able to use it in a future round. Here's an example game between two players:

Here is an example game between three players:

Player 1: puzzle - parts are * - puzzle and puzzle - *
Player 2: game - parts are * - game and game - puzzle
Player 3: hard - parts are game - hard and hard - puzzle
Player 1: hat - parts are hard - hat and hat - puzzle
Player 2: has - parts are hard - has and has - hat
Player 3: I don't know any words between "hard" and "hat" other than "has"

Player 3 loses, and players 1 and 2 gain a point.

What is the optimal strategy, assuming the game is played between $$n$$ players $$m$$ times?

• Hmm.. Usually, if there are more than $2$ players, then the strategy will be "biased" as if they may cooperate with other players or stuffs.. And also, why do we need $m$? The strategy usually works with $1$ game, and just apply the same strategy for the other games.. – athin Apr 26 at 5:59
• The players are not allowed to communicate, and that they can't use the words they play to communicate with the other players. You can assume that all players are interested in winning. $m$ is needed since playing the game several time will help you figure out which words other players don't know, or if they know more words than you. – Stefan Apr 26 at 6:04
• @athin You need m because, if you use the same strategy every iteration, you can't win, you can only tie. – João Mendes Apr 26 at 15:22
• Looks like player three was in haste to leave the game. – Brandon_J Apr 26 at 19:05
• @Brandon_J Eager to get back to their harum? – Rubio May 6 at 9:46

Let's assume every player knows the exact same list of words. Player 1 can ensure a loss for player 3 on the first turn by selecting the second word from the list. This allows player 2 to pick the first word, leaving no possible words for player 3. (Equivalently, player 1 can pick the second-to-last word, allowing player 2 to pick the last one.)

Say the dictionary consists of the words aardvark, beerdvark, ceerdvark, ..., zeerdvark.

Player 1: beerdvark - parts are * - beerdvark and beerdvark - *
Player 2: aardvark - parts are * - aardvark and aardvark - beerdvark
Player 3: I don't know any words before "beerdvark" other than "aardvark".

Player 3 loses, and players 1 and 2 gain a point.

• This is good enough to force a loss, but it leads to a tie, not a win. Is there an alternating strategy that player 1 or 2 can use such that they can actually win after m rounds? – João Mendes Apr 26 at 15:24
• Player 2 can also play "deerdvark". – Bass Apr 27 at 12:19
• @Bass Hmm that's a good point. – jafe Apr 27 at 16:14
• @Bass Although no, playing D is worse for p2. With A p2 always wins, whereas by playing D they give p3 the opportunity to play F which would make p2 lose. – jafe Apr 27 at 18:10

In the unrealistic case of there being two players, both knowing the same $$n$$ words then it really is a type of Nim game. If $$n$$ is odd, then the first player can always win, and if $$n$$ is even then the second player can always win.

Whenever a word is played, it results in two ranges of words from which the next player has to choose a word. One or both of those ranges may be empty, containing zero words.
The winning strategy is to always choose a word from a range containing an odd number of words, and in doing so split that range into two ranges that both have an even number of words (or empty, as zero is even). The opponent either loses immediately when both ranges are empty, or else will have to choose a word from one of those even ranges and thereby leave one range with an odd number of words.

I'm not sure how mathematically rigorously you can analyze this game, given that

1. the players are not playing under the same set of conditions (dictionaries)
2. the conditions change as the game progresses (the players learn words from their opponents).

If everybody agrees to use the exact same dictionary to get their words from, then the game can be considered a heavily modified form of Grundy's game, which is a Nim variant where the players split an initial heap into smaller heaps of unequal size, until someone is given a position with only heaps of size 1 and 2, at which point that someone has lost. In this case, the initial heap is all the words in the dictionary, and the players then take turns splitting it into smaller heaps using the words.

The main modifications for this game, which in my opinion make it more difficult to analyze, are:

• there are potentially more than two players (Nim and Nim-variants assume only two players are playing)
• whenever one of the two existing heaps is used, the other one can no longer be acted upon.

So far, I haven't been able to find any existing research or informal work done on games with these restrictions; if you happen to stumble across some, let me know!

Without dictionaries, it becomes a lot more complex. I can see metagaming becoming more prevalent, which essentially turns the game into a subjective analysis of what you think others will do. I don't know how much rigorous game theory you can apply in this scenario other than what people already do to construct the "meta" for a game.

Given all this, I'm inclined to believe that there is no optimal strategy, but there are ways you can increase your chance of winning, such as

• having a very, very large vocabulary (or memorizing esoteric words from the dictionary)
• going first, if you're playing with a very large group
• always choosing a "midpoint" word between two "endpoint" words e.g. playing "nine" instead of "Nim" if you're given nil - nip. This ensures that your opponents get heaps that are of minimal possible size.

(Side note: There's also a potential loophole of people saying words that aren't valid but can't be challenged under the current rule set, and this could go on to infinity (a - ab $$\rightarrow$$ aa - ab $$\rightarrow$$ aaa - ab $$\rightarrow$$ aaaa - ab $$\rightarrow \cdots$$). Unless OP declares that that's a valid strategy, I believe there need to be more restrictions on what qualifies as a "word.")

• Aa is actually an English word: basaltic lava forming very rough, jagged masses with a light frothy texture. Ab is one abdominal muscle, usually referred to in plural. (I remember this stuff because I wrote the internet's top Scrabble-type game in 1996.) – Swiss Frank Apr 26 at 12:46

Long time Puzzling.SE reader, first time answering. I believe I have a potentially optimal strategy for this puzzle, though it relies on the foreknowledge that each player only uses a specific set of words. The strategy involves leaving a specific amount of possible words after your turn.

For example, say we have a dictionary/vocabulary that consists of aa, ab, ac,...az.

For $$n$$ number of players, you will attempt to limit the possible words remaining to $$n$$ or $$n + 1$$ words remaining. So for instance, with 3 players:

Player 1: af - parts are * - af and af - *.
Player 2: ap - parts are * - af and af - ap.
Player 3: al - parts are af - al and al - ap.
Player 1: ak - parts are ak - al and al - ap.

At this point, Player 1 has eliminated all possible words from the left part of the alphabet and left only three possible words on the right side (am, an, ao). Regardless of the word chosen, two words will remain.

Player 2: an - parts are al - an and an - ap.
Player 3: am - parts are am - an and an - ap.
Player 1: ao - parts are an - ao and ao - ap.
Player 2: I can't think of any words between an - ap except for ao.

For $$n + 1$$ words left, Player 1 just needs to select aj instead of ak, leaving 4 moves, thus causing Player 3 to lose the round. Alternating this strategy between playing for $$n$$ or $$n + 1$$ words remaining should amount to a victory for Player 1 where $$m > 2$$.

• In your first example, after Player 2 states 'ap', I think the ranges should instead be af - ap and ap - *. The new word is always the inner value. – Phlarx Apr 29 at 15:42

The optimal strategy is to pick words that can be built on. So if you end up with has and hat, then pick haste. That's between both of them and from there, you narrow down with tenses. Haste-Hasty-Hat.

Playing a word that ends in y will force them to only build in one direction, between Haste and Hasty. They might say Haste-Hasten-Hasty. From there you can you can keep going between either of them until there is no other form of the words. Hastens, Hastes, Hasting. It just really becomes a trial of who knows their conjugations the best, and who can plan far enough ahead to make sure that they will be the one to have the last word.

Edit
Planning ahead, as in knowing roughly how many word options are left. More than 5? Doesn't matter. Less than 5? Then based on how many people and when it would become your turn again, choose a word in the middle to give your opponents a narrower range and end before your turn, or perhaps choose a word that is right after another to keep the range wide enough that you'll have another turn before the number of words run out.

• This will make the game go on longer, but it's not clear how choosing words with many conjugations actually helps you win. As you point out, it just turns into who knows their conjugations better, so this is a sub-optimal strategy for someone who doesn't know them very well. Basically, this answer boils down to two things: "know more words than your opponent" and "plan far enough ahead", the latter of which is so non-specific it's meaningless. – Nuclear Wang Apr 26 at 14:32