Chapter 11

From IPRE Wiki
Jump to: navigation, search

Artificial Intelligence

Artificial Intelligence  Movie Poster  Warner Bros., 2001

David: My mother told me to run away.
Gigolo Joe: Why did she say that?
David: I guess because Henry didn't like me.
Gigolo Joe: Why was that?
David: Martin came home.
David: Martin is Mommy and Henry's real son. After I find the Blue Fairy then I can go home. Mommy will love a real boy. The Blue Fairy will make me into one.
Gigolo Joe: Is Blue Fairy Mecha, Orga, man or woman?
David: Woman.
Gigolo Joe: Woman? I know women! They sometimes ask for me by name. I know all about women. About as much as there is to know. No two are ever alike, And after they've met me, no two are ever the same. And I know where most of them can be found.
David: Where?
Gigolo Joe: Rouge City. Across the Delaware.
-: Dialog between two Artificial Intelligence entities: Gigolo Joe (played by Jude Law) and David (played by Haley Joel Osment) in the movie, Artificial Intelligence (2001), Directed by Steven Speilberg, Warner Bros.

The question of intelligence

The quest for the understanding of intelligence probably forms the oldest and yet to be fully understood human inquiry. With the advent of computers and robots the question of whether robots and computers can be as intelligent as humans has driven the scientific pursuits in the field of Artificial Intelligence (AI). Whether a computer can be intelligent was lucidly discusses by Professor Alan Turing in 1950. To illustrate the issues underlying machine intelligence, Turing devised a thought experiment in the form of an imitation game. It is played with three people, a man, a woman, and an interrogator. They are all in separate rooms and interact with each other by typing text into a computer (much like the way people interact with each other over IM or other instant messaging services). The interrogator's task is to identify which person is a man (or woman). To make the game interesting, either player can try and be deceptive in giving their answers. Turing argues that a computer should be considered intelligent if it could be made to play the role of either player in the game without giving itself away. This test of intelligence has come to be called the Turing Test and has generated much activity in the community of AI researchers (see exercises below). The dialog shown above, from the movie Artificial Intelligence, depicts an aspect of the test of intelligence designed by Alan Turing. Based on the exchange between Gigolo Joe and David, can you conclude that they are both intelligent? Human?

After over five decades of AI research, the field has matured, and evolved in many ways. For one, the focus on intelligence is no longer limited to humans: insects and other forms of animals depict varying degrees and kinds of intelligence have been the subject of study within AI. There has also been a fruitful exchange of ideas and models between AI scientists, biologists, psychologists, cognitive scientists, neuro-scientists, linguists and philosophers. You saw examples of such an influence in the models of Braitenberg vehicles introduced earlier. Given the diversity of researchers involved in AI there has also been an evolution of what AI itself is really about. We will return to this later in the chapter. First, we will give you a few examples of models that could be considered intelligent that are commonly used by many AI scientists.

Language Understanding

One aspect of intelligence acknowledged by many people is the use of language. People communicate with each other using a language. There are many (several thousand) languages in use on this planet. Such languages are called natural languages. Many interesting theories have been put forward about the origins of language itself. An interesting question to consider is: Can people communicate with computers using human (natural) languages? In other words, can a computer be made to understand language? Think about that for a minute and see if you can come up with a possible answer.

To make the question of language understanding more concrete, think of your Scribbler robot. So far, you have controlled the behavior of the robot by writing Python programs for it. Is it possible to make the Scribbler understand English so that you could interact with it in it? What would an interaction with Scribbler look like? Obviously, you would not expect to have a conversation with the Scribbler about the dinner you ate last night. However, it would probably make sense to as it to move in a certain way? Or to ask whether it is seeing an obstacle ahead?

Researchers working in the field of computational linguistics (or natural language understanding) have proposed many theories of language processing that can form the basis of a computational model for a Scribbler to understand a small subset of the English language. In the section, we will examine one such model which is based on the processing of syntax and semantics of language interaction. Imagine, interacting with the Scribbler using the following set of sentences:

You: do you see a wall?
Scribbler: No

You: Beep whenever you see a wall.
You: Turn right whenever you see a wall to your left.
You: Turn left whenever you see a wall to your right.
You: Move for 60 seconds.

[The Scribbler robot moves around for 60 seconds turning whenever it sees a wall.
 It also beeps whenever it sees a wall.]

Earlier, you have written Python programs that perform similar behaviors. However, now imagine interacting with the robot in the fashion described. From a physical perspective, imagine that you are sitting in front of a computer, and you have a bluetooth connection to the robot. The first question then becomes: Are you actually speaking or typing the above commands? From an AI perspective, both modalities are possible: You could be sitting in front of the computer and speaking into a microphone; or you could be typing those commands on the keyboard. In the first instance, you would need a speech understanding capability. Today, you can obtain software (commercial as well as freeware) that will enable you to do this. Some of these systems are capable of distinguishing accents, intonations, male or female voices etc. Indeed, speech and spoken language understanding is an fascinating field of study that combines knowledge from linguistics, signal processing, phonology, etc. You can imagine that the end result of speaking into a computer is a piece of text that transcribes what you said. So, the question posed to the Scribbler above: Do you see a wall? will have to be processed and then transcribed into text. That is, assume that there is a software module that has the interface shown in the figure below:

Game Playing

In the early history of AI, scientists posed several challenging tasks which if performed by computers could be used as a way of demonstrating the feasibility of machine intelligence. It was common practice to think of games in this realm. For example, if a computer could play a game, like chess, or checkers, at the same level or better that humans we would we convinced into thinking that it was indeed feasible to think of a computer as a possible candidate for machine intelligence. Some of the earliest demonstrations of AI research included attempts at computer models for playing various games. Checkers and chess seemed to be the most popular choices, but researchers have indulged themselves into examining computer models of many popular games: poker, bridge, scrabble, backgammon, etc. In many of these games, it is now possible for computer models to play at the highest levels of human performance. In Chess, for example, even though the earliest programs handily beat novices in the 1960's, it wasn't until 1996 when an IBM computer chess program, named Deep Blue, beat the world champion Gary Kasparov at a tournament-level game, though Kasparov did manage to win the match 4-2. A year later, in New York, Deep Blue beat Kasparov in a 6 game match representing the very first time a computer beat the best human player in a classical style game of chess. While these accomplishments are worthy of praise, it also now clear that the quest for machine intelligence is not necessarily answered by computer game playing. This has resulted in much progress in game playing systems and game playing technology which now stands in its own right as a multi-billion dollar industry.

It turns out that in many chess-like games the general algorithm for a computer to play the game is very similar. Such games are classified as two-person zero-sum games: two people/computers play against each other and the result of the game is either a win for one player and loss for the other, or it is a draw (which makes it a zero-sum end result). In many such games, the basic strategy for making the next move is simple: look at all the possible moves I have and for each of them all the possible moves the other player might have and so on until the very end. Then, trace back from wins (or draws) and make the next move based on those desirable outcomes. You can see this easily in a simple Tic-Tac-Toe game (see picture below):

Tic-Tac-Toe picture

When you play against an opponent, you are anticipating possible moves down the road and then playing your own moves with those in mind. Good players are able to mentally picture the game several moves ahead. In many games, like Chess, certain recognizable situations lead to well determined outcomes and so a great part of playing a successful game also relies on the ability to recognize those situations. Looking ahead several moves in a systematic manner is something computers are quite capable of doing and hence anyone (even you!) can turn them into fairly good players. The challenge lies in the number of moves you can look ahead and in the limited capacity, if time to make the next move is limited, how to choose among the best available options? These decisions lend interesting character to computer game programs and continues to be a constant source of fascination for many people. For example, a computer program to play Tic-Tac-Toe can easily look at all the possible moves all the way to the end of game in determining its next move (which, in most situations leads to a draw, given the simplicity of the game). However, if you consider a typical game of Chess, in which each player makes an average of 32 moves and the number of feasible moves available at any time averages around 10, you would soon realize that the computer would have to examine something of the order of 10^65 board positions before making a move! This, even for the fastest computers available today, will take several gazillion years! More on that later. But, to play an interesting two-person zero-sum game, it is not essential to look so far ahead.

Here we will describe an "intelligent" version of the Rock-Paper-Scissors game based on Case-Based-Reasoning

# A program that plays the game of Paper, Scissors, Rock!

from myro import *
from random import randrange

def beats(me, you):
   # Does me beat you? If so, return True, False otherwise.
   
   if me == "Paper" and you == "Rock":       # Paper beats rock
      return True
   elif me == "Scissors" and you == "Paper": # Scissors beat paper
      return True
   elif me == "Rock" and you == "Scissors":  # Rock beats scissors
      return True
   else:
      return False

def main():
    # Play a round of Paper, Scissors, Rock!
    print "Lets play Paper, Scissors, Rock!"
    print "In the window that pops up, make your selection>"
    
    items = ["Paper", "Scissors", "Rock"]

    # Computer and Player make their selection...
    # Computer makes a selection
    myChoice = items[randrange(0, 3)]
    
    # Player makes a selection
    yourChoice = askQuestion("Pick an item by clicking on it.", items)

    # inform Player of choices
    print
    print "I picked", myChoice
    print "You picked", yourChoice
    
    # Decide if it is a draw or a win for someone
    if myChoice == yourChoice:
        print "We both picked the same thing."
        print "It is a draw."
    elif beats(myChoice, yourChoice):
        print "Since", myChoice, "beats", yourChoice, "..."
        print "I win."
    else:
        print "Since", yourChoice, "beats", myChoice, "..."
        print "You win."

    print "Thank you for playing. Bye!"
    
main()

from random import *
from myro import *

items = ["Rock", "Paper", "Scissors"]
history = {}

def makeKey(choices):
    key = ""
    for c in choices:
        key += c
    return key

def lookup(choices):
    # look up the history for next choice
    key = makeKey(choices)
    if history.has_key(key):
        data = history[key]
        hiData = max(data)
        return items[data.index(hiData)]
    else:
        return None

def update(choice, choices):
    key = makeKey(choices)
    if history.has_key(key):
        data = history[key]
    else:
        data = [0, 0, 0]
        
    data[items.index(choice)] += 1
    history[key] = data
        
def IWon(computer, user):
    return ((computer == "Rock" and user == "Scissors")
          or (computer == "Scissors" and user == "Paper")
          or (computer == "Paper" and user == "Rock"))

def main():
    # Play rock, paper, scissors

    choices = [' ', ' ', ' ']
    
    while True:
        # Computer makes a selection
        #computer = items[randint(0, 2)]
        computer = lookup(choices)
        if computer == None:
            computer = items[randint(0,2)]
            
        # user makes a selection
        user = askQuestion("Make a selection.", items, "Rock, Paper, Scissors")
        update(user, choices)
        choices.append(user)
        choices.pop(0)
        
        # inform user of selections
        print "I picked", computer
        print "You picked", user

        # decide who won

        if computer == user:
            print "It is a draw."
        elif IWon(computer, user):
            print "I won!"
        else:
            print "You won."

        # ask if play again
        if askQuestion("Want to play again?") == "No":
            print "It was fun playing with you. Bye!"
            break
main()

Learning

Using conx, an example of teaching Scribbler how to do obstacle avoidance (std. backprop).

Discussion

The very idea of considering a computer as an intelligent device has its foundations in the general purpose nature of computers. By changing the program the same computer can be made to behave in many different ways. At the core of it a computer is just a symbol manipulator: manipulating encodings for numbers, or letters, or images, etc. It is postulated that the human brain is also a symbol manipulator. The foundations of AI lie in the fact that most intelligent systems are physical symbol systems and since a computer is a general purpose symbol manipulator, it can be used for studying or simulating intelligence.