haskell代写comp1100: Assignment 3: Backgammon Bot minmax人工智能

Assignment 3: Backgammon Bot

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 at http://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 ahorseshoe, 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 omoves 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 |

—————————————————

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 byonly 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 URLhttps://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment3.git for this assignment:

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.
Click on theForkbutton to create your own private version of the assignment, so you can work on it independently from everyone else.
Click on your name and wait a little while.
Your web page should automatically refresh, and if everything went well, displayyourrepository 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.
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.
Change the role permission from “Guest” to “Reporter” so that your tutor can access your assignment
Click on the green button “Add to project”
Click on “Overview” in the menu on the left.
Next to the “Fork” button inyourrepository, there is a button which says “SSH”. Click on it and switch it to “HTTPS”.
Copy this URL.
Open IntelliJ. If some other project opens up then close the window: click on the menuFile at the top of the IntelliJ window and select Close Project.
In the IntelliJ IDEA window, click onCheck out from Version Control and select Git.
Paste the URL that you copied above into theClone Repository dialogue box as the Git Repository URL. Set Parent directory to be ~/comp1100, and the directory name as assignment3.
ClickClone 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 filesrc/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 asX).

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 | | | | | ||| o | | | | | |

| | | | | | ||| | | | | | |

—————————————————

| | | | | | ||| | | | | | |

| o | | | | | ||| x | | | | | |

| o | | | | x | ||| x | | | | | |

| 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:

performMoves

This 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 moves error will occur.

performSingleMove

This 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.

legalMoves

This 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.

isLegalMove

This is used to check if any given move is legal for the current State.

legalMovesTree

This 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 makeMovefunction 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 Lookahead value 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:

maximise the scope of search, and
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:

your function takes too long to return a move for a given lookahead value, or
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.

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:

You will always choose what’s best for you.
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

You may only change the fileshsand PlayAsWhite.hs.
No impure side-effecting libraries or implementations are permitted in these files. (This includesIO, Foreign Function Interface,Network, etc.). If there is something that you are unsure about, please ask on Piazza before importing it into your module.
No unsafe functions are permitted in these files (such asTrace). 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 yourPlayAsWhite.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 yourPlayAsWhite.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:

GitLab will “tell” the tournament server that a file is recently submitted if noOptOutfile is found.
The tournament server will fetch yourhsfile.
It will be compiled using the same framework that we have provided to you.
Yourhsfile will be copied on the server to PlayAsBlack.hs, and you will play a match against yourself.
If all of the above succeeds, then yourhsfile 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.

Related Posts