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

| 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 projects, but using the following template repository URLhttps://gitlab.cecs.anu.edu.au/comp1100/comp1100-project3.git for this project:

1. Go to the project’s gitlab repository: https://gitlab.cecs.anu.edu.au/comp1100/comp1100-project3. 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 project, 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 project 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 project

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

14. Click Clone and follow the same IntelliJ steps as Lab 2 starting from the clone step. Make sure you add the upstream remote:

15. git remote add upstream https://gitlab.cecs.anu.edu.au/comp1100/comp1100-project3.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 project 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 project 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 |

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

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