Markos Mentzelopoulos 6CCGD002W 2021/22

Coursework Description
This is a group coursework. Teams can form up to 2 students only. Team members do not
have to be from the same course or tutorial group. A spreadsheet will be provided to add your
names and group-names. Deadline will be Monday 21st March. Teams cannot change after
this deadline. Students not allocated will be added by the module leader to teams.

1 Dynamic Learning 30 Marks

a) Use dynamic learning approach to calculate alignment sequences, correct pathways

and step analysis for the following sequences:

ggaatggmeeff
gatge

i. Provide a full step-diagram analysis for the alignments [ 8 Marks]

ii. What will be the possible alignment sequences? [8 Marks]
iii. Provide the best alignment sequence/s and highlight the final correct
pathway/s also Include the full costs for each case [4 Marks]

b)A Markov model is described by the following set of Transition Probabilities and
Initial Probabilities

A A G B T
A 0.2 0.7 0.1 0 0
A 0 0 0.5 0 0.5
G 0 0 0.2 0.8 0
B 0.4 0.2 0 0 0.4
T 0.7 0 0 0 0.3

Initial Probabilities
P(A) = 0.3
P(A)= 0.4
P(B) = 0.2
P(G)=0
P(T) =0.1

Observation Probabilities

P(A|1) = 1.0 P(A|2) = 0.5 P(A|3) = 0.4

P(A|1) = 0.0 P(A|2) = 0.1 P(A|3) = 0.1
P(G|1) = 0.0 P(G|2) = 0.3 P(G|3) = 0.2
P(B|1) = 0.0 P(B|2) = 0.1 P(B|3) = 0.2
P(T|1) = 0.0 P(T|2) = 0.0 P(T|3) = 0.1
Markos Mentzelopoulos 6CCGD002W 2021/22

Observation Probabilities

P(A|4) = 0.0 P(A|5) = 0.0

P(A|4) = 0.2 P(A|5) = 0.0
P(G|4) = 0.3 P(G|5) = 0.0
P(B|4) = 0.3 P(B|5) = 0.0
P(T|4) = 0.2 P(T|5) = 1.0

i. Plot the Markov Model for the Sequence [ 4 Marks]

ii. What is the probability to observe the following sequences?
a. AABGA [ 3 Marks]
b. ABBGT [ 3 Marks]

2 Classification 40 Marks

Consider the following data set of game assets (Table 1). These are enemies (E1 and E2 types)
deployed in X & Y coordinates

Subject X Y E1 E2
1 1.0 1.0 1
2 1.0 6.0 1
3 2.0 1.0 2
4 3.0 9.0 2
5 3.0 10.0 2
6 4.0 6.0 1
7 5.0 6.0 1
8 7.0 2.0 1
9 8.0 1.0 1
10 8.0 9.0 1
11 9.0 1.0 2
12 9.0 9.0 1
13 9.0 10.0 1
14 10.0 3.0 1
15 10.0 5.0 2
Table 1

Use the K-means Clustering to classify the enemies into 3 regions (clusters). Use first 1)
Euclidean Distance as a measure and 2) Mahalanobis Distance Use only three iterations!

a) Provide full analysis of your mathematical approach for both approaches and plot

her excel, MATLAB, python or even

hand-written version. Also use distinguished colours for each cluster assets

i. Euclidean Distance Clustering [12 Marks]

ii. Mahalanobis Distance Clustering [ 18 Marks]
Markos Mentzelopoulos 6CCGD002W 2021/22

b) Analyse the outcomes from both cases. Which one performs better? Considering
development stage, which algorithm will you use for 1) open terrain generation and
2) arena-based games? Justify your answers. Provide at least 2 optimised methods
that could help the terrain generation with examples. [ 10 Marks]

3 Reinforcement Learning 15 Marks

In the deterministic gridworld below allowable moves for an agent are up, down, left or right.
The agent is not allowed to move to the black squares [walls]. The agent must move at every
step or exit. The reward for any move is zero. However, from a numbered square, if he wants,
the agent can exit to a terminal state X and collect rewards equal to the number in the square.

-1
1

4 8
1
3 2

i. Consider the gridworld above. Duplicate this gridworld and draw an arrow in
each square (not the blackened squares), to indicate the optimal policy the
agent will calculate with the discount factor
to exit from a particular square, draw an X instead of an arrow. Explain your
approach. [6 Marks]

ii.
function F1 1

This new reward function, F1, favours moving towards numbered squares.
Let d(s) be defined as the Manhattan distance from s to the nearest
numbered square. If s is numbered, d(s) = 0.
Markos Mentzelopoulos 6CCGD002W 2021/22

F1

Duplicate the gridworld again and draw appropriate arrows in each square
(not the blackened squares), to indicate the optimal policy the agent will
calculate with the discount factor = 0.5 and the modified reward function
R1 1

Again, explain your approach

[6 Marks]

4 Complex System 15 Marks

i. Solve the following system of simultaneous linear equations using LU decomposition
method.

+ + . + =
+ + . + =
. + + + = .
. +2 + . + = .
[7 Marks]

ii. Full mathematical approach should be provided in your solutions. Fully implement the
above-mentioned problem through any programming language. Provide code solution
(python, Visual Studio) as script in attachment and print outs of testing/evaluation of
output in the report.
[8 Marks]
iii. Update the above program so that the system can check sub-matrices determinants
and if any is zero to perform re-ordering of the invertible matrix so that the LU
decomposition can be processed. Demonstrate the result in the following system:

A= [

1 ]

[3 Marks]
 Markos Mentzelopoulos 6CCGD002W 2021/22
Coursework Marking scheme
The Coursework will be marked based on the following marking criteria:

Criteria Mark per component Mark Comments

provided

Section 1: Dynamic Learning 30

Step Diagram of Alignments 8

Alignment Sequences 8

Best Alignment Sequence and costs 4

Plot Markov Model for the sequence 4

Observation Probabilities 8

Section 2: Classification 40

Euclidean Distance Approach 12

Mahalanobis Distance Approach 18

Discussion 10
Section 3: Reinforcement Learning
12
Section 4: Complex System
15
Solve System
7
Coding Solution
8
Code Adaptation
3

Total 100

Marking Grade descriptors: For every section the following grade descriptor will be followed. For
example, on Maximum number of 5 marks: Excellent =5, Good =4, Average =3, Basic =2, Insufficient
=0 or 1

Excellent: demonstrates an outstanding understanding of topic principles (both in mathematical

and implementation) with exceptional initiative, creativity, originality. The solution is well-structured
Markos Mentzelopoulos 6CCGD002W 2021/22
and demonstrated. Documentation is in professional level and overall complexity in outstanding
level close to publicity level.

Good: demonstrates a good overall knowledge behind the topic. Covers fundamentals taught
within the module and applied accurately to demonstrate a solution. Communicates ideas clearly
and succinctly with good standard of presentation.

Average: demonstrates a production and documentation to a reasonable level of implementation.

Minor errors exist and overall performance is close to demonstration. The mathematical solution
follows correct approach with minor mistakes in both written and development of the algorithms.
The report covers important topics of the implementation but lucks of justification and analysis.

Basic: demonstrates a basic understanding behind mathematical solutions and algorithmic

interpretation to implement the project solution. Report is very basic without clear justification for
the given approach followed towards the implementation of the solution and without any
comparative results.

Insufficient: demonstrates a poor understanding behind mathematics and/or programming for

generating a given solution. Report is insufficient and is missing critical components.