CPSC 453, Fall 2003 Assignment 4 and Information About Test 1 ------------------------------------------------------------------------- Assignment 4: As you know, you are required to do a term project for this course, as described in the course handout. On Monday, February 17, you should turn in a first progress report, representing at least several hours of work. You should by that time have chosen a problem area and done some research on it (remembering that you can change to a different problem any time before Spring Break). Your initial report should be at least two pages long. It should state what problem you have selected and discuss why you selected it. It can, if you like, discuss other problems that you considered working on, and why you didn't select them. It should discuss what you have learned about approaches that researchers have taken. And it should list the ideas that you have for continuing your work on the project. A bibliography would be useful. This is probably the only thing related to the term project that I will collect and grade before the end of the term. ------------------------------------------------------------------------- Test Info: The first test in this course will be given in class on Wednesday, February 12. It will cover Prolog programming, readings from the textbook (pages 33 to 46, 193 to 243, and 603 to 616), and handouts (Turing's paper, "What is an AI technique", "Evolving Inventions", two stories by Stanislaw Lem, and the excerpt from "Robot"). You should NOT assume that questions on these readings will be limited to what we've done in class. Here are some of the things you should know about: what is artificial intelligence? first-order predicate logic as a representation language logical deduction basics of Prolog programming predicates, facts, and rules variables, atoms, numbers, lists how variables get values and how those values are used anonymous variables, named as "_" expressing AND and OR with "," and ";" operators such as "+", "/", and "=<" the meaning of "=" in Prolog evaluation of numerical expressions using "is" recursive rules head and tail of a list; recursive list processing; [X|T] notation implementation: matching and backtracking the cut operation, "!" assert(Fact) and retract(Fact) basic built-in predicates such as member(X,L), length(L,N), append(L1,L2,L) applying prolog to state-space search (as in the buckets problem) representing problem states or configuration representing possible moves basic path-finding using Prolog's built-in depth-first search search ( AI = representation + search ?) examples of search in AI (buckets puzzle, game playing, genetic algorithm, theorem proving) depth-first search, breadth-first search, and best-first search heuristics generic search procedure, using Open and Closed lists Physical Symbol System Hypothesis (Traditional AI) symbol structures, rule-based manipulation independent of meaning, problem-solving as search Knowledge Representation Hypothesis semantic nets "isa" hierarchies and inheritance frames and scripts; slots and default values schemes for representing propositional knowledge: conceptual dependency (basic ideas); semantic primitives conceptual graphs the Turing Test (Turing's "Imitation Game") idea of language as a central test for intelligence some objections to AI: the mathematical objection (Goedel's Theorem; Halting Problem) the problem of consciousness; solipsism computers can only follow rules; can only do what they are told artificial intelligence vs. traditional programming approaches role of knowledge in AI programs genetic programming; solving problems by simulated evolution Trurl's problems and the issues that they raise mind as computation achieving and surpassing human equivalency? If you want to practice your prolog, here are some predicates that you can try to write; I would consider any of these to be fair test questions: sum(NumList,S) -- compute the sum of a list of numbers nth(N,L,X) -- X is the N-th element of list L. remove(X,L,NewL) -- remove the first occurrence of X in list L, giving NewL as the resulting list. removeAll(X,L,NewL) -- remove ALL occurrences of X from list L. deepReverse(L,NewL) -- reverse list L and also recursively reverse any members of L that are lists; for example deepReverse( [ a, [b,c], [d, [e, f], g] , h ] , X ) sets X = [h, [g, [f, e], d], [c, b], a]. sorted(NumList) -- is true if NumList is a list of numbers that is in non-decreasing order. listOfN(N,Item,List) -- make a list consisting of N copies of the specified Item. knightMove([A,B],[C,D]) -- for a chess game, if a knight is at row A, column B, this will generate legal moves to a new row (C) and column (D). (Actually, this wouldn't be fair if you don't know chess, but there could be some question about representing moves in some specified game or puzzle.) --------------------------------------------------------------------- And here, for your information, is my solution to the missionaries and cannibals problem. You can find this program in the file /home/cs453/prolog/cannibals.pl : /* This prolog program solves the missionaries and cannibals problem. Three missionaries and three canibals are on one side of a river. There is a boat that can carry either one or two people at a time. The problem is to move everyone to the far side of the river, but subject to the following restriction. If there are ever more missionaries than cannibals on either side of the river, then the outnumbered cannibals will be converted. We want to find a sequence of moves that will get everyone across the river with no conversions. (There is a coversion if the number of missionaries is greater than the number of cannibals AND if there is at least one cannibal.) States are prepresented in this program in the form [M,C,S] where M and C are the numbers of missionaries and cannibals on the near side of the river, and S indicates which side of the river the boat is on. S is 'e' to indicate the near (east) side and is 'w' to indicate the far (west) side. The initial state is thus [3,3,e], and the desired state is [0,0,w]. */ /* * The solve predicate will find a path from the initial state, * where eveyone is on the near side of the river, to the final * state, where everyone is on the far side, and it will print * out the solution using the simple printMoveList(L) predicate. */ solve :- path([3,3,e],[0,0,w],[[3,3,e]],MoveList), nl,nl,printMoveList(MoveList). printMoveList([]) :- nl, nl. printMoveList([[A,B,Desc]|T]) :- write(A), write(' --> '), write(B), write(' by '), write(Desc), nl, printMoveList(T). /* * path([A,B,C],[D,E,F],Visited,Moves) finds a path of legal moves * from the [A,B,C] to the state [D,E,F]. It does this by recursively * generating all paths starting from [A,B,C]. Visited is a list of * states on the path currently under consideration; it is used to * avoid making a cycle of moves. The Moves argument will be set * to the list of moves. [A,B,C] must be instantiated before this * predicate is called. */ path([A,B,C],[A,B,C],_,[]). path([A,B,C],[D,E,F],Visited,Moves) :- move([A,B,C],[I,J,K],Description), write('Try move '), write([I,J,K]), write(' '), write(Description), nl, safe([I,J,K]), % Don't use this move unless it's safe. not(member([I,J,K],Visited)), % Don't reuse a move. path([I,J,K],[D,E,F],[[I,J,K]|Visited],MoreMoves), Moves = [ [[A,B,C],[I,J,K],Description] | MoreMoves ]. /* * The move(State1,State2,Desc) is true if there is a * move from State1 to State2. Desc is a description of * the move. State1 must be instanticated before this is * called. If State1 is instanticated and State2 is not, * this will generate all possible moves from State1 by * backtracking. This predicate does not chekc whether * State2 is a safe position. That is, it generates all * possible ways of moving people, regardless of whether * there are conversions. The safety of the new state is * checked elsewhere. */ move([A,B,e],[C,B,w],'One missionary rows across') :- A > 0, C is A - 1. move([A,B,e],[C,B,w],'Two missionaries row across') :- A > 1, C is A - 2. move([A,B,e],[C,D,w],'One missionary and one cannibal row across') :- A > 0, B > 0, C is A - 1, D is B - 1. move([A,B,e],[A,D,w],'One cannibal rows across') :- B > 0, D is B - 1. move([A,B,e],[A,D,w],'Two cannibals row across') :- B > 1, D is B - 2. move([A,B,w],[C,B,e],'One missionary rows back') :- A < 3, C is A + 1. move([A,B,w],[C,B,e],'Two missionaries row back') :- A < 2, C is A + 2. move([A,B,w],[C,D,e],'One missionary and one cannibal row back') :- A < 3, B < 3, C is A + 1, D is B + 1. move([A,B,w],[A,D,e],'One cannibal rows back') :- B < 3, D is B + 1. move([A,B,w],[A,D,e],'Two cannibals row back') :- B < 2, D is B + 2. /* * Check whether a state is safe, i.e., produces no conversions. */ safe([A,B,_]) :- (A =< B ; B = 0), % Check for no coversions on the near side. C is 3-A, D is 3-B, % Compute numbers on far side. (C =< D; D = 0). % Check for no conversions on the far side.