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...

noptargetsource
priestscannibalspriestscannibals
00033
1cannibals-from-start0231
2cannibal-from-target0132
3cannibals-from-start0330
4cannibal-from-target0231
5priests-from-start2211
6both-from-target1122
7priests-from-start3102
8cannibal-from-target3003
9cannibals-from-start3201
10cannibal-from-target3102
11cannibals-from-start3300

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...

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...

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...

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.