You will write a player robot—or bot for short—for the 2-player board game Backgammon. The objective is to choose the best move at each turn of the game in the face of an opponent (human or bot) who will seek to do the same. What’s more, we plan to run a class-wide tournament, allowing you to play your bot against those of other students in the class. You will be able to work on your bot to improve its capabilities, entering each new version into the tournament.

Deadline
Friday 25 May (end of Week 12): Your work should be committed and pushed to GitLab no later than 11:59pm on Friday 25 May as recorded by timestamp on GitLab.

Backgammon

Quoting Wikipedia:

Backgammon is one of the oldest known board games. Its history can be traced back nearly 5000 years to archaeological discoveries in the Middle East. It is a two player game where each player has fifteen pieces (checkers) which move between twenty-four triangles (points) according to the roll of two dice. The objective of the game is to be first to bear off, i.e. move all fifteen checkers off the board. Backgammon is a member of the tables family, one of the oldest classes of board games.

If you don’t know Backgammon already, you will probably want to familiarise yourself with its rules and play by trying it yourself online athttp://247backgammon.org. To emulate the game configuration in which your bot will be expected to play you should choose settings as follows:

• Reverse Direction: OFF
• Doubling Cube: OFF

Fortunately, you don’t need to know or program the rules of Backgammon for this assignment. We will provide the machinery to tell you the possible moves at each turn of the game. Your task is simply to choose from among the legal moves at each turn. Thus, it is possible to complete this assignment with minimal understanding of the game. Nevertheless, in what follows we will go ahead and describe the basics of Backgammon for you, because we hope you will find the game fun to play and strategise.

The Board

Each side of the board comprises a series of 12 points, or positions on which the pieces are placed, and to which they can move according to a dice roll. The points form a continuous track in the shape of a horseshoe, and are numbered from 1 to 24 depending on the perspective and direction of play of each player. Each player begins with 15 pieces, two placed on their 24-point, three on their 8-point, and five each on their 13-point and their 6-point. The two players move their pieces in opposite directions, from their 24-point to their 1-point.

Points 1 through 6 are called the home or inner board, and points 7 through 12 are called the outer board. The 7-point is referred to as the bar point, and the 13-point as the mid point.

The board starts in the configuration illustrated below, with each player’s pieces distinguished as x or o. Here the points are numbered from the perspective of the player playing as x who moves in the anti-clockwise direction around the horseshoe from the 24-point to the 1-point. The player playing as o moves in the opposite direction (the 24-point for x is the 1-point for o, and vice versa the 1-point for x is the 24-point for o).

    OUTER BOARD for o         INNER BOARD for o
  13  14  15  16  17  18    19  20  21  22  23  24
---------------------------------------------------
| x |   |   |   | o |   ||| o |   |   |   |   | x |
| x |   |   |   | o |   |B| o |   |   |   |   | x |
| x |   |   |   | o |   |A| o |   |   |   |   |   |
| x |   |   |   |   |   |R| o |   |   |   |   |   |
| x |   |   |   |   |   ||| o |   |   |   |   |   |
|   |   |   |   |   |   |||   |   |   |   |   |   |
---------------------------------------------------
---------------------------------------------------
|   |   |   |   |   |   |||   |   |   |   |   |   |
| o |   |   |   |   |   |B| x |   |   |   |   |   |
| o |   |   |   |   |   |A| x |   |   |   |   |   |
| o |   |   |   | x |   |R| x |   |   |   |   |   |
| o |   |   |   | x |   ||| x |   |   |   |   | o |
| o |   |   |   | x |   ||| x |   |   |   |   | o |
---------------------------------------------------
  12  11  10  9   8   7     6   5   4   3   2   1
    OUTER BOARD for x         INNER BOARD for x

The Objective

The objective is to move all of the pieces into the inner board, after which they can then be removed one by one from the board in what is called bearing off. The legal moves are as follows.

Movement

To start the game, each player rolls one die. The player with the higher number on their die moves first using the numbers shown on both dice. If both players roll the same number they must roll again. The players then alternate turns, rolling two dice at the beginning of each turn.

After rolling the dice, the player must move her pieces forward (towards the lower points) according to the number shown on each die, unless there is no such move possible. For example, if the player rolls a 3 and a 4 (written “3-4”, she must move one piece 3 points forward, and another or the same piece 4 points forward. The same piece can be moved twice, so long as both moves can be made separately and legally: 3 and then 4, or 4 and then 3. If the player rolls two dice the same, called a double roll, then that player must play the value of each die twice. For eample, a roll of “6-6” allows four moves of 6 points each. A player must move according to the numbers on both dice if it is at all possible to do so. If no move is possible then the player forfeits that move and the turn ends. If a move can be made according to either one die or the other, but not both, then the higher number must be used. If there is no move for one die, but its move is made possible by a move for the other die, then that sequence of moves is compulsory for that turn.

The destination point of each move must be:

• empty, or
• occupied by one or more of the player’s own pieces, or
• occupied by only one of the opponent’s pieces, called a blot.

Landing on a blot results in the opponent’s piece being hit: it is removed from the board and placed on the bar that divides the inner and outer boards. A player cannot move a piece to a destination point occupied by more than one of the opponent’s pieces; such moves are blocked. Otherwise, there is no limit to the number of pieces that can occupy a point at any given time.

Pieces placed on the bar must re-enter the board through the opponent’s inner board. A roll of 1 allows the piece to enter the board at the 24-point, a roll of 2 to the 23-point, and so on, up to a roll of 6 allowing entry on the 19-point. As above, a piece is blocked from re-entering if its entry point is occupied by two or more of the opponent’s pieces, in which case it remains on the bar. A player must re-enter all pieces from the bar before resuming movement of pieces on the board. Thus, if the opponent’s inner board is completely closed, with all six points occupied by two or more of the opponent’s pieces, then there is no roll that will allow the player to enter a piece from the bar. That player forfeits turns until at least one point numbered 19 through 24 becomes open.

Bearing Off

When all of a player’s checkers are in their inner board (points 1 through 6) she begins bearing off. A roll of 1 allows removing a piece from the 1-point, a roll of 2 from the 2-point, up to 6 to remove a piece from the 6-point. If all of a player’s checkers are on points lower than the number shown on a particular die, then that move can be applied to bear off one piece from the highest occupied point. The player can also move a lower die roll before the higher even if that means the full value of the higher die is not fully utilised. As before, if there is a way to use all moves showing on the dice, by moving checkers within the inner board or bearing them off, then the player must do so.

The first player to bear off all of their pieces is the winner of the game.

Luck

Dice rolls introduce an element of luck into the game. While the dice may determine the outcome of a single game, the player with the better strategy will usually come out ahead of weaker players over multiple games. For this reason, matches comprise a number of games (e.g., best of three, or best of five).

---

Setting things up

Follow the set up guide for previous assignments, but using the following template repository URL https://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment3.git for this assignment:

1. Go to the assignment’s gitlab repository:https://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment3. You will need to log in if you are not already.
2. Click on the Fork button to create your own private version of the assignment, so you can work on it independently from everyone else.
3. Click on your name and wait a little while.
4. Your web page should automatically refresh, and if everything went well, display your repository containing the assignment files. You can check this by looking above the banner “The project was successfully forked.”, it should display your name instead of comp1100.
5. In the menu on the left, hover over “Settings” and then click on “Members”. Under “Select members to invite”, type in your tutor’s name, and select your tutor.
6. Change the role permission from “Guest” to “Reporter” so that your tutor can access your assignment
7. Click on the green button “Add to project”
8. Click on “Overview” in the menu on the left.
9. Next to the “Fork” button in your repository, there is a button which says “SSH”. Click on it and switch it to “HTTPS”.
10. Copy this URL.
11. Open IntelliJ. If some other project opens up then close the window: click on the menu File at the top of the IntelliJ window and select Close Project.
12. In the IntelliJ IDEA window, click on Check out from Version Control and select Git.
13. Paste the URL that you copied above into the Clone Repository dialogue box as the Git Repository URL. Set Parent directory to be ~/comp1100, and the directory name as assignment3.
14. Click Clone and follow the same IntelliJ steps as Lab 2 starting from the clone step. Make sure you add the upstream remote:

    git remote add upstream https://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment3.git
    

---

The Task

Your sole task is to (re-)implement the single function makeMove located inside the file src/PlayAsWhite.hs, which has the following function signature:

makeMove :: State -> Lookahead -> Moves

Given the current state of the game and a Lookahead value (we will describe this presently), this function returns the sequence of moves that you’d like to play. You only need to complete this one function. However, you might find writing peripheral functions useful.

---

Framework

As with Assignment 1 and 2, we are using cabal, the Haskell build tool, to streamline the compilation of our programs. You should be familiar with the following commands from Assignment 2:

• cabal clean
• cabal build
• cabal repl

You have also been using cabal run. However, this time, the program will also accept a number of command-line arguments. To view the available arguments you can use the cabal command as shown:

$ cabal run -- --help
Preprocessing executable 'Backgammon' for Backgammon-0.2.0.0..
Building executable 'Backgammon' for Backgammon-0.2.0.0..
[8 of 8] Compiling Main             ( src/Main.hs, dist/build/Backgammon/Backgammon-tmp/Main.o )
Linking dist/build/Backgammon/Backgammon ...
Running Backgammon...
Backgammon - an AI game for COMP1100/1130.

Usage: Backgammon [-t|--timeout ARG] [-p|--playTo ARG] [-h|--human]
  Run the Backgammon game with some options.

Available options:
  -t,--timeout ARG         How many seconds before times out. (default: 2)
  -p,--playTo ARG          How many points to play to. (default: 3)
  -h,--human               If there is a human player.
  --help                   Show this super helpful help text

For example, to play Black as a human, use cabal run -- -h.

If you want to change the timeout to 3 seconds:

• cabal run -- -t 3, or
• cabal run -- --timeout 3, or
• cabal run -- --timeout=3

There are a number of Haskell source code files, in the src subdirectory.

Main.hs

This is the main module, containing the functions required to perform IO actions (printing to the Terminal, getting input from Terminal, etc.), which you are not required to understand. However, if you are interested, you are more than welcome to ask about it. This is also where the dice rolling is implemented in getDice (random generation of two numbers each between 1 and 6).

Player.hs

This is where the Player enumeration data type is defined: White (displaying as O) or Black (displaying as X).

Board.hs

The custom data type Board is defined in this file. Note that this definition looks a bit different from what you might have seen previously—this one has curly brackets:

data Board = Board
  { points :: [Point]
  , wBar :: Int
  , bBar :: Int
  }

This is written using record notation, which is really just syntactic sugar for the following definitions:

data Board = Board [Point] Int Int

points :: Board -> [Point]
points (Board ps _ _) = ps

wBar :: Board -> Int
wBar (Board _ w _) = w

bBar :: Board -> Int
bBar (Board _ _ b) = b

So if you want to check if there are 24 points on a board:

enoughPoints :: Board -> Bool
enoughPoints (Board ps _ _) = length ps == 24

However, the record notation can handle the pattern matching for you:

enoughPoints' :: Board -> Bool
enoughPoints' b = length (points b) == 24

This can be handy when you are writing larger functions.

In this file there is also a definition for instance Show Board, which tells Haskell how to print a Board to the Terminal nicely:

*Board> initialBoard

  13  14  15  16  17  18    19  20  21  22  23  24
---------------------------------------------------
| x |   |   |   | o |   ||| o |   |   |   |   | x |
| x |   |   |   | o |   ||| o |   |   |   |   | x |
| x |   |   |   | o |   ||| o |   |   |   |   |   |
| x |   |   |   |   |   ||| o |   |   |   |   |   |
| x |   |   |   |   |   ||| o |   |   |   |   |   |
|   |   |   |   |   |   |||   |   |   |   |   |   |
---------------------------------------------------
---------------------------------------------------
|   |   |   |   |   |   |||   |   |   |   |   |   |
| o |   |   |   |   |   ||| x |   |   |   |   |   |
| o |   |   |   |   |   ||| x |   |   |   |   |   |
| o |   |   |   | x |   ||| x |   |   |   |   |   |
| o |   |   |   | x |   ||| x |   |   |   |   | o |
| o |   |   |   | x |   ||| x |   |   |   |   | o |
---------------------------------------------------
  12  11  10  9   8   7     6   5   4   3   2   1

Oherwise we would see the following, which is not so nice:

*Board> initialBoard
Board {points = [Just (Black,2),Nothing,Nothing,Nothing,Nothing,Just (White,5),Nothing,Just (White,3),Nothing,Nothing,Nothing,Just (Black,5),Just (White,5),Nothing,Nothing,Nothing,Just (Black,3),Nothing,Just (Black,5),Nothing,Nothing,Nothing,Nothing,Just (White,2)], wBar = 0, bBar = 0}

Some peripheral functions for the Board data type are also defined in this module.

State.hs

The State data type defined in this module uses the record notation extensively. Peripheral functions related to the State type appear in this module.

Move.hs

The mechanics and logic of the game manifest in Move.hs. Some functions you might find interesting/useful are:

• performMovesThis function takes the current State, and a list of moves, and performs each move in order, producing the state after all the legal moves have been played. However, it is important to note that there must be no remaining moves after the list of moves have been given, otherwise a Did not make enough moveserror will occur.
• performSingleMoveThis function is similar to performMoves, but produces the State after a given move. If the move is not valid, it leaves the State unchanged. You might find this useful in figuring out intermediate moves.
• legalMovesThis produces a list of all immediately legal moves given the current State. Note that the list of legal moves will change after every single move played.
• isLegalMoveThis is used to check if any given move is legal for the current State.
• legalMovesTreeThis function produces a Rose Tree (remember Lab 8) containing all states that are reachable by remaining moves for the current turn from the current state. We are using the Rose Tree implementation obtained by import Data.Tree. The leaves of this tree will be all possible alternative states the player can reach on the current turn. Naturally, a player will want to choose the best of these according to some criterion.

Options.hs

This module does handles the command line flags: when you issue the Terminal command cabal run -- -p 3, this module “translates” it into options that the program will use to configure a match. You don’t need to worry about this file, though you are welcome to ask questions if interested.

PlayAsBlack.hs

This contains the bot intelligence for the Black player. For testing purposes, you might find it useful to use PlayAsBlack.hs to hold your previous best algorithm, to see if your newer White player is an improvement. The implementation of Black that we have provided to you is currently very dumb! It generates a list of all 600 possible combinations of point positions with dice rolls (i.e., moves) regardless of the legality of those moves for the current state. Fortunately, this works because our move machinery will perform the first nn legal moves it finds in the list to finish out the current turn.

If you play a match as a human then the the Black player code will be ignored and the human (i.e., you) will play as Black instead.

PlayAsWhite.hs

This is where the bot intelligence of the White player appears. The White player always plays using this bot opposed to the Black player (human or bot). This is also the file that gets played in the tournament whenever you push it back to GitLab (unless you opt out)—details below. It is important to note that in the tournament this player may play as either Black or White, so your intelligence should not bake in an assumption that it is playing as White. Fortunately, you can tell your player colour in your makeMove function by inspecting the state and asking whose turn it is when the function is called.

Lookahead

Lookahead is a type synonym for Int:

type Lookahead = Int

The framework provdes Lookahead values greater than 0. You should use this value to decide how “hard” your function should try in finding a good sequence of moves. You need to be able to provide an answer within a fixed time limit, and the last answer you provide within this time limit will be used. Otherwise, there are no inherent properties behind this number. The most common use of the Lookaheadvalue is to decide how many turns ahead in the game you should search to decide the best possible moves to make on the current turn. For example, a Lookahead value of 1 will indicate to your function that it only needs to return a move based on what’s best for your player given where you can position yourself on the current turn. A lookahead of 2 will suggest that you try look two moves into the future, and so on. It is entirely up to you how you want to use this value.

You will notice in the starting template code we have provided for the White player that we use the lookahead to introduce a delay that computes how many primes there are up to some limit that is a function of the lookahead. Of course, this is contrived, but it emulates the White player thinking hard about the next move, even if it is simply to become distracted by computing prime numbers.

Think about how applying lookahead will affect the success of your player?

Best move within time

As mentioned above, there is a timeout per turn while playing the game. There is also an upper limit on how much time can be used for your function to return a list of moves. If your player exceeds the maximum time limit it will be forced out of the game.

However, it is very difficult to design your algorithm such that it will:

1. maximise the scope of search, and
2. make sure it stays under the time limit for all situations.

This is why we use the notion of “best move within time”. When it is your player’s turn, a lookahead value of 1 will be passed into your function. If your function returns within the time limit, a lookahead value of 2 will be passed into your function. This goes on until:

1. your function takes too long to return a move for a given lookahead value, or
2. your function doesn’t take any longer to evaluate higher lookahead values (stalling).

At this point, the last returned moves within time will be played. Here is an example of situation 1:

• Given a state, and a timeout of 3 seconds, your function is called to return a list of moves.
• With a lookahead value of 1, your function returns [(23, 5), (21, 3)]. This takes 0.5 seconds.
• With a lookahead value of 2, your function returns [(22, 3), (18, 5)]. This takes 1.4 seconds.
• With a lookahead value of 3, your function returns [(18, 3), (17, 5)]. This takes 2.7 seconds.
• With a lookahead value of 4, your function times out. It takes more than 3 seconds and gets killed.
• Your moves for this turn will be [(18, 3), (17, 5)]

An example of situation 2 is:

• Given a state, and a timeout of 3 seconds, your function is called to return a list of moves.
• With a lookahead value of 1, your function returns [(18, 6), (12, 6), (6, 6)]. This takes 0.205 seconds.
• With a lookahead value of 2, your function returns [(18, 5), (13, 6), (7, 6), (1, 1)]. This takes 0.21 seconds.
• With a lookahead value of 3, your function returns [(18, 6), (12, 6), (6, 6)]. This takes 0.211 seconds.
• With a lookahead value of 4, your function returns [(18, 6), (12, 6), (6, 6)]. This took 0.21 seconds.
• With a lookahead value of 5, your function returns [(18, 6), (12, 6), (6, 6)]. This took 0.213 seconds.
• Your function is treated as stalling. Moves for this turn will be [(18, 6), (12, 6), (6, 6)].

This is all handled in the framework for you. You just need to make use of the lookahead value passed into your function to adjust how “hard” your function looks for a successful solution.

---

Trees

So far so good. So how is this related to trees? Playing as humans, we don’t abstract this problem to trees, right? Actually, we somewhat do.

Think about it this way: for every move that you make, there may be a set of moves that your opponent can make, and for every one of those moves, there may be a set of moves that you can make. As the game plays out the players are exploring these alternatives, and a strategic player will think ahead some number of moves to gain better board position. At some point neither player can move and the game ends.

For some games, if you generate the entire game tree (which is astronomically large for most games, and sometimes can be infinitely deep), you will know the shortest path to the game finish, as well as be able to deduce every single outcome of the game. However, due to the randomness in playing Backgammon (thanks to the dice), this is slightly trickier—even if you have the entire game tree, you are still not sure if you would win the game overall as luck might not be on your side when rolling the dice.

However, to outplay an opponent, you don’t need to see the entire tree. You just need to look further ahead into the tree than your opponent! This is why a more efficient or cleverly thought out algorithm will perform better than an average one.

Search

Choosing the current move based on future moves is a type of search problem. The value of an outcome is measured via its utility. The utility indicates how “happy” you are about that outcome. Thus a higher utility is always preferred to a lower one. A function that approximates the utility value of a given state is called a heuristic. As you play a game you will intuitively come up with your own heuristics to maximise your success.

Minimax

For games where opponents take turns to play, there is a well-known decision rule called minimax. The assumptions of minimax are that each player will choose the best moves (for themselves) at each turn. To express it from your perspective:

1. You will always choose what’s best for you.
2. Your opponent will always choose what’s worst for you.

Every time you can make a move you will thus choose a move that maximizes your utility value—i.e., you will choose what’s best for you.

On the other hand, you will assume that your opponent’s moves will seek to minimize your utility value—i.e., choose what’s worst for you.

So minimax is a “find the best of the worst” algorithm. More information about minimax can be found on Wikipedia at https://en.wikipedia.org/wiki/Minimax.

You can build a minimax search tree as an explicit data-structure (using an algebraic type and applying recursive functions to it as you did before), or implicitly via recursive functions alone where the returned expression of each function is the value of a node in your tree. The former has the advantage that you can pass the whole tree along to other functions and can process the tree in multiple passes without building it each time. The latter has the advantage that information is only held as long as needed (using less memory over time)—once a “node” function has received the required value from a “sub-node” function, this sub-node will be forgotten.

Expectiminimax (Expectimax)

Having looked through the minimax Wikipedia page, you should spot that minimax works for decisions that are entirely deterministic—making no assumptions about the probabilities of various outcomes. However, Backgammon introduces an element of chance with the rolling of dice. We need to make decisions in the face of probabilistic outcomes.

Expectiminimax is a variation of the minimax algorithm for 2-player games in which the outcome depends on both the skill of the players as well as chance. This makes it suitable for Backgammon.

Heuristic Pruning

As the game tree branches so quickly in Backgammon, heuristic search is almost necessary rather than preferred. Alpha Beta Pruning can dramatically improve the performance of minimax (and expectiminimax), by reducing the branching factor of the search tree by logically eliminating branches that are not relevant.

Of course, there are many other heuristics that can apply to a given game, some based on known strategies, and others that avoid giving too much weight to successes and failures. We encourage you to experiment with different approaches in order to improve your player.

---

Programming Constraints

1. You may only change the files PlayAsBlack.hs and PlayAsWhite.hs.
2. No impure side-effecting libraries or implementations are permitted in these files. (This includes IO, Foreign Function Interface, Network, etc.). If there is something that you are unsure about, please ask on Piazza before importing it into your module.
3. No unsafe functions are permitted in these files (such as Debug.Trace). One way of checking if a library is safe is to find it on Hackage (e.g.,Debug.Trace), and check the “Safe Haskell” attribute in the information block on the top right. Everything you have learnt in this course so far is safe, with the exception of trace.

---

Tournament

We will make an announcement on Piazza once the tournament site is up and running. In the meantime, you can easily test your work by playing yourself as Black against your PlayAsWhite.hs implementation using the cabal run -- -h terminal command. It is important that you understand that the ranking of your player in the tournament plays no role in the marks you receive for this assignment.

If you don’t opt out, once the tournament is running, then every time you commit and push your PlayAsWhite.hs file back to GitLab it will be entered into a Backgammon AI Tournament along with other COMP1100/1130 students to see how effective your algorithm is against others.

Opt-out

If you decide not to participate in the tournament, you just need to have a file called OptOut in the root directory of your assignment repository. The easiest way of achieving this is to use the following command in the IntelliJ Terminal for your project:

touch OptOut
git add OptOut

This will create an empty file named OptOut. After committing and pushing, your player will no longer participate in the tournament. If at any time you want to participate in the tournament, just remove this file, commit and push:

git rm OptOut
git commit -a -m "Opting back in"

Submission Pipeline

When you commit and push your file into GitLab, it will automatically trigger a “pipeline” which is a sequence of processes that are automatically executed on your code in order to add it to the tournament:

1. GitLab will “tell” the tournament server that a file is recently submitted if no OptOut file is found.
2. The tournament server will fetch your PlayAsWhite.hs file.
3. It will be compiled using the same framework that we have provided to you.
4. Your PlayAsWhite.hs file will be copied on the server toPlayAsBlack.hs, and you will play a match against yourself.
5. If all of the above succeeds, then your PlayAsWhite.hs file will be entered into the tournament pool and will play matches agains all other players. If your code fails any of the above, then the pipeline will end and your player will not be added to the tournament.

All you need to do is commit and push to GitLab, and we will handle the rest for you.

Matches

For now, every player will be pitted round-robin against every other player in the tournament. So with 400+ students, there will be approximately 160,000 matches in total, assuming that everyone submits only once. Since this is an unrealistic assumption, we are expecting the total number of matches to be over 300,000. This means that it will take a while for your player to play against everyone else after submitting it. This also means that towards the deadline for the assignment it is very unlikely that any new submissions will be added to the tournament. So if you’d like to get an indication of how your player is going, make sure to enter early! We may yet change to running a Swiss style tournament where players play off against similarly-ranked players, but will announce if that happens.

The server will continue running until all matches are played out even after the assignment deadline. However, no new submissions will be taken after the deadline.

Environment

The tournament server is running on a rack server with 4 x 12-core Intel Xeon Gold processors. Each match occupies one thread, and with hyper-threading disabled, one thread occupies one core. Only 44 out of the total of 48 cores will be used at a time, with the remaining 4 cores acting as a temporary buffer for any performance peaking and system-wide operations. This is to ensure that no matter how busy or idle the server is, no players are advantaged or disadvantaged.

---

Report [30 marks]

As this assignment is intrinsically linked to performance, discussion of the performance of your program is expected. This includes, but is not limited to:

• How did you evaluate the utility of a given board configuration?
• What made you try or submit a specific search method?
• What problems did you encounter, and how did you overcome them?
• Did you try a sequence of players, and how did they evolve?
• Why do you think your player succeeded or failed in the tournament?
• Why does performance matter?
• What most affects the performance of your program, how did you measure and compare performance, how did you improve performance, and which improvements had the biggest impact?
• What more could you have done to improve your program, and why did you decide not to implement those improvements?

Since you have complete creative freedom for this assignment, in addition to the performance discussions, you should also cover your major design choices and how they affect the overall maintainability and readability of your code.

The word limit on the report is 1500 for COMP1100 students, and 3000 for COMP1130 students. As with previous assignments, these are the maximum number of words that your marker will read. Please be succinct with your report. Keep in mind that the purpose of your report is to inform your reader efficiently, which means that structure, sequence, writing, readability, and technical soundness are important.

Your report should cite all sources of information that you used to complete the assignment, including Web sites, discussions with classmates (including those you helped), any on-line exchanges, papers and articles your read, etc. We expect all code in your assignment to be authored by you. Any code that was not authored by you (excluding code that you forked from the assignment template repository) should be noted and the source cited. Remember that you are otherwise formally representing the code you submit as your own creative work. Misappropriating another’s creative work is considered an integrity violation.

Your report must be in PDF format, located at the root of your assignment repository on GitLab and named Report.pdf. Otherwise it may not be marked. Use git add Report.pdf and then commit and push your work to GitLab. You should check your project on https://gitlab.cecs.anu.edu.au to see that everything, including your report, is there by the deadline.

The report should have a title page with the following items:

• Your name
• Your laboratory time and tutor
• Your university ID
• Collaborators, if any

---

Communicating

Do not post your code publicly, either on Piazza or via other forums. If by mistake you post your code publicly on Piazza, an email containing your post with your code will be sent to all students. This means that others will have access to your code and you may be held responsible for plagiarism.

Once again, and we cannot stress this enough: do not post your code publicly. If you need help with your code, post it privately to the instructors.

When brainstorming with your friends, do not show your code to them. There might be some pressure from your friends and even some judgements that you are not sharing the code, but it is for both your and their benefit. Anything that smells of plagiarism will be dealt with seriously and there may be serious consequences.

Sharing ideas is perfectly fine, but sharing should stop at ideas.

Course staff will not look at assignment code unless it is posted privately in piazza.

Course staff will typically give assistance by directing you to relevant exercises from the labs, or definitions and examples from the lectures.

Before the assignment is due, course staff will not give individual tips on writing functions for the assignment or how your code can be improved. You will receive their feedback when the mark is released.

---

Submission Checklist

Preferably 24 hours prior to the assignment deadline, you should make sure that:

• You have fully read and understand the assignment specification.
• Your code works on the lab machines.
• Your latest commit is pushed to GitLab. Ensure this by going to the web interface of GitLab and check manually.
• Your report is in PDF format, located at the root of your project on GitLab, and named Report.pdf. Otherwise, it may not be marked.
• You have given your tutor Reporter access to your comp1100-assignment3 repository.

Your assignment code should not have any warnings when compiled with cabal clean && cabal build. Some of the marks will be attributed to the styling of your code. Thus it’s important that you do not have any obfuscated code or unnecessary repetitions in the code. Your file should be correctly indented uniformly throughout and lines should not be longer than 80 characters long.

Your report should be of relatively professional quality, incorporating any styling advice given by your tutor from previous assignments.

Please don’t email your tutor asking them to check if they can see your commit. As long as they have reporter access, and your files are on GitLab, they can see it.

---

Marking

The marking is divided roughly into 70% for the code and 30% for the report. For exceptional reports or code fragments we might take the liberty to shift those percentages slightly to acknowledge extra efforts.

Marks in the code will be awarded for functionality (i.e., it works), clarity of code (i.e., we immediately understand why it works), and efficiency (i.e., it transitions at a reasonable pace).

Marks in the report will be awarded to concise writing, completeness of the report, and your understanding of your own designs and findings.

Here is a breakdown of example student cases with different marks awarded:

Grade	Criteria
Pass	Code compiles and delivers a complete move sequence for the turn at all times. The game strategy is noticeably different from “do the first sequence of moves you find”. The report shows basic understanding of the problem and explains the submitted code.
Credit	Code compiles without warnings and delivers a complete move sequence for the turn at all times and in time. Minimax search is fully functional. The code is well structured and well supported in the report.
Distinction	Code is well structured, efficient and implements a fully working minimax search utilizing a well thought out board evaluation function. The report is excellently written and addresses all items.
High Distinction	The submitted solution significantly exceeds the expected performance of a plain minimax tree design. The report is excellently written and explains in detail which additional measures have been taken and how they have been implemented.

Roughly, you can expect to be able to reach a distinction level mark with an excellent submission of a minimax based solution, and a high distinction mark with an excellent submission which goes beyond that. Again, keep in mind that addressing a more complicated assignment part does not guarantee you any kind of mark—it only shifts the upper end for the potential mark.

Exceptionally elegant solutions, common programming mistakes and complete disaster submissions may be discussed in class (with your name removed of course).

---

Final Words

Good luck, and have fun!

---

References

There is a deep and longstanding body of literature on the topics of search in game trees. We encourage you to search and read widely in devising your bots. Here we provide some jumping off points into the literature.¹²³⁴⁵