Introduction to Artificial Intelligence

Assignment 2

Programming assignment - games and reasoning

In this assignment, you will write a program that plays the number guessing game. The program will use logical reasoning and search in order to attempt optimal or near-optimal play.

The rules of the game

Each player picks a 4-digit decimal number, with no repeated digits (may begin with 0). Each player turn is a guess of a 4-digit number, and the opponent (truthfully) replies with the number of exact matches, i.e. which digits are guessed correctly, as well as in the correct position (BULLS), and the number of digits in the guess that appear in the number, but in the wrong position (COWS). The idea is to gather information as the game progresses, until a "sure" guess can be made. The winner is the player that guesses the opponent's number first. 

Example:

Number to be found:     0561

                        Guess     Result

                        1234      1 COW
                        0456      1 BULL, 2 COWS

What to implement

Note that although this appears to be an adversarial game, there is not much sense in treating it that way. There is no reasonable scheme for affecting the opponent's guesses, and the only decisions which can be usefully made is the sequence of guesses. Thus, the way you should implement this game is, the user enter a "secret" number. (It is "secret" because the program knows it, but is not allowed to use this information in its guesses.) The program then prompts the user, who responds with one of the following action requests:

  1. Tell the program to just continue with its next guess.
  2. Query about the knowledge gathered from previous guesses (see below).
  3. Force the program to make a particular next guess entered by the user (this is mainly for debugging the logical reasoning, but will also be required in the final version).
At each guess, print out information about reasoning, the guess, and the result.

Reasoning in the program

Your program should use propositional logic to reason about the sequence of past guesses. It should then (optionally) make the guess that has "highest utility", in the sense that the number of possible choices remaining after the next guess is minimal, or the one that will minimize the number of guesses in the worst case (you get to choose which).

First, you must choose the set of propositions to be used in your logical system. We make the following suggestion. Use propositions Gijt to denote that on turn t we guessed that digit i is in position j. Use Dij as propositions that denote that digit i is in position j in the acual number. Use proposition Bit (resp. Cit) to denote that at turn t the result was i BULLS (resp. COWS). In addition, you should generate the axioms for this domain, e.g. NOT (D11 and D12), because a digit cannot appear twice in the number. As the number of axioms is large (there are 60 sentences of THIS TYPE ALONE needed in the system), we require that you generate them by using limite first-order logic and RE-WRITE rules and an interpreter to convert these rules to propositional sentences. Note that the interpreter can be a program, an editor macro, or whatever, but you need to submit the first-order rules, your interpreter, and the resulting propositional rules. For example, you can state: 

Forall i, j, k  (Dki AND Dkj) implies i=j

In addition, you will need to demonstrate the logical reasoning capabilities of the system. In order to perform that, your program should accept, at any point in the game, a logical query, and should state whether it is provably true, or provably false, or neither. The queries are limited to:

  1. Digit i in position j
  2. Digit i in any position

Note that you do not need to necessarily implement a parser, it may be easier to prompt for a query type and then for i and j, and to generate the logical query from that information yourself.

Note: the idea here is that you IMPLEMENT the proof engine (resolution), and USE IT in the program. A game-playing program that does NOT use logical reasoning will NOT be accepted (even if it IS more efficient!)

Deliverables

Electronic submission of source code and executables. A non-trivial example of the logical reasoning and the search capabilities of your program. Frontal grading and checking of the program(s).

Deadline: January 3, 2002.