Session 1, 2011

This tutorial will ask you step-by-step to unlock the mystery behind the the following single-player game -- and then to solve it.

role(you) succ(1,2) succ(2,3) succ(3,4) succ(4,5) succ(5,6) succ(6,7) succ(7,8) init(row(1,one_coin)) init(row(Y,one_coin)) <= succ(X,Y) init(step(1)) legal(you,jump(X,Y)) <= true(row(X,one_coin)) ∧ true(row(Y,one_coin)) ∧ ( kate(X,Y) ∨ kate(Y,X) ) harry(X,Y) <= succ(X,Y) harry(X,Y) <= succ(X,Z) ∧ true(row(Z,empty)) ∧ harry(Z,Y) will(X,Y) <= succ(X,Z) ∧ true(row(Z,empty)) ∧ will(Z,Y) will(X,Y) <= succ(X,Z) ∧ true(row(Z,one_coin)) ∧ harry(Z,Y) kate(X,Y) <= succ(X,Z) ∧ true(row(Z,empty)) ∧ kate(Z,Y) kate(X,Y) <= succ(X,Z) ∧ true(row(Z,one_coin)) ∧ will(Z,Y) kate(X,Y) <= succ(X,Z) ∧ true(row(Z,two_coins)) ∧ harry(Z,Y) next(row(X,empty)) <= does(you,jump(X,Y)) next(row(Y,two_coins)) <= does(you,jump(X,Y)) next(row(X,C)) <= true(row(X,C)) ∧ does(you,jump(Y,Z)) ∧ distinct(X,Y) ∧ distinct(X,Z) next(step(Y)) <= true(step(X)) ∧ succ(X,Y) terminal <= ¬open open <= legal(you,M) goal(you,100) <= true(step(5)) goal(you, 0) <= ¬true(step(5))

**Logic Programming -- Answer Substitutions**Compute all answer substitutions to the query

`?- init(F)`.Hint: You should obtain 9 different answers for variable

`F`. These 9 features compose the initial game state. Can you draw a simple diagram to visualise this position?**Logic Programming -- Derivations**The key to unlocking the mystery is to understand the meaning of the three recursive relations,

`kate, will, harry`. To get the idea, suppose given the following facts:true(row(1,one_coin)) true(row(2,empty)) true(row(3,empty)) true(row(4,one_coin)) true(row(5,one_coin)) true(row(6,one_coin)) true(row(7,two_coins)) true(row(8,one_coin))

Which of the following queries have a successful derivation?

`?- harry(1,4)``?- harry(1,5)``?- will(1,5)``?- kate(1,5)``?- kate(1,6)``?- kate(1,7)``?- kate(6,8)`

Can you now guess what

`kate(m,n)`"counts"?**Planning -- Action Preconditions and Effects**- Next, have a look at the definition for
`legal(you,jump(X,Y))`. In words, what are the preconditions for jumping from row X to row Y? How many actions are possible in the initial state of the game (cf. exercise 1)? - Pick any one of the actions
`jump(m,n)`that are possible in the initial state and, with the help of the rules for`next(F)`, compute the new state after`does(you,jump(m,n))`. In words, what are the effects of jumping from X to Y?

- Next, have a look at the definition for
**Planning**The definitions for

`terminal`and`goal(you,100)`respectively imply that the game ends when you are stuck (i.e. there are no more legal moves) and that you win the game when you can make the maximum of 4 moves before getting stuck. Find a plan (i.e. a sequence of 4 actions) that solves this problem! (Hint: there is more than one solution.)**Planning**Bonus Challenge: We humans are often better than computers when it comes to generalising a solution. How would you solve the game if initially there were 1,000 coins in a row and the goal is to make 500 moves?