Solve the word game Ghost (as seen on xkcd) - spelling letters without making a word

Question

How can one solve the word game Ghost? Ghost is a two player word game. Players take turns adding letters to a growing word fragment.

Quoting Randall Munroe

To play Ghost, you alternate saying letters. The first person to either (a) spell a word, or (b) create a string that cannot be the start of a word, loses. So you alternate building a word, and you have to always be working toward a word, but you can’t be the one to end it. Sample games, with players one and two alternating letters:

G-A-M-E — Player 1 loses by spelling “Game”

A-B-S-O-R-B — Player 2 loses by spelling “ABSORB”

B-Z-”Challenge” — Player 1, seeing “Z”, says “Challenge.” meaning “I think you’re not building toward a word. Name a word that starts with ‘BZ’ and prove you’re not just making stuff up.” Player 2 can’t, and loses. If he could, he’d win.

Munroe then blags that he solved the game (against a particular dictionary) on a flight. He

• asserts the first player can always win
• exhibits a short crib sheet the first player can use to gaurantee a win
• exhibits a short crib sheet the second player can use to win if the first player errs

For example, if the first player opens with 'L', the second player can reply with another 'L', forcing the first player to lose at 'LLAMA'.

Munroe didn't share his algorithm or his code :( How did he solve Ghost?

---

There's also a harder variant where letters can be prepended to the word fragment.

Answer 1

To solve for a dictionary--

You create a tree structure where the root node is no letters, and each child node is the result of adding the next letter in a word to a tree.

The leaf nodes are complete words (you can throw away words that have an initial subset that is also a complete word).

When you've built the complete tree and have all the leaf nodes, the leaf nodes with an odd-number of letters are goals for player two and the nodes with an even number of letters are goals for player 1.

You go up a level; if all the nodes beneath a given node are goals for player x, that node also becomes a goal for player x; or if any of the nodes beneath a given node are goals for player x, and the node will be hit on player x's turn, that node becomes a goal for player x.

If a single character node is a goal for player 1, player 1 can always win the game.