Skip navigation

Programming as Problem Solving (including Advanced) [2019 S1]
ANU College of Engineering & Computer Science


Programming as Problem Solving (including Advanced) [2019 S1]
ANU College of Engineering & Computer Science
Search query
•Search ANU web, staff & maps
•
Search 
•
•COMP1100/1130 [2019 S1]
•Lectures
•Labs
•Assignments
•Exams
•Resources
•COMP1100/1130 [2019 S1]
•Lectures
•Labs
•Exams
•Resources
Search COMP1100/1130 [2019 S1]
•
assignments
•Assignment 1: Shapes
•Assignment 2: Turtle Graphics
•Assignment 3: Sushi Go
news
•10 May | Assignment Three has been released
•12 Apr | Assignment Two has been released
•29 Mar | Reminder – No Lectures Thursday or Friday
•» view all
related sites
•2018 Semester 2 page
•Echo360 (for lecture recordings)
•Piazza discussion forum
•Current students
•Programs and courses
◦• COMP1100
◦• COMP1130
•Timetabling
•Exam Scheduling
•Academic Skills
Home
1.» Assignments
2.» Assignment 3: Sushi Go
Assignment 3: Sushi Go
In this assignment, you will develop an AI that plays a variant of the Sushi Go card game. We have implemented the rules of the game for you, but you will have to decide how best to play the game.
This assignment is worth 15% of your final grade.
Deadline: Monday June 3, 2019, at 9:00am Canberra time sharp
Overview of Tasks
All students are required to complete the same set of tasks, but COMP1130 students have an additional card to consider when developing their AI:
COMP1100
COMP1130
Main Task: Sushi Go AI (no Chopsticks)
55 Marks
N/A
Main Task: Sushi Go AI (with Chopsticks)
N/A
65 Marks
Unit Tests
10 Marks
10 Marks
Style
10 Marks
10 Marks
Technical Report
25 Marks
35 Marks
As with assignment 2, code that does not compile will be penalised heavily. It is essential that you can write code that compiles and runs. 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.
Getting Started
Fork the assignment repository and create a project for it in IntelliJ IDEA, following the same steps as in Lab 2. The assignment repository is at https://gitlab.cecs.anu.edu.au/comp1100/comp1100-assignment3.
Overview of the Game
The aim of Sushi Go (and our restricted version) is to collect cards (representing dishes) to make the highest-scoring (most delicious) meal possible. There are two players: Player 1 and Player 2. Each player is given a hand of cards and on their turn, they chose a single card to keep. After Player 2’s turn, both players swap hands and keep going. The game is over when everyone’s hand is empty. The winner is the person whose cards are worth the most points, according to the scoring rules below.
The Cards
Players must therefore select cards that are valuable to them. Careful selection can also deny your opponent valuable cards. The cards are represented by constructors of the Card type, defined in SushiGo.hs:
Nigiri
Nigiri (Nigiri Int) is your basic meal, and is worth the number of points in its argument (between 1 and 3, inclusive). It is more delicious if you add Wasabi, below.
Wasabi
Wasabi (Wasabi (Maybe Card)) makes Nigiri taste even better! The next Nigiri you take will be attached to the Wasabi, and is worth triple points. Taking Wasabi after Nigiri has no effect. A Wasabi with no Nigiri is worth zero points at the end of the game.
Dumplings
Dumplings (Dumplings) are delicious – the more you have, the more you want! They are scored based on the number you have:
Count
Score
1
1
2
3
3
6
4
10
5 or more
15
Eel
Eel (Eel) is an acquired taste – the first one tastes gross, but it gets better with time. It is also scored based on the number you have:
Count
Score
1
-3
2 or more
7
Tofu
Tofu (Tofu) is good for you, but eat too much and you will feel sick! It is also scored based on the number you have:
Count
Score
1
2
2
6
3 or more
0
Sashimi
Sashimi (Sashimi) is tasty, but best served in threes. Every three sashimi is worth 10 points, but any leftovers are worth zero.
Chopsticks (COMP1130 Only)
Chopsticks (Chopsticks) will only show up for COMP1130 students. They are worth zero if you are holding them at the end of the round, but you can trade them for an extra pick on a future turn.
Overview of the Repository
Most of your code will be written in src/AI.hs, but you will also need to write tests in test/AllTests.hs. A small program to play the game (either Human vs. Human, or Human vs. AI, or AI vs. AI) is provided at app/Main.hs, and you can run it with cabal run.
src/SushiGo.hs implements the rules of the game. You should read this file carefully as many types and functions defined there will be useful to you. You do not need to understand the implementation of playMove or scoreCards, but knowing what they do will be helpful.
test/SushiGoTests.hs is the suite of unit tests we used to develop this assignment. You should read over as an example of unit testing style, or to understand how edge cases in the rules are resolved.
The only files you are allowed to modify in your submission are src/AI.hs and test/AllTests.hs. Any other modifications risk changing the rules of the game, so you would be playing a different game to the one in the assignment.
Other Files
•app/Main.hs implements an interface to play the game, and for you to test your skills against your AI. You are not required to understand it.
•duel/Main.hs implements a test program that tests your AIs against each other. You are not required to understand it.
•comp1100-assignment3.cabal tells the cabal build tool how to build your assignment. You are not required to understand this file, and we will discuss how to use cabal below.
•The files under src/Dragons/ contain advanced code that you are not required to understand or modify.
•src/ListUtils.hs contains some helper functions for manipulating lists. You might find these handy, or you might not need them.
•src/TextLayout.hs contains a helper function to render a grid of strings. You probably will not need this.
•test/Testing.hs is a testing library that is similar to the ones used in previous assignments. It has been extended to allow you to group related tests together.
•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.
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 build: Compile your assignment.
•cabal run sushigo: Build your assignment (if necessary), and run one of the test programs.
•cabal run duel: Build your assignment (if necessary), and run the other test program. We discuss the test programs in detail below, as there are a number of ways to launch them.
•cabal repl comp1100-assignment3: Run the GHCi interpreter over your project.
•cabal 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.
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 the IntelliJ Terminal tool for your project).
Overview of the Test Programs
sushigo
When you run cabal run sushigo, you play the game against your AI called “default”. On player turns, you will be presented with a list of cards you can take, and you can type in the letters next to a card to pick it from your hand.
You can change the behaviour of the programm by calling it with different arguments, like this: cabal run sushigo — arg1 arg2 arg3…. These are the arguments you can provide:
Argument
Effect
-chopsticks
Add Chopsticks to the game (COMP1130 students will almost always want this)
-p1ai ainame
Use AI called “ainame” for Player 1
-p1human
Use human input for Player 1 (default)
-p1random
Use random moves for Player 1
-p2ai ainame
Use AI called “ainame” for Player 2
-p2human
Use human input for Player 2
-p2random
Use random moves for Player 2
Example: cabal run sushigo — -chopsticks -p1ai skynet -p2random: Add Chopsticks to the game, and play the AI called “skynet” as player 1 against random moves for player 2.
duel
When you run cabal run duel, two of your AIs will square off against each other ten times. You can select which AI to run, and whether or not to use Chopsticks by passing in arguments from the table below:
Argument
Effect
-chopsticks
Add Chopsticks to the game (COMP1130 students will almost always want this)
-p1ai ainame
Use AI called “ainame” for Player 1
-p1random
Use random moves for Player 1 (default)
-p2ai ainame
Use AI called “ainame” for Player 2
-p2random
Use random moves for Player 2 (default)
Example: cabal run duel — -p1ai skynet -p2ai mother: Add Chopsticks to the game, and play ten games where the AI called “skynet” plays against the AI called “mother”. Player 1 will always move first, and Player 2 will always move second.
With ten games and two AIs each taking four seconds to make each of its 15 moves, a full duel will take about 20 minutes. You should not have to run too many duels, but it is important to keep that running time in mind. You can tweak the time limits by editing the definition of timeLimit in either app/Main.hs or duel/Main.hs, but we will be using four second timeouts in our tests.
Main Task: Sushi Go AI (COMP1100: 55 Marks; COMP1130: 65 Marks)
Your Task
Implement an AI (of type AIFunc) for Sushi Go 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.
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.
It is vital that you indicate one AI as “default”, otherwise we will not know which one to mark.
Understanding the AIFunc type
The AIFunc type is an alias for the type GameState -> Int -> Move. The GameState argument describes the current game, and the Int argument is an indication of how far you might want to look ahead when searching for a good move.
You do not have to arrange for your AI to be called; any test program we provide will do so for you. When it is your AI’s turn, we will call your AI with the current game state and lookahead 1, then 2, then 3, etc, until four seconds have passed overall. The most recent result will be taken as the final result.
Very simple AIs that do not look ahead will ignore the Int argument.
Discussion
Your AI should inspect the GameStatus within the GameState to see whose turn it is. You may call error if the GameStatus is Finished – your AI should never be called on a finished game. You can then use the Player value and otherPlayer function to look up the hands and cards for each player. The framework calls the set of cards to select from the “hand”, and calls the set of cards already selected the “cards”.
You may also assume that the current player’s hand is never empty, but note that gratuitous use of functions like head and tail is still poor style.
COMP1100 students will never see a Chopsticks card, so should call error on Chopsticks if case-matching on Card values.
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.
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 AIFunc looks like.
Interlude: Heuristics
Heuristic functions were 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.
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 taking the card that will give it the greatest increase in heuristic. Try writing a simple heuristic and a greedy strategy, and see whether it beats your “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, which was 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:
◦Lookahead: 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 lookahead, Eel looks like a bad pick, but at deeper lookahead the AI can see that 2 Eels is worth a good number of points.
◦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 GameState 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 acheive a deeper lookahead 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 at current score. If there is only one copy of Sashimi in the game, you will never get the 3 copies to get 10 points, so the card is worth zero and you probably will not want to pick it. If you can complete the set, each card in the set is effectively worth a pretty-good 3+1/3 points.
•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 AIs, 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 – test/Testing.hs now allows you to group tests into a tree structure. As before, you run the tests using cabal test.
To see examples, open test/SushiGoTests.hs. This file contains the tests we wrote while developing the assignment framework. You should read this file to get an idea for how tests are structured: sushiGoTests is the top-level group of tests in this file, and collects the tests for the playMove and scoreCards functions defined in src/SushiGo.hs. assertEqual (and the other assert functions in test/Testing.hs) now takes an extra parameter that describes the test’s meaning.
test/AllTests.hs collects all the tests for the assignment, and contains the code to run the test suite (main = defaultMain allTests).
Your Task
Add additional tests to test/AllTests.hs that test your AI.
Hints
•Most of the hints from Assignment 2 apply here. Reread 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. Most of the playMoveTests exist for this reason.
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 think about the problem and your solution to it.
Your Task
Ensure that your code is written in good Haskell style.
Technical Report (COMP1100: 25 marks; COMP1130: 35 marks)
You are to write a concise technical report explaining the design of your AI and the choices you made in its design and implementation. An excellent report will: demonstrate conceptual understanding of all major functions, and how they interact when the program as a whole runs; explain your design process, including your assumptions, and the reasons behind choices you made; discuss how you tested your program, and in particular why your tests give you confidence that your code is correct; and be well formatted without spelling or grammar errors.
The maximum word count is 1500 for COMP1100 students. COMP1130 students have a maximum word count of 2500, so they have space to discuss their choices for a more complex game. This is a limit, not a quota; concise presentation is a virtue. If you are in COMP1100 and can detail your AI in 1000 words, it is better to submit the 1000 word report than to waste your time padding it to 1500.
Once again: These are not required word counts. They are the maximum number of words that your marker will read. If you can do it in fewer words without compromising the presentation, please do so.
The marks allocated to the report, and the word count, have both increased for this assignment. This assignment is more open than previous ones, and so we expect more from the report.
Your report must be in PDF format, located at the root of your assignment repository on GitLab and named Report.pdf. Otherwise, it may not be marked.
The report must have a title page with the following items:
•Your name
•Your laboratory time and tutor
•Your university ID
Content and Structure
Your audience is the tutors and lecturers, who are proficient at programming and understand most concepts. Therefore you should not, for example, waste words describing the syntax of Haskell or how the minimax algorithm works. After reading your technical report, the reader should thoroughly understand what problem your program is trying to solve, the reasons behind major design choices in it, as well as how it was tested. Your report should give a broad overview of your program, but focus on the specifics of what you did and why.
Remember that the tutors have access to the above assignment specification, and if your report only contains details from it then you will only receive minimal marks. Below is an potential outline for the structure of your report and some things you might discuss in it.
Introduction
If you wish to do so you can write an introduction. In it, give:
•A brief overview of your program:
◦how it works; and
◦what it is designed to do.
Content
Talk about why you structured the program the way you did. Below are some questions you could answer:
•Program design
◦Describe what each relevant function does conceptually. (i.e. how does it get you closer to solving the problems outlined in this assignment spec?)
◦How do these functions piece together to make the finished program? Why did you design and implement it this way?
◦What major design choices did you make regarding the functions that you’ve written, and the overall structure of your program?
◦For this assignment specifically, you could also ask yourself:
▪How does your AI select a good move?
▪What data structures did you choose, and why?
▪How did you develop the AI that is your main submission?
•Assumptions
◦Describe assumptions you have made about how the turtle behaves, and how this has influenced your design decisions.
•Testing
◦How did you test individual functions?
▪Be specific about this – the tutors know that you have tested your program, but they want to know how.
▪Describe the tests that prove individual functions on their own behave as expected (i.e. testing a function with different inputs and doing a calculation by hand to check that the outputs are correct).
◦How did you test the entire program? What tests did you perform to show that the program behaves as expected in all (even unexpected) cases?
•Inspiration / external content
◦What resources did you use when writing your program (e.g., published algorithms)?
◦If you have used resources such as a webpage describing an algorithm, be sure to cite it properly at the end of your report in a ‘References’ section. References do not count to the maximum word limit.
Reflection
Discuss the reasoning behind your decisions, rather than what the decisions were. You can reflect on not only the decisions you made, but the process through which you developed the final program:
•Did you encounter any conceptual or technical issues?
◦If you solved them, describe the relevant details of what happened and how you overcame them.
◦Sometimes limitations on time or technical skills can limit how much of the assignment can be completed. If you ran into a problem that you could not solve, then your report is the perfect place to describe them. Try to include details such as:
▪theories as to what caused the problem;
▪suggestions of things that might have fixed it; and
▪discussion about what you did try, and the results of these attempts.
•What would you have done differently if you were to do it again?
◦What changes to the design and structure you would make if you wrote the program again from scratch?
•Are parts of the program confusing for the reader? You can explain them in the report (in this situation you should also make use of comments in your code).
•If you collaborated with others, what was the nature of the collaboration? (Note that you are only allowed to collaborate by sharing ideas, not code.)
◦Collaborating is any discussion or work done together on planning or writing your assignment.
•Other info
◦You may like to briefly discuss details of events which were relevant to your process of design – strange or interesting things that you noticed and fixed along the way.
This is a list of suggestions, not requirements. You should only discuss items from this list if you have something interesting to write.
Things to avoid in a technical report
•Line by line explanations of large portions of code. (If you want to include a specific line of code, be sure to format as described in the “Format” section below.)
•Pictures of code or IntelliJ.
•Content that is not your own, unless cited.
•Grammatical errors or misspellings. Proof-read it before submission.
•Informal language – a technical report is a professional document, and as such should avoid things such as:
◦Unnecessary abbreviations (atm, btw, ps, and so on), emojis, and emoticons; and
◦Stories / recounts of events not relevant to the development of the program.
•Irrelevant diagrams, graphs, and charts. Unnecessary elements will distract from the important content. Keep it succinct and focused.
If you need additional help with report writing, the academic skills writing centre has a peer writing service and writing coaches.
Format
You are not required to follow any specific style guide (such as APA or Harvard). However, here are some tips which will make your report more pleasant to read, and make more sense to someone with a computer science background.
•Colours should be kept minimal. If you need to use colour, make sure it is absolutely necessary.
•If you are using graphics, make sure they are vector graphics (that stay sharp even as the reader zooms in on them).
•Any code, including type/function/module names or file names, that appears in your document should have a monospaced font (such as Consolas, Courier New, Lucida Console, or Monaco)
•Other text should be set in serif fonts (popular choices are Times, Palatino, Sabon, Minion, or Caslon).
•When available, automatic ligatures should be activated.
•Do not use underscore to highlight your text.
•Text should be at least 1.5 spaced.
Communication
Do not post your code publicly, either on Piazza or via other forums. Posts on Piazza trigger emails to all students, so if by mistake you post your code publicly, others will have access to your code and you may be held responsible for plagiarism.
Once again, and we cannot stress this enough: do not post your code publicly . If you need help with your code, post it privately to the instructors.
When brainstorming with your friends, do not share code. There might be pressure from your friends, but this is for both your and their benefit. Anything that smells of plagiarism will be investigated and there may be serious consequences.
Sharing ideas and sketches is perfectly fine, but sharing should stop at ideas.
Course staff will not look at assignment code unless it is posted privately in piazza.
Course staff will typically give assistance by asking questions, directing you to relevant exercises from the labs, or definitions and examples from the lectures.
Before the assignment is due, course staff will not give individual tips on writing functions for the assignment or how your code can be improved. We will help you get unstuck by asking questions and pointing you to relevant lecture and lab material. You will receive feedback on your work when marks are released.
Submission Advice
Start early, and aim to finish the assignment several days before the due date. At least 24 hours before the deadline, you should:
•Re-read the specification one final time, and make sure you have covered everything.
•Confirm that the latest version of your code has been pushed to GitLab.
•Ensure your program compiles and runs, including the cabal test test suite.
•Ensure your submission works on the lab machines. If it does not, it may fail tests used by the instructors.
•Proof-read and spell-check your report.
•Verify that your report is in PDF format, in the root of the project directory (not in src), and named Report.pdf. That capital R is important – Linux uses a case-sensitive file system. Check that you have succesfully added it in GitLab.
Updated: 10 May 2019/ Responsible Officer: Director, RSCS/ Page Contact: Course Convenor
•Contact ANU
•Copyright
•Disclaimer
•Privacy
•Freedom of Information
+61 2 6125 5111
The Australian National University, Canberra
CRICOS Provider : 00120C
ABN : 52 234 063 906




You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles.
» Learn how to fix this
» Ignore this warning in future
Reviews
There are no reviews yet.