CS代写 COMP1100 Assignment 3

# COMP1100 Assignment 3

In this assignment, you will develop a [software
agent](https://en.wikipedia.org/wiki/Software_agent) or *AI bot* that

plays “Consecutive Dots”. Consecutive dots is similar to a game of [Connect Four](https://en.wikipedia.org/wiki/Connect_Four), however connections that *wrap around* the board are allowed.

{:.msg-info}
This assignment is worth 15% of your final grade.

{:.msg-warn}
**Deadline**: Friday 28th October, 2022, at 11:00pm Canberra time _sharp_

## Overview of Tasks

This assignment is marked out of 100 for COMP1100 students.

{:.msg-warn}
As with assignment 2, code that does not compile will be
penalised heavily. This means that **both** the commands `cabal v2-run game`
(with sensible arguments) **and** `cabal v2-test` **must** run without
errors. If **either** command fails with an error, a significant mark deduction
will be applied. If you have a partial solution that you cannot get
working, you should comment it out and write an additional comment
directing your tutor’s attention to it. You are also welcome to ask questions
about error messages in drop-ins or on Piazza.

## Getting Started

Fork the assignment repository and clone it to your computer,
following the same steps as in [Lab 2]({% link _labs/02.md %}). The
assignment repository is at
.

## Overview of the Game

Consecutive Dots is a two-player strategy board-game designed to avoid any
potential trademark infringement with a popular toy company.
The version we will be playing has players vying to be the first to get
**four consecutive tokens in any direction**. If a consecutive run of tokens
reaches the end of the board, it may **continue** through the opposite side,
as though the board took the shape of a cylinder (for example,
[Blue’s win here]({% link assignments/03/BlueWinsWrapRow.png%}),
or [Red’s win here]({% link assignments/03/RedWinsWrapDiagonal.png %})).

* The game starts with an empty $$8\times 7$$ board with the following starting
configuration: [Initial State]({% link assignments/03/InitialBoard.png %}).

* The blue token is considered player 1 and always moves first.
The red token is considered player 2 and always moves second.

* Players take turns choosing a column to “drop” their token into.
Once dropped, the token falls until it reaches the bottom of the board,
or an existing token of either colour. This token then takes up the slot
in the next available row.

* If a column is full of tokens (the space at the top of that column is full)
then no moves may be made in that column. The player must select an
alternative column to drop their token. If no free columns exist and no
winner has been found then **the game ends in a draw**.

* Otherwise if the player’s dropped token results in a run of 4 connected tokens
in any direction (up, down, top-left to bottom-right diagonal,
or bottom-left to top-right diagonal), even if the direction wraps around
the board edge, then **that player wins the game.
The other player loses the game.**

## Overview of the Repository

Most of your code will be written in `src/AI.hs`, but you will also
need to write tests in `src/AITests.hs`.

### Other Files

* `src/ConsecutiveDots.hs` implements the rules for Consecutive Dots.
You should read through this file and familiarise yourself with the
data declarations and the type signatures of the functions in it, as you
will use some of these to analyse the game states. You do not need
to understand how the functions in this file works in detail.

* `src/ConsecutiveDotsTests.hs` implements some unit tests for the game. You
are welcome to read through it.

* `src/AITests.hs` is an empty file for you to write tests for your

* `src/Testing.hs` is a simple test framework similar to the one in
Assignment 2. However, it has been extended so that you can group
related tests together for clarity.

* `src/Dragons` contains all the other code that makes the framework
go. You do not need to read or understand anything in this
directory. Here be dragons! (On medieval maps they drew pictures of
dragons or sea monsters over uncharted areas.) The code in those
files is beyond the areas of Haskell which this course explores.

* `Setup.hs` tells cabal that this is a normal package with no unusual
build steps. Some complex packages (that we will not see in this
course) need to put more complex code here. You are not required to
understand it.

* `comp1100-assignment3.cabal` tells the cabal build tool how to build
your assignment. We will discuss how to use `cabal` below.

* `.ghcid` tells the `ghcid` tool which command to run, which is what
supplies VSCodium with error highlighting that automatically updates
when you save a file.

* `.gitignore` tells `git` which files it should not put into version
control. These are often generated files, so it doesn’t make sense
to place them under version control.

## Overview of Cabal

As before, we are using the `cabal` tool to build the assignment
code. The commands provided are very similar to last time:

* `cabal v2-build`: Compile your assignment.

* `cabal v2-run game`: Build your assignment (if necessary), and run
the test program. We discuss the test program in detail below, as
there are a number of ways to launch it.

* `cabal repl comp1100-assignment3`: Run the GHCi interpreter over
your project so you can test functions interactively.

* `cabal v2-test`: Build and run the tests. This assignment is set up
to run a unit test suite, and as with Assignment 2 you will be
writing tests. The unit tests will abort on the first failure, or
the first call to a function that is `undefined`.

* `cabal v2-haddock`: Generate documentation in HTML format, which you
can read with a web browser. This might be a nice way to read a
summary of the game module, but it also documents the `Dragons`
modules which you can safely ignore.

{:.msg-info}
You should execute these cabal commands in the **top-level directory**
of your project: `comp1100-assignment3` (i.e., the directory you are
in when you launch a terminal from VSCodium).

## Overview of the Test Program

To run the test program, you need to provide it with command line
arguments that tell it who is playing. This command will let you play
against the current `”default”` AI bot.
Before you replace this with your own bot, the default will be
`firstLegalMove` playing with COMP1100 rules:

cabal v2-run game — –p1 human –p2 ai

using `ai` to get the default AI is part of how we mark
your assignment, so it is **vital** that you update your
default bot to be whatever you want to be marked!

To play with a differently named AI, say, `”greedy”`, use:

cabal v2-run game — –p1 human –p2 ai:greedy

In general, the command to run the game looks like this:

cabal v2-run game — ARGS

Replace `ARGS` with a collection of arguments from the following list:

* `–timeout DURATION`: Change the amount of time (in decimal seconds)
that AI functions are given to think of a move (default = `4.0`).
You may want to set this to a smaller number when testing your program,
so that things run faster.

* `–height LENGTH` and `–width LENGTH`: Alter the size of the board
to the given value. The default values are 8 and 7 respectively, and your
implementations will only be tested on that size.
Your AI does not need to work for differently sized boards, but you may
want to test it on simpler boards if it does!

* `–n LENGTH` can change the number of Consecutive Dots needed to win the game.
setting this to 1 will result in a very boring game, but numbers other than
4 may be useful to more clearly test whether your AI is making the right decisions.

* `–debug-lookahead`: When an AI is done thinking, print out how many
moves ahead it considered, and the candidate move it came up with at
each level of lookahead. The first item in the printed list is the
move it came up with at lookahead 1, the second item is the move it
came up with at lookahead 2, and so on.

* `–ui codeworld`: Show the game using CodeWorld. This is the default
user interface. Use your web browser to play the game, as in
previous assignments. Unlike the codeworld programs in previous
assignments, you must terminate the program with `Ctrl-C` and
restart it if you want to restart your game.

* `–ui text`: Show the game in the terminal.

* `–ui json`: Run a non-interactive game (i.e., AI *vs* AI, or AI *vs*
network), and output a report of the game in JSON format. You
probably won’t have a use for this, but it’s documented here for
completeness.

* `–host PORT`: Listen for a network connection on `PORT`. You only
need this for network play (see below).

* `–connect HOST:PORT`: Connect to someone else’s game. You only need
this for network play (see below).

* `–p1 PLAYER`: Specify the white player. Required.

* `–p2 PLAYER`: Specify the black player. Required.

The `PLAYER` parameters describe who is playing, and can take one of
the following forms:

### Network Play

{:.msg-warn}
Network play is provided in the hope that it will be useful, but we
are unable to provide support for this feature, or diagnose problems
related to tunnelling network connections between computers.

The assignment framework supports network play, so that you can test
agents against each other without sharing code. One machine must
_host_ the game, and the other machine must _connect_ to the game. In
the example below, machine A hosts a game on port 5000 with the agent
`crashOverride` as player 1, then machine B connects to the game,
providing the AI `chinook` as player 2:

# On Machine A:
cabal v2-run game — –host 5000 –p1 ai:crashOverride –p2 network

# On Machine B (you’ll need Machine A’s external IP address somehow):
cabal v2-run game — –connect 198.51.100.66:5000 –p1 network –p2 ai:chinook

{:.msg-info}
Under the bonnet, the network code makes a single TCP connection, and
moves are sent over the network in JSON. You will need to set up your
modem/router to forward connections to the machine running your
assignment. A service like [ngrok](https://ngrok.com/) may help, but
as previously mentioned we are unable to provide any support for this

## Main Task: Consecutive Dots AI (COMP1100: 55 Marks)

Implement an AI (of type `AIFunc`, defined in `src/AI.hs`). There is a
list called `ais` in that file, and we will mark the AI you call
`”default”` in that list. This list is also where the framework looks
when it tries to load an AI by name.

We will test your AI’s performance by comparing it to implementations
written by course staff, using a variety of standard approaches. Its
performance against these AIs will form a large part of the marks for
this Task.

{:.msg-warn}
It is **vital** that you indicate one AI as `”default”`, otherwise we
will not know which one to mark. To indicate an AI as `”default”`,
you must have a `(String, AIFunc)` pair in the `ais` list of AIs
in `src/AI.hs` where the `String` is **precisely** `”default”`.

## Understanding the `AIFunc` Type

The `AIFunc` type has two constructors, depending on whether you are
implementing a simple AI that looks only at the current state, or a
more complicated AI that performs look-ahead.

The `NoLookahead` constructor takes as its argument a function of type
`GameState -> Move`. That is, the function you provide should look at
the current state of the game and return the move to play. This
constructor is intended for very simple AIs that do not look ahead in
the game tree. As such, this function should never run for more than
a moment at a time, but nevertheless, it is also subject to the timeout
of 4 seconds.

The `WithLookahead` constructor takes as its argument a function of
type `GameState -> Int -> Move`. The `Int` parameter may be used to
represent how many steps you should try to look ahead in the game
tree. The assignment framework will call your function over and over,
with look-ahead `1`, then `2`, then `3`, etc., until it runs out of
time. The framework will take the result of the most recent successful
function call as your AI’s best move. If your AI does not return a
move in time, the program will stop with an error.

### Getting Started

This is a very open-ended task, and it will probably help if you build
up your solution a little at a time. We suggest some approaches below.

Your AI should inspect the `Turn` within the `Game` to see whose turn
it is. You may call `error` if the `Turn` is `GameOver` — your AI
should never be called on a finished game. Your AI can then use the
`Player` value and `otherPlayer` function to work out how to evaluate
the board.

A `Move` in Consecutive Dots corresponds to the index of the column in
which you intend to drop a piece. If you try to apply a move that corresponds
to a column that is already full, `applyMove` will return `Nothing`.

{:.msg-info}
You may also assume that we will only ever call your AI if there is a
legal move it can make. In particular, this means that we will not
deduct marks for assuming that a list of legal moves is non-empty
(e.g., you used the `head` function). Note that gratuitous use of
`head` and `tail` is still poor style. Note also that, in general, you cannot
make this assumption about `GameStates` you have generated
within your AI function.

### First Legal Move

The simplest AI you can build is one that makes the first legal move
it can. We have provided this for you, so you can see what a simple
`AI` looks like.

### Interlude: Heuristics

Heuristic functions are discussed in the lecture on game trees. We
expect the quality of your heuristic function—how accurately it
scores game states—to have a large impact on how well your AI
performs. There is no obvious heuristic for this game, so you will need
to get creative, or research heuristics that have been used in similar games.
If you take the latter approach, be sure to cite *all* the sources that you access.

### Greedy Strategy

“Greedy strategies” are the class of strategies that make moves that
provide the greatest _immediate_ advantage. In the context of this
game, it means always making the move that will give it the greatest
increase in heuristic. Try writing a heuristic and a greedy
strategy, and see whether it beats our “first legal move” AI.

### Interlude: Game Trees

To make your AI smarter, it is a good idea for it to look into the
future and consider responses to its moves, its responses to those
responses, and so on. The lecture on game trees may help you here.

### Minimax

Greedy strategies can often miss opportunities that need some
planning, and get tricked into silly traps by smarter opponents. The
Minimax Algorithm was discussed in the lecture on game trees and will
likely give better performance than a greedy strategy.

### Pruning

Once you have Minimax working, you may find that your AI exploring a
number of options that cannot possibly influence the result. Cutting
off branches of the search space early is called _pruning_, and one
effective method of pruning is called **alpha-beta pruning** as
discussed in lectures. Good pruning may allow your search to explore
deeper within the time limit it has to make its move.

### Other Hints

* There are four main ways your AI can be made smarter:

– Look-ahead: If your function runs efficiently, it can see further
into the future before it runs out of time. The more moves into
the future it looks, the more likely it will find good moves that
are not immediately obvious. Example: at 1 level of look-ahead, a
move may let you threaten a simple win, but at deeper look-ahead
you might see that it leaves you open to a large “forking” threat.

– Heuristic: You will not have time to look all the way to the end
of every possible game. Your heuristic function guesses how good a
`Game` is for each player. If your heuristic is accurate, it will
correctly identify strong and weak states.

– Search Strategy: This determines how your AI decides which
heuristic state to aim for. Greedy strategies look for the best
state they can (according to the heuristic) and move towards that
state. More sophisticated strategies like Minimax consider the
opponent’s moves when planning.

– Pruning: if you can discard parts of the game tree without
considering them in detail, you can process game trees faster and
achieve a deeper look-ahead in the allotted running
time. Alpha-beta pruning is one example; there are others.

* Choosing a good heuristic function is very important, as it gives
your AI a way to value its position that is smarter than just
looking to see if the game is won or lost. Perhaps you might find that some squares
are more valuable than others, when it comes to winning games, and
so your AI should value them more highly.

* Do not try to do everything at once. This does not work in
production code and often does not work in assignment code
either. Get something working, then take your improved understanding
of the problem to the more complex algorithms.

* As you refine your bots, test them against each other to see whether
your changes are actually an improvement.

## Unit Tests (10 Marks)

As with Assignment 2, you will be expected to write unit tests to
convince yourself that your code is correct. The testing code has been
extended from last time—`src/Testing.hs` now allows you to group
tests into a tree structure. As before, you run the tests using `cabal

### Your Task

Add tests to `src/AITests.hs` to test your AI.

#### Hints

* Most of the hints from Assignment 2 apply here. Re-read those.

* If a function is giving you an unexpected result, try breaking it
into parts and writing tests for each part. This helps you isolate
the incorrect parts, and gives you smaller functions to fix.

* If your function has subtle details that need to be correct, think
about writing tests to ensure those details do not get missed as you
work on your code.

## Coding Style (10 Marks)

As you write increasingly complex code, it is increasingly important
that the code remains readable. This saves wasted effort understanding
messy code, which makes it easier to think about the problem and your
solution to it.

If you wish, you know how, and you have a good reason,
you may split your code into multiple modules. However this is not a
requirement, and you will never be penalised for not doing so.

You **MUST NOT** edit any of the files in the framework (with the
obvious exceptions of `AI.hs` and `AITests.hs` ).

### Your Task

Ensure that your code is written in good Haskell style.

## Technical Report (COMP1100: 25 Marks)

You are to write a concise [technical report]({% link
_resources/08-reports.md %}) about your assignment.

The **maximum word count** is **1500** words. This is a *limit*, not a
*quota*; concise presentation is a virtue.

{:.msg-warn}
Once again: Th

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts