What is the optimal strategy for the Dictionary Game?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.")

Answer 4

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

Answer 5

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.