T13-D1: (Rule-based System Spring 2013-Exam) -- Check answer given.
To answer this question, it is helpful to FIRST draw out a relationship diagram.
Here, I leave that to you to DIY.
(Note that the knowledge-base system do NOT need this relationship diagram.)
(a) ?Parent(Alan,James) Answer: NO (or FALSE)
?Parent(Frank,P) Answer: P = James, P = Diana
THE-STEPS: [if that is needed in the question]
?-parent(Alan,James)
|
+==> R1: Mother(Alan,James) ==> NO [Pattern-Matching with fact-base]
|
+==> R1: Father(Alan,James) ==> NO
?Parent(Frank,P) P = James, P = Diana
|
+==> R1: Mother(Frank,P) ==> NULL
|
+==> R1: Father(Frank,P) ==> P = James, P = Diana
(b) R3: Ancestor(X,Y) if Parent (X,Y)
R4: Ancestor(X,Y) if Parent (X,T), Ancestor(T,Y)
(c) ?Ancestor(Alan,Diana) Answer: YES (or TRUE)
?Ancestor(Betty,Q) Q = Irene, Q = Ben, Q = Tom
THE-STEPS: [if that is needed in the question]
?Ancestor(Alan,Diana) Answer: YES (or TRUE)
|
+==> R3: Parent(Alan,Diana) ==> R1: Mother(Alan,Diana) ==> NO
| ==> R2: Father(Alan,Diana) ==> NO
|
+==> R4: Parent(Alan,T), Ancestor(T,Diana)
|
+==> R1: Mother(Alan,T) ==> NO
+==> R2: Father(Alan,T) => Father(Alan,Frank) => T=Frank
Check Ancestor(Frank,Diana)
+==> R3: Parent(Frank,Diana)
|
+==> R1: Mother(Frank,Diana) ==> NO
+==> R2: Father(Frank,Diana) ==> YES
EXPLANATION: Father(Alan,Frank), Father(Frank,Diana)
[Idea: Work backwards from small numbers] (Backward chaining)
L1: There is 1 stick for your opponent, then you win, s/he loses.
If it is your turn and there are...
W2: 2 sticks; You choose-1 & FORCE state L1 to your opponent;
W3: 3 sticks; You choose-2 & FORCE state L1 to your opponent;
W4: 4 sticks; You choose-3 & FORCE state L1 to your opponent;
So, the next losing position is
L5: There are 5 sticks for your opponent, he loses;
(if opponent choose y, you choose (4 - y) and force L1)
And, the next losing position is
L9: There are 9 sticks for your opponent, he loses;
(if opponent choose y, you choose (4 - y) and force L5)
And so on, 1, 5, 9, 13, 17, 21, ... are all losing positions;
In general, losing positions are (4k + 1), k=0,1,2,3...
So, winning strategy for you, is to leave your opponent with (4k+1) sticks.
|
COOL!
A winning strategy obtained by a careful state-space analysis, starting from small states, and working upwards! |