T10-D2: (Pick Up Sticks -- Game Strategy) [SOLUTION SKETCH]
[Idea: Work backwards from small numbers]
D0: If there is 1 stick for your opponent, then s/he loses.
Imagine if is your opponent's turn:
D1: if there are 5 sticks, then s/he loses.
(if opponent choose y, you choose (4 - y) and guarantee D0.)
To guarantee condition D1 for your opponent, you should...
D2: Leave your opponent with 9 = 5 + 4 sticks.
(if opponent choose y, you choose (4 - y) and guarantee D1.)
If you continue this, then you will see that you will need to
leave your opponent with 4k + 1 sticks.
(i) ?-before(jefferson, kennedy) Answer: FALSE
(ii) ?-president(X, lewis_and_clark) Answer: X=jefferson
[Note: For both the above, we just match with the knowledge base.]
(iii) ?-precedes(jefferson, X)
Answer: X={lincoln, fdr, kennedy, nixon}
Working for (iii): [to get the answer, need inference engine]
?-precedes(jefferson,X)
|
+--> R1: before(jefferson,X) Gives: X=lincoln
|
+--> R2: [before(jefferson,Z) and precedes(Z,X)]
substitute Z=lincoln
[before(jefferson,lincoln) and precedes(lincoln,X)]
precedes(lincoln,X)]
+--> R1: before(lincoln,X) Gives: X=fdr
+--> R2: [before(lincoln,W) and precedes(W,X)]; subs W=fdr
[before(lincoln,fdr) and precedes(fdr,X)]
precedes(fdr,X)] (shortened working)
+--> R1: before(fdr,X) Gives: X=kennedy
+--> R2: [before(fdr,kennedy) and precedes(kennedy,X)]
precedes(kennedy,X)]
+--> R1: before(kennedy,X) Gives: X=nixon
+--> R2: [before(kennedy,nixon) and precedes(nixon,X)]
precedes(nixon,X)]
+--> R1: before(nixon,X) No solution for X
+--> R2: [before(nixon,S) and precedes(S,X)] No-soln-for-S
[Note the recursive application of the rule R2 in the above.]
First define the knowledge based-system: (a) a knowledge/fact base (b) rules (or production rules) Knowledge Base: Junction(X) to represent junction X and Road(X,Y) to represent road from junction X to Y;
Junction(A), Junction(B), ... , Junction(E) Road(A,B), Road (A,D), Road(B,A), Road(B,C), Road(B,D), Road(C,B), Road(D,E), Road(E,C), Road(E,D) Rules: Note: Use Path(X,Y) to denote there is a path from X to Y; The definition of Path(X,Y) is recursive! (Analogy/Inspiration: A journey of a 1000 miles begins with 1 step!) R1: Path(X,Y) if Road(X,Y) //(base case) direct connection R2: Path(X,Y) if Road(X,Z) and Path(Z,Y) //connection via Z; Queries: (which we can now answer...) -------- Then, the query: ?Road(B,C) Answer: TRUE ?Road(B,F) Answer: FALSE ?Road(X,E) Answer: X=D X=F To answer the query* ?Path(A,E), we need to invoke the rules: (Note: We always invoke the base case rule (R1) first. Else, we may run into infinite loop of expansions! Try it.) ?Path(A,E) R1 / or \ R2 / \ ?Road(A,E) Road(A,z)-and-Path(z,E) false; / \ /z=B z=D\ / \ Road(A,B)-and-?Path(B,E) Road(A,D)-and-?Path(D,E) true R1 / or \ R2 true R1| or \R2 / \ | Road(D,s)-and-?Path(s,E) ?Road(B,E) Road(B,x)-and-?Path(x,E) ?Road(D,E) |(no solution here) false; | \ true |x=C \x=D Soln: Road(A,D),Road(D,E) | \ Road(B,C)-and-?Path(C,E) Road(B,D)-and-?Path(D,E) true | true R1/ or \ R2 (more steps...) / \ (but no solution) / Road(D,w)-and-?Path(w,E) ?Road(D,E) |(No solution here) True Soln: Road(A,B),Road(B,D),Road(D,E) Summary: Answer: Road(A,B), Road(B,E) Answer: Road(A,B), Road(B,D), Road(D,E) *Now, you should work out the assigned query: ?Path(A,F)
1 2
453
786
|
+-------------------------+-------------------------+
| | |
12 152 12
453 4 3 453
786 786 786
| | |
| +------------+------------+ |
| | | | |
412 152 152 152 123
53 43 483 43 45
786 786 7 6 786 786
| | | | |
+--+--+ +--+--+ +--+--+ +--+--+ +--+--+
| | | | | | | | | |
412 412 52 152 152 152 15 152 123 123
753 5 3 143 743 483 483 432 436 4 5 456
86 786 786 86 76 76 786 78 786 78
Goal state is reachable in three moves!
1 2 12 123 123
453 ---> 453 ---> 45 --> 456
786 786 786 78
T10-Q2: (5 points) (Are Vending Machine Smart?) -- SOLUTION SKETCH
(a) Vending machine is hard-wired to respond to button presses --
each button press is hard-wired to activate a particular
"disposal tray" in the machine to dispense the "product".
When a button is pressed, the machine has no idea whatsoever
what the user wants, or what physical product is being dispensed.
(b)
One simple test will be to jumble up the labels of the buttons;
Another is to jumble up the products in the different disposal tray.
Then it will be very clear that the when a given button is pressed,
the machine has no idea which product will actually be dispensed.
Or worse, for each "disposal tray" put in a random mix
of "products"!
T10-Q3: (10 points) (Rule-based Systems) -- SOLUTION SKETCH
(a) Family Tree -- DIY. (Be careful with left for LChild, and right for RChild.)
(b) NO; X=Ruby; Y=David, Y=Diana
(c)
Descendant(X,Y) if Child(X,Y)
Descendant(X,Y) if Child(X,Z) and Descendant (Z,Y)
(d) YES; W=Mary, W=Bill; Z=Ruby, Z=Diana, Z=John