[SOLVED] haskell代写：Assignment 3 – ConnectX

Assignment 3 – ConnectX

Steven X. Han

DUE DATE AND TIME: Monday Week 12 (October 23), 9:00AM sharp.

No late submissions will be accepted.

Your work should be pushed to GitLab and your repository should be shared with your tutor and with Steven with Reporter permission.

Start working on the assignment as soon as possible. The completion may require several sessions of work.

Note: The webpage of Assignment 3 always contains the most recent version of the assignment. We advise you to open/refresh this page every time you recommence working on the assignment. In case of changes and corrections in the assignment, we will make an announcement in piazza. Check piazza regularly.

Academic Integrity

Do not plagiarise.

• Do not show your code to anyone. • Do not view anybody else’s code. • Do not share your code.
• Do not copy anybody else’s code.

• Do not read anybody else’s report.
• Do not show your report to anybody.

All parts of code and report for the assignment should be written by you alone. It is not team work!

You are required to complete an Assignment Cover Sheet and submit it as the first page of your report with your code via GitLab before the due date. Otherwise, your assignment will not be assessed and will attract a zero mark.

1

Introduction

Many of you probably have heard and played the game “Connect Four”, where a blue player and a red player alternate in placing discs on a vertical grid which would fall to the bottom. The first person to get four in a row, be it horizontally, vertically or diagonally, wins. There are 4,531,985,219,092 unique ways to fill a 7-column 6-row standard grid and 1,904,587,136,600 ways to get four in a row! If you haven’t played this game before, you can find a version of it here:

https://www.mathsisfun.com/games/connect4.html
If you are looking for a description, you can look at this Wikipedia page: https://en.wikipedia.org/wiki/Connect_Four
If you want to watch a YouTube video about it, Numberphile has an excellent one: https://www.youtube.com/watch?v=yDWPi1pZ0Po
On the Wikipedia page there is an excellent demonstration of the gameplay:

Figure 1: Gameplay

Connect Four is a two-player, adversarial, zero-sum connection game involving ab- stract strategy with perfect information. On the Wikipedia page, you can see a section called Mathematical Solution. John Tromp, although not the first to solve the game, wrote a program in C++, which solved a 9×6 version of the game. The program took over 2000 hours of computation. If you are interested in his fascinating write-up, you can go to his website at the link below:

https://tromp.github.io/c4/c4.html

The solution is based on a 7-column 6-row grid, which is the most common version of the game published by Milton Bradley and Hasbro. For smaller grids, it is easier to calculate the mathematical solution. However, as the grid gets larger, the number of possible ways to fill a grid increases extremely rapidly!

2

Task

The task of this assignment is as follows:

Write a function

makeMove :: Board -> LookAhead -> Index

that takes two arguments and outputs an integer Index that indicates the column where your player drops the disc.

Details of the definition of Board can be found in the next section. LookAhead is an Integer value, used to indicate the depth of the tree the function is searching through. A value of LookAhead equal to one means you are only looking at the next step of the game and making a decision based on that. Your function will initially be called with a LookAhead value of 1, and this value will increase one by one until your function exceeds the timeout. At this point the last response that is within the time limit by your function is used to play the move.

You should implement this function in the file Bot/Blue.hs. You are not required to implement the red bot. However, if you’d like to test your player locally, you might want to implement a strategy in the Bot/Red.hs file to verse against.

We will only mark your Blue.hs file.

3

Foundations

We have done all the foundation work for you. Below we give a short overview of the essential modules.

All of the definitions for the data types and some of their peripheral functions can be found in the modules located in the Data folder.

Data.Board

This module provides the definition for the custom record type Board, as well as the Show instance of it so that it can be printed out in a nice way in the terminal.

This module defines Board record that contains: a. The current configuration of the grid b. Your score c. Your opponent’s score d. Whose turn it is and whether the game is finished. e. The number of discs needed to be connected to win the game (this number is called a “streak”)

data Board = Board { board :: M.Matrix Cell , blueScore :: Score

deriving (Eq) where

type Matrix a = [Column a] type Column a = [a]
data Cell = Empty | Blue | Red

, redScore:: Score

, turn, connect}

:: Player:: Int

deriving (Eq, Read)
type Score = Int
data Player = BlueBot | RedBot | Finished

deriving (Show, Eq)

The game is designed so that it will work with any configurations of board dimension and any streaks. Your function makeMove should also work with arbitrary dimensions and streaks too.

Let’s have a closer look at getScore.

4

getScore

This function calculates the score for one of the players in the following way:

1. The minimum number of consecutive same-coloured discs, M, which would give you points

   is streak `div` 2 + 1

   For example, for the Connect Four version, M is 3. For the Connect Seven version, M is 4.

2. The grid will be scanned first by column, then by row, then by the two diagonals.
3. Any consecutive same-coloured discs of length greater or equal to M is counted.

   For example, for the game displayed below, the blue player’s points are counted as follows:

   Figure 2: Example Game

   • By column: 6 points (In column 1 and column 5) • By row: 3 points (In the bottom row)
   • By diagonals: 3 points
   • Total points: 12 points

   For the red player:

   • By column: 6 points (In column 3 and column 4)
   • By row: 3 points (In second bottom row)
   • By diagonals: 6 points (The red disc on the top of column 5, spreading both left and

     right)

   • Total points: 15 points
4. The points are then be scaled up by a factor of 4, so the blue player will have 48 points, and red player will have 60 points.
5. If you win the game, you get additional points equal to 2 multiplied by the grid width multiplied by the grid height.

5

Data.Cell

This module provides the definition for the custom sum data type Cell, along with the definition for the Show instance for it. A Cell can be Blue, Red, or Empty.

Data.Column

This module provides the definition for the Column data type, which is a synonym for a standard list from Haskell prelude.

pushToColumn

This function will add an element to the end of the list.

unfillColumn

When a disc is placed in a column, it falls down. Since the bottom disc has the index of 0 in our column, we can deduce that everything after the first Empty cell will all be empty. This means that it is redundant to store the elements after the first Empty, so this function drops them. This function is written polymorphically so that it will work on a Column of anything.

> unfillColumn 3 [1, 5, 2, 3, 3, 3, 3, 3][1, 5, 2]

fillColumn

From the name you can guess that this is the reverse of unfillColumn. For a Column, if we know the maximum height it can be (in our case, the vertical component of the grid dimension), we can fill up the “Empty spots” in the lists with Empty values.

> fillColumn Empty 5 [Blue, Red][Blue, Red, Empty, Empty, Empty]

Data.Matrix

This module provides the definition for the Matrix data type. Instead of having the matrix represented as a list of rows, such as the one used in the Battleship assignment, this matrix is represented as a list of Columns. The reason is that the grid of ConnectX is inherently grouped by columns as all pieces fall down and there are no horizontal displacements.

Data.Player

This module provides the definition for the custom sum data type Player, as well as some peripheral functions.

6

Commandline.Options

This module provides support for command line argument handling. You are able to change the game’s default timeout, whether it is played by two bots or a bot and a human, the dimension of the board, and the winning streak.

The default options are:

defaultOptions :: OptionsdefaultOptions = Options {

timeLimit = 5.0,isHuman = Nothing,boardDim= (11, 10),winStreak = 5}

However, you are able to change all of these by passing arguments to the program in the terminal or command line. Assuming that you have compiled the program:

• stack exec ConnectX — -t3 will change the timeout from default to 3 seconds.
• stack exec ConnectX — -hB will make Blue player the human player.
• stack exec ConnectX — -d”(8, 9)” will change the board dimension to an 8 column

  9 row configuration.

• stack exec ConnectX — -s5 will change the winning streak requirement to 5 in a row.
• stack exec ConnectX — -t3 -hB -d”(8, 9)” -s5 will do all of the above.

  You can enter these options in any order.

  ConnectX.hs

  This module deals with any direct IO of the game such as printing things out onto the screen and receiving arguments.

  Transition.Mechanics

  This module defines the core logic and mechanics of the game. You can say that “this is where the magic happens”. The functions defined in this file are very important. You aren’t required to understand this file for this assignment. However, the functions might be useful for when you are learning about IO.

7

Programming

Randomly choosing an index to place your disc isn’t a great strategy, so what is? If you look into algorithms for adversarial games, you will inevitably come across the terms Minimax Tree or Negamax Tree. The concept of Minimax trees will be explained in the lectures. More information can be found on Wikipedia:

https://en.wikipedia.org/wiki/Minimax

Negamax tree is a special variant of the Minimax tree. It relies on the zero-sum property of a two-player game. It is up to you to decide whether to use minimax or negamax trees.

Advanced Techniques

Let’s say that we use a minimax tree to do some “look-aheads”. How many elements will we have to look at? Let’s look at a 15×17 grid. During the early stage of the game, both players will have 15 possible columns to place their discs, therefore looking ahead one step is 15 nodes to evaluate. Looking ahead 2 steps is 152 nodes to evaluate. By the time you get to the 5th step, you will be looking at three-quarters of a million nodes. This is a lot of nodes!

However, there is a technique called Alpha-Beta Pruning which can drastically reduce the number of nodes that need evaluation. If you want to get ahead on the scoreboard, you might need to implement this technique.

Example of it can be found here: http://inst.eecs.berkeley.edu/~cs61b/fa14/ta-materials/apps/ab_tree_practice/

8

Help

As with previous assignments, your tutors are not allowed to look at your code. However, feel free to bounce ideas off your classmates while keeping in mind that viewing each other’s code is strictly forbidden.

Technical Help

For this assignment, we have used a couple of external libraries. However, to simplify things for you, we also created a Stack package which makes things a lot simpler and more streamlined.

When running the program for the first time, you need to setup the Stack environment:

stack setup

For any subsequent runs, you do not have to do this again. If you want to compile your program, use the following command:

stack build

If you want to run the program with default options, simply do:

stack exec ConnectX

9

Frequently Asked Questions

1. What do I do if I get Failed to load interface for ‘Data.Universe.Helpers’
   You are getting this error message because you haven’t installed the relevant packages in

   cabal. There are two ways around this.

   • Instead of loading the modules directly, use stack. At the root directory (where the .cabal file is), type in stack repl. This will load all the modules, and just do :l <Module Name> in order to load that particular module.
   • Install the packages in cabal with the following commands: cabal install universe-base split
2. My GitLab repo is stuck on “Forking in progress”

   This is the issue of CECS’s GitLab server. Go to Settings, scroll down to the bottom, remove the repository entirely and fork it again.

3. Failed to load interface for ‘Data.Board’
   This is likely due to you loading Data.Board module at the wrong working directory. If

   you want to load the modules manually, make sure you are inside the src folder.

   Then you can load the module by ghci -Wall Data/Board.hs. Likewise for other modules.

4. BlueBot failed to make a move in time

   This is due to one of two reasons:
   • Your bot keeps selecting an invalid move

   • Your bot ran out of time with a LookAhead value of 1. You can check this by increasing the default timeout.

5. My pipeline isn’t working.
   Please post under [Piazza @541](https://piazza.com/class/j53tz2pnw591bb?cid=541).

10

IntelliJ – New Project

1. Open IntelliJ
2. Top left corner -> File -> New -> Project
3. Select Haskell on the left, and click Next
4. Select “Build with cabal”, and click Next
5. Deselect initialise cabal package (This step is crucial.) 6. Give your project a name (e.g. comp1100-ass03)

Git – Fork the repository

1. Go to https://gitlab.cecs.anu.edu.au/comp1100/ass03.git
2. Click on “Fork”, and select your user.
3. Give your tutor and Steven X. Han Reporter access to your new repository.
4. Go to IntelliJ terminal.
5. Initialise the folder as a git repository (Make sure you are in the project you created earlier.

   Likely in ~/IdeaProjects/comp1100-ass03)

6. Add your assignment 3 repository as the origin
7. Add comp1100 assignment 3 repository as the upstream
8. Pull the origin remote to your local computer

11

Report

We require that you write a report which fully explains your solution to the assignment. Below are some of the things you should keep in mind while writing your report:

• This is a technical document. Therefore, only technical details should be discussed in it.

• Your audience is your tutor, and they know and understand how a Minimax tree works. They also know the definition of foldl, and the inner workings of most commonly used Haskell functions.

• Discuss the reasons behind your functions. This does not mean describe your functions! For example, a function might utilise the Negamax tree instead of the Minimax tree, you should have a thorough explanation of the reasons behind this decision.
• Discuss the efficiency of your program. This assignment is heavily reliant on algorithmic efficiency, thus efficiency should be extensively covered in your report. How many LookAhead can your function handle within five seconds?
• Tell us the implementations you might do in the future. While not necessary, this is preferred. This shows us your understanding of the problem and ability to think critically. What might your ConnectX 2.0 do?
• Explain anything that the reader might find confusing. If you you think your tutor cannot figure something out within a few seconds, then it is a good idea to explain it in your report.
• Avoid spelling or grammatical errors. Utilise the spelling and grammar checking tools.

12

Marks

The total mark for this assignment is 100. It is split among code, report, and testing with the following ratio:

• Code: 75% • Report: 20% • Testing: 5%

The following description is an indication only. Please note that the rank of your player does not contribute to your overall marks. The rank descriptions below are where your player is expected to be if you implemented the techniques correctly.

Fail

Below are some of the reasons which will lead to fail:

• There is no report.
• The code does not compile.
• Strategy is at the same level of complexity as making a random move (this includes the

  leftmost legal move, rightmost legal move, or any strategy that is not dependent on future outcomes)

  Pass

  • The code compiles with some warnings (with -Wall flag).
  • The report does a basic job at explaining the strategies implemented. • The strategy performs consistently better than making a random move. • The code only works for a 11×10 connect five game.

  Credit

• The code compiles with some warnings (with -Wall flag).
• The report explains the implemented strategies well and is at the expected standard of a

  technical report (refer to Report section).

• The strategy involves the usage of a Minimax (or Negamax) tree. There are some prob-

  lems with the implementation. However, the conceptual understanding is justified and

  demonstrated in your code.

• The strategy performs significantly better than making a random move. The rank of your

  player should be in the middle third of all players.

• The code works for a board of any size with any streak settings.

13

Distinction

• The code compiles with no warnings (with -Wall flag).
• The report demonstrates the understanding of the problem and the implemented strategies

  excellently. The report also shows significant critical thinking. The report describes all relevant information succinctly. The efficiency of the program is properly and correctly discussed in the report.

• The code involves the correct implementation of a Minimax (or Negamax) tree. The code style is very good and the code is easy to read and understand. There is some optimisation of efficiency.
• The rank of your player should be above the average of all players.
• The code works for a board of any size with any streak settings.

  High Distinction

• The code compiles with no warnings (with -Wall flag).
• The report demonstrates the understanding of the problem and the implemented strategies

  excellently. Excellent critical thinking skills, as well as technical document writing skills, are demonstrated. The report is succinct but should cover all aspects of the problem. The discussion of efficiency is correct and thorough. Reasons for potential bottlenecks are discussed and valid future implementations are proposed.

• The strategy involves correct advanced techniques of tree pruning and optimisation tech- niques. The code has excellent style. The efficiency is extensively considered and optimised for.
• The rank of your player should be in the top 25.
• The code works for a board of any size with any streak settings.

14

Submission Checklist

Preferably 24 hours prior to the due time of the assignment (9AM, 23 October 2017), you should make sure that:

• you have fully read and understood the entire specification of the assignment
• your work is pushed to GitLab and your repository is shared with your tutor and Steven

  X. Han with Reporter permission.
  – Do not email your tutor and Steven to ask if they can see your repository. If you

  can see it on GitLab, and it is shared with your tutor (which you can check through

  Settings -> Members) with Reporter access, they will be able to see it.

• the relevant Pipeline tests are passed.
• your program works on the lab machines – if the program does not work on the lab machines,

  it will not work on the tournament server and during marking.

• the report is in PDF format, located at the root of your assignment repository and named

  Report.pdf. Otherwise, it may not be marked.

• the completed assignment cover sheet is not in a separate document, but the first page of

  your report.

15

Tournament

Many of you have heard of the Kalaha tournament that happened in the past 5 years. We are very lucky to have the founder of the Kalaha tournament server Jan Zimmer on board to run a similar style tournament for our ConnectX game.

The server verses players by a system similar to a Swiss Tournament. This means that it is non-eliminating, yet ensures a quick estimation of a player’s rank after submission. Players with a smaller number of matches will be prioritised and versed against a player of similar rank. Eventually, all players will compete against everyone else.

Every time you push to your GitLab repository, and the pipelines are passed, all of your previous results will be deleted and you will appear as a new player and be pitted against other players. You can submit your player at any time, even when your player is currently playing a match on the server.

Your player will only be submitted to the tournament server if all pipeline tests are passed.

Please note that only the Bot/Blue.hs file will be submitted to the tournament server.

As with assignment 2, you will be anonymised. However, this time you will receive a number that will be your identifier in the tournament. Feel free to share this with your friends.

All pages are automatically updated every 15 seconds, with programs running continuously. Refreshing the web page more often than this will not give you any extra information.

Tournament Matrix

The ConnectX server status is displayed in a few different ways, but the most common way to view the tournament status is via the Tournament Matrix. This matrix displays the match status of the top 40 players, sorted by their ranks. Therefore, the player in the first row is currently the first in the tournament. The entry in the matrix indicates the outcome of the game between the player in the row of the matrix and the player in the column of the matrix. You can click on a player number and the current status of the player will appear. You can also click on an individual match to see the full transcript for that match. Matches that are currently running or in an error state do not provide a current transcript.

Entry keys:

• – Win
• – Tie
• – Loss
• – Running • – Error

16

Stages of the tournament matrix Early & Middle

During the early and middle stage of the tournament, most matches are played amongst players of similar ranks. As students submit their players quite frequently, and their players usually change ranks after every match, there is always a chain of matches were players to move to a new rank and then verse a player close to this new rank. Therefore the active games are clustered around the diagonal for the most of the tournament.

Figure 3: Early Stage

17

Later Stage

During the later stage, players will begin to verse more and more players of different ranks. You can now expect the matrix to fill up slowly.

Figure 4: Later Stage

18

Steady State

Eventually, the matrix will form a steady state (this will happen after the submission is closed). The matrix will be completely filled with every player having matched against everyone else.

Figure 5: Steady State

19

Player Profile

By clicking on a player number you can view the player profile of any particular player. This will display all the matches that player has played, and the results of them.

Figure 6: Player Profile

20

Ranks & Statistics

The complete list of all players and their statistics can be viewed on the overall ranking page.

Figure 7: Overall Ranking

21

Prepared by Steven X. Han with assistance from Katya Inspired by Kalaha assignment by Uwe Zimmer Tournament developed and maintained by Jan Zimmer

22