Python Algorithm- For the game "Ghost"- need a way to intelligently look up all 'winning' permutation of letters
Question: I'm writing a computer program to play the word game
["Ghost."](http://en.wikipedia.org/wiki/Ghost_%28game%29)

Here's how the current programs works:

\--User selects a letter (right now it only works if the user moves first)

\--Computer has a list of all possible odd-numbered words in its dictionary
(this is so that the user will have to complete each word and therefore lose).
After each letter the user selects, the list of words that the computer has is
trimmed via this loop:

    
    
     wordList = [w for w in wordList if w.startswith(currentWord)]
    

so that it only has words in its "wordList" that conform to the currentWord
that is collaboratively being spelled.

\--The computer then randomly selects a word from its current list of words
and returns the appropriate letter of the word via It then updates its list to
include the letter it selected via this code sample:

    
    
     randomnumber = random.randint(0, len(wordList)-1)
     currentWord+=wordList[randomnumber][len(currentWord)]
     wordList = [w for w in wordList if w.startswith(currentWord)]
    

\--This then continues until either the user spells a word and that is
detected via the checkLoss function, or if the computer is unable to continue
a word without losing and triggers the checkBluff function. The checkBluff
function requires the user to write what word he is thinking to make sure he
isn't making one up.

\--*_HERE'S THE PROBLEM: *_ obviously, because the computer randomly selects
which character to pick there are certain words that will force a loss. For
example, if the the first player selects the word "d", there is a very high
probability that the computer will select an "e" because there are so many
words that have "de" and the very beginning. However, if the user on the third
turn selects the letter "e" such that the current spelling is "dee" the
computer has no words in its list (there is only one word in the english
language that fits that form: 'deed' and it is even-numbered and thus losing),
so the bluff function is triggered and the computer loses when the user
reveals he was thinking of a real word "deed."

**SO, I would like an algorithm that makes the computer think in advance such
that it does not ever pick a follow-up letter for which the first player can
force a loss.** So, if a "d" is picked, the computer should never pick an "e",
because that would force a loss with a subequent e. Similarly, if the user
selects an "h" the computer should never follow with an "o" because the user
can then say "c" which forces a "k" spelling the word "hock."

I cannot think of a way to do this.

If needed, here's the program in its full incarnation:

    
    
    import os, random, sys, math, string
    
    def checkBluff(currentWord, choice, fullList):
        if choice.startswith(currentWord):
            #print "this is accurate"
            for line in fullList:
                if line == choice:
                    return 1
        return 0
    
    def checkLoss(currentWord, fullList):
        for line in fullList:
           if currentWord == line:
               return 1
        return 0 
    
    def instantiateWordList(dictionary, wordList):
        for line in dictionary:
            wordList.append(line.strip())
        return wordList
    
    
    
    def main():
    
        fullDict = open("wordlist.txt", "r") #fullDict contains all possible words
        winFirst = open("firstwin.txt", "r") #winFirst contains all odd-numbered words
        winSecond = open("secondwin.txt", "r")#winSecond contains all even-numbered words
        turn = "Human"
        currentWord = ""
        wordList = []
        fullList= []
        bluff = ""
    
    #Instantiates a list with every word for use in evaluating win/loss
    for line in fullDict:
        fullList.append(line.strip())
    
    #Decide who goes first
    choice = raw_input("1. I will go first \n2. I will go second\n>>")[0]
    
    if choice == "1":
        wordList = instantiateWordList(winSecond, wordList)
        turn == "Human"
    else:  
        wordList = instantiateWordList(winFirst, wordList)
        turn == "Computer"
    
    while True:
        if turn == "Human":  
            choice = raw_input("Choose a letter: ")[0]
            currentWord+=choice
    
    
            if checkLoss(currentWord, fullList) == 1:
                print "You have lost by spelling the word "+ currentWord
                break 
    
    
            print "**Current Word**"+ currentWord
            wordList = [w for w in wordList if w.startswith(currentWord)]
            turn = "Computer"
    
        if turn == "Computer":
            try: 
                randomnumber = random.randint(0, len(wordList)-1)
                currentWord+=wordList[randomnumber][len(currentWord)]
                print "I am thinking of the word: "+ str(wordList[randomnumber])
                wordList = [w for w in wordList if w.startswith(currentWord)]
    
                print "**Current word**: "+ currentWord
                print "length: "+ str(len(wordList))
                turn = "Human"
            except StandardError:
                bluff = raw_input("I call bluff.  What word were you thinking of?\n>>")
                if checkBluff(currentWord, bluff, fullList) == 1:
                    print "You actually won!"
                    break
                else:
                    print "You lost.  You lying son of a bitch."
                    break 
    
    
    if __name__ == "__main__":
        main()
    


Answer: You want the computer to look ahead, and yet choose randomly? :-)

This game is predictable enough and simple enough for you to make the computer
always win, if you want. In fact, you can have it pre-generate strategy trees
to guarantee a win. [They aren't even that
big](http://blog.xkcd.com/2007/12/31/ghost/), you could learn them by heart if
you want.

If you don't want that, you should only look one round ahead. In your deed
example, one round a head would show that the opponent can force a win in one
round, so it would avoid "de". But it would not avoid something that would
force a loss in two rounds.

But for that you need to go through all possibilities. You can then choose
randomly between the remaining choices.

