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.)
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:
- Add a starting node to the graph, connect it to all the regular nodes
- Map the graph into a dictionary using the method above
- Play this game using that dictionary, starting at the starting node
- Use the strategy that is better than a brute force search to acquire knowledge of the existence of the Hamiltonian Circuit
- Win a million dollars.