Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Challenge: Designing A Computer Opponent

by Limbic~Region (Chancellor)
on Dec 13, 2007 at 00:45 UTC ( #656731=perlquestion: print w/replies, xml ) Need Help??

Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:

All,
I am writing a Lingo-ish game for my mother. One of the problems I am having is designing a computer opponent. The trouble is that I want the difficulty to be configurable. For those unfamiliar, here is a brief description of the game:

The game starts with a secret word of a fixed number of letters with only the first letter known. A player guesses a word. Provided the guessed word is within the rules, each letter falls into 1 of 3 categories:

  • Letter is not in the target word
  • Letter is in target word but in a different position
  • Letter is in target word and correct position
This information is presented visually (usually with colors) and previous guesses are displayed so all known information about the target word is available for subsequent guesses.

While I am still working out the exact rules I intend to use, there are 4 types of guesses:

  • Perfect - target word is guessed
  • Good - new information about target word is acquired
  • Bad - no new information is acquired
  • Worst - turn is lost

Some good guesses are better than other good guesses depending on how much new information they reveal. What I need help with is making a guessing algorithm that can be better or worse depending on configuration. Here are the factors that can go into making a guess:

  • Time taken to guess (faster = more points)
  • Guesses resulting in loss of turn
    • Mispelled word
    • Previously guessed word
    • Incorrect number of letters
    • Does not begin with provided first letter
    • Not within given time limit
  • Known vocabulary
  • Use (or non-use) of available information
    • Letters known NOT to be in target word
    • Letters in target word but misplaced
    • Letters in target word and correct position

Your challenge, if you choose to accept it, is to design an algorithm that can take the above factors into consideration to make a configurable computer opponent. While I would hope for something better than just "Easy, Medium, Hard", I will be very appreciative of anything I can get.

I have explained more about the game play here.

Cheers - L~R

  • Comment on Challenge: Designing A Computer Opponent

Replies are listed 'Best First'.
Re: Challenge: Designing A Computer Opponent
by dragonchild (Archbishop) on Dec 13, 2007 at 03:05 UTC
    A couple additional parameters:
    • Ubiquity of the word. For example, common words are more likely to be put up there, so a better AI would pick common words first. A worse AI will pick at random.
    • Figuring out what letters can or cannot be next to another. For example, "xz" doesn't happen ever in English. Same with eeii and other combinations. A smart algorithm uses that information to prune the search tree. A dumb one doesn't.

    My criteria for good software:
    1. Does it work?
    2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
Re: Challenge: Designing A Computer Opponent
by Hercynium (Hermit) on Dec 13, 2007 at 03:20 UTC
    Discussion on the CB led me to some ideas for you...

    Do you use a dictionary of words that the computer opponent uses to find words to guess? If so, you could simply generate different dictionaries for different difficulty levels. There may even already be pre-computed dictionaries available online with words rated by how common/simple they are, and thus provide a convenient basis for categorization!

    Also, the type of analysis required to solve the problem lends itself well to recursive solutions... perhaps build-in a (configurable) limit to how deep the analysis goes?

    If all else fails, or isn't enough, I am partial to my earlier suggestion - make the computer make mistakes! Randomly inject bad data into the algorithm in the form of bad or mis-spelled dictionary entries, randomly delete previously-guessed entries, etc...

    Update: While I don't have the time right now to come up with code, it looks like what's needed is some degree of intelligence for how to hamper a solving algorithm in a somewhat-consistient human-like fashion. My experience with programming for work points me towards a more straight-forward modeling approach with a pile of configurable-options that are tweaked until it 'feels' right, but my inner nerd wants something more like AI. I'll keep thinking about it, but I'd bet soup-to-nuts there's about 1000 monks here who could do this 10x faster and better than I :)
      Hercynium,
      Do you use a dictionary of words that the computer opponent uses to find words to guess? If so, you could simply generate different dictionaries for different difficulty levels.

      Yes. As I indicated in my original post, known vocabulary is one of the factors that can be used for a configurable difficulty level. The problem is finding the right balance.

      Also, the type of analysis required to solve the problem lends itself well to recursive solutions... perhaps build-in a (configurable) limit to how deep the analysis goes?

      I am not sure how to apply this. My current expert solution is not recursive and I am not sure how I could stop it midstream. Did you have an implementation in mind?

      If all else fails, or isn't enough, I am partial to my earlier suggestion - make the computer make mistakes! Randomly inject bad data into the algorithm in the form of bad or mis-spelled dictionary entries, randomly delete previously-guessed entries, etc...

      As I indicated in my post, mistakes are factors that can be used in the difficulty factor. The problem is an actual implementation that results in a realistic player and not something too easy or too hard.

      Cheers - L~R

Re: Challenge: Designing A Computer Opponent
by eric256 (Parson) on Dec 13, 2007 at 03:29 UTC

    Hey,

    I would think that you build a guess() function that scans a dictionary and removes all the impossible words. Then sorts those words based on use frequency. Then your different degrees of difficulty could control where you pick words from the list. Most difficult would only pick the very best words, and the lower the difficult the lower down the list the computer picks from.

    A smarter AI might also be able to use its first few guesses to get a better idea what letters are in the word, i'm not sure how this could be done but i would guess that good players would be able to work the system to get more info out of it (like when you play mastermind).

    If you already have code for score() that would be nice to see ;)


    ___________
    Eric Hodges
Re: Challenge: Designing A Computer Opponent
by Limbic~Region (Chancellor) on Dec 13, 2007 at 14:20 UTC
    All,
    I intentionally didn't explain too much about the game for a couple of reasons. The first is because I haven't finalized the rules in my variation of the game. The second is because I didn't want people to focus too much on the game but rather on the guessing algorithm. Thanks to a private /msg, I realize knowing more about the game play can affect an implementation of guess().

    Turns and Control

    Players alternate who has control each time a new target word is presented. The player with control keeps control until they have guessed the secret word or lose control due to a violation of the rules or the total number of guesses reaches five. Both opponents have visibility to all information about the secret word regardless of who obtained the information.

    Losing Control For Too Many Guesses

    For each secret word, there are a total of five guesses where control can be retained. This is not per-opponent but total for the secret word. If player 1 guesses three times and loses control to player 2, player 2 only has two guesses before losing control. Once there have been five guesses for a secret word, the first unknown letter in the secret word is filled in and control passes to the opponent. If the opponent is unable to guess the word, the next unknown letter is filled in an controll passes again. This continues until all but one of the secret letters is revealed. If both players fail to guess the word at this stage - the secret word is declared a draw.

    Example Scenarios

    • Player 1 has control and guesses the secret word in 3 guesses
    • Player 2 gets control for the next secret word

    • Player 1 mispells a word on the 3rd guess
    • Player 2 gets control, sees everything player 1 did, and guesses the secret word
    • Player 1 gets control for the next secret word

    • Player 1 exceeds the time limit on the second guess
    • Player 2 gets control and mispells a word on the 4th guess
    • Player 1 regains control and guesses the secret word
    • Player 2 gets control for the next secret word

    Cheers - L~R

Re: Challenge: Designing A Computer Opponent
by kyle (Abbot) on Dec 13, 2007 at 16:16 UTC

    I'd probably start by designing a perfect player. It has a dictionary, and it can narrow it down to every possible word according to the data it knows. It always guesses so as to gain the most information or eliminate the most possible words.

    Then I could run the ideal player against every word there is to see how it scores—how fast it guesses the word. That's a baseline.

    Each less than ideal opponent, I could implement and then run a similar test. This way I can rank the algorithms. I can see which modifications have an effect, which don't, and how much.

    I'd implement the lesser guessers by making them some degree of forgetful. It has a smaller vocabulary. It forgets some of the facts it has learned in the course of the game. By losing some of its rules, it would make worse guesses.

    I'm imagining some data structure that has all the known game information in it, and a routine that has a dictionary and presents all words that match the data. The lesser guesser would randomly lose parts of the real data structure before passing to the dictionary selector.

Re: Challenge: Designing A Computer Opponent
by Not_a_Number (Prior) on Dec 13, 2007 at 18:18 UTC

    Just a couple of thoughts.

    To hamper the computer, presuming you have a good algorithm for guess():

    - Have the computer select n words at random from its list. If none of these words fit the grill, it 'times out'.

    - Add m misspelt words to the computer's list.

    By adjusting m and n (down to zero and up to infinity, respectively, for 'expert' level), you can configure any number of levels.


    Choice of dictionary:

    - If the dictionary is too small, players will get fed up with the program refusing quite common words (including inflected forms, which seem to be allowed by the rules).

    - If, on the other hand, it's too big*, there's a chance that it will too often choose extremely obscure words, again annoying the player.

    Maybe use two wordlists, a fairly simple one from which the words to guess are selected, and a more comprehensive one to check for existence/spelling?

    * The biggest English wordlist on my hard drive contains 278,468 entries. Here's an alphabetical sample:

    bahut, bahuts, bahuvrihi, bahuvrihis, baidarka, baidarkas, baigan, baigans, baignet...
Re: Challenge: Designing A Computer Opponent
by husker (Chaplain) on Dec 13, 2007 at 20:53 UTC
    There are various Lingo strategies out there, including dictionary-like attacks where the goal is to use your first two guesses to include as many distinct letters as possible. A "smart" opponent might have a larger or more comprehensive list of such "starter" words. Difficulty might, in fact, differ only by how "intelligent" the first two guesses are, and then you could use a general strategy after that.

    Another factor that a "smarter" algorithm might use things like word frequentcies and letter frequencies to guide guesses. An "easier" opponent might have more of a random selection to it, whereas a more difficult opponent might put more weight on these frequencies.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://656731]
Approved by grep
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2023-01-30 22:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?