Introduction to Computer Science • Sedgewick and Wayne • Copyright © 2007 • http://www.cs.Princeton.EDU/IntroCSArtificial Intelligence2Conway's Game of Lifehacker's emblemJohn Conway3Conway's Game of LifeConway's game of life.•Critters live and die in an infinite square grid.•Time proceeds in discrete steps.Survival. Critter lives and dies depending on 8 neighbors:•Too few? (0-1) die of loneliness•just right? (2-3) survive to next generation•too many? (4-8) die of overcrowdingBirth. Critter born if exactly 3 neighbors.time t time t+1deathbirth4Conway's Game of LifeGlider. Propagates a signal.time t time t+1 time t+2 time t+3 time t+55Conway's Game of LifeGosper glider gun. Generates gliders.http://www.ibiblio.org/lifepatterns/6 What Could This Be?ImplicationsIs REAL life described by discrete rules, or not?Can we build a UTM from living components?Can a machine do anything a human can do? Can human intelligence be simulated by a machine?Artificial Intelligence (AI): The science and engineering of making intelligent machines78Weak AICan a machine appear to be intelligent?9Artificial IntelligenceGoal. [Turing 1950] Program computer to exhibit intelligent behavior.1960s. Very optimistic predictions.Reality. Slow progress with some striking successes.“ Every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it. ” — J. McCarthy *5110The Chess-Playing Turk11Tic tac toe. Two person game of skill.Number of possible games 255,168.Tic-Tac-Toe12Tic-Tac-ToeMinimax algorithm.Tic-tac-toe is solved. X will never lose; O will never lose.assuming optimal play by X13ChessChallenge. [Claude Shannon] Develop a computer program to play chess.Number of possible games. ! 1023.14Kasparaov vs. Deep BlueDeep Blue. [IBM]•Supercomputer, augmented by VLSI chess chips.•200 million board positions per second.Machine beats man. [February 1996] First computer program to win a chess game against reigning world champion.Q. Does a chess-playing computer program appear intelligent?15“ Once again, man beats machine! ”Chess16Checkers (Draughts)Number of possible games. ! 1031.17Checkers (Draughts)Chinook. [Jon Schaeffer] Computer program for checkers.Man vs. machine. Chinook awarded world championship in 1994after 6 draws with Marion Tinsley (who withdrew).Checkers is solved! [Science, September 2007]•Proof that black will never lose with optimal play.•Proof that white will never lose with optimal play.18BackgammonBackgammon. Two-player game of skill and luck.TD gammon. [Gerry Tesauro 1980s]•Program was given no expert backgammon knowledge.•Learned strategy by playing itself 300,000 times.•Among best backgammon players in the world.19PokerPoker. Multi-player game of skill and luck.Poker bots. Not currently competitive with pros.20Turing TestCan a machine appear intelligent?If so, how could we tell?21Turing TestJudge types questions to both.•Computer claims to be human.•So does human.Pass. If judge cannot tell which entity is human,we say computer has passed the test and is "intelligent."Prediction. [Turing] Computer would pass test by 2000.22ElizaEliza. [Weizenbaum 1966]•Program imitates Rogerian psychiatrist.•Works by generating scripted responses to keywords.•Just 200 lines of code!Q. Does Eliza appear intelligent?A. You be the judge: http://chayden.net/eliza/Eliza.html23Eliza Pattern Matching Rules…key: perhaps decomp: * reasmb: You don't seem quite certain. reasmb: Why the uncertain tone ? reasmb: Can't you be more positive ? reasmb: You aren't sure ? reasmb: Don't you know ?key: francais decomp: * reasmb: goto xforeign reasmb: I told you before, I don't understand French.key: sorry decomp: * reasmb: Please don't apologise. reasmb: Apologies are not necessary. reasmb: I've told you that apologies are not required.key: apologise decomp: * reasmb: goto sorry…24ParryParry. [Colby 1972] Program imitates a paranoid schizophrenic.Q. What happens when Parry "meets" Eliza?A. You be the judge: http://tools.ietf.org/html/rfc43925Turing TestLoebner Prize•$100,000 to first program to pass restricted Turing Test.•Annual competition held since 1995.•Small awards given to best programs.26Loebner Contest Dialogs“Hello, Judge. My name is Ella. Please tell me your first name, or whatever I should call you."“Call me Lisa. Am I male or female?”“ Okay, I will call you 'Lisa. Am I Male Or Female?' I am here recently from Tainjin, China, so please be patient with me.”“ I'm not a patient because I am not ill. Are you feeling well today?“ What do you think it means that you are not ill?”“ Have you ever been ill?” “ 'Have you ever been ill?' you say? That's it, Lisa Am I Male Or Female! I will schedule a whipping for you."”27Loebner Contest Dialogs"What do you think of Reading?""I'm somewhat crazy about reading. I like to read mystery novels.""I meant the town.""Jones lives in the city and is a writer of children's books.""Does Jones live in Reading, then?""Tomorrow is another day. We can only live today well.""Do you live, then?""I live then a lot. Someday we will live on another planet.""I think you are already there."28Loebner Contest Dialogs"What is it?""What is what?""A high-yield, perennial, four-lobed hybrid of wheat and rye whose root grain, triticale, can trace its ancestry to twentieth-century Canada.""At last. Another classic grain freak.""Lewis. Jim Lewis. Would you like for me to show you some poetry?""No, thanks.""I didn't want to show you the stupid poetry anyway."29Digression: "Reverse" Turing TestStandard Turing test. Judge is human.Reverse Turing test. Judge is computer!Why?•Google allows each user 7GB storage.•PayPal once offered $5 for each user who opens a new account.•Both need to distinguish real humans from bots.30Exploiting Intractability: Captcha'sOCR. Given degraded text, find original text.CAPTCHA. [completely automated public Turing test to tell computers and humans apart]http://online.wsj.com/public/resources/images/OB-AB313_captch_20060524170113.gif31Knowledge DatabasesTwenty questions. http://www.20q.netQuestion answering system. http://start.csail.mit.eduQ. Does a computer that can answer questions appear intelligent?32DARPA Grand Challenge2004 Grand Challenge.