THE UNIVERSITY OF HONG KONG
FACULTY OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE
Final Examination
COMP7404D Computational Intelligence and Machine Learning
May 23 (Sat) 9:30am - May 24 (Sun) 9:30am
• This is an open-book examination. You may use the following materials:
o Any materials provided by the teacher on Moodie.
o All internet search engines (e.g., google) for general python related queries regarding syntax.
o All Python libraries that were used in code examples shown on the lecture slides.
• Answer ALL questions yourself in your own words.
• Submit your answers to all questions as TWO files to Moodie before the deadline.
o For question B.2: Submit a single python code file named sokoban.py.
o For other questions: Hand write answers and scan them into a single PDF file.
• Time/Space limit: You may use up to 4GB memory and 15 minutes of runtime on a modern mid-range
CPU (Grading machine will use a AMD Ryzen 3600 CPU which is roughly equivalent to a Intel Core i7
9700k).
Part Question Max. Mark
1 15
A
2 15
1 20
B 2 40
3 10
Total 100
Part A
Question A.1 (15 marks]:
In this question you are going to build an MDP and use approximate reinforcement learning to pick an attraction in
Disneyland. There is a chance that some attractions make you feel sick. Initially you feel well and enjoy the
attractions. You are getting rewards. When you are sick and you continue visiting the attraction there is a chance that
you feel well again. When you feel sick and you continue visiting an attraction you will get a lower reward.
This is your first time in Disneyland. You don't know how much reward you may obtain while sick or well. You
also don't know what the chances are of getting sick/well again for each attraction.
The available actions and some more information about them is available in the following table.
action type wait speed
Big Grizzly rollercoaster short slow
Iron Man rollercoaster long fast
Dumbo carousel short fast
Toy Soldier drop tower short slow
Leave Disney leave short slow
In our MDP, let there be two states: Well and Sick. Every attraction is an action. The leave Disney action will end
the current run through the MDP. Taking an attraction action will lead back to the same state with some probability
or take you to the other state. We are going to use the following features
fo(state, action) = 1, if and only if type = rollercoaster,
fi(state, action) = 1,
fz(state, action) = 1, if and only if wait = short,
fistate, action) = 1, if and only if type = carousel,
and the weights: w0 = 3, w 1 = 1/2, w2 = 1, w3 = 1/2. Assume a discount of y = 1/3 and a learning rate of a = 1/2.
Features can only be O or 1.
A.1.1 (3 marks]: Determine Q(Well, Big Grizzly)
A.1.2 (8 marks]: Apply an approximate Q-Learning update based on the sample
(Well, Big Grizzly, Sick, -8.5).
Write down all weights after the update is complete.
A.1.3 [4 marks]: Is Q(Well, Big Grizzly) = Q(Sick, action) for all actions after the update of A. 1.2? Explain why /
why not.
Page 2 o/6
Question A.2 (15 marks]:
In this question you are going to apply the Perceptron algorithm on four 2D training samples. Let the training
samples be given as follows.
y
- 1
- 1
- 1 - 1
-1 -1 - 1
In the table above, x1 and x2 are the features and y is the class label. Let all initial weights be
w 1 = w2 = 0.4 and let the bias be w0 = -0.5.
A.2.1 (5 marks]: Calculate the estimate y for all samples.
A.2.2 [10 marks]: Perform two epochs of training using a learning rate of 1/3.
Page 3 o/6
PartB
In this part of the final exam you will attempt to solve a difficult computational problem: the game of sokoban. We
will test your ability to design a solution, think computationally and use AI to solve a challenging game without
providing you with a skeleton program (i.e., you have to start from scratch).
Warning: If you plagiarize, even if it is only for a few lines of code, we will use the strongest consequence available
to us.
Sokoban Uapanese for warehouse keeper) is a puzzle game invented by Hiroyuki Imabayashi. The player pushes
boxes around in a warehouse, trying to get them to storage locations. Here is gif a sokoban level 1 being solved. If
you cannot see the animation visit the wikipedia page of sokoban.
You may visit this website to play the game and familiarize yourself with the game play. We suggest solving the
first three levels before starting to program.
Each level represents a warehouse, where boxes are placed. A warehouse keeper has to push the boxes around the
warehouse so that all boxes are on goals at the end of the game. The warehouse is a two dimensional grid of squares.
If a square contains nothing it is called a floor, otherwise it is occupied by one of the following entities:
Wall: Walls make up the basic outline of each level. They cannot be moved and nothing else can be on a
square occupied by a wall. A legal level is always surrounded by walls.
Box: A box can either occupy a goal or an otherwise empty square. At the start of the game a box may
already occupy a goal. They can be moved in the four cardinal directions by pushing.
Goal: Goals are treated like floors for the most part. Only when each goal is occupied by a box the game is
completed. In a legal level the number of goals matches the number of boxes. For the sake of simplicity, we
will call a square that is either a goal or a floor square free since the player and boxes can enter both. At the
start of the game a goal cannot be occupied.
Player: The player can execute moves to alter his position. A move can be up, down, left or right. A move
is also a push if it alters the position of a box.
The player cannot move through walls or boxes. It can only move onto a square occupied by a box if it can
execute a push to move it out of the way. Therefore a player cannot push more than one box at a time, nor
can he pull them.
Page 4 o/6
You are going to load the start state of a certain level from a * • txt file. Here is the start state of level 1 as seen
above.
The characters define the following entities:
'#':Wall
'B': Box ('X': Box on goal)
' ' : Goal
' & ' : Player ( '%' : Player on goal)
' , : free square
The goal of the game is to find a solution. A solution is a sequence of moves that leads to every box being on a goal.
It does not matter which box ends up on which goal. Note that in our version of this game all solutions are equally
good, i.e., we don't score by the number of moves the player makes or number of box moves that are made. You
may assume that every level we provide to you is legal and has a solution.
We are going to define a particular sequence of actions as a string, i.e., a list of letters for the four directions: u, d, 1,
r. They are capitalized if the move was a push. For example, the solution above has the following sequence of
actions:
Rurrdddd1DRuuuuLLLrdRDrdd1Ldl1UUdR
Page 5 o/6
Question B.1 [20 marks]:
B.1.1 [5 marks]: How is this game different from chess, tic-tac-toe or other simple problems discussed in class?
B.1.2 [5 marks]: What makes solving sokoban difficult from a computational perspective?
B.1.3 [8 marks]: Propose a problem definition to be used to solve sokoban. Describe the state space graph and
search tree of your problem. The state space should be identical to the one that you will use in question B.2.
B.1.4 [2 marks]: What is the branching factor of the state space that you proposed in the previous question?
Question B.2 (40 marks]:
Write a python program named sokoban.py (only use this file for all your code) that will take the file name of a level
as a parameter and then output a solution. E.g., if you call
python3 sokoban.py levell.txt
the output should be
Rurrdddd1DRuuuuLLLrdRDrdd1Ldl1UUdR
You may use any algorithm discussed in class ( or any extension of it) to achieve this. Test your implementation on
the test level pack that you can download here. You can assume that all levels that we use to test your
implementation have a solution.
Make sure that your program does not output anything else (e.g., debug messages) and that your output is indeed a
valid solution.
Question B.3 (10 marks]:
In this part of the exam you should describe your solution and you should specify which levels your solution is able
to solve, if any.
If you cannot find solutions successfully, tell us why and describe your progress in detail. If you exceed the space or
time limit you can also let us know here.
END OF PAPER
Page 6 o/6

欢迎咨询51作业君