# Word game - possible to play all words?

You're trapped in a chamber and the only way out is to beat the chamber guardian on his own game: Word88.

Both of you each take a turn to play a word. You can play one of the following:

• Example: to -> toy, man -> mean
2. Change Play - Change a character on the current word

• Example: love -> live, pan -> par
3. Anagram Play - rearrange all the characters to form a new word

• Example: live -> evil, dog -> god

The game ends where one player are unable to play the next move and loses the game.

Here's a prototype for the game:

http://word88vs.com/

and uses the dictionary at:

http://word88vs.com/Dictionary.txt

What's a good strategy to win the game? Regardless of playing first or second, without having to brute force all the possibilities?

Extra question: If both players collaborate, Is there a way to play all the words in the dictionary?

• Are we allowed to use a word more than once?
– Bass
Mar 13 '18 at 5:19
• @Bass no, we are not allowed. Otherwise both players can just keep playing anagrams back and forth and will have no progression. Mar 13 '18 at 5:22
• Does "Regardless of playing first or second" mean we can choose whether to go first for second for our strategy? Or that we should be able to win from both first and second positions? The latter is impossible since the existence of a winning strategy for going first naturally excludes the possibility of a winning strategy for going second and vice versa. Mar 22 '18 at 5:07
• In other words, you are not necessarily looking for a winning strategy but just a "good" one. In that case I would argue that, barring the discovery of a complete solution, the question is too broad in it's current state. The definition of a "good" strategy that doesn't guarantee a win is very hard if not impossible to define. Furthermore, consensus on what strategies are "good" for unsolved games often evolve over time. Mar 22 '18 at 17:07
• The two links are broken. May 30 '18 at 10:14

I think the answer is that

there is no meaningful strategy that doesn't amount to a brute force search.

That follows from the observation that

If such a strategy existed, you could use this game to effectively solve several graph theoretical problems known to be in NP, like finding a Hamiltonian Circuit.

To do so, you would represent the graph as a dictionary of same-length words, and then you would play this game using that dictionary, and at every choice you make, you'd have to check which words are still accessible. (Disclaimer: I haven't actually created a method for mapping an arbitrary graph onto a dictionary. On the surface, it seems doable, since you can add intermediate nodes to an edge without affecting the shape of the graph, and you can make the words arbitrarily long to accommodate all the required adjacency. There may be some unseen hurdles yet, though.)

Or in other words,

This game is NP-hard.

EDIT: here's one possible way to map an arbitrary graph into a Word88 dictionary. It's not very well thought out, and the number of possible links is finite, (although extremely large) because my brain started hurting when I tried to allow unlimited links. The number of nodes is unlimited though.

Let's say we want to represent the [complete $K_5$ graph].

• Firstly, to avoid anagramming leakage, number the nodes in unary.

• Secondly, to avoid replacement leakage, repeat every character.

I used "A" for node names, underscores for padding to same length, numbers for link layers, and the letter pair X,Y for the first order link group. You can replace them with any unique characters if you want a more dictionary-looking dictionary

Name       Link layer Link group     Comment
AA________ 00         XX             Node 1
AAAA______ 00         XX             Node 2
AAAAAA____ 00         XX             Node 3
AAAAAAAA__ 00         XX             Node 4
AAAAAAAAAA 00         XX             Node 5

AAA_______ 00         XX             Link 1 to 2
AAAAA_____ 00         XX                  2 to 3
AAAAAAA___ 00         XX                  3 to 4
AAAAAAAAA_ 00         XX                  4 to 5

Link node 1 to node 3
AA________ 10         XX              Switch to
AA________ 11         XX              link layer 1
AAA_______ 11         XX              to skip over
AAAA______ 11         XX              intermediate
AAAAA_____ 11         XX              nodes and links
AAAAAA____ 11         XX
AAAAAA____ 10         XX

link node 1 to node 4
AA________ 20         XX              Yet another
AAA_______ 22         XX
AAAA______ 22         XX
AAAAA_____ 22         XX
AAAAAA____ 22         XX
AAAAAAA___ 22         XX
AAAAAAAA__ 22         XX
AAAAAAAA__ 20         XX

link node 1 to node 5
AA________ 00         YX              If you run out
AA________ 10         YY              identifiers,
AA________ 11         YY              change the link
AAA_______ 11         YY              group to reuse
AAAA______ 11         YY              identifiers
AAAAA_____ 11         YY
AAAAAA____ 11         YY
AAAAAAA___ 11         YY
AAAAAAAA__ 11         YY              (you can also have
AAAAAAAAA_ 11         YY               groups of groups,
AAAAAAAAAA 11         YY               and so on, if you
AAAAAAAAAA 10         YY               need them, so the
AAAAAAAAAA 00         YY               name space is Very
AAAAAAAAAA 00         YX               Large.)

etc etc.


To get the words to add to the dictionary, write everything except the comment field together.

Since the winning strategy to this game requires, as a subproblem, the knowledge of whether or not there is a path visiting all the remaining nodes, you can solve the Hamiltonian Circuit problem like this:

1. Add a starting node to the graph, connect it to all the regular nodes
2. Map the graph into a dictionary using the method above
3. Play this game using that dictionary, starting at the starting node
4. Use the strategy that is better than a brute force search to acquire knowledge of the existence of the Hamiltonian Circuit
5. Win a million dollars.
• The generalized problem with any dictionnary might be NP-complete, but this doesn't say that given this dictionnary, there's no smart shortcut. Personally, I'd try to first find all the dead-ends, this should be doable easily if you have the graph I guess. Then the goal is to send the other player to that dead end. Notice that we can't remove letters, this games reminds me of nim Mar 13 '18 at 12:50
• @FlorianBourse just finding a dead end isn't enough, you need a dead end where the length of every path finally leading to the dead end has the same parity, otherwise it may be you that gets stuck in the dead end. Also you need your opponent to step into the wrong spot so you can drive the game into the dead end with your opponent to move. And since we are making a general strategy, the opponent will resist that, so you'll have to figure out a way of forcing your opponent to step on the wrong spot, and oh look it's a brute force search.
– Bass
Mar 13 '18 at 13:03

Extra question:

It is not possible to play all the words in the dictionary. Take for example the words ZZZ and ZUZ. They can only be reached from each other, but never from any other word.

• Z->ZZ->ZZZ->ZUZ Mar 14 '18 at 0:49
• @TrojanByAccident Neither Z nor ZZ are in the used dictionary. Even if, it would present a dead end.
– w l
Mar 14 '18 at 7:53

The rules of the game are a little ambiguous - they just say the first player plays "a word". If you can play any word of any length then the obvious strategy is to play the longest word that cannot be changed by any of the 3 play options and win on the first turn! However the online simulation only allows a single letter word to be played first (very limiting - there only two or three of these)

The longest words in the dictionary the game uses are 15 characters long, of which there are 3157. Assuming this is allowed, playing one of these words first is the most limiting, as you cannot use Add Play (because the dictionary does not recognise any 16 character words); and of course the more complex the word, the less likely you will be able to make an acceptable anagram or make an acceptable word by changing just one letter.

ZOOGEOGRAPHICAL for example is 15 characters long and so cannot be appended to. There are no acceptable single-word anagrams of this word, and I cannot think of a word that can be made by changing a single letter.

If however the rules of the game are such that only one-letter words (eg "A" or "I") may be played first, the best strategy would be to force the other player into a situation where they are presented with a long word that cannot be appended, changed, or used as an anagram.

This is not fool proof, but ideally each of your turns should:

1. Be an "Add Play", to make the word longer and therefore more complex,
and
2. Try to create a word which cannot be easily changed, or *at the very least cannot be added to". Hopefully, if the other player can make a turn they will only be able to make an anagram or change it, allowing you to use "add play" and once again force a more complex word.

In general, try to think more than one step ahead. Before playing a word, think of the options that word will give the other player.

Another very general strategy revolves around the use of Add Play with the letters "S" and "Y". Pluralising a word by adding "S" is an obvious turn on many words, and once played removes an option from the other player. Unless they can anagram it so the S is not at the end of the word, they are limited to changing the root word. Adding a different letter to make a new word may give the next player the easy option of pluralising. However, DO still think ahead to the next player's turn. If for example you turned LENGTH into LENGTHS, the other player could change it to LENGTHY - and then you're scuppered.

As for the bonus question of working together to play every word: I'm not checking all 178696 words, but I don't believe it is possible.

Sticking with the 15 character words in the game's dictionary and assuming you could even get that far, the word XEROGRAPHICALLY has no anagrams and so could not be reached that way. There are no other 15-letter words that contain "-EROGRAPHICALLY" so the X could not be introduced to the beginning of the word either by Add Play or by Change Play. This word could never be played.

• Presumably, the initial word is "", meaning the first action that must be taken is "add play". May 30 '18 at 13:48
• @IanMacDonald Really?? So the first play is ALWAYS either "I" or "A"? This is nowhere in the rules... it says you begin by playing "a word". If this question is all about a strategy that must begin with a choice of just two one-letter words then the "correct" answer to this puzzle can only be A or I. What a massive, massive waste of time. May 30 '18 at 14:51
• None of the only three rules are "play a multi-letter word". But the choice of which letter to play first does not at all dictate a sound strategy for the remainder of the game play. The purpose of this question is to produce such a strategy. May 30 '18 at 16:06
• @IanMacDonald I think you might have got that back-to-front... I agree the rules don't say you must play a multi-letter word. My point is that the rules don't prohibit it either - and yet the AI of the online game does. I quite enjoyed approaching this puzzle with logic and probability - I wouldn't have bothered if it was genuinely about developing a real strategy for this game. You might as well develop a strategy for tic-tac-toe. Or conkers. May 30 '18 at 16:14
• I think you got the right answer, but didn't formulate it properly : The best strategy is to use "Add Play" whenever possible, because the more letters there are, the harder it will be to find new combinations that works. May 31 '18 at 11:47

There is only one way I figure the game can end: to steer the word into a word that cant have anagrams or substitutions. Since there is no play available to subtract letters, adding that last decisive letter will make you the winner. However, it could easily backfire if the opponent detects it.

The trick is to be

the one to add a letter that makes the word unplayable. For eg: if (somehow), you manage to land on the word Rhythm, then add s to make it rhythms, and i doubt there is a play left.Though i don't think arriving at Rhythm is going to be easy or even possible,this was just as an example. Someone might find a substitution for rhythms i hadn't thought. But the key is finding a word like this.

If we were able to make the dictionary a multilinked tree where children were defined based on the available plays, then this word would be a leaf. Just a thought

Might work

• Hello and welcome to PSE. Please hide your answers in a spoiler. May 30 '18 at 10:18

One strategy is to

Steer the word into what you want, so that they can’t change the word and they lose

Example:

They go first, play A.
You go next and play AA (aiming for one of the three or 4 letter A words).
They play AAH.
You see a chance and change it to AAL (idk what exactly that is, but...) .
They, undaunted, anagram it to ALA.
You now seize and change it to AHA.

This can go on for some time, but as long as you keep your wits about you and control the flow, you can win fairly easily

• Can you elaborate on this a bit maybe? I don't see why this wouldn't potentially backfire on you if your opponent has the exact same strategy here. Mar 13 '18 at 13:09
• Well with that, you could just rearrange back to AAH, right? Mar 13 '18 at 16:40
• @Paige not from what I understand. If that was possible. the game could never end. Then they could each just revert to the previous one Mar 14 '18 at 0:50
• @Levieux any strategy can potentially backfire on you, especially if your opponent has the same one Mar 14 '18 at 0:51
• @Paige see op’s comment above puzzling.stackexchange.com/questions/61811/… Mar 14 '18 at 4:35