Exercises from Nilsson's Principles of Artificial Intelligence

Gene Michael Stover (gene@acm.org)

created Tuesday, 2021 December 21
updated ????

Chapter 1. Prodction systems and AI

Ex 1.1. priests & cannibals

      lisp> (load "ex_01_01.lisp")

      lisp> (in-package "NILSON_PRINCIPLES.EX_01_01")

      lisp> (run)
       ;; final state
      (#S(WORLD :PRIESTS 3 :CANNIBALS 3 :BOAT? T)
       ;; list of operations in reverse (first in list was
       ;; last operation)
       (CANNIBALS-FROM-START CANNIBAL-FROM-TARGET
                             CANNIBALS-FROM-START
                             CANNIBAL-FROM-TARGET
                             PRIESTS-FROM-START
                             BOTH-FROM-TARGET
                             PRIESTS-FROM-START
                             CANNIBAL-FROM-TARGET
                             CANNIBALS-FROM-START
                             CANNIBAL-FROM-TARGET
                             CANNIBALS-FROM-START))
      3388  ; worlds examined
      3533  ; maximum depth of queue
    

It takes about 1 second to run. That's quick enough, though I can imagine that in about 1981 on my Atari 800 it would have taken minutes, maybe an hour. And on a computer in the 1960s, it could have taken longer than that.

I believe the list of operations is correct. Notice that they are in reverse order that they were applied. Here's a table to show the actual solution, in order...

I hard-coded each of the operations. Each one verifies that the boat is on a certain side. If so, it creates a new world with updated counts & with the boat on the other side. Each operation could perform other checks before creating the new world, but since the conditions to detect failure are always the same, I put them in an is-lose? function & called that from the loop.

As I said in the comments in ex_01_01.lisp, a more general, more flexible solution would probably break the preconditions out of the operations & express them as data that the driver could examine. However, I wanted to do this quick-&-dirty (cuz face it, I won't be using this elsewhere), & I also wanted to see just how cumbersome it is to express each operation as a function that integrates the preconditions with the world-generation code.

Some things I learned & observed include...

• If each operation checks its own preconditions, returns an empty list when they don't apply, & if the overhead of a function call isn't too terrible (which is true on a modern computer), then the driver can simply call all of the operations. You could still break the preconditions out of the operations, but the driver wouldn't need to know about them.
• Unless you build code that constructs the operations, you'll write a lot of operations. To do that, you must recognize all of the operations. That has a lot to do with the data structures you used for the world. In the end, when you program it this way, your ability as a programmer is large compared to the work required to solve the problem once you have programmed it. Solving the problem (the work that your program does) is like uncoiling a spring; your insights while programming determined the spring. It makes you question the capability of the “artificially intelligence” algorithm.
• The hard-coded operations are often done by copy, paste, & edit (of operations you already did). I seriously suspect that this is why the early A.I. programmers (the famous ones, the ones whose names you know) so often claimed that what A.I. needed was “common sense”.
  I mean, as you are copy-&-pasting a few operations so you can find-&-replace some text in them, you are thinking about how, if your program already had some knowledge of the world, you could give it the same problem description you were given, & it could figure out the operations. Those early A.I. programmers must have been thinking the same thing as they wrote one searcher after another, & they concluded that the basic knowledge of the world was “common sense&rduo;.
  I recognize that “common sense&rduo; or something similar is necessary for a general intelligence, but I've always felt it was over-emphasized (before about 1990). I suspect that I now see where the source of the idea.
• I can see that, if you have a problem that's more complicated than this priests-&-cannibals toy, you'll have a lot more operations, easily thousands of them. And they won't be as discrete & as easily recognized. Defining & programming the operations transforms from mild annoyance at the repetitive code to nearly impossible without a program to do it for you.
• It is nifty to see the working program find a solution to the problem, but given that I had to spell out the problem & the operations in such standard (for programming), mind-numbingly specific detail, it is difficult to see how anyone could have mistaken this type of algorithm for intelligence. At the same time, the annoyance at the copy-&-paste code leads to thoughts of a program that could recognize the operations on its own leads to thoughts of, if not a program that would be intelligent in real-time, then might be an offline problem-solver in a box.
• Overall, this simple exercise was elucidating.
• I'm sure that I have written similar programs before, but it was probably in college in about 1990. I had forgotten about them.

Ex 1.2. water jugs

      lisp> (load "ex_01_02.lisp")

      lisp> (in-package "NILSON_PRINCIPLES.EX_01_02")

      lisp> (print-world (run))
      Start. [0, 5]
      Pour 2 from 5 into 2. [2, 3]
      Pour 2 from 2 onto the ground. [0, 3]
      Pour 2 from 5 into 2. [2, 1]
      Pour 2 from 2 onto the ground. [0, 1]
      Pour 1 from 5 into 2. [1, 0]
      PRINT-WORLD
    

Things I learned & observed in exercise 1.2 include...

• I was able to re-use the general structure & the breadth function from exercise 1.1 with little modification. That was convenience.
• One modification was that operations return a new world or nil. (In exercise 1.1, an operation returns a list of worlds. The list could be empty.)
• Instead of hard-coding each operation, I wrote functions that crated the operations. So I wrote 3 such functions. All together, they created 6 operations. That was an improvement compared to hard-coding every operation in exercise 1.1..
• An early run resulted in an infinite loop. This caused me to make the is-lose? function look for repeated world states. That didn't fix the infinite loop. I realized that I had forgotten one type of operation (2 operations). Once I implemented them, the program worked fine.
• As when I programmed exercise 1.1 & experienced the nit-picky debugging difficulties (unlike debugging, say, a parser or a network protocol), I could imagine how the historical A.I. programmers, writing one after another program of this nature, would think “If only the program was already smart enough to understand the problem, it could generate these operations & the data structures itself, no need for me to do it”. It's a chicken-&-egg situation, & I am certain that the thought occurred to those old programmers.

Ex 1.3. generate sentences

Describe how the rewrite rules of section 1.1.6 can be used in a production system that generates sentences. What is the global database and the termination condition for such a system? Use the system to generate five grammatical (even if not meaningful) sentences.

Instead of simply describing & then generating sentences by hand, I'll write a program that really does generate sentences. ex_01_03.lisp

      lisp> (load "ex_01_03.lisp")

      lisp> (in-package "NILSON_PRINCIPLES.EX_01_03")

      lisp> (sentence)

      ("any" "stinky" "feline" "new" "stinky" "electric" "human" "observes"
       "a" "electric car" "into" "an" "aromatic" "president" "of" "an"
       "rocket")

      lisp> (sentence)

      ("a" "aromatic" "cat" "repairs" "any" "couch")

      lisp> (sentence)

      ("an" "green" "stinky" "cat" "of" "the" "robot" "of" "this"
       "black bear" "from" "the" "red" "red" "ancient" "chair" "with" "the"
       "computer" "by" "some" "stinky" "humming bird" "into" "the"
       "computer" "by" "an" "electric" "sale" "by" "the" "brown bear" "by"
       "that" "human" "into" "some" "lionine" "aromatic" "new" "stinky"
       "human" "with" "some" "new" "android" "with" "the" "lionine"
       "rocket" "from" "some" "recreational" "electric car" "of" "this"
       "green" "new" "stinky" "aromatic" "rocket" "from" "the" "stinky"
       "dog" "from" "an" "human" "by" "an" "lionine" "ancient" "feline"
       "humming bird" "by" "some" "electric car" "in" "an" "rocket" "in"
       "this" "ancient" "lionine" "new" "ancient" "electric" "stinky"
       "stinky" "mauve" "lionine" "red" "new" "stinky" "stinky" "cat" "of"
       "a" "humming bird" "with" "any" "chair" "from" "some" "new" "robot"
       "from" "any" "cat" "by" "that" "aromatic" "green" "new" "sale"
       "from" "this" "humming bird" "with" "that" "electric" "electric"
       "green" "stinky" "feline" "electric car" "with" "the" "new" "chair"
       "from" "an" "new" "stinky" "brown bear" "of" "the" "aromatic"
       "black bear" "with" "the" "president" "from" "any" "rocket" "by"
       "some" "robot" "from" "an" "ancient" "aromatic" "brown bear" "of"
       "an" "green" "couch" "into" "some" "new" "green" "electric car" "by"
       "an" "brown bear" "of" "that" "president" "by" "an" "electric"
       "chaise lounge" "fixes" "some" "green" "red" "red" "couch" "from"
       "the" "dog" "into" "an" "feline" "stinky" "chair" "from" "any"
       "green" "chair" "by" "that" "red" "feline" "company" "into" "some"
       "mauve" "lionine" "aromatic" "sale" "with" "a" "aromatic"
       "brown bear" "with" "a" "couch" "by" "an" "couch" "of" "that"
       "mauve" "brown bear" "in" "some" "red" "green" "brown bear")

      lisp> (sentence)

      ("that" "rocket" "wonders" "the" "mauve" "dog")

      lisp> (sentence)

      ("a" "stinky" "sale" "observes" "some" "chair")
    

I added a lot of words to the generative grammar in the book.

The assignment was easy & fun.

Ex 1.4. Tom vs Paul Revere

Easier to start with Tom & work back to Paul Revere.

Reason is that Tom should be able to name his ancestors, or most of them. It'll be a sequence of N people, where N is roughly (2020 - 1776) / 20 = 12 people. Tom should have the names of most of them, so you just look them up from most recent to oldest (which should be Paul Revere).

If Tom cannot name his ancestors, then the work for each technique depends. There are 2 cases...

• If you start with Tom & work backwards without names (other than Tom's), you must lookup the parents of a person, then lookup the parents of each of them. Everyone has 2 parents, & we already guessed that you will need to go back 12 generations, so unless you can prune whole branches of the family, you might need to examine 2¹² = 4096 people.
• However, I read somewhere (in a book by Richard Dawkins, possibly River out of Eden) that few people are ancestors. If true, it might be less work to start with Paul Revere & work forward in time because, even if a person has more than 2 children, if few people are ancestors, then most of them will have no children, so you lookup that person, learn that they have no children, & you are done with that branch of Paul Revere's descendants; they ended.

In the end, if Tom can name most of his ancestors back to Paul Revere, that's the least work; you simply look up each person to verify that the historical records show that one of their parents is a person that Tom named. You'll examine about 12 people. If Tom cannot name people other than himself & Paul Revere, then it is probably less work to hope that few people are ancestors, start with Paul Revere & work forward.

Ex 1.5. commutative production system on a database

Suppose a rule R of a commutative production system is applied to a database D to produce D'. Show that if R has an inverse, the set of rules applicable to D' is identical to the set of rules applicable to D.

End.