COMP4418 10s2 - General Game Playing Assignment

Email answers to Michael Thielscher (mit --AT-- cse.unsw.edu.au). Feel free to post questions about this assignment on the course forum. I will also be available for consultation. Email me to set a time.

Questions

1. (10 marks)

   Consider the following GDL game.

     role(robot)
   
     legal(robot,a)
     legal(robot,b)
   
     next(p) <= ( does(robot,a) ∧ ~true(p) )
                ∨ ( does(robot,b) ∧ true(q) )
     next(q) <= ( does(robot,a) ∧ true(q) )
                ∨ ( does(robot,b) ∧ true(p) )
   
     terminal <= true(p) ∧ true(q)
     
     goal(robot,100) <= true(p) ∧ true(q)
   

   This game description uses the two fluents p and q, both of which are false in the initial position since there are no clauses for "init". Give all components of the game model (R,S,A,l,u,s₁,t,g) described by these rules. (Hint: It may be a good idea to draw the state transition system for yourself.)

2. (20 marks)

   In competitions, game rules are usually obfuscated in order to hide their meaning. Try to figure out what the following game is about. Find a sequence of moves to win the game.

     role(you)
   
     succ(1,2)
     succ(2,3)
     succ(3,4)
     succ(4,5)
     succ(5,6)
     succ(6,7)
     succ(7,8)
   
     init(cell(1,1))
     init(cell(Y,1)) <= succ(X,Y) ∧ init(cell(X,1))
     init(step(1))
   
     legal(you,jump(X,Y)) <=
        true(cell(X,1)) ∧ true(cell(Y,1)) ∧
        ( gillard(X,Y) ∨ gillard(Y,X) )
   
     oakeshott(X,Y) <= succ(X,Y)
     oakeshott(X,Y) <= succ(X,Z) ∧ true(cell(Z,0)) ∧ oakeshott(Z,Y)
   
     abbott(X,Y) <= succ(X,Z) ∧ true(cell(Z,0)) ∧ abbott(Z,Y)
     abbott(X,Y) <= succ(X,Z) ∧ true(cell(Z,1)) ∧ oakeshott(Z,Y)
   
     gillard(X,Y) <= succ(X,Z) ∧ true(cell(Z,0)) ∧ gillard(Z,Y)
     gillard(X,Y) <= succ(X,Z) ∧ true(cell(Z,1)) ∧ abbott(Z,Y)
     gillard(X,Y) <= succ(X,Z) ∧ true(cell(Z,2)) ∧ oakeshott(Z,Y)
   
     next(step(Y))   <= true(step(X)) ∧ succ(X,Y)
     next(cell(X,0)) <= does(you,jump(X,Y))
     next(cell(Y,2)) <= does(you(jump(X,Y))
     next(cell(X,C)) <= does(you,jump(Y,Z)) ∧
                        true(cell(X,C)) ∧
                        distinct(X,Y) ∧ distinct(X,Z)
   
     terminal   <= ~continuable
     continuable <= legal(you,M)
     
     goal(you,100) <= true(step(5))
     goal(you,  0) <= true(cell(X,1))
   

3. (50 marks)

   Nim is a two-player game in which players take turns removing objects from a heap. Starting with a heap of size 15, on each turn a player must remove at least 1 and at most 4 objects. The player to take the last object loses. Describe this game in GDL. Make sure that your description satisfies all syntactic restrictions of GDL.

4. (20 marks)

   Although in GDL-II all players start with the same information, incomplete and asymmetric information may easily result from random moves and the fact that different players may get to see different aspects of the position.

   Describe an arbitrary game in GDL-II with only one fluent "p" and with four players "alice", "bob", "carol", and "random" such that the following situation may arise after two joint moves: Alice knows whether fluent "p" is true; Bob knows that Alice knows whether "p" is true without himself knowing the truth-value of "p"; Carol does not know if Alice knows about "p" or not.

   Hint: You don't have to specify termination or goal values. Make sure that your description satisfies all syntactic restrictions of GDL-II and that it is playable, that is, every player must have a legal move both initially and after the first joint move.