共计 15077 个字符，预计需要花费 38 分钟才能阅读完成。
FIT2102 Programming Paradigms 2019
Assignment 2: Functional Programming in Haskell
Due Date: Friday 25th October, 11:55pm
Weighting: 20% of your final mark for the unit
Task Description:
You will create an autonomous player for the card game“Hearts.” You will do this by filling in the
undefined playCard function in the Player.hs file that you receive in the code bundle.
Hearts is an “evasion-type” trick-taking playing card game for four players, […] players
avoid winning certain penalty cards in tricks, usually by avoiding winning tricks
altogether.
— Wikipedia
Your goal in this assignment is to write a player for the Hearts game. As in the previous
assignment, the focus will be on having functional code rather than implementing AlphaGo.
However, marks will be awarded for advanced strategies.
Submission Instructions:
- You need to submit your Player.hs, as a single file, to the uploader. It is a webform
where you can submit your player file, to be run in a continuous tournament against all
other submissions (see“The Tournament”, below).
- You need to submit your code bundle — whatever extra players you may have, extra
libraries you wrote — to Moodle. To do so, zip up your whole code directory using the
following format:
A .zip file named studentNo_name.zip which should extract to a folder named
studentNo_name
We will deduct up to ten (10) marks to people not respecting this convention.
The template Player code (which you have to implement) is in staticgame/Player.hs. All
code for your player must be in this one file. You may include multiple players (each in their
own files) if you think they are interesting, and you may have other code files (e. g., as per the
“getting an HD section below”), but all the files that you have edited or added must be clearly
identified in the top-level ChangeLog.md.
NOTE: The uploader is separate from and does not replace the Moodle submission.
The Game
The game of Hearts is a trick-taking game where the goal to score as few points as possible. All
cards in the Hearts are worth one point, and the Queen of Spade is worth 13. Your task will be
to implement a simple AI to beat other players (students and staff) at this game.
There will be two versions of the game:
- A two-player version, which will be used to assess the strength of your player. This
version will use calibrated opponents and can be seen as a test.
- An online tournament where your player will be pitted against other students’AIs in
four-player matches – Coming Soon...
To play the game with your AI, you will need to implement a function called playFunc which
will be given a number of parameters upon which you will need to act and return the card you
believe will lead to victory. An important component of the game setup is that you will be
allowed to have a form of memory.
Memory, in this case, will be entirely determined by you. The game will simply pass you
information pertaining to the current trick: your hand; cards played by players before you; and
the previous trick: the complete set of cards played at the previous trick and your memory.
The game you will play will follow most of the classic rules of Hearts. This game is very popular
as it is easy to learn and play, thus many online versions are available if you want to train. Do
note, though, that most of them usually vary a little, so take care to read the rules carefully.
At the core of the game of Hearts are the point cards: all cards in Hearts and the Queen of
Spade. The goal of the game is to score as few points as possible. An alternative exists
though: if a player manages to take all point cards, she gets 0 points and every other player
gets 26 points (the maximum).
At the end of each round, when players have played all the cards in their hands, we tally the
points in every trick taken by each player. That is, we sum the point cards they won.
The game goes on until at least one player has scored more than 100 points and there is
exactly one player with the lowest score. The player with the lowest score is the winner.
Scoring system
Counting points in Hearts is done as follows:
● Point cards: Each Heart is worth 1 point, the Queen of Spades is worth 13 points.
● Hand: At the end of each hand (players have played all their cards), each player
receives the amount of points in the tricks they won.
● Game: The game stops when a player has reached 100 points and exactly one other
has the lowest score; the latter is the winner.
Rules of play
The rules of Hearts we will use are as follows:
● Reneging: Each turn starts with a player playing a single card, the suit of which
determines the suit of the trick. Other players must follow suit (play cards in the same
suit) if they are able to; if they do not have any cards in that suit, they may discard any
card of their choosing.
● Bleeding: No point card may be played during the first trick unless the player has no
other choice.
● Leading: The player with the Two of Clubs leads (starts) the first trick with this card.
● Breaking: No player may start a trick with a Heart before any has been played, unless
they have no other choice.
● Shooting the Moon: In case a player took all the point cards, she scores 0 points and
the other players all score 26 points.
Deliverable
You will submit a .zip file named studentNo_name.zip which should extract to a folder
named studentNo_name
Your task is to write a Player for Hearts which will implement the following function:
playCard :: PlayFunc – play a card from your hand during a trick
Look carefully at the type of PlayFunc defined in src/Hearts/Types.hs. Your player must
pass the tests to be eligible to run in the tournament. Your implementation must respect the
rules explained above. Also, your code must compile without warnings.
You will have two tasks during the assignment period:
- Upload your player to the tournament so you can evaluate your player’s performance.
- Upload your Player.hs file to Moodle before Friday 18th October 11:55pm.
Before uploading your player, please check that the following run:
● $ stack test
This will run the tests on your player, making sure your functions respect the playing
rules. If your code does not pass the tests, you will not be able to access the
tournament.
The code provided uses the Safe pragma to make sure the code you use is okay to run. It is 1
also compiled with the -Werror flag which means that all warnings will throw errors and prevent
your code from compiling. So do make sure you run the test suite before you upload your
player.
Memory
An important concept during a game is memory. In this implementation, you can decide what
information you want to save between turns, the only condition is it needs to be converted to a
String. This is shown in the type of the play function:
— | Play function type.
— Cards are added to each trick from the front. Thus, the
— first-played card in a trick is the last in its list of cards,
— the lead suit is the suit of the first-played card in the
— trick. A play is only legal if it does not renege on the lead
— suit. That is, the player must play a card of the suit led if
— they have it. The winner is the highest trump card (if any
— were legally played), or, if no trumps were played, the
— highest card in the lead suit.
type PlayFunc
= PlayerId – ^ this player’s Id so they can identify
— themselves in the bids and tricks
-> [Card] – ^ the player’s current hand
-> [(Card, PlayerId)]
— ^ cards played in the current trick, i.e., previous
— players cards for this trick
-> Maybe ([(Card, PlayerId)], String)
— ^ ([all the cards played in the previous trick], “memory”)
— in the first trick, this will be Nothing, then it will
— report the cards played and the memory returned by the player
-> (Card, String)
— ^ should return: (chosen Card, “new memory”); the memory is
— a string
The memory is the last parameter to the function, of type:
Maybe (cards from the previous trick, previous memory).
1 More info at SafeHaskell, but this should not hinder your work.
In the first trick, this will be Nothing. Good use of the memory is one of the key features we will
evaluate.
Type ambiguity
One thing to note, the game code uses a number of functions with the same name. While this is
not an issue in most cases as the compiler can disambiguate using types, this can lead to
spurious error messages if you are not careful. For example:
error:
Ambiguous occurrence‘tricks’
It could refer to either the field‘tricks’,
imported from‘Hearts.Types’at …
(and originally defined at …/Hearts/Types.hs:52:3-8)
or the field‘tricks’, …
To avoid this error, you need to explicitly define the type of either the variable or the function:
tricks (hr :: HandResult)
— or
map (tricks :: HandResult -> [Trick]) results
Multiple players
If you want to test multiple players, you can use the code at app/Main.hs. To do so, you will
need to create a new file with the name of your player and provide the proper header:
E. g., file: StrongPlayer.hs
module StrongPlayer where
— add your code
Remember to switch the module name back to Player for the one you decide to upload to the
server.
Extra functions
If you write additional functions for your Player which you wish to test in GHCi, for example, you
need to export them. Like so:
module Player (
playCard,
makeBid,
splitBySuit
) where
The Tournament
We will run a tournament online based on the code provided. Except the interface, this will be
the same game.
When you submit your player, we will run the test suite on it (stack test). The tests on the server
will be slightly longer, your player will compete in:
- A 1v1 against a basic player.
- A 1v1 against the minmax player.
- A 1v1 against the advanced player.
- A free-for-all, four player match against all the players above.
After the tests have run successfully, your player will join the tournament by immediately playing
ten games against selected opponents. After that, it will be selected at random to play against
newcomers.
The testing and running the tournament can be resource intensive and the server is a fairly slow
machine. If you do not get immediate feedback, especially during the last days, no need to
spam the Upload button, wait a bit.
Reminder: Your rank in the tournament will not have a direct impact on your mark. A
high-performing player with spaghetti code will be graded lower than an average, well-written
player.
The server for the course is at https://fit2102.monash with the following pages:
● The uploader: after logging in, this page will allow you to upload your code and compete
in the tournament.
● The ladder: this page will display the scores of the last tournament run.
● The docs: documentation about the assignment’s code.
Once you upload your player, you will see two links on the page:
● home.php: shows your current ranking, last upload, and previous games played.
● status.php: shows the status of your current upload.
Furthermore, you can inspect your games by clicking on their number.
Game AI
The goal of this assignment is not for you to develop an AI which can compete with openAI or
AlphaGo. The emphasis should be on code quality and applying functional concepts. Below,
you can find a list of standard AI algorithms, ranked roughly by implementation difficulty. It is
possible to receive an HD with a well implemented heuristic player that meets the other HD
criteria. However, students who research and successfully implement the latter strategies will
be rewarded.
● Naïve AI: tries to play its best card given the current state of the game, you can start by
implementing one to make sure you respect the game’s rules.
● Heuristic player: will save additional information about the game being played to
enhance its decision at each turn.
● Probabilistic player: will make use of probabilities to determine which cards have the
highest chance of winning the game (not the trick).
● MinMax: tries to minimise the maximum loss of a player by building a tree of possible 2
moves and playing against itself. This method was developed for two-player, zero-sum
game with perfect information. In this context, it will be useful in the two-player version 3
but will require modification in the four-player context.
● Monte Carlo Tree Search: is the fusion between search algorithms such as minmax 4
and using probabilities to determine the branching in the search tree. Will also make use
of a simulation phase to explore deeper.
Assessment
The assessment for this assignment will be in three parts:
- Code quality, documentation and comments (30 marks)
- Functional programming (40 marks)
- Performance (30 marks)
Code quality, documentation and comments
Documentation and comments
You are required to provide a file-level comment, function comments and line comments where
necessary. The most important part of commenting is to provide information, not to describe the
code.
● File-level doc: You should provide an overview of your code and explain your rationale
(how you decided to play) in a block comment at the top of the file. Think of this as a
technical report: you want to summarise the workings of the code and highlight the
interesting parts.
2 https://en.wikipedia.org/wiki…
3 Such as chess, checkers, or more exotic ones.
4 Difficult, implementing such a strategy would qualify as an extension.
● Function comments: These comments should be situated above the type declaration of
the function they refer to. They should give the manual of the function, explaining how it
works — and not simply describing what each line/function does.
● Line comments: In some cases, your code might be hard to read, or the action you do
is counter-intuitive; in those cases, you can add a line comment to add information.
Code quality
The quality of your code is a measure of how easy it is for us to understand it. This is a bit more
than a simple style guide but you can use the following as guidelines:
- Keep a reasonable length for lines of code.
- Do not nest control structures (if, where, case, let, etc.).
- Use point-free notation where appropriate. 5
- Write small reusable functions.
- Have clear, informative variable and function names.
Functional programming
Your use of FP concepts will be the main evaluation criterion for your assignment. Your code
needs to use, efficiently, concepts from the course. You can think of this as a two-part marking
scheme:
- Apply concepts from the course. The important thing here is that you need to actually
use them somewhere. For example, defining a new type and its Monad instance, but
then never actually needing to use it will not give you marks. 6
- Have general code. Because of the tournament format, you should try to have code that
can deal with two- and four-player games using the same functions instead of writing two
separate blocks of code.
Finally, make good use of the memory, not only in what you save but in how you define and use
it. In a way, this goes hand-in-hand with the two points above; you will have to have a non-trivial
implementation and be able to use it in the two- and four-player contexts.
You can use the following as a non-exhaustive list of FP concepts, but beware not to affect your
code quality:
- Leverage higher-order functions.
- Use function composition.
- Have custom types and typeclasses.
5 Rule of thumb: if you start having double points, stop.
6 Note: using bind (>>=) for the sake of“using the Monad”when it is not needed will not count
as efficient usage.
Extensions
Below is a non-exhaustive list of possible extensions. As with code quality, your implementation
needs to be non-trivial and you need to use it to qualify.
● Using the tournament server logs to improve, or learn, your strategy.
● Using a form of State monad.
● Creating your own RNG. 7
Performance
The important thing in this assignment is: your rank in the tournament will not influence your
mark. The performance of your player will be evaluated automatically by the test suite. You get
10 marks for defeating each:
- The basic player, only tries to play a valid move.
- The minmax player, which uses a simple implementation of the min-max algorithm.
- The advanced player, which will use a more advanced search strategy.
Marking rubric
Below are the guidelines for the different grades for this assignment. This does not mean that
you automatically get the grade if you fulfill them, rather, this is what a good implementation
would achieve.
● Pass: The code compiles and your players respects the rules of the game.
● Credit: In addition to the criteria for a Pass, the game implements some strategy to
choose cards that make it stronger than a random card selecting player.
● Distinction: The code is well structured, efficient, and uses some advanced concepts
from the course (higher order functions, function composition, monadic operations, etc.).
The code should use the memory string parameter of the playFunc to inform card choice
based on what has already been played.
● High Distinction: The code does not contain any excess parts, the player can defeat all
training opponents, it implements at least one extension, and the commenting supports
the submission. The code uses advanced concepts like state monad and parser
combinators (e.g. to parse the memory string).
You can expect a higher mark with an average level AI with elegant code that demonstrates
functional concepts covered in lectures, rather than a high-performing AI with poorly structured
spaghetti code.
7 Hint: you can use the shuffled deck as a source of entropy.
Outstanding submissions, common mistakes and complete disasters may be discussed in class
with your name removed.
Plagiarism
We will be checking your code against the rest of the class, and the internet, using a plagiarism
checker. Monash applies strict penalties to students who are found to have committed
plagiarism.
Any plagiarism will lead to a 0 mark for the assignment and will be investigated by the staff.
There is a zero-tolerance policy in place at Monash. So be careful and report any collaboration
with other students or other sources.
更多可加 V 讨论
V：woshibb55
