by Tim Menzies

LCSEE, WVU, Spring 2011

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License (http://creativecommons.org/licenses/by-sa/3.0/), Copyright © 2011, Tim Menzies.

Top
***

Change history:
===============

Jan 6, 2010
     Ready for students to review (see table of contents (cs472_toc.html)):

       * 1. Syllabus

       * 2.1 Fundamental Issues of Intelligent Systems

       * 2.2 AI Programming in LISP

       * 2.3 Cognitive Science

       * 2.9 Rule-based Programming

       * 3.1 Groups

       * 3.2 Setting up

       * 3.3 Submitting

       * 3.4 Project1: Basics

       * 3.4.1 Warming up

       * 3.4.2 Lisp101

       * 3.4.3 Text Game Engine

Syllabus
********

  * Course name: CS472, Artificial Intelligence

  * Effective data of syllabus: Jan 11, 2011

  * Site: LCSEE, WVU

  * Course number: 12912

  * Pre-requisite: CS 230 or consent for non-majors

  * Course format: 3 credit hours 3 hr lectures, exams, weekly homework

  * Textbooks : note that students do not need to buy all three since the Barski text is available via WVU's license to Safari on line.

          Paul Graham, ANSI Common LISP http://goo.gl/lDSVp.

       * Stuart Russell and Peter Norvig: Artificial Intelligence: A Modern Approach (2nd Edition)

       * Conrad Barski, Land of Lisp http://j.mp/hiZMjS

  * Schedule : Tuesday, Thursday, 1400-1515

  * Location : ESB 449

  * Instructor name: Tim Menzies Ph.D. ESB 841a, tim@menzies.us. Note: use this  email for private messages. For most of the class traffic, use the class discussion list (https://groups.google.com/forum/?fromgroups#!forum/csx72)

  * Consultation times : Tuesday, Thursdays 1300 to 1400 or by appointment

Objectives
==========

Upon successful completion of this course, students should understand:

  * Basic theory of artificial intelligence (AI).

  * Knowledge of AI programming, basic and advanced search, knowledge-based reasoning, machine learning

  * Applications of AI to gaming and agents, natural processing.

Topics
======

  * Fundamental Issues of Intelligent Systems:  (1)

  * AI programming in LISP (a, c, k)

  * AI & Gaming  (c, k)

  * Basic Search Strategies (1, c, k)

  * Knowledge-Based Reasoning (1, c, k)

  * Advanced Search (2, c, k)

  * Agents (2, k)

  * Natural Language (2, k, l)

  * Machine Learning (2, k, l)

ACM topics:

  * 1 Core

  * 2 Elective

CS program outcomes :

  * a	Be exposed to a variety of programming languages and systems, and will be proficient in programming in at least two languages.

  * c Have knowledge of the basic principles of data structures, discrete mathematics and algorithms, and be able to apply this knowledge to problem solving in relevant application areas.

  * g Be able to communicate ideas effectively in writing, verbally, be able to work and learn effectively as members of a team.

  * k Be familiar with advanced concepts of several specialized computer science areas.

  * l Have the knowledge of mathematics through differential and integral calculus, discrete mathematics and probability and statistics.

Expected Workload
=================

You MUST be prepared to dedicate AT LEAST 5-8 working hours a week to this class (excluding the time spent in the classroom).  Laboratory instruction is not included in CS 472. You will be given class accounts on CS Department machines and all assignments will have to be submitted and run there. Please note that a Linux server can be accessed from any PC using a secure connection service, such as SSH (explanation to be provided in class).

All students will commit their work to an on-line repository, supplied by the lecturer.

This is a tools-based subject and it is required that students learn those tools (Ssh, Emacs, Subversion, LISP).

Assessment
==========

  * Mid-term: 20 marks

  * Final exam: 41 marks

  * Four projects, 12 marks each.

       * These projects will be called 1,2,3,4

       * Each will have weekly deliverables a,b,c  where a,b  are worth 3 mark each and c is worth 6 marks.

       * Each project will end with a live demo in front of a tutor where groups will lose marks if:

            * The day before the demo, each student member did not fill out and email the group peer assessment form (studentPeerEvaluation.doc) to the tutor.

            * Members do not attend,

            * or if the required functionality is not demonstrable,

            * or if they cannot explain randomly selected line of codes.

Final Grades
------------

  * A : 90 - 100

  * B : 80 - 89

  * C : 70 - 79

  * D : 60 - 69

  * F : otherwise

See also, below, for how to lose marks due to poor attendance.

Attendance Policy
-----------------

Lectures: Students are expected to regularly attend lectures. After three noted absences, students will lose two points per absence. After three noted lated arrivals, students will lose one point per late arrival. If you have another commitment that requires you to be consistently late, you should drop the class.

Exams: Consistent with WVU guidelines, students absent from regularly scheduled examinations because of authorized University activities will have the opportunity to take them at an alternate time. Make-up exams for absences due to any other reason will be at the discretion of the instructor.

Late Work
---------

There are no late marks. Late homework scores zero marks.

Total student marks add up to 20+41+12*4 = 109.

That is, you can skip some of the homeworks and get full marks.

The wise student will hoard all their ``skip'' marks and use them only for sickness.

Special Consideration
---------------------

See me at start of semester advising planned absences or if you need other special considerations.

Timetable
=========

Homework due: weeks 2,3,4,5,6,7, then 9,10,11,12,13,14

Mid-session test: week 8

Final exams: as per university timetable.

Social Justice Statement
========================

West Virginia University is committed to social justice. I concur with that commitment and expect to foster a nurturing learning environment based upon open communication, mutual respect, and non-discrimination. Our University does not discriminate on the basis of race, sex, age, disability, veteran status, religion, sexual orientation, color or national origin. Any suggestions as to how to further such a positive and open environment in this class will be appreciated and given serious consideration.

If you are a person with a disability and anticipate needing any type of accommodation in order to participate in this class, please advise me and make appropriate arrangements with Disability Services (293-6700).

Statement of Academic Integrity
===============================

The integrity of the classes offered by any academic institution solidifies the foundation of its mission and cannot be sacrificed to expediency, ignorance, or blatant fraud. Therefore, I will enforce rigorous standards of academic integrity in all aspects and assignments of this course.

For the detailed policy of West Virginia University regarding the definitions of acts considered to fall under academic dishonesty and possible ensuing sanctions, please see the Student Conduct Code at http://www.arc.wvu.edu/admissions/integrity.html. Should you have any questions about possibly improper research citations or references, or any other activity that may be interpreted as an attempt at academic dishonesty, please see me before the assignment is due to discuss the matter.

Lecture notes
*************

Fundamental Issues of Intelligent Systems
=========================================

(Reading: R&N, chapter 1)

What is Intelligence?
=====================

Intelligence:

  * ``the capacity to learn and solve problems'' (Webster dictionary)

  * the ability to think and act rationally

Goal in Artificial Intelligence:

  * build and understand intelligent systems/agents synergy between philosophy, psychology, and cognitive science computer science and engineering mathematics and physics

What is involved in Intelligence?
=================================

  * A) Ability to interact with the real world

       * to perceive, understand, and act

       * speech recognition, understanding, and synthesis

       * image understanding (computer vision)

  * B) Reasoning and Planning

       * modeling the external world

       * problem solving, planning, and decision making

       * ability to deal with unexpected problems, uncertainty

  * C) Learning and Adaptation

       * we are continuously learning and adapting

       * Also: we want systems that adapt to us!

       * Major thrust of industry research.

What is Artificial Intelligence
===============================

Rich and Knight: the study of how to make computers do things which, at the moment, people do better.

Handbook of AI: the part of computer science concerned with designing intelligent computer systems, that is, systems that exhibit the characteristics we associate with intelligence in human behavior - understanding language, learning, reasoning, solving problems, etc.

Dean, Allen and Aloimonos: the design and study of the computer programs that behave intelligently.

Russell and Norvig: the study of [rational] agents that exist in an environment and perceive and act.

Riesbeck: AI is the search for answers to the eternal question: AI is a repair process to answer "Why are computers so stupid?" (if most humans can do it, and computers can't, we have to ask "why?" and "what can we do about that?").

Different Approaches
====================

I Building exact models of human cognition: view from psychology and cognitive science

II The logical thought approach: emphasis on ``correct'' inference

III Building rational ``agents'': agent: something that perceives and acts emphasis on developing methods to match or exceed human performance [in certain domains]. Example: Deep Blue.

Our focus is on III (most recent progress).

Historical Perspective i
========================

Obtaining an understanding of the human mind is one of the final frontiers of modern science.

George Boole, Gottlob Frege, and Alfred Tarski (formalizing the laws of human thought)

Alan Turing, John von Neumann, and Claude Shannon (thinking as computation)

John McCarthy, Marvin Minsky, Herbert Simon, and Allen Newell (the start of the field of AI)

Goals in AI
===========

Engineering Goal : To solve real-world problems. Build systems that exhibit intelligent behavior.

Scientific Goal:	 To understand what kind of computational mechanisms are needed for modeling intelligent behavior.

Turing Test
===========

Interrogator asks questions of two ?people? who are out of sight and hearing. One is a person; the other is a machine.

30 minutes to ask whatever he or she wants.

Task: to determine, only through the questions and answers typed into a computer terminal, which is which

If can't reliably distinguish the human from the computer, then the computer is deemed intelligent.

Artificial intelligence is the enterprise of constructing an artifact that can pass the Turing test.

Objections to Turing Test
=========================

Newell and Simon [1976]

  * Turing test is as much a test of the judge as it is of the machine.

  * Promotes the development of artificial con-artists, not artificial intelligence (Loebner competition).

Non-human Intelligence
======================

Why not?

Maybe "intelligence" could be coded any number of ways (biological, mechanical, a collection of wind-powered beer cans, whatever)

Now you might object at this separation of "rationality" from "humanity". You might protest that the only thing that can be rational like a person is another person. And many people would agree with you.

But I don't think that I am the only kind of thing that can think. That would be like saying that only birds can fly and that air planes, which don't flap their wings, don't "really" fly.

What I do think is that there is some abstract notion of flying/thinking that is independent of birds/humans. Like Spock said: "Intelligence does not require bulk, Mr. Scott".

Every computer scientist knows this to be true. Two generations of algorithms research has shown that there exist properties of computation that are independent of what processor the algorithm runs on, or the implementation language. Dijkstra once said "computer science is no more about computers than astronomy is about telescopes"- and he could have been talking about AI.

Not convinced? Well, try another example. Do you think that a robot could/should walk like a human? (see movie of Dinesh Pai's Platonic Beast (http://people.cs.ubc.ca/~pai/movies/beast.mpg)). This little fellow walks by occasionally throwing a spare limb over the top of itself. Such a move would tear us apart, but it is the natural way to do it for that kind of walking thing.

And here's another example:

  * Here's a movie (http://menzies.us/csx72/img/latin.mov) showing two AI algorithms trying to solve the "latin's square" problem: i.e. pick an initial pattern, then try to fill in the rest of the square with no two colors on the same row or column.

  * The deterministic method is the kind of exhaustive theorem proving method used in the 1960s and 1970s that convinced people that "AI can never work".

  * The stochastic method is a 1990s-style AI algorithm that makes some initial guess, then refines that guess based on logic feedback.

  * This stochastic local search kills the latin squares problem (and, incidently, many other problems).

Now the point of this example is that you would not expect a human to think using stochastic search (too much CPU twiddling). But for a computer, stochastic search is a useful inference method since each local twiddle can be done very quickly.

The Current Frontier
====================

Interesting time for AI

Deep Blue vs. Kasparov (May, '97)

  * first match won against world-champion

  * ``intelligent & creative'' play

  * 200 million board positions per second

Kasparov: "I could feel - I could smell - a new kind of intelligence across the table." ... still understood 99.9% of Deep Blue's moves.

Intriguing issue: How does human cognition deal with the combinatorics of chess?

Different Algorithms, Similar Behavior
======================================

Drew McDermott (New York Times, May, 1997): Saying Deep Blue doesn't really think about chess is like saying an airplane doesn't really fly because it doesn't flap its wings. ftp://ftp.cs.yale.edu/pub/mcdermott/papers/deepblue.txt

The brain

  * a neuron is the basic processing unit ( 1011)

  * many more synapses (1014) connect the neurons

  * cycle time: 10-3 seconds (1 millisecond)

How complex can we make computers?

  * 108 (Itanium) or more transistors per CPU

  * -supercomputer: thousands of CPUs, 1011 bits of RAM

  * cycle times: order of 10-9 seconds

Examples, cont
==============

36 Human-Competitive Results by Genetic programming (http://www.genetic-programming.com/humancompetitive.html).

Qualitative difference from previous brute-force results.

Does technique generalize? Or is a kludge?

Machine learning
================

TD Gammon (Tesauro 1993; 1995)

  * World champion level but learns from scratch by playing millions of games against itself!

  * Has changed human play

ALVINN (Pomerleau 1993)

  * Neural net used to steer vehicle in coast-to-coast highway driving

  * Speeds of up to 90 mph

  * DARPA Grand Challenge / Urban Challenge

Natural Language Processing
===========================

BOGOTA, 9 JAN 90 (EFE) - RICARDO ALFONSO CASTELLAR, MAYOR OF ACHI, IN THE NORTHERN DEPARTMENT OF BOLIVAR, WHO WAS KIDNAPPED ON 5 JANUARY, APPARENTLY BY ARMY OF NATIONAL LIBERATION (ELN) GUERRILLAS, WAS FOUND DEAD TODAY, ACCORDING TO AUTHORITIES. CASTELLAR WAS KIDNAPPED ON 5 JANUARY ON THE OUTSKIRTS OF ACHI, ABOUT 850 KM NORTH OF BOGOTA, BY A GROUP OF ARMED MEN, WHO FORCED HIM TO ACCOMPANY THEM TO AN UNDISCLOSED LOCATION.

Summary:

  * Date: 05 JAN 90

  * Location: COLOMBIA: BOLIVAR (DEPARTMENT): ACHI (TOWN)

  * Type: KIDNAPING

  * Weapon: *

  * Victim: ?RICARDO ALFONSO CASTELLAR? (MAYOR OF ACHI)

  * Perpetrator: ?GROUP OF ARMED MEN''

  * Organization: ?ARMY OF NATIONAL LIBERATION (ELN)?

Challenges ahead
================

Note that the examples we discussed so far all involve quite specific tasks.

The systems lack a level of generality and adaptability. They can't easily (if at all) switch context.

Key issue: knowledge acquisition bottleneck

  * Lack of general common sense knowledge.

  * CYC project small (Doug Lenat et al.). Attempt to manually encode millions of facts.

  * But the Internet is BIG place now. Now possible to automate encoding of facts (machine learning).

The Future
==========

Based on all this, I offer two predictions for the future. One, that we will see a growing number of rational computers but, two, they are going to be aliens (i.e. won't work exactly like human intelligence) with very different motivations, needs, and desires to us. Instead, the 21st century will see a menagerie of many different kinds of intelligence. Some you'll know about, like the book-buying assistants wired into Amazon.com that sometimes send you recommendations about what books to read. And some you won't even see-

  * like the Bayesian SPAM filter that eats silly emails,

  * like the power-grid specialist that spins up a coal-fired electrical plant since it has guessed that, in two hours time, there will be a spike in the power generation,

  * like the NSA data miners rushing SWAT teams to the airport cause it has realized we're going to be hit with a bomb attack in 20 minutes 19,18,17,....

Think of it as a jungle of AIs, working together, all living in their little ecological niches. And like any ecology, we'll learn that:

  * most can be ignored,

  * some have to be to avoided (don't step on the red ants- they sting)

  * while others are useful (if you tie up a flock of swans, you can fly to the moon).

AI Programming in LISP
======================

A fast skim, with examples, over Land of Lisp chapters 1,2,3,4,5,6,7,9,10,11,12

Cognitive Science
=================

This subject is about inhuman AI, all the tricks that computers can use to be smart that humans may or may not use.

Just to give the humans' a little more equality in this subject, today were going to talk about humans and AI. The field of cognitive science is devoted to discovering more about human intelligence using insights from a range of other areas including:

  * neuro-physiology

  * philosophy

  * linguistics

  * mathematics

  * cognitive psychology

  * AI

  * Neuro-physiology

Human brain cells are very different to computer chips. In your brain, there is:

  * More distributed processing;

  * No explicit representation mechanism stored at one bit location (no "grandmother cell" which, if it dies, all your knowledge of granny is lost).

  * Much more use of parallelism. Throw a pen at the lecturer (just kidding). My hand can jerk out to catch that pen in the time required for just a few neurons to fire. The idea that some sequential algorithm has solved the trajectory problem using matrix mathematics (lots of iterations of row and columns) seem very unlikely.

  * More use of a single structure (the neuron) used repeatedly (28 billion times)

  * Not this menagerie of parts:

  * But one part, repeated many times:

A nerve cell can have up to 1000 dendritic branches, making connections with tens of thousands of other cells. Each of the 10^11 (one hundred billion) neurons has on average 7,000 connections to other neurons.

It has been estimated that the brain of a three-year-old child has about 10^16 synapses (10 quadrillion). This number declines with age, stabilizing by adulthood. Estimates vary for an adult, ranging from 10^15 to 5 x 10^15 synapses (1 to 5 quadrillion).

Just to say the obvious- that's a BIG network.

Neuro-physiology is a very active field. The latest generation of MRI scanners allow for detailed real-time monitoring of human activity, while they are performing cognitive tasks.

This field shows great promise but, as yet, they are still working on locomotion and pain perception and vision and have yet to rise to the level of model-based reasoning.

The field of neural networks (http://en.wikipedia.org/wiki/Neural_networks) originally began as an experiment in exploiting massive repetition of a single simple structure, running in parallel, to achieve cognition. As the field evolved, it turned more into some curve fitting over non-linear functions (and the tools used to achieve that (http://www.autonlab.org/tutorials/neural.html) fit have become less and less likely to have a biological correlate).

For another example of AI research, initially inspired by a biological metaphor, see genetic algorithms (http://en.wikipedia.org/wiki/Genetic_algorithm).

Linguistics
===========

Noam Chomsky is one the towering figures of the 20th century. He's a linguistic and a political commentator. Every few years he disappears to re-emerge with a new book the redefines everything. For example, a lot of computer science parsing theory comes from Chomsky's theory of language grammars.

In AI circles, Chomsky is most famous for his argument that we don't learn language. Rather, we are born with a general grammar and , as a child grows all up, all they are doing is filling some empty slots referring to the particulars of the local dialect.

This must be so, argues Chomsky otherwise language acquisition would be impossible.

  * Children are exposed to very little correctly formed language. When people speak, they constantly interrupt themselves, change their minds, make slips of the tongue and so on. Yet children manage to learn their language all the same. This claim is usually referred to as the Argument from Poverty of the Stimulus.

  * Children do not simply copy the language that they hear around them. They deduce rules from it, which they can then use to produce sentences that they have never heard before. They do not learn a repertoire of phrases and sayings, as the behaviourists believe, but a grammar that generates an infinity of new sentences.

The implications are staggering. Somewhere in the wet-ware of the brain there is something like the grammars we process in computer science. At its most optimistic, this also means that grammar-based languages (like LISP, etc) have what it takes to reproduce human cognition. We'll return to this below (when we talk about the "physical symbol system hypothesis").

But is there really a "language" of thought? Or is this just an interpretation of chemicals sloshing around the dendrites (under the hood) which we interpret as language.

Well, there is evidence of some model-based manipulation by our wet ware. In classic mental rotation experiments (http://en.wikipedia.org/wiki/Mental_rotation), it was shown that the time required to check if some object was rotation of another was linear proportional to the size of the rotation. It is as if some brain box is reaching out to a sculpture of the thing we are looking at, the turning it around at some fixed rate.

Anyway, if ask a philosopher, "is it really neurons, or are their symbolic models in between our ears?", they might answer who cares?. Whatever stance works best is the right one.

Philosophy: part1 (we love AI)
==============================

Daniel Dennett asks a simple questions. Try and beat a chess playing program. What are you going to do?

  * Assume a physical stance and work out the physics and chemistry of the device? In this stance, you are trying to work out which way the wires will flow through the computer. Good luck with that.

  * Assume a design stance and reason about the biology or engineering of the device. Look for large functional blocks are reasoning about the next move of the chess playing computer by thinking about the surge suppressors, the coolant system, etc etc. Again, good luck with that.

  * Assume an intentional stance (the level of software and minds) where we ascribe beliefs, desires, intents/goals to a device, then act accordingly. For example, we might say "the program wants to take my queen and believes that if it offers me a trap, I'll fall into it".

Which is the right stance? The answer is, it depends. What do you want to do? Stop being short circuited by a loose wire? You want the physical stance? Beat the program at chess? You want the intentional stance.

Bottom line: a computer is not just "a machine". It is a mix of things, some of which are best treated like any other intelligence.

Don't believe me? Well, pawn to king four and may the best stance win.

(By the way, for a good introduction to AI and philosophy, see The Mind's I (http://en.wikipedia.org/wiki/The_Mind's_I)).

Philosophy: Part2 (AI? You crazy?)
==================================

I think therefore I am. I don't think therefore...

There used to be a savage critic by certain philosophers along the lines that AI was impossible. For example, John Searle is a smart guy. His text Speech Acts: An Essay in the Philosophy of Language. 1969 is listed as one of the most cited works on the 20th century (http://home.comcast.net/~antaylor1/fiftymostcited.html).

In one of the most famous critiques of early AI, Searle invented the Chinese Room: an ELIZA-like AI that used simple pattern look ups to react to user utterances. Searle argued that this was nonsense- that such a system could never be said to be "really" intelligent.

Looking back on it all, 27 years later, the whole debate seems wrong-headed. Of course ELIZA was the wrong model for intelligence- no internal model that is refined during interaction, no background knowledge, no inference, no set of beliefs/desires/goals, etc.

Searle's argument amounts to "not enough- do more". And we did. Searle's kind of rhetoric (that AI will never work) fails in the face of AI's many successes (http://menzies.us/pdf03/aipride.pdf).

Here's some on-line resources on the topic:

  * Wikipedia's entry on the Chinese Room (http://en.wikipedia.org/wiki/Chinese_room).

  * The original article Brains from The Behavioral and Brain Sciences, vol. 3. Copyright 1980

  * A spirited debate (http://www.nybooks.com/articles/archives/1982/jun/24/the-myth-of-the-computer-an-exchange/)  about this idea between Searle and Daniel Dennett. For my money, Searle's argument grows tired and stale against Dennett's insights.

And here's some more general links:

  * A very old FAQ (http://www.dontveter.com/caipfaq/index.html) from comp.ai.philosophy.

  * Some more recent AI & philosophy (http://en.wikipedia.org/wiki/Philosophy_of_artificial_intelligence) notes from Wikipedia.

Mathematics
===========

Godel's Incompleteness Theorem
------------------------------

There is some mathematical support for Searle's pessimism. In 1930, the philosophical world was shaken to its foundation in 1930 by a mathematical paper that proved:

  * For any consistent formal, computable enumerable theory that proves basic arithmetical truths, an arithmetical statement that is true, but not provable in the theory, can be constructed.1 That is, any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete.

  * For any formal recursively enumerable (i.e. effectively generated) theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent.

That is, formal systems have fundamental limits.

So Godel's theorem gives us an absolute limit to what can be achieved by "formal systems" (i.e. the kinds of things we can write with a LISP program).

Godel's theorem might be used to argue against the "logical school" of AI. If formal logics are so limited, then maybe we should ignore them and try other procedural / functional representations instead:

  * This is a very old debate

  * The proceduralists lost.

  * Logic turns out to be a very succinct way to describe an implementation. And in that uniform view, impressive optimizations can be achieved (e.g. Markov Logic).

  * Meanwhile, the proceduralists were left struggling to patch yet another specific mechanism with one value in one specific domain. There may indeed be a neural net in my that implements any number of procedural kludges, but it has had billions of years to evolve and patch (and patch again) those kludges. The experience of the 1990s is that we can go must further with logical AI than thought possible in the 1970s and 1980s.

BTW, I do not regard Godel's theorem as a limit to current research. I don't know the length of my 1000th hair above my right ear but I can still buy a house, write programs, balance my check book, etc. So Godel's theorem does not make me want to junk my LISP compiler and go off into procedural neural net land.

Cook and NP-Complete
--------------------

Godel's theorem is somewhat arcane. He showed that some things were unknowable but he did not say what those things are.

Enter Steve Cook. In 1971, he showed that commonly studied problems (e.g. boolean satisfiability) belong to a class of systems for which the solution takes exponential time to compute.

An army of algorithms researchers have followed Cook's lead and now there are vast catalogues of commonly studied programs (http://en.wikipedia.org/wiki/List_of_NP-complete_problems)  for which there is no known fast (less than exponential time) and complete (no heuristic search) solution.

BTW, Cook showed that there exist algorithms that can't implement a complete and fast solution to a wide range of problems. But neither can people. And (using stochastic search) we can get pretty good solutions pretty fast, even from pretty big problems.

Psychology (part1)
==================

O.K., so formal systems can never be omniscient, but how good do you have to be to "as smart as humans"?

The answer is, sometimes, not very smart at all. The cognitive psychology literature is full of examples where humans repeatedly reason in characteristic sub-optimal ways (see the wonderful Wikipedia page listing 35 decision-making biases and 28 biases in probability and belief and 20 social biases and 7 memory errors (http://en.wikipedia.org/wiki/List_of_cognitive_biases)).

AI
==

In fact, one the early successes of AI was not replicated some human cognitive skills, but also human cognitive failings. In the 1970s, AI researchers adopted the physical symbol system hypothesis:

     A physical symbol system has the necessary and sufficient means of general intelligent action.

Here, by physical symbol system they mean

     the basic processes that a computer can perform with symbols are to input them into memory, combine and reorganize them into symbol structures, store such structures over time,. . . .compare pairs of symbols for equality or inequality, and "branch" (behave conditionally on the outcome of such tests)

(Note that tacit in this hypothesis is Chomsky's language of thought and the notion that computers can think like people if they can push around symbols, just like the brain.) Rule-based programs designed around this hypothesis could replicate not just feats of human comprehension, but also human inadequacies in the face of (e.g.) limited short term memory or immature long-term memory (see Expert and Novice Performance in Solving Physics Problems, Science, 1980 Jun 20;208(4450):1335-1342 Larkin J, McDermott J, Simon DP, Simon HA).

Psychology (part2)
==================

The AI work did not come in isolation. The physical symbol system hypothesis, for example, owed much to decades of psychological research. In particular, the cognitive psychology research that evolved as a reaction to behaviorism (from the early part of the 20th century). In its most extreme view, behaviorism denied all internal states and allowed for only the objective study of externally observable behavior (i.e. no mental life, no internal states; thought is covert speech).

Well, that flew for a few decades then it just ran out of steam. After decades of trying to map human behavior into (what seems now) trite stimulus response models, cognitive psychology made the obvious remark that the same input yields different outputs from different people because of their internal models. That is, intelligence is not just a reaction to the world. Rather, it is the careful construction and constant review of a set of internal states of belief which we use to decide how to best act next.

Models of expert and novice behavior
====================================

(Reference: Science, 20 June 1980, Vol. 208. no. 4450, pp. 1335 - 1342 "Expert and Novice Performance in Solving Physics Problems", Jill Larkin, John McDermott, Dorothea P. Simon, and Herbert A. Simon. )

Much of the early AI research was informed by a cognitive psychology model of human expertise. The model has two parts:

  * LTM (http://en.wikipedia.org/wiki/Long-term_memory): A large long term memory (100,000s of patterns)

  * STM (http://en.wikipedia.org/wiki/Short-term_memory): A (much) smaller short term memory (seven, plus/minus two)

Reasoning was, according to this mode: a match-act cycle:

  * Content of the STM matches patterns in the LTM

  * LTM patterns have actions when, when they fire, rewrites the STM contents

  * Goto 1.

In this model

  * experts and experts because of the "power" patterns they have laboriously learned and added to their long term memory.

  * novices are novices because they clog short term memory with irrelevant goals

  * experts dodge that since their LTM patters tell them

Q: How to experts know what is relevant?

A: feature extractors- gizmos that experts learn to let them glance at a situation and extract the salient details. E.g. chess experts can reproduce form memory all the positions on a chess board But if you show the same experts a gibberish game (one where all the rules are broken- e.g white pawns on white's back row) then they can't reproduce the board. Why? Well, when they glance at a board, their feature extractors fire to offer them a succinct summary. Gibberish boards baffle the feature extractors, so no summary

Patch in context
----------------

We study AI to learn useful tricks. Sometimes, we also learn something about people. Here's a radically different, and successful, method to the above. What does it tell us about human cognition?

Ripple-down rules is a maintenance technique for rule-based programs initially developed by Compton. Ripple-down rules are best understood by comparison with standard rule-based programming. In standard rule-based programming, each rule takes the form
 rule ID IF condition THEN action
where condition is some test on the current case. In the 1970s and early 1980s rule-based systems were hailed as the cure to the ills of software and knowledge engineering. Rules are useful, it was claimed, since they: represent high-level logic of the system expressed in a simple form that can be rapidly modified.

However, as these systems grew in size, it became apparent that rules were surprisingly harder to manage. One reason for this was that, in standard rule-based programming, all rules exist in one large global space where any rule can trigger any other rule. Such an open architecture is very flexible. However, it is also difficult to prevent unexpected side-effects after editing a rule. Consequently, the same rule-based programs hailed in early 1980s (XCON) became case studies about how hard it can be to maintain rule-based systems.

Many researchers argued that rule authors must work in precisely constrained environments, lest their edits lead to spaghetti knowledge and a maintenance nightmare. One such constrained environment is ripple-down rules that adds an EXCEPT slot to each rule:
 rule ID1 IF condition THEN EXCEPT rule ID2 THEN conclusion because EXAMPLE

Here, ID1,ID2 are unique identifiers for different rules; EXAMPLE is the case that prompted the creation of the rule (internally, EXAMPLEs conjunction of features); and the condition is some subset of the EXAMPLE, i.e., condition ⊆ EXAMPLE (the method for selecting that subset is discussed below). Rules and their exceptions form a ripple-down rule tree:

At run time, a ripple-down rule interpreter explores the rules and their exceptions. If the condition of rule ID1 is found to be true, the interpreter checks the rule referenced in the except slot. If ID2's rule condition is false, then the interpreter returns the conclusion of ID1. Else, the interpreter recurses into rule ID2.

(Note the unbalanced nature of the tree, most patches are shallow. This is a common feature of RDRs).

Ripple-down rules can be easier to read than normal rules:

But in practice, Compton advises hiding the tree behind a difference-list editor. Such an editor constrains rule authoring as follows:

  * Recall that these rules are only ever added in response to some new EXAMPLE. That is, each rule is useful for at least one example.

  * Hence ripple-down rules never delete old rules; rather they are patched with EXCEPT rules.

  * These EXCEPT rules cover the special case that confused the parent rule. If the parent rule with condition1 has EXAMPLE1 and the new rule is being created in response to EXAMPLE2, then the new rule's condition2 must be formed from the features not used in the parent rule and must hold for the new EXAMPLE2; i.e.
     condition2 = EXAMPLE1 - condition1
     condition2 ⊆  EXAMPLE2

When users work in a difference list editor, they watch EXAMPLEs running over the ripple-down rules tree, intervening only when they believe that the wrong conclusion is generated. At that point, the editor generates a list of features to add to condition2 (this list is generated automatically from the above equations). The expert picks some items from this list and the patch rule is automatically to some leaf of the ripple-down rules tree.

Ripple-down rules are a very rapid rule maintenance environment. Compton et.al. report average rule edit times between 30 to 120 seconds for rule bases up to 1000 rules in size [Compton 2005]

AFAIK, ripple-down-rules are the current high-water mark in knowledge maintenance (http://menzies.us/csx72/doc/kbs/rdr2005.pdf).

Q: what does this tell us about human knowledge?

     [file search.texi not included]

     [file basicsearch.texi not included]

     [file advancedsearch.texi not included]

     [file games.texi not included]

Natural Language
================

Machine Learning
================

Rule-based Programming
======================

(Reference: Science, 20 June 1980, Vol. 208. no. 4450, pp. 1335 - 1342 "Expert and Novice Performance in Solving Physics Problems", Jill Larkin, John McDermott, Dorothea P. Simon, and Herbert A. Simon. )

Much of the early AI research was informed by a cognitive psychology model of human expertise. The model has two parts:

  * LTM (http://en.wikipedia.org/wiki/Long-term_memory): A large long term memory (100,000s of patterns)

  * STM (http://en.wikipedia.org/wiki/Short-term_memory): A (much) smaller short term memory (seven, plus/minus two)

Reasoning was, according to this mode: a match-act cycle:

  * Content of the STM matches patterns in the LTM

  * LTM patterns have actions when, when they fire, rewrites the STM contents

  * Goto 1.

In this model

  * experts and experts because of the "power" patterns they have laboriously learned and added to their long term memory.

  * novices are novices because they clog short term memory with irrelevant goals

  * experts dodge that since their LTM patters tell them

Q: How to experts know what is relevant?

A: feature extractors- gizmos that experts learn to let them glance at a situation and extract the salient details. E.g. chess experts can reproduce form memory all the positions on a chess board But if you show the same experts a gibberish game (one where all the rules are broken- e.g white pawns on white's back row) then they can't reproduce the board. Why? Well, when they glance at a board, their feature extractors fire to offer them a succinct summary. Gibberish boards baffle the feature extractors, so no summary

Enter rule-based programming
============================

Much, much work on	 mapping this cognitive psychological insight into AI programs

Success story #1: PIGE (not well known)
---------------------------------------

(Reference: "An Expert System for Raising Pigs" by T.J. Menzies and J. Black and J. Fleming and M. Dean. The first Conference on Practical Applications of Prolog 1992 . Available from http://menzies.us/pdf/ukapril92.pdf )

PIGE: Australia's first exported rule-based expert systems

Written by me, 1987 who trapped the expertise of pig nutritionists in a few hundred rules.

PIGE would find factors to control, try them on a simulator of a farm, then adjust its factors accordingly.

Here's PIGE out-performing the experts:

Why did PIGE success so well? Limits to short-term-memory. PIGE had none. The humans, on the other hand, had the standard human limitations

Success story #2: MYCIN (famous)
--------------------------------

( V.L. Yu and L.M. Fagan and S.M. Wraith and W.J. Clancey and A.C. Scott and J.F. Hanigan and R.L. Blum and B.G. Buchanan and S.N. Cohen, 1979, Antimicrobial Selection by a Computer: a Blinded Evaluation by Infectious Disease Experts, Journal of American Medical Association, vo. 242, pages 1279-1282)

Given patient symptoms, what antibiotics should be prescribed?

Approx 500 rules.

Extensively studied:

Compared to humans, performed very well:

Why did it perform so well?

  * Not because of the power of its algorithm (recursive descent through the rules- backward chaining)

  * But only because of the knowledge in its rules

  * In this case, algorithms, not knowledge, is power.

Success story #3: XCON and VT (very famous)
-------------------------------------------

John McDermott, DEC, 1980s. Two systems:

  * XCON, early 1980s, auto-configured DEC computers for customers. At its peak, 8,000 to 12,000 rules. Maintained by a team of 20 developers. Saving DEC (approx) $20M/year. (Reference: J. McDermott, 1993, R1 ("XCON") at age 12: lessons from an elementary school achiever, Artificial Intelligence, 59, 241-247)

  * VT, mid to late 1980s, designer of elevators, 7000 rules. (Reference: ". Marcus and J. McDermott, 1989, (SALT): A Knowledge Acquisition Language for Propose-and-Revise Systems, Artificial Intelligence, 39, 1, pages1-37.)

The First AI Bubble
===================

With strong theoretical support and excellent industrial case studies, the future for AI seemed bright.

Begin the AI summer (mid-1980s). Just like the Internet bubble of 2000: fledgling technology, over-hyped, immature tool kits.

And after the summer, came the fall. Enough said.

Happily, then came the 1990s, data mining, and results from real-time AI planners, and stochastic theorem provers.

By 2003, I could say I was an AI-nerd and people would not run away.

Inside Rule-based programming
=============================

Here's a good introduction on rule-based programming (http://menzies.us/csx72/doc/kbs/rules.pdf). Read it (only pages 1,2,3,4,5,6,7) carefully to learn the meaning of:

  * Conditions,

  * Actions

  * Backward chaining

  * Forward chaining

  * Working memory

Backward chaining supports how and why queries:

  * How did you prove this goal?

  * Why are you trying to prove this goal?

Forward chaining supports only how not why.

  * Explain.

Define match, resolve, act

  * With respect to the BAGGER system, define with examples conflict resolution using:

       * Rule ordering

       * Data ordering

       * Size ordering

       * Specificity ordering

     (Note: BAGGER is a toy example of how XCON configured computers.)

Rules: the Real Story
=====================

Rules- the good news
--------------------

Some nice advantages for software engineering:

  * Uniform representation simplified tool construction:

       * Rules are rules;

       * Feature extractors could be written as rules that run before anything else runs;

       * Conflict resolution operators could be written as rules.

       * For example, CMU's SOAR language added a whole meta-layer called TAQL (http://menzies.us/csx72/doc/kbs/yost99.pdf) to handle: Within each problem space: problem space proposal, problem space initialization;

       * For each state in a problem space: state initialization, state elaboration, state evaluation

       * For each operator that can jump you between states: operator proposal, operator selection, operator implementation, how to handle operator failure, operator evaluation

     And guess what- all this was code with rules!

But Rules Have Problems
-----------------------

As rule-based programs became more elaborate, their support tools more intricate, the likelihood that they had any human psychological connection became less and less.

As we built larger and larger rule bases, other non-cognitive issues became apparent:

  * Speed: within match-resolve-act, 80% of the time is spend in match.

  * Maintenance: any rule can change the working memory to effect any other rule. XCON was the commercial AI success story of the early 1980s and the maintenance nightmare of the mid-1980s.

       * What works for 400 rules does not work for 8000

       * At its peak, DEC was claiming it saved the, $20M/year (which, in 1984, was real money!) but if any of XCON's 20 developer's left, ouch!

Note that both these problems come from the global nature of match: all rules over all working memory.

  * A search by all rules through all possible working memory contents is slowwww.

  * When humans maintain rules, understanding the connections between rules is difficult.

Improving Rule-based Programming
================================

Solution #1: throw away rules.
------------------------------

Go to simpler representations. e.g. state machines (used in gaming, next lecture)

Solution #2: the RETE network
-----------------------------

As used in many rule-based tools including OPS5, ART, JESS.	 Compile all the rules into a big network wiring all the conditions together.

  * If 10 rules make the same test, represent the test once in the network.

  * New facts get dropped into the top, bubble over the network, and matched actions pop out at the bottom.

  * A little complex to implement (to say the least):

  * Alpha nodes; matching within one test (e.g. a ≤ 7);

  * Beta nodes: matching between tests (joins across tables)

  * But what is Type? select?dummy?

RETE supports standard resolution operators: e.g.:

  * Specificity: number of links in the network;

  * Data ordering: when advancing over the net, work left to right, most recent to oldest

Note: RETE changes some constant time factors in the search but does not tame the fundamental problem of all rules looking in all places all the time.

Solution #3: divide the global space
------------------------------------

If searching/understanding all is too much, find ways to built the whole from local parts. Have separate rule bases for each part.

Q: How to divide the system?

A1: Using domain knowledge; e.g. from [Tambe91]:

A2: using background knowledge of problem solving types. Add tiny little specialized rule bases to the implement knowledge-level operators.

E.g. here's Clancy's abstraction of MYCIN:

And here's his abstraction of an electrical fault localization expert system:

Note that the same abstract problem solving method occurs in both

A whole mini-industry arose in the late 1980s, early 1990s defining libraries of supposedly reusable problem solving methods.

e.g. Here's "diagnosis"

Here's "monitoring":

Note that you could write and reuse rules based to handle select, compare, specify.

And there's some evidence that this is useful. Marcus and McDermott built rule bases containing 7000+ rules via role-limiting methods. That is, once they knew their problem solving methods, they write specialized editors that only let users enter in the control facts needed to just run those methods.

  * If you can't use it...

  * ... don't ask for it.

For a catalog of problem solving methods, see Cognitive Patterns (http://www.amazon.com/Cognitive-Patterns-Problem-Solving-Frameworks-Technology/dp/0521649986) By Karen M. Gardner (contributors James Odell, Barry McGibbon), 1998, Cambridge University Press

Student Projects
****************

Students will work in groups of three. Group membership will be randomly assigned. All group members will have the same mark, except (at the discretion of the tutor) if the the group peer assessment forms (studentPeerEvaluation.doc) show uneven effort by group members.

Overview
========

We will learn LISP and AI, one games at a time, using the text http://j.mp/hiZMjS (Land of Lisp).

For more on Land of Lisp: watch the videos:

  * The rock video (http://www.youtube.com/watch?v=HM1Zb3xmvMc) (4 mins)

  * The lecture (http://vimeo.com/9605639) (8 mins)

Groups
======

Students will work in groups of three.

1 : rault rmoneype zcowell

2 : abenabde jlake8 oatif

3 : jyaworsk wsmolder ashepard

4 : lblake2 mgharee2 nclay1

5 : cbrown50 jcraig6 dswisher

6 : cmcgee1 rrawling nnewman1

7 : acosta1 jsheppa3 kcruse1

8: mkobe dharlan2 bokanyme

FYI: students were assigned to groups, at random, using this script:

cat names |
gawk 'BEGIN { srand('$RANDOM')} {N[rand()]=$0} END {for(i in N) print N}'

Setting up
==========

Initial Set up
==============

Before doing the regular weekly setups, perform the following one-time steps.

Setting up Subversion
---------------------

  * Find out your group number (XX)

  * Run these commands:
     cd ~/
     mkdir  svns
     cd svns
     svn co  https://websvn.lcsee.wvu.edu/cs472gpXX 472

Setting up Lisp
---------------

Edit the file $HOME/.emacs and add this line:
(load  "/home/timm/etc/dotemacs.lisp")

Weekly set up
=============

Say you are setting up for project 1, homework a.

One person in the group  run these commands
cd ~/svns/472
svn mkdir 1
cd 1
svn export http://unbox.org/wisp/var/timm/11/472/src/1/a a
cd ~/svns/472
svn commit -m 'project 1a created'

Then, everyone else runs these commands on their accounts:
cd ~/svns/472
svn update

Now, everyone in the group can edit and share the same files.

Submitting
==========

If you've exported my files to your directories, then you should see at least the following files:

$ ls go*
go*     go_bash*    go_lisp

To run your system, you must edit a file boot.lisp that loads your lisp system. This file is called by go_lisp in the following script (the contents of which, you can ignore):

#|
exec sbcl --noinform --load $0 --end-toplevel-options "$@"
|#
(load "boot.lisp")
(quit)

Now go_lisp is called by go which looks like this:
[ -f go_bash ] && bash go_bash
nice -n 20 sh go_lisp
[ -f stop_bash ] && bash stop_bash

Note that before and after we call go_lisp, we look for any shell commands in go_bash or stop_bash. So, if you want to show your source code, you could edit go_bash:

cat aa.lisp bb.lisp cc.lisp

Or, if you want to show what output files were generated by your lisp code, you could edit stop_bash:

cat out.txt

To prepare your weekly handin, one member of your group must run the following command:
 ~timm/bin/handin homeWorkNumber groupNumber lastname1 lastname2 lastname3...
where homeWorkNumber is something like 2c and lastname is the last name of each member of the group. For example:

~timm/bin/handin 2a 22 zedong washington

This command generates a file ~/tmp/2print.pdf in your tmp directory. This file stores a pretty print of what happens when the go command (mentioned above) is executed.  Here's a sample file (2print.pdf) (and a real one would have much more content).

To hand in your homework, print out ~/tmp/2print and hand it in to the box outside 841a before the Thursday class. Note that:

  * These homeworks will not be collected at the lectures.

  * If you do not staple your file, it will not be marked.

Project1: Basics
================

In this project you do some intro LISP exercises and write your first game.

Warming up
----------

How to hand in
==============

Following the Submitting instructions, edit the file ~/svns/472/1/a/go_bash to include the lines

report() {
       for i in $*; do
              echo ""
              echo "=====|  $i |============================"
              cat $i
       done
}

report boot.lisp repl.txt keystrokes.txt log.txt

Then following the following steps to generate the report files.

Finally, run the handin code (described in Submitting).

What to hand in
===============

Report the REPL log (described below) and all the lisp files you created or modified.

Setting up
==========

Follow the initial set up instructions.

Perform the weekly set up instructions for project 1, homework a.

Exercise 1: Learning Emacs
==========================

Open Emacs using emacs boot.lisp. You should see two buffers: one with boot.lisp and one with the REPL (the interactive read-eval-print loop of LISP).

In the REPL,  work out what one plus one equals.

In the file boot.lisp, add a format statement on the last line saying "COBOL is the bestish language in the whoooole world...NOT":

(format t "COBOL is the bestish language in the whoooole world...NOT")

Save the file (using C-xC-s) then load it from the REPL:

(load "boot.lisp")

Now you should see in the REPL lines that look like this:

; SLIME 2009-09-08
CL-USER> (+ 1 1)
2
CL-USER> (load "boot.lisp")
;tricks.lisp
LITHP ITH LITHTENING
COBOL is the bestish language in the whoooole world...NOT
T
CL-USER>

Save the REPL buffer to a file (using C-xC-x) called ~/svns/472/1/a/repl.txt.

Exercise 2: Learning more Emacs
===============================

Write down a file ~/svns/472/1/a/keystrokes.txt that shows what keystrokes in Emacs:

  * Save a file

  * Open a new file

  * Split a buffer in two, vertically

  * Split a buffer in two, horizontally

  * Start a shell in a buffer (hint: is it  M-x eshell?)

Hint: http://www.columbia.edu/acis/publications/emacs.html.

Exercise 3: Sing a song together
================================

Take the West Virginia fight song (http://lyricsondemand.com/miscellaneouslyrics/fightsongslyrics/westvirginiafightsonglyrics.html) and break it up between all group members.

In the directory ~/svns/472/1/a, every member of the group write a file lastname.lisp that prints their bit of the entire song. e.g.

(format t "Let's give a rah for West Virginia~%")
(format t "And let us pledge to her anew,~%")
(format t "Others may be black or crimson,~%")
(format t "but for us it's Gold and Blue.~%")

Then, edit boot.lisp so that it loads every one's file.

Finally, make sure the whole song prints:

bash go_lisp

Exercise 4: Learning Subversion
===============================

Run this command :
cs ~/svns/472/1/a
svn log > log.txt

Edit that file. Write a comment at the end describing what you see.

Lisp101
-------

Code all the examples chapters 1 to 4 of LandOfLisp.

Most of this code are little 3 liners and these can be demonstrated using deftest (as shown by the lecturer).

For the guessing the numbers game, you need to run a session in the REPL, then save that buffer to guess.txt.

Important:
     Find some way to divide up the work so that the whole system is at least 3 files (one for each member of the group) which are loaded by boot.lisp. Each file name should include the last name of the author of that file.

Even more important:
     Come demo time, anyone may be asked about anyone else's file. So make sure you can read an understand each other's code.

Text Game Engine
----------------

Code Chapter 5 of LandOfLisp, with the modifications discussed below.

What to hand in
===============

Report the REPL log (described below) from running rwalk!-worker (see below) and all the lisp files you created or modified.

Hints
=====

You may need to know about the following LISP commands (see Graham): dolist, dotimes, list, append, let, let*, if, when, unless, setf, mapcar, lambda.

Random Landscapes
=================

Create random landscapes using (landscape n f1 f2) where n is the number of nodes and f1,f2 are the min to max fanout from a room (number of rooms connecting to this one). Internally, landscape will rewrite the *edges* and *nodes* and *objects* and *objects-location* variables.

To do this, create the random *nodes* first then, create random edges by selecting f1 to f1  nodes, at random. To select the right number of nodes from the fanout, use
(defun within (x y) (+ x (* (- y x) (randf 1.0))))

(round (within f1 f2))

To create random node names, e.g. use (gensym "garden").  To create random descriptions, just use (format nil "You are in ~a.~%" nodeName).  To add the new node to *objects* using (push newnode *nodes*).

To pull a random node, use
(defun any (alist)
  (nth (randi (length alist)) alist))

(any *nodes*)

To create random objects, use e.g. (gensym "sword") then put them into randomly selected rooms.

Random Walk
===========

Write a random walk routine that walks around the random landscape, picking up everything it encounters, everywhere:
(defun !rwalk-worker (&optional (rooms 20) (f1 1) (f2 5) (steps 100))
    (reset-seed)
    (landscape 20 1 5)
    (format t "nodes: ~a~%~%edges: ~a~%~%objects: ~a~%~%at: ~a~%~%"
            *nodes* *edges* *objects* *object-locations*)
    (dotimes (i steps)
           (rwalk))
    (inventory))

Write a deftest that uses !rwalk-worker that checks for the right inventory output.

Project 2 : Grand Theft Wumpus
==============================

In this project, you will explore ISSAMP and influence maps in the context of the Grand Theft Wumpus game.

2a: Setting up
--------------

As before:

  * Work in a new directory (2/a) and start by exporting my code from my (2/a).

  * Also, hand in the 2print.pdf stuff- report on all the changed files, show the results of your deftests, etc etc.

Note that:

  * You are about to enter the weird and wonderful world of randomized search. Remember that your deftests will not work unless you first (reset-seed).

  * You starting to work with  conrad's code. this has not been done before at this site. so, you are all now systems programmers, porting code from platform to platform, lisp to lisp. act like fourth year students at a research-level-one university. if you meet problems, fix them and report them to the subject newsgroup.

To help you with the debugging, the following pages may be useful:

  * The  the errata section of the Land of Lisp book (http://landoflisp.com/errata.html). Here, you can find fixes to Conrad's.

  * The land of lisp google group (http://groups.google.com/group/land-of-lisp). A word of caution about this group- if you ask questions there, remember that the tone of your posts will skew people's perceptions of your university. Try to solve your own problems before you ask questions in a global arena. And if you do ask questions, be courteous, be brief, and do not flame/ nag/ or pester. And try to offer more information back that what you take from that source.

Your task is to:

  * Get Grand Theft Wumpus running on CSEE machines (see the files wumpus.lisp and graph-util.lisp, which are loaded by the boot.lisp file in my downloads). This will requiring finding the location of the dot program. On my Mac it is /opt/local/bin/dot but on your system, it could be somewhere else (hint: use which dot to get the pathname).

What to Hand In
---------------

As before, report any changed code.

Include in your stapled layout a png generated by graph-util of the biggest wizard landscape you generated in 1c.

Also, hand in a repl session of you playing wumpus.

2b: Dumb Wumps agent
--------------------

This week, we'll add an automatic wumpus walker. It will be pretty stupid. We'll make it smarter next week.

Work in a new directory (2/b) and start by copying your 2/a code into 2/b.

To do:

  * Get rid of the all the globals in GTF. Replace them with a working memory (hereafter, wme) consisting of...
     (defstruct wme edges nodes pos visited)
     Now add a w var that is initialized at start of game and carried around all the wumpus code.

  * Convert GTW from manual to automatic. So the code now longer reads input from the REPL by a function that asks "where can i go?" and selects one direction, as per the next point.

  * Dumb wumpus gets a set of nodes and orders them by some value heuristic. Then selects the top one of that order (if ties, then it picks at random). Given the rules of the game, given a set of out edges from one node, implement a sort order on those edges.

Internally, this will be some multi-utility functions that does feature extraction of each edge (sirens? glow? stink?, whatever, use your creativity) and weights these is some way; e.g.

; something like this. note: written, not tested
(defun what2DoNext (node)
    (let* ((edges  (edges-from-this-node node))
           (scored (mapcar #'edgeScore edges))
           (sorted (sort scored #'> :key #'car)))
      (second (first sorted))))

(defun edgeScore (e)
    (let ((sirens? (hasSirens  e))
          (glow?   (hasGlow    e))
          (etc?    (otherStuff e)))
       (cons (edgeScoreFn sires? glow? etc?) e)))

(defun edgeScoreFn (sirens? glow? etc?)
    "a b c  are weights on different heuristic search measures"
     (+ (* a (if sirens? 1 0) (zip))
        (* b (if glow?   1 0) (zip))
        (* c etc)             (zip)))

(defun zip ()
    "Returns a random number between 0.99 and 0.999.
     Enables random selection."
    (+ 0.99 (randf 0.009))
)

What to Hand In
---------------

As before, report any changed code.

Also, hand in a REPL session of dumb wumpus playing the game. Include enough trace info so the REPL session reveals what is going on. Include displays of moves, deaths, captures, etc in the REPL text.

Text files (short) describing your edge ranking heuristics.

Smart Wumpass
-------------

Smart Wumpus using Influence Maps and ISSAMP

Work in a new directory (2/c) and start by copying your 2/b code into 2/c.

Influence Maps
--------------

Look at a map of the earth. Before we explore it, we might know where are the hills and valleys. But we don't know which oceans have dragons and which ports have labor relation problems. We can only learn that from experience.

So take a second piece of paper- thin paper- and lay it over the first map. Now send 100 ships around the world with orders to mail back locations of dragons, hurricanes, riots, etc. Color the overlay  with red for every place something bad happened to one of these explorers.

Now, when the 101-th ship sails off, it takes two maps. One of the earth, and the overlay (which we will call an influence map). Now, when charting a new course, our captain adds together the distance of the trip along with the number of trouble spots meet on the way. The captain, if she is wise, picks the route which minimizes miles and trouble spots.

ISSAMP
------

ISSAMP (iterative sampler) is a stochastic explorer. At any time, it selects any option at random. If anything goes wrong, ISSAMP aborts and jumps back to the root and starts all over again. Since ISSAMP does not waste time trying to be clever to fix any problem, it can explore more, faster.

ISSAMP and WUMPUS
-----------------

ISSAMP can be used to iteratively build influence maps. Consider Grand Theft Wumpus, with one addition. Suppose that when our explorer is caught, or dies, they hit a special button on their vest that detonates a stink bomb that spreads N edges from the location of their misfortune. The stink obviously weakens as it spreads so all edges immediately adjacent to capture/death get 0.5 units of stink, all edges adjacent to that get 0.25 units, all edges adjacent to that gets 0.125 (after that, the stink is too faint to smell).

We will assume that this stink is really hard to wash off. It lingers, forever. So the stink for each explorer adds to the stink of all previous ones.

How to do it
------------

So the scenario is this:

  * Your family is shamed by you being tricked by the wumpus. Hence, the clan has come to support you.

  * One by one they go off into Congestion City. If they are caught, or get captured, you can just hear the sound of their stink vests going off (actually, its the sound of the locals holding their noise and going "phew, yuck, can anyone stop that stink???").

  * Each new explorer may stumble across the stink of failure of the prior explorers (the influence map).

  * Which means, when they are considering what edge to take next, they can sort possible edges according to their sirens, blood trails, glow and by how much they stink.

To implement this, you need some data structure that stores the amount of stink in each edge.

Then you need to augment the edge sorting heuristics implemented last week such that edge stink changes where our agent walks next. Internally, this will be some multi-utility functions that does feature extraction of each edge (sirens? glow? stink?, whatever, use your creativity) and weights these is some way; e.g.

(defun edgeScore (sirens? glow? stink? etc?)
    "a b c d are weights on different heuristic search measures"
     (+ (* a (if sirens? 1 0) (zip))
        (* b (if glow?   1 0) (zip))
        (* c stink)           (zip))
        (* d etc)             (zip)))

(defun zip ()
    "Returns a random number between 0.99 and 0.999.
     Enables random selection."
    (+ 0.99 (randf 0.009))
)
Then, you need a main driver that sends of explorers, waits for their stink to go off, they adjusts the edge stink weights before the next explorer goes off.

Finally, you need to experiment with your rig:

     Record the number of explorers required before we find the wumpus.

  * See how that number is altered by setting different values of  a,b,c,d

What to Hand In
---------------

All your changed, new, LISP code.

Charts that show which (if any) combinations of a,b,c,d mean we find the wumpus faster.

All stapled up, as usual.

Project3 : Evolutionary Algorithms
==================================

3a: Setting up
--------------

As before, work in a new directory (3/a) and start by exporting my code from my (3/a).

What to do:

  * Get Conrad's code running for 5,000,000 days. See if you can confirm (or deny) the graph on p217 (i.e. do we tend to evolve two breeds)?

  * Code an extension to Conrad's evolution.lisp file (it is in 3/a). Do *not* run the extension- that is for next week. But to code this extension, you have to understand how to hook into Conrad's code. Note that your new code can contain deftests, even if it does not run.

Note that you can generate distributions using simple ascii graphics (see the dist function in 3/a's tricks.lisp). e.g.
> (dist '((apple . 30) (dogs . 40) (beds . 20)))
                                        ******************** : BEDS
                              ****************************** : APPLE
                    **************************************** : DOGS"

In this extension, animals have four preference wheels (right now, they only have one: genes). One of them controls direction (taken from the current code). Wheels two and three controls what happens when two animals are side my side.  For these two wheels, the zero pos is aligned to neighbor and then the animal moves in a direction according the weights in that wheel (so this overrides the current wheel in Conrad's code). Wheel two controls same gender meetings and wheel tree controls different gender meetings. Moving in position 0 means "stay".

  * If different genders "stay" then they mate, (if their energy is above *reproduction-energy*), losing half their energy to their kid (so the kid gets two lots of energy from mummy and daddy). As with Conrad's current game, the wheels from mummy and daddy mutate and pass to the kid. Each wheel is passed separately (so their genes do not mingle). But now, mummy and daddy's genes combine before passing (using two-point crossover).

  * If same genders "stay" then they fight. Each animal expends a random amount of their remaining energy on the fight, controlled by wheel four. The one who expends the most energy lives and the other dies.

If an animal has more than two neighbors, then a random pair is picked at the others are ignored.

What to hand-in:

  * For the as-is game: a graph like p217 and a text file commenting on whether or not we got two breeds.

  * For the new game : a new version of evolution.lisp with the new code installed and lots of comments describing its behavior.

3b: Baselining
--------------

As before, work in a new directory (3/b) and start by exporting my code from my (3/b).

WARNING: this is an exploratory project for code that has never run before. I have no idea what will happen when they new, sexed-up, animals get running. So there is an X% chance that all your animals will instantly die and we'll have to think about the direction of this project.

Anyway, enough hedging...

What to do:

 1. Get your code running from 3a. Remember to run things with nice -n 20 (as done in go).

 2. Optimize your code. For a small number of days (say 100,000) run evolution inside the watch command in tricks.lisp. See if you can find any hotspots that can be optimized.

 3. Run your optimized system for  5,000,000 days (and if that is too slow, go for smaller numbers). Generate distributions for the preference wheels. See if you can find multiple species evolving in this space.

What to hand in:

  * All you code, deftests, as per usual.

  * The results from watch, see if you can see a hotspot also a text file commenting on the hot spots, and what you can do about it.

  * Your distributions see in point 3 (above) as well as a text file commenting on the distributions that you see.

3c: Improvements
----------------

In the GA lecture, there are some standard settings for GAs:

All generalities are false. But, just to get you started:

 1. Population size: 50

 2. Number of generations: 1,000

 3. Crossover type: typically two point

 4. Crossover rate: 60%

 5. Mutation type: bit flip

 6. Mutation rate: 0.001

Using the new sexier animals, see which (if any) of the above matter.

You'll need to define a success function: minimize population variance over the generations while increasing population and life expectancy,

What to hand in:

  * All your code and deftests, as before.

  * A pdf report (*no* MS-WORD)  that defines all the above 6 items and shows the effect of altering them on your animal population, population variance, population life expectancy. Cool graphics please! That report should have all the names of the team members on page 1 and include a recommendation about what settings are best for your species.

Project4: Very Large Games
==========================

Tips and Hints
**************

Slime short cuts
================

Slime selector
==============

C-c s calls the slime-selector function:
Select Methods:

4:     Select in other window
?:     Selector help buffer.
c:     SLIME connections buffer.
d:     *sldb* buffer for the current connection.
e:     most recently visited emacs-lisp-mode buffer.
i:     *inferior-lisp* buffer.
l:     most recently visited lisp-mode buffer.
n:     Cycle to the next Lisp connection.
q:     Abort.
r:     SLIME Read-Eval-Print-Loop.
t:     SLIME threads buffer.
v:     *slime-events* buffer.

(BTW, my favorite SLIME short-cut is C-c s r- which jumps me back to the SLIME repl.

Finding definitions
===================

M-.
     Edit the definition of the function called at point.

M-,
     Pop the definition stack to go back from a definition.

Programming aids
================

C-c TAB
     Complete the Lisp symbol at point. (Also M-TAB.)

C-c RET
     Macroexpand once.

C-c M-m
     Macroexpand all.

Cross-referencing
=================

C-c C-w c
     WHO-CALLS a function.

C-c C-w r
     WHO-REFERENCES a global variable.

C-c C-w s
     WHO-SETS a global variable.

C-c C-w b
     WHO-BINDS a global variable.

C-c C-w m
     WHO-MACROEXPANDS a macro.

C-M-.
     Goto the next reference source location. (Also C-c C-SPC)

Documentation commands
======================

C-c C-d
     Describe symbol.

C-c C-a
     Apropos search.

C-c M-d
     Disassemble a function.

Evaluation commands
===================

     C-M-x Evaluate top-level from containing point.

C-x C-e
     Evaluate sexp before point.

C-c C-p
     Evaluate sexp before point, pretty-print result.

Bibliography
************

A to F
======

stuff

G to M
======

N to T
======

stuff

U to Z
======

stuff