Word game - possible to play all words?

Question

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:

1. Add Play - Add a character to the current word

   • 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?

Answer 1

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
AA________ 22         XX              link layer
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________ 00         YY              link layer
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.

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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