Cover image was generated with Nano Banana 2

Introduction

I love word games and puzzles, so I have one currently under review on the App Store called Criket. Check it out here. One of the games I’m yet to include is the Ghost game because though it looks simple, it has some interesting technical bumps I wanted to explore! Like the Minimax game theory tactic and the Trie data structure. I have built it separately here before I include it in the final app build.

The goal is to build a bot that almost never loses in the Ghost game. If you are not familiar with the Ghost game, it’s the first thing I explain after this paragraph

How to play the game
How to avoid losing
Minimax Game Theory Tactic
Building the word tree (Trie)
Conclusion
References

How to play the game

Players take turns adding letters to a growing word. The goal is to avoid being the one to complete a valid word, as that player loses.

Assuming play resumes and A is played, the next player can play P, making the word AP, then the next player can play P, making the word APP, then the next player can play L, making the word APPL, then the next player can play E, making the word APPLE. Since APPLE is a valid word, the player who played E loses. It is the duty of the other player to highlight the completion of the word. This is called a Word Bluff! Otherwise play continues.

Another type of bluff a player can call is a No Possible Word bluff if they think the current set of letters does not form or lead to a valid word. If so, the player who called the bluff wins. Otherwise, he/she loses.

Below is a flowchart summary

How to avoid losing

My computer science and leetcode muscles never atrophied so I knew exactly what to use : The Trie Data Structure and a Greedy Algorithm. I was right about the Trie because of the optimal time complexities (O(1) and O(N)) in word search and insertions, but wrong about the Greedy approach. I explain why later

Think about it. What do you need to win? You need to know all the words that will never end with you! But also factor in the fact that your opponent might choose other words. The question then becomes... how do you determine these winning paths to force the outcome you want?.

With the greedy approach I thought about, you would choose the best option available right now, which is unrealistic because there is no absolute best option if you can’t predict what your opponent plays. The best option will only be relative to what you have in mind. So if you have Panama in mind, the best option is to play P as the first and hope that your opponent plays along. But they could as well have Peru in mind, so they play E instead.

Instead of choosing the best option right now (greedy approach), minimax game theory tactic simulates the future by pre-computing every possible winning and losing position in the word tree (Trie). So for every letter node, you know whether you are in a winning or losing position. Boom!

Minimax Game Theory Tactic

Lets start with these words in our trie PP and PE. Our word tree (trie) will look like this…

Red nodes are losing positions Green nodes are winning positions

With the rules of the game, we know the endings P and E are losing positions because they complete words, which automatically makes the root P a winning position. Two observations here

If there are no children nodes, the current node is a losing one (the last P and E in the diagram have no children)
If the children are losing positions, the immediate parent node is a winning one.

Now lets expand this tree again…

By adding A as the root to have the words (APP, APE), the board state changes completely.

As established before, the middle P is a Winning node because it can force a terminal loss.
Now look at Root A. Its only move is to P.
Because the opponent at P will now be in a Winning Position, the player at A is in a Losing Position

Now watch what happens when we expand the tree again.

The player at Root A now has a choice: play P (giving the opponent a win) or play N.
N is a terminal word-ender (Loss). By playing N, the current player completes a word and loses.
For the player at Root A, choosing N means the opponent is the one who has to deal with the state after N.
Thus, Root A becomes a Winning Node because it can force the opponent into the terminal loss N.

Let's expand the tree a final time

Finally, expanding AN into ANT changes N from a terminal node to a winning node.

N is no longer a word-ender. ANT is the word.
So the player at N can choose T, forcing the opponent to lose. This makes N a Win.
Now Root A has two choices: move to P (Win for opponent) or move to N (Win for opponent).
Since every possible path from A leads to an opponent's win, Root A is back to being a Losing Node.

In summary

A node is winning if any child is losing
A node is losing if all children are winning

Takes a while to grasp. Grab a pen and paper and draw out different scenarios. It will click eventually!

What you are basically doing throughout is maxing your chances while your opponent tries to minimize them. This is the core idea behind the minimax game theory tactic — to guarantee the best worst-case outcome.

To do this, you need to know all the possible words that can be formed from the current set of letters. This is where the Trie data structure comes in. Then you can start from the base of the tree and assign winning and losing labels to the nodes just like we did progressively with our example above.

Building the word tree (Trie)

Talking about tries is a whole blog on its own. This video explains it best Prefix Tree but here is how the final Trie looks like

Trie.ts

// A node in the trie for each letter
class TrieNode {
    children: Map<string, TrieNode>
    endOfWord: boolean
    isWinning: boolean

    constructor() {
        this.children = new Map()
        this.endOfWord = false // indicates if the node is a complete word
        this.isWinning = false // indicates if the node is a winning node
    }
}

// The complete Trie
class Trie {
    root: TrieNode

    constructor() {
        this.root = new TrieNode()
    }
    
    // Insert a word into the trie
    insert(word: string){
        let curr = this.root
        const lowerWord = word.toLowerCase()
        
        for(let char of lowerWord){
            if(!curr.children.has(char)) {
                curr.children.set(char, new TrieNode())
            }
            curr = curr.children.get(char)!
        }
        
        if (!curr.endOfWord) {
            curr.endOfWord = true
        }
    }

    // Insert many words into the trie
    insertAll(words: string[]) {
        for (const word of words) {
            this.insert(word)
        }
    }

    /**
     * Recursively computes and caches whether each node is a winning or losing state.
     * In Ghost:
     * - Node with endOfWord = TRUE is a LOSS for the player who formed it, thus a WIN for the player currently at this node.
     * - A node is a WIN for the current player if ANY child is a LOSS for the next player.
     * - A node is a LOSS for the current player if ALL children are WINS for the next player.
     */
    computeWinningStates(node: TrieNode = this.root): boolean {
        // If the game ended here (previous player completed a word), the current player wins!
        if (node.endOfWord) {
            node.isWinning = true
            return true
        }

        let canForceWin = false
        // Evaluate all valid subsequent moves (children)
        for (const child of node.children.values()) {
            const childIsWinningForNextPlayer = this.computeWinningStates(child)
            
            // If we can make a move that puts the next player in a losing state, 
            // then our current state is a winning state!
            if (!childIsWinningForNextPlayer) {
                canForceWin = true
            }
        }

        node.isWinning = canForceWin
        return canForceWin
    }
    
    // word call
    search(word: string){
        let curr = this.root
        const lowerWord = word.toLowerCase()
        
        for(let char of lowerWord){
            if(!curr.children.has(char))
                return false
            curr = curr.children.get(char)!
        }
        
        return curr.endOfWord
    }
    
    // bluff call
    startsWith(prefix: string){
        let curr = this.root
        const lowerPrefix = prefix.toLowerCase()
        
        for(let char of lowerPrefix){
            if(!curr.children.has(char))
                return false
            curr = curr.children.get(char)!
        }
        
        return true
    }
}

From here, everything else is just ReactJS and TailwindCSS to hook the Trie to a UI. Find the full code on my GitHub repo..still tweaking it though! Play against the bot here

Conclusion

My first instinct (greedy approach) felt intuitive but broke down the moment I tried to account for an opponent who doesn't cooperate. Minimax forced me to think differently: instead of optimising for right now, you optimise for every possible future, which is a mindset shift that applies well in most games (tictactoe, chess, etc)

The "almost never loses" part of the title is shakey though. The bot plays perfectly given the words it knows — but if you steer the game toward an obscure word outside its dictionary, you might just catch it off guard. That's the fun of it.

If you want to poke around the implementation, the full code is on GitHub and you can play against the bot live at triebot.faddal.dev. Go beat it if you can!