Python Algorithm- For The Game "Ghost"- Need A Way To Intelligently Look Up All 'winning' Permutation Of Letters

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) --Co

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

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