spec-50001-1-0.pdf
COMP 50001: Coursework 1
Autumn Term, 2022
Copyright By PowCoder代写 加微信 powcoder
1 Introduction
The goal of this coursework is to implement algorithms that will be
used to control your army in a game of Imperial Conquest: a real-
time strategy game created for this course. It takes place in a galaxy
far, far away, where space travel to different planets is made possible
through a network of wormholes. Planets are able to produce fleets of
ships that can be sent to divide and conquer the enemy.
Figure 1: Imperial Conquest boasts a
fashionable text-based interface (though
it will only come to life for the second
part of the coursework)
Both coursework assignments will use the same infrastructure. This
first assignment concerns itself with choosing a basic initial strategy
and some simple pathfinding. The second assignment will deal with
more complex strategies and dealing with opponents.
2 Submission
The code in this specification can be found in Submission1.hs, which is
a trimmed down version of what is presented here, that contains all the
relevant code. Your task is to modify Submission1.hs by implementing
the solutions to the questions.
During development, you might find it useful to load the source
file into GHCi by running ghci Submission1.hs. This way, you can test
your solutions, and ensure there are no compilation errors as you’re
working on your code.
comp 50001: coursework 1 2
This coursework will be automarked: test suites are provided to
check your answers. In order to run the tests, you should run the
following command in the root directory of the repository:
$ make test
The submission of your coursework should be done via LabTS using
git commits in the usual way.
3 Background
Imperial Conquest is a game inspired by Galcon, a two player real-
time strategy game. A game of Imperial Conquest is played between
two players, and time progresses in a series of turns. All of the datatypes in this section are
relied upon for communication with the
server and should not be modified.
The Player data type represents the two players of the game.
data Player = Player1 | Player2
This first coursework involves no interaction between players, but the
data types will be shared between the second coursework, and so are
defined here. A newtype uses an existing type as the
basis of a new type by wrapping values
in a new constructor. Here it means that
a Ship cannot be confused with a Growth,
even though both are fundamentally stor-
ing an Int.
The game is played on a map with a number of planets. Planets are
represented by the Planet type.
data Planet = Planet Owner Ships Growth
newtype Ships = Ships Int
newtype Growth = Growth Int
Thus, a planet is a value (Planet owner ships growth), where an
owner can be either neutral, or one of the two players:
data Owner = Neutral | Owned Player
Planets have a number of spaceships in garrison, represented by ships
that belong to the owner of the planet. Finally, each turn, planets that
are owned by a player have factories which can produce a number of
ships given by the growth value.
In order to refer to planets, they each have an identifying number,
which is presented as a value of type PlanetId:
newtype PlanetId = PlanetId Int
A Map is a data structure that is pro-
vided in the Data.Map module, which
is documented at https://hackage.
haskell.org/package/containers-0.6.
2.1/docs/Data-Map-Lazy.html, which
gives operations and their complexities.
The Planets type represents a collection of planets as a key-value map
from planet identifiers to the planet structures:
type Planets = Map PlanetId Planet
The planets in this galaxy are too far away for spaceships to travel
between them within a reasonable amount of time using traditional
propulsion systems, but certain planets are connected by wormholes,
allowing spaceships to travel through them faster than light.
comp 50001: coursework 1 3
data Wormhole = Wormhole Source Target Turns
newtype Source = Source PlanetId
newtype Target = Target PlanetId
newtype Turns = Turns Int
Crucially, a Wormhole connects two planets in a directed way. That is,
wormholes are one-way streets with a value of type Source for the
source, and Target for the target. The value of type Turns indicates
how many turns it takes to travel through the wormhole.
Similarly to Planets, Wormholes are also referred to by an identifier
which is just a wrapper around an Int:
newtype WormholeId = WormholeId Int
These are collected into a key-value map in much the same way:
type Wormholes = Map WormholeId Wormhole
As spaceships go through wormholes, the number of turns left
on their journey before they arrive is tracked. The Fleet data type
represents a fleet of ships by storing whose ships they are, how many
of them are there, which wormhole they’re in, and how many turns left
before they reach their target.
data Fleet = Fleet Player Ships WormholeId Turns
When a fleet of ships arrives at the target of the wormhole, they join
forces with the ships that are there if they belong to the same owner.
Otherwise, the fleet attacks the ships on the defending planet, cancelling
each other out one-to-one. If there are more ships in the fleet than on
the planet then the remaining ships from the fleet capture the planet
garrison, and the planet is owned by the fleet owner.
The Fleets type represents a collection of fleets. Note that these do
not have identifiers, as they are not referred to anywhere.
type Fleets = [Fleet]
The state of the whole game at any given time is represented by the
GameState data type:
data GameState = GameState Planets Wormholes Fleets
Finally, at every turn, the server takes a list of orders and begins to
execute them.
data Order = Order WormholeId Ships
The exact rules of the game are not important for this assignment,
though they will become relevant in the next.
comp 50001: coursework 1 4
4 Dynamic Programming
Dynamic programming is a technique for optimising the runtime per-
formance of a recursive algorithm that has overlapping subproblems.
The speedup comes from storing the subsolutions for later use instead
of recomputing them every time they are needed.
The strategy is developed in two stages:
1. Write an inefficient recursive algorithm that solves the problem.
2. Improve efficiency by storing intermediate shared results.
As a simple example, dynamic programming can be applied to speed
up a naive implementation of the Fibonacci function. While the input to fib is usually bound
by an Int, even for small inputs the func-
tion will overflow in its output, hence the
return type is Integer, which can repre-
sent arbitrarily large integers.
Each Fibonacci number for a given value n is given by fib n given
by the following recursive algorithm:
fib :: Int -> Integer
fib n = fib (n-2) + fib (n-1)
fib 8 fib 9
fib 6 fib 7 fib 7 fib 8
Figure 2: Call tree of fib 10, showing
multiple repeated computations.
This code is remarkably inefficient, since there are repeated calls to
computations that recalculate the same value. Figure 4 shows that fib 8
is called twice in the calculation of fib 10. In turn, fib 7 is called three
times, fib 6 five times, etc. As a lower bound of its complexity, we
have the following recurrence relation:
Tfib(n) � 1 + 2 ⇥ Tfib(n � 2)
Solving this recurrence gives Tfib(n) 2 O(2n/2). This is remarkably
expensive and due to the fact that there are large overlaps in the
solutions of subproblems, which keep getting recalculated.
This recalculation can be avoided by building up the intermediate
values up to the result. More concretely, the computation of fib n,
involves defining an array containing the values of fib for all numbers
from 0 up to n.
The Array Int Integer type represents
an array indexed by Int containing val-
ues of type Integer.
The function (!) provides constant-
time random access.
The function array takes a range (u,v)
of values as its bounds, and a list of pairs
where each pair (i,x) is used to place x
at index i in the table.
table :: Int -> Array Int Integer
table n = array (0,n) [ (0, 0)
, (2, table ! 0 + table ! 1)
, (3, table ! 1 + table ! 2)
This is, of course, not the best way to cal-
culate Fibonacci numbers (which can be
done in sublinear time), but it illustrates
how a recursive algorithm can be made
more efficient.
Notice that every element of table refers to solutions of previous
problems that eventually lead to a base case: there are no circular
references so the self-referential definition is well-defined. Here is a
comp 50001: coursework 1 5
version of fib that builds the right table and returns the last element
of the array.
fib’ :: Int -> Integer
fib’ n = table ! n
table :: Array Int Integer
table = tabulate (0, n) mfib
mfib 0 = 0
mfib 1 = 1
mfib n = table ! (n-1) + table ! (n-2)
It is important that mfib is in the same
level of scope as table: if it were top-
level then a new table would be created
on each call!
The table given by tabulate (x,y) f contains the results of applying f
to all the values between x and y. It is implemented as an array which
gives constant time access to its elements. The constraint Ix i allows the values of
type i to be drawn from those given by
the range function, as well as enabling
values to be indexed over in an array.
This allows arrays to be indexed by types
other than Int. For instance, a valid
index is a tuple (Int, Int) for a two-
dimensional array indexed by pairs of
tabulate :: Ix i => (i,i) -> (i -> a) -> Array i a
tabulate (u,v) f =
array (u,v) [ (i, f i) | i <- range (u, v)] The cost of building this table is the sum of all the individual calls of f. The key to efficiency is that the function f can itself refer to the table that is being constructed. If the cost of f is constant, such that Tf(i) 2 O(1), and the table has n elements, then the cost of its construction is Ttable(n) 2 O(n). In the code above, mfib is a local version of fib that finds values in the table rather than by recursion. The function takes constant time since (!) is a constant time operation. Thus, the time complexity of evaluating fib’ n is given by: Tfib’(n) = 1 + Ttable(n) + T!(n) where Ttable(n) is the time it takes to construct the table, and T!(n) is the time it take to look up a value in that table. Therefore, the overall cost is Tfib’(n) 2 O(n), which is much better than before. The slogan for dynamic programming algorithms is to memoize shared sub-computations: by memoizing the results of sub-computations in a table, repeated computations are avoided whenever possible, resulting in a much faster algorithm. 5 Planet Picking The first task of this coursework is to plan which planets to conquer first. To simplify things, assume that there are a number of planets that are equally reachable from your forces. comp 50001: coursework 1 6 As an example, here is a map with 5 planets, planet 0 being your home planet, and planets 1..4 being the neutral planets that you can conquer, each in a single turn. Furthermore, the planets are not reachable from one another. example1 :: GameState example1 = GameState planets wormholes fleets where planets = M.fromList [ (PlanetId 0, Planet (Owned Player1) (Ships 300) (Growth 0)) , (PlanetId 1, Planet Neutral (Ships 200) (Growth 50)) , (PlanetId 2, Planet Neutral (Ships 150) (Growth 10)) , (PlanetId 3, Planet Neutral (Ships 30) (Growth 5)) , (PlanetId 4, Planet Neutral (Ships 100) (Growth 20)) wormholes = M.fromList [ (WormholeId 0, Wormhole homePlanet (Target 1) (Turns 1)) , (WormholeId 1, Wormhole homePlanet (Target 2) (Turns 1)) , (WormholeId 2, Wormhole homePlanet (Target 3) (Turns 1)) , (WormholeId 3, Wormhole homePlanet (Target 4) (Turns 1)) ] where homePlanet = Source 0 fleets = [] The information in a GameState can be queried. For instance, the targetPlanets function lists the planets that can be reached from a given source, and the shipsOnPlanet function finds how many ships are garrisoned on a planet. targetPlanets :: GameState -> Source -> [(PlanetId, Ships, Growth)]
targetPlanets st s
= map (planetDetails . target) (M.elems (wormholesFrom s st))
planetDetails :: PlanetId -> (PlanetId, Ships, Growth)
planetDetails pId = (pId, ships, growth)
where Planet _ ships growth = lookupPlanet pId st
shipsOnPlanet :: GameState -> PlanetId -> Ships
shipsOnPlanet st pId = ships
where Planet _ ships _ = lookupPlanet pId st
Both of these functions use lookupPlanet to extract a planet from
the GameState:
lookupPlanet :: PlanetId -> GameState -> Planet
lookupPlanet pId (GameState ps _ _) = fromJust (M.lookup pId ps)
It is also possible to determine the wormholes that correspond to a
planet, whether that be wormholes to or from that planet:
comp 50001: coursework 1 7
wormholesFrom :: Source -> GameState -> Wormholes
wormholesFrom pId (GameState _ ws _)
= M.filter (\(Wormhole s _ _) -> s == pId) ws
wormholesTo :: Target -> GameState -> Wormholes
wormholesTo pId (GameState _ ws _)
= M.filter (\(Wormhole _ t _) -> t == pId) ws
Here is an example of how ghci can be used to query some values:
ghci> targetPlanets example1 (Source (PlanetId 0))
[(1,200,50),(2,150,10),(3,30,5),(4,100,20)]
If the overall number of defenders among all these planets is over-
whelming, you will have to pick which planets to conquer first. Planets
have a different intrinsic value, which is represented by their growth
rate. The question is which planets to conquer in the first turn to maximise
the growth rate obtained in this turn. In the case of example1, the optimal
strategy if your fleet has 300 ships is to conquer planet 1 and planet 4,
resulting in a growth rate of 70.
Planets have different intrinsic value, so you should aim to maximise
the value of your conquest given your capacity to attack. This is
optimisation problem is an example of the classic knapsack problem.
5.1 Unbounded Knapsack
The unbounded knapsack problem concerns itself with packing a knap-
sack with some given capacity c with elements of some weight and
value drawn from a list. There is no limit to the number of times an
element can be picked from the list. The goal is to maximise the value of
the items that can be placed in the list, without going over the capacity.
Thus, the available items are represented as a list of triples, where
each item has a name, some weight, and some value. The name parameter is not used in this
first function, but it will become useful
later.[(name, weight, value)]
As a recursive algorithm, knapsack is easily stated: take an item
(name, weight, value), and consider what would happen if we put it
in the knapsack. The total value would be increased by the value of the
item, but the remaining capacity would be decreased by the weight of
the item. So, if the starting capacity is c, then picking this item would
result in a maximum value of the item’s value plus the maximum value
of the subproblem where the capacity is c-w (since after putting this
item in, we need to maximise the value by filling in the remaining
capacity). The optimal solution is achieved by trying every item as the
first one, then recursively optimising the remaining capacity, ultimately
finding the maximum one.
The knapsack function is highly polymor-
phic, as it works on any types of in-
puts, as long as they can be compared
(as stated by the Ord constraint) and sup-
port basic arithmetic (as stated by the Num
constraint). Here the abstraction helps
make clear exactly which properties of
the types are relied upon.
This recursive description can be written as the following:
comp 50001: coursework 1 8
knapsack :: forall name weight value .
(Ord weight, Num weight, Ord value, Num value) =>
[(name, weight, value)] -> weight -> value
knapsack wvs c = maximum 0 [ v + knapsack wvs (c – w)
| (_,w,v) <- wvs , w <= c ] That is, from the input list wvs, find all items whose weight is less than the capacity, and try them by recursively solving the smaller problem. Finally, take the largest element of this list using maximum. maximum :: Ord a => a -> [a] -> a
maximum x xs = foldr max x xs
The maximum value here is bounded below by 0.
This implementation of knapsack correctly produces the maximum
value, which can be tested in ghci:
ghci> knapsack [(“a”, 35, 10), (“b”, 153, 200), (“c”, 100, 20)] 800
However, the efficiency of this algorithm is quite terrible when
the knapsack can be filled to a given capacity by picking different
combinations of elements, since this leads to repeated computations.
Try increasing the capacity to see how slow it gets.
The forall is used to put the type vari-
ables name, weight, and value in scope so
that they can be referred to in the where
Notice the additional (Ix weight) type
class constraint in the function’s signa-
ture. This indicates that the weight will
be used as an array index when building
the table for the subproblem solutions.
Problem 1: Dynamic Knapsack
Use dynamic programming to improve the running time of knapsack,
by giving a definition of mknapsack in the code below.
knapsack’ :: forall name weight value .
(Ix weight, Num weight, Ord value, Num value) =>
[(name, weight, value)] -> weight -> value
knapsack’ wvs c = table ! c
table :: Array weight value
table = tabulate (0,c) mknapsack
mknapsack :: weight -> value
mknapsack c = undefined
Hint: compare the recursive version of fib with the dynamic
programming version to see how to translate one to the other.
While this correctly and efficiently calculates the maximum value
of the knapsack, it does not announce what the items that are picked
actually are (in other words, the name elements are ignored). To do this,
the return type Value needs to be modified to something that holds
comp 50001: coursework 1 9
both the value and the index of the item that was chosen. Then, you
will have to modify the algorithm so that the index does not get in the
way, and so that the indices are properly combined.
Problem 2: Knapsack Elements
Implement knapsack’’ as a modified version of knapsack’ so that
it outputs the maximum value of the knapsack, as well as a list of
the element indices that are chosen to obtain that value.
knapsack’’
:: forall name weight value .
(Ix weight, Num weight, Ord value, Num value) =>
[(name, weight, value)] -> weight -> (value, [name])
knapsack’’ wvs c = table ! c
table :: Array weight (value, [name])
table = tabulate (0,c) mknapsack
mknapsack :: weight -> (value, [name])
mknapsack c = undefined
Hint: You may need to make use of maximumBy to be able to ig-
nore the indices that are being used. A fantastic site for finding
useful functions is https://hoogle.haskell.org/, where even type
signatures can be typed in.
If your solution is correct, you should see something like this:
ghci> knapsack’’ [(“a”, 35, 10), (“b”, 153, 200), (“c”, 100, 20)] 800
(1010,[“b”,”b”,”b”,”b”,”b”,”a”])
5.2 Bounded Knapsack
The unbounded knapsack problem allows the items to be used multiple
times. However, the planets can only be conquered once, so it doesn’t
make much sense to allow them to be picked multiple times. The goal
of this section is to implement the bounded knapsack problem to help
decide which planets should be conquered.
Problem 3: Bounded Knapsack
This is the type of bknapsack, which is similar to knapsack except
that the elements are not replaced when picked.
bknapsack :: forall name weight value .
(Ord weight, Num weight, Ord value, Num value) =>
comp 50001: coursework 1 10
[(name, weight, value)] -> weight -> (value, [name])
bknapsack = undefined
Hint: Perform case analysis on the list of items. After using an item,
remove it from the recursive call.
To implement this function, first write a recursive definition, where
the result of bknapsack wvs c is the maximum value that can be
packed into a capacity of c from the elements of wvs by only using
each element at most
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com