Assessed assignment 3
Instructions
If you have not yet cloned the module Gitlab repository, then do that with:
git clone https:git.cs.bham.ac.ukzeilbernfplearning20192020.git If youve already cloned the repository, run
git pull
to ensure that you have the most recent version including this assignment.
Go into the AssignmentsAssessedAssessed3 directory and copy the given Assessed3Template.hs to a new file Assessed3.hs . Work on that file to produce your
solution and then submit it to Canvas.
It is important to copy the file as explained, since any future git pull may overwrite the template. Hence dont work directly on the template.
If you work inside another directory besides the git repository, you will also need to copy the file Types.hs , which includes type definitions that are imported by the template file. Any data or types that you define yourself should be in Assessed2.hs , but the ones defined in the assignment are and should stay in Types.hs . You should not modify the Types.hs file.
You will also probably want to copy the file DomViz.hs , which contains some visualization procedures based on the diagrams library. If you dont already have this library installed on your personal machine, installing it could be as simple as running
cabal install diagrams
from a terminal. On the other hand, if that doesnt work and you have trouble installing the library, your options are to:
1. try to get help on Slack;
2. use the lab machines, which already have the diagrams library installed; 3. comment out the import DomViz statement from your solution file.
Of course, option 3 sadly means that you wont have access to the visualization procedures on your machine. They are intended to make the programming task more enjoyable and to help you with debugging, but strictly speaking they are not needed to complete the assignment.
Because the marking is automatic, we need your submission to be in the correct format, and compile and type check without errors. A presubmit script will be released, which you need to run before you submit your assignment on Canvas. Submissions that dont pass the presubmit test wont qualify for marks.
Be aware that:
Your solutions must work with GHC 8.6.5. To use GHC 8.6.5 on a lab machine, see
HardwareAndSoftware.md.
If you wish to import modules, then you may only import libraries from the standard library. Additionally, all modules you import must be Safe on Hackage.
Some of the questions are harder than others, and these are indicated according to the rubric below. IT IS OKAY IF YOU DONT FIND COMPLETE SOLUTIONS TO ALL THE QUESTIONS.
Background
The game of Domineering
Domineering is a twoplayer strategy game that can be played over any shape board composed out of some collection of squares. Players alternate taking turns placing dominoes on the board to cover up a pair of squares, with one player which we will refer to as H always placing them horizontally, and the other player V always placing them vertically. The first player who cannot make a move loses.
For example, below is the full record of a game played on a 44 board, with H playing first in round 1 and winning in round 8, since V has nowhere left to place a domino.
1
1
2
3
2
4
5
2
2
3
1
1
4
6
3
5
7
7
4
8
3
5
1
6
2
1
2
4
3
1
2
4
3
5
6
1
Here is another example of a game on a 55 board, where this time H loses in round 13. We give only the abbreviated transcript of the game, showing the final position and the labelling of the moves by round.
4
11
2
13
3
12
8
1
6
9
5
7
10
A Domineering board does not necessarily have to be square. For example, here we see the transcript of a game on a board with two columns and nine rows.
4
5
3
1
7
6
2
8
Nor does the board have to be contiguous. Here are some games played on crosshatchshaped boards of different sizes:
6
13
2
15
17
14
3
10
16
8
11
12
9
7
4
5
1
5
4
8
10
3
1
6
7
2
9
Recent developments
This year, one of the most remarkable games in Domineering history was played between Alpha Dom and Lee Sedom, with Alpha Dom claiming victory in round 28. We show the transcript of the game below, together with another one demonstrating Alpha Doms mastery over a lowerskilled opponent.
Alpha Dom vs Lee Sedom 2019:
9
8
27
18
28
16
1
7
19
17
2
26
20
11
22
6
14
5
24
23
4
13
15
3
21
25
10
12
Alpha Dom vs Ran Dom 2019:
16
21
15
22
9
7
8
19
14
12
4
13
10
20
11
2
18
5
17
1
3
6
Representing the game
In this assignment, you will be tasked with writing various functions related to playing the game of Domineering. Some of these will be very similar to analogous functions covered in the Tic Tac Toe lectures and in Chapter 11 of Hutton, so you may want to review that material as preparation for this assignment. In a few places we will make slightly different design decisions, which will be signaled.
Lets begin by establishing the basic representation for players, moves, and boards.
data PlayerHV
deriving Eq, Ord, Show
type CellInt, Int
data BoardBoardturn :: Player, free :: Cell, hist :: Cell
deriving Eq, Show
A board is represented by a record containing three fields:
turn specifies the player whose turn it is to play;
free specifies the list of unoccupied squares;
hist specifies the list of previous moves played over the course of the game, in reverse
order.
We do not make any type distinction between squares and moves: both are represented by values of type Cell , this being a synonym for the type Int, Int of twodimensional integer coordinates. However, when we indicate a move by a cell, this is always interpreted as referring to the coordinate of the lower left corner of the domino.
For example, consider this board:
2
1
3
board4x43BoardturnH,
free1,1,1,2,2,2,2,3,2,4,3,2,3,3,3,4,
4,1,4,2,4,3,4,4,
hist1,3,2,1
Here we have assigned coordinates to the cells ranging from 1,1 for the lower left square to 4,4 for the upper right square. In round 1, H plays a horizontal domino at 2,1, which also occupies the cell 3,1. In round 2, V plays a vertical domino at 1,3, which also occupies the cell 1,4. Note our visualization conventions are the same as we used for the Game of Life, with the x coordinate increasing as we move rightwards across the board, and with the y coordinate increasing as we move upwards across the board.
The following utility functions will be useful:
given a cell c and a player p, compute the adjacent cell c
that is also occupied if p plays a domino at c
adjCell :: CellPlayerCell
adjCell x,y Hx1,y
adjCell x,y Vx,y1
compute the opponent of a player
opp :: PlayerPlayer
opp HV
opp VH
determine whether a move is valid in a given board
valid :: BoardCellBool
valid b cc elem free badjCell c turn b elem free b
You may also wish to experiment using the following functions that construct boards of different shapes.
create an empty board from an arbitrary list of cells
empty :: CellBoard
empty csBoardturnH, freecs, hist
create a rectangular board of arbitrary dimensions
board :: IntIntBoard
board maxx maxyempty x,yx1..maxx, y1..maxy
create a crosshatchshaped square board of arbitrary dimension
hatch :: IntBoard
hatch nempty x,yx1..2n1, y1..2n1, odd yx1x
2n1odd x
Representing game trees
We will represent game trees using rose trees just as we did for Tic Tac Toe, although for convenience we will import the type from Data.Tree . Officially, Tree a is defined in Data.Tree as a record type in mutual definition with Forest a ,
but if you prefer you can simply ignore the field labels and the type synonym, treating Tree as though it were defined by our usual definition:
data Tree aNode a Tree a
Visualization
The module DomViz exports a pair of functions
for visualizing games of Domineering, implemented using the diagrams library. Given a board b and a string basename , the command boardSVG b basename creates an SVG file named
basename.svg containing a graphical representation of b . For example, visualizations for the two recent victories by Alpha Dom that we mentioned above can be created by running the commands
type Forest aTree a
data Tree aNode rootLabel :: a, subForest :: Forest a
boardSVG :: BoardStringIO
gametreeSVG :: Tree BoardStringIO
boardSVG alphaDomvsLeeSedom alphadomvsleesedom
boardSVG alphaDomvsRanDom alphadomvsrandom
after introducing the following definitions:
alphaDomvsLeeSedom
BoardturnV,
free4,1,4,3,2,0,2,4,2,1,2,4,3,4,3,4,4,2,
4,0,
1,2,4,3,1,2,2,2,4,4,2,2,2,2,4,4,3,1,2,4,4,4,
1,3,4,2,3,2,3,1,1,3,2,3,3,1,1,3
alphaDomvsRanDom
BoardturnV,
free4,3,4,0,2,4,2,2,1,4,1,2,1,2,1,4,
0,4,0,2,0,2,0,4,1,4,1,2,1,2,1,4,2,4,2,2,2,4,3,4,
4,0,4,3,
hist3,4,2,1,3,2,4,2,4,4,4,3,3,4,2,1,
3,1,3,1,4,1,2,1,2,3,4,1,1,3,4,4,4,2,4,1,1,3,
3,2,2,3
hist0,4,4,1,0,4,4,3,1,2,2,1,2,4,4,1,
Similarly, given a game tree t and a string basename , the command gametreeSVG t basename creates an SVG file named basename.svg containing a graphical representation of t . We will give a demonstration of this below.
The DomViz module also exports a related pair of functions:
Both take an extra scale factor as first input, in case you want to grow or shrink the SVG graphics, and gametreeSVG takes a game tree where each node has been annotated with a label. Note that boardSVG and gametreeSVG are defined by boardSVGboardSVG 1 and gametreeSVGgametreeSVG 1 . fmap bb, respectively.
Questions
This assignment is worth a total of 60 marks. Harder questions are indicated with extra stars.
1. The first group of questions involves determining what moves are legal, performing legal moves, and undoing moves to recover the full record of a game.
5 marks Write a function
that returns the list of all legal moves for a player on a given board. Note that here we mean the legal moves for either player, regardless of whether it is that players turn to play.
boardSVG :: DoubleBoardStringIO
gametreeSVG :: DoubleTree Board, StringStringIO
legalMoves :: PlayerBoardCell
legalMovesundefined
legalMoves H board4x43
1,2,2,2,2,3,2,4,3,2,3,3,3,4
legalMoves V board4x43
1,1,2,2,2,3,3,2,3,3,4,1,4,2,4,3
5 marks Write a function
that takes a board and a legal move for the player whose turn it is to play, and returns the new board resulting from executing that play. If the move is actually illegal for the current player, then the behavior of moveLegal is unspecified.
10 marksWrite a function
that takes a board with some possibly nonempty history of moves, and returns the full record of the game leading up to that position, starting from an initially empty board.
moveLegal :: BoardCellBoard
moveLegalundefined
moveLegal board4x43 2,3
Board turnV, free1,1,1,2,2,2,2,4,3,2,3,4,4,1,
4,2,4,3,4,4, hist2,3,1,3,2,1
replay :: BoardBoard
replayundefined
replay board4x43
Board turnH, free1,1,1,2,2,2,2,3,2,4,3,2,3,3,
3,4,4,1,4,2,4,3,4,4,1,3,1,4,2,1,3,1, hist
,Board turnV, free1,1,1,2,2,2,2,3,2,4,3,2,
3,3,3,4,4,1,4,2,4,3,4,4,1,3,1,4, hist
2,1,Board turnH, free1,1,1,2,2,2,2,3,2,4,3,2,
3,3,3,4,4,1,4,2,4,3,4,4, hist1,3,2,1
2. The second group of questions are about playing optimally using minimax search on game trees.
Now that youve implemented legalMoves and moveLegal , game trees for Domineering can be computed almost exactly as we did for Tic Tac Toe:
If you like, you can visualize such trees using the gametreeSVG function mentioned above. For example, the command
gametree :: BoardTree Board
gametree bNode b gametree moveLegal b cclegalMoves turn b
b
gametreeSVG gametree board 3 3 board3x3full
will generate a rendering of the full game tree for the 33 board with H to start. However, you will find that these game trees can grow quite large! For example, the full game tree for the 55 board has 2103584601 nodes. Pruning of game trees can be implemented exactly as before:
For example, click here to see the depth 2 pruned game tree for the 33 board.
Minimax is parameterised by a scoring function that assigns values to the leaves of a game
tree. We will introduce the following type for scores:
data ScoreWin PlayerHeu Intderiving Show,Eq
The idea is that either we already know that some player p has a winning strategy from a given board, in which case we can assign it the score Win p , or else we can assign it some heuristic integer value Heu x , with negative values favoring H and positive values favoring V. Values of type Score are therefore naturally ordered, with
Win HHeu xWin V
for all x, and Heu xHeu y just in case xy. There is a corresponding instance of Ord Score provided in Types.hs .
5 marks Write a scoring function
implementing the following heuristic: if it is p s turn to play, return a win for p s opponent if p has no legal moves, and otherwise return a heuristic value based on the formula
where signH1 and signV1 . Example:
prune :: IntTree aTree a
prune0Nodex Nodex
prune n Node x tsNode x prune n1 ttts
score :: BoardScore
scoreundefined
legal moves for Vlegal moves for Hsignpnumber of
legal moves
score board4x43
Heu 2
5 marks
Write a function
haskell
minimax :: BoardScoreTree BoardTree Board, Score
minimaxundefined
that annotates every node of a game tree with a minimax score, computed
relative to an arbitrary scoring function for the leaves first argument.
Your implementation will probably be very similar to the implementation of
minimax we wrote for Tic Tac ToeLectureNotestictactoe.md,
except that it takes the extra scoring function as a parameter.
It should leave the tree untouched other than annotating each node with a score in other words, it should satisfy fmap fst minimax sfn tt .
Click here to see the minimax scoring of the depth 2 pruned game tree
diagramsboard3x3depth2minimax.svg for the 33 board, using the scoring
function score from above.
This diagram was generated with the following command:
hs
gametreeSVG 1 fmap b,vb,show vminimax scoreprune 2
gametree board 3 3 board3x3depth2minimax
10 marks
Write a function
haskell
bestmoves :: IntBoardScoreBoardCell
bestmovesundefined
which takes a depth d and a scoring function scorefn as parameters, and
defines a function from boards to lists of optimal moves.
Each move returned should be optimal in the sense that it has the best minimax
score for the current player, relative to the scoring function scorefn
applied to the game tree pruned to depth d.
Moreover, the list returned should be the complete list of optimal moves, although they can be returned in any order.
Take notice that an optimal move is not necessarily a winning move, in the
case where the player has no better options.
Your implementation will probably be very similar to the function bestmove
we wrote using minimax for Tic Tac Toe, except that we are asking you to
return the list of all optimal moves.
Examples:
hs
bestmoves 4 score board 3 3
1,2,2,2
bestmoves 4 score moveLegal board 3 3 1,2
3,1,3,2
3. Now that youve implemented bestmoves , we can combine it with an operation chooseSafe implemented using our old friend the PickingMonad to get a player who
selects optimal moves at random, and compare it against a player who selects legal moves at random.
chooseSafe :: PickingMonad mam Maybe a
chooseSafe return Nothing
chooseSafe xsdo
ipick 0 length xs1
return Just xs !! i
randomBestPlay :: PickingMonad mIntBoardScoreBoardm
Maybe Cell
randomBestPlay d sfnchooseSafe . bestmoves d sfn
randomPlay :: PickingMonad mBoardm Maybe Cell
randomPlay bchooseSafe legalMoves turn b b
Note we have to use chooseSafe here, which returns a Maybe type, since it is possible that the list of optimallegal moves is empty.
10 marks Write a function
that takes two players playH and playV of type Boardm Maybe Cell , and plays them off against each other starting from some initial board to produce a final board. It should run in any PickingMonad , and it should stop and return the current board as soon as either player gives up i.e., returns Nothingor makes an illegal move.
runGame :: PickingMonad mBoardm Maybe CellBoardm
Maybe CellBoardm Board
runGameundefined
For example, here are three games on a 44 board produced by setting randomBestPlay 8 score vs randomBestPlay 8 score , randomPlay vs randomBestPlay 8 score , and randomPlay vs randomPlay , respectively.
2
4
6
7
3
1
5
6
1
4
8
2
3
7
4
5
1
8
6
7
3
5
2
4. Now that you have a good supply of Domineering players, youd like some more interesting boards!
10 marksWrite a function
that generates an infinite sequence of empty boards, corresponding to the successive iterations of the Sierpinski carpet, where player H starts on evennumbered carpets and V starts on oddnumbered carpets. Heres what the first few look like we omit carpets !! 0 , which is a pretty boring board:
carpets !! 1
carpets :: Board
carpetsundefined
1
carpets !! 2
carpets !! 3
1
A challenge problem, and the official AFP Domineering Challenge
If youve already finished the assignment and want to try a harder problem, you can think about how to improve your minimaxbased player by implementing alphabeta pruning.
Later, as we did with the wordrects challenge, we will run a minicompetition to find the most effective Domineeringplaying programs. Precise rules are to be announced, but will involve implementing a strategy function
strategy :: PickingMonad mBoardm Maybe Cell
that takes a board and returns a move, potentially using randomness.t
1
Reviews
There are no reviews yet.