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."

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 1

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, 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.

Answer 2

In order for program to not lose, it needs to also keep the list of even-numbered words (oh, it does, didn't notice it at first)

When deciding on a next letter it should first consult it's even-numbered (losing) word list. If there are n+2 (4 for n=1, 6 for n=3 etc, n is current letter index) character long words, then it should not use letter in n position of those.

So, using "deed" example:

1. User types "d"
2. Program sees that there is 1 word that starts with "d" and is 4 characters long: "deed".
3. It adds "deed"[1] to the list of "restricted" letters
4. It scans the list of the "winning" words, ignoring the ones that start with "de" and gets a list of "available" characters.
5. It randomly selects a character from list and displays it to the user.