share via whatsapp
share via whatsapp

Implement an AI (of type AIFunc) for Sushi Go in src/AI.hs. There is a list called ais in that...

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.
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 immediateadvantage. 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.
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.
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:
o 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.
o 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.
o 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.
o 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: sushiGoTestsis 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.
• 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.


Related Questions

Recent Questions in Capstone