The University of Melbourne
School of Computing and Information Systems
Declarative Programming COMP90048
Semester 1
Project Specification
Project due Thursday, 12 April 2018 at 5pm Worth 15%
The objective of this project is to practice and assess your understanding of functional pro- gramming and Haskell. You will write code to implement the guessing part of a logical guessing game.
The Game of ChessGuess
ChessGuess is a two-player logical guessing game created for this project. You will not find any information about the game anywhere else, but it is a simple game and this specification will tell you all you need to know.
For a ChessGuess game, one player will be the hider and the other is the guesser. The hider begins by selecting the size of the game which can be from 0 to 32. The hider then selects up to size chess pieces out of a chess set and hides them. Each piece has a colour one of ’B’ black or ’W’ white and a kind: ’K’ king, ’Q’ queen, ’R’ rook, ’B’ bishop, ’N’ knight or ’P’ pawn. We will represent pieces by length 2 strings, e.g. ”BK” is a black king, and ”WP” is a white pawn. Note that they are selected from a standard chess set so there is e.g. at most two black rooks that can be selected, or at most 8 white pawns.
Once the hider has selected the target set of pieces, the guesser repeatedly chooses a subset of chess pieces up to size size and tells it to the hider, who responds by giving the guesser the following feedback:
1. how many pieces in the guess are included in the target (correct pieces)
2. how many pieces have the right kind but the wrong colour (correct kinds) 3. how many pieces have the right colour but the wrong kind (correct colours)
In counting correct pieces, kinds and colours, multiple occurrences in the guess are only counted as correct if they also appear repeatedly in the target. Correct pieces are not also counted as correct kinds and colours. For example, with a target of BK, WQ, BR, BR, a guess of WK, BN, BQ, WQ, BR would be counted as 2 correct pieces (WQ, BR), one correct kind (WK) and two correct colours (BQ,BN). BQ would not be counted as a correct kind, even though it has the same kind as the target WQ, because the target WQ was already used to count the guess WQ as a correct piece. A few more examples:
1
Target
BK,WQ,BR,BR BK,WQ,BR,BR BP,BP,BP,BK BK,WP BK,WQ,BR,BR BP,BP,BP,BR
Guess
BK,BR,WQ WK WP,BP,BR WP,WP,BR,WK WR,WR,WR WR,WR,WR
Answer
3,0,0 0,1,1 1,1,1 1,1,1 0,2,1 0,1,0
Note that the last two guesses are impossible, since they contains three white rooks, but you are allowed to make these as guesses, even though they will never be correct.
The game finishes once the guesser guesses the correct set of pieces (the target and the guess are the same set). The object of the game for the guesser is to find the target with the fewest possible guesses.
The Program
You will write Haskell code to implement the guesser part of the game. This will require you to write a function to return your initial guess, and another to use the feedback from the previous guess to determine the next guess. The latter function will be called repeatedly until it produces the correct guess. You will find it useful to keep information between guesses; since Haskell is a purely functional language, you cannot use a global or static variable to store this. Therefore, your initial guess function must return this game state information, and your next guess function must take the game state as input and return the updated game state as output. You may put any information you like in the game state, but you must define a type GameState to hold this information. If you do not need to maintain any game state, you may simply define type GameState = ().
You may use any representation you like for guesses, pieces, kinds and colors internally, and may use this representation inside your GameState type. However, to avoid prejudicing your choice of representations, we use a very simple representation for the inputs and outputs of your functions. A piece is represented as a list of two-character strings, where the first character is an upper case ’B’ (black) or ’W’ (white) representing the colour, and the second character is one of the characters ’K’ (king), ’Q’ (queen), ’R’ (rook), ’B’ (bishop), ’N’ (knight), ’P’ (pawn) representing the kind.
You must define following functions:
initialGuess :: Int ! ([String],GameState)
takes an input argument giving the size of the game, and returns a pair of an initial guess and a game state.
nextGuess :: ([String],GameState) ! (Int,Int,Int) ! ([String],GameState)
takes as input a pair of the previous guess and game state, and the feedback to this guess as a triple of correct pieces, kinds and colours, and returns a pair of the next guess and game state.
You must call your (main) source file Project2.hs (or Project2.lhs if you use literate Haskell), and it must contain the module declaration:
module Project2 (initialGuess, nextGuess, GameState) where
2
You may divide your code into as many files as you like, as long as your main file (and the files it imports) imports all the others. But do not feel you need to divide your program into many files if it is reasonably small.
I will post a test driver program Project2Test.hs, which will operate similarly to how I actually test your code. I will compile and link your code for testing using the command:
ghc -O2 --make Project2Test
or similar. To run Project2Test, give it the size of the game and then the target as separate command line arguments, for example ./Project2Test 5 BK WQ WN BB would search for the target [“BK”, “WQ”, “WN”, “BB”] in a game of size 5. It will then use your Project2 module to guess the target; the output will look something like:
Your guess 1: ["BK","BQ","BR","BR","BN"] My answer: (1,2,1) Your guess 2: ["BN","BP","WR","WR"] My answer: (0,1,4)
Your guess 3: ["BR","BB","WK","WQ"] My answer: (2,1,2) Your guess 4: ["BQ","BB","WK","WN","WB"] My answer: (2,2,2)
Your guess 5: ["BK","BB","WQ","WN"] My answer: (4,0,0) You got it in 5 guesses!
Assessment
Your project will be assessed on the following criteria:
70% Quality and correctness of your implementation; 30% Quality of your code and documentation
The correctness of your implementation will be assessed based on whether it succeeds in guessing the targets it is given in the available time. Quality will be assessed based on the number of guesses needed to find the given targets. Full marks will be given for an average of 3.91 guesses per target for size 4, 4.10 guesses per target of size 5, but even the full game size of 32 should only require less than 7 guesses on average. Marks will fall on a logarithmic scale as the number of guesses rises. Thus moving from taking 5 guesses to 4 will gain similar number of points as going from 7 to 5 guesses. Therefore as the number of guesses drops, further small decreases in the number of guesses are increasingly valuable.
Note that timeouts will be imposed on all tests. You will have at least 10 seconds to guess each target, regardless of how many guesses are needed. Executions taking longer than that may be unceremoniously terminated, leading to that test being assessed as failing. Your programs will be compiled with GHC -O2 before testing, so 10 seconds per test is a very reasonable limit.
See the Project Coding Guidelines on the LMS for detailed suggestions for coding style. These guidelines will form the basis of the quality assessment of your code and documentation.
3
Submission
You must submit your project from the student unix server dimefox.eng.unimelb.edu.au or nutmeg.eng.unimelb.edu.au. Make sure the version of your program source files you wish to submit is on this server, then cd to the directory holding your source code and issue the command:
submit COMP90048 project2 Project2.hs
(substitute Project2.lhs if you use literate Haskell). If your code spans multiple source files, add the extra ones to the end of that command line.
Important: you must wait a minute or two (or more if the servers are busy) after submitting, and then issue the command
verify COMP90048 project2 | less
This will show you the test results from your submission, as well as the file(s) you submitted. If the test results show any problems, correct them and submit again. You may submit as often as you like; only your final submission will be assessed.
If you wish to (re-)submit after the project deadline, you may do so by adding “.late” to the end of the project name (i.e., project2.late) in the submit and verify commands. But note that a penalty, described below, will apply to late submissions, so you should weigh the points you will lose for a late submission against the points you expect to gain by revising your program and submitting again.
It is your responsibility to verify your submission.
Windows users should see the LMS Resources list for instructions for downloading the (free) Putty and Winscp programs to allow you to use and copy files to the department servers from windows computers. Mac OS X and Linux users can use the ssh, scp, and sftp programs that come with your operating system.
Late Penalties
Late submissions will incur a penalty of 0.5% of the possible value of that submission per hour late, including evening and weekend hours. Late submissions will incur a penalty of 0.5% per hour late, including evening and weekend hours. This means that a perfect project that is much more than 4 days late will receive less than half the marks for the project. If you have a medical or similar compelling reason for being late, you should contact the lecturer as early as possible to ask for an extension (preferably before the due date).
Hints
1. A very simple approach to this program is to simply guess every possible combination of pieces until you guess right. For a size 3 game there are only 397 possible targets, so on average it should only take about 200 guesses, making it perfectly feasible to do in 10 seconds. However, this will give a very poor score for guess quality, and larger games will fail. Note that this will completely fail for larger games, the full size 32 game has 944,784 possibilities. But most of the testing will be on small games, we expect not all students to have a solution which works for all game sizes.
4
- A better approach would be to only make guesses that are consistent with the answers you have received for previous guesses. You can do this by computing the list of possible targets, and removing elements that are inconsistent with any answers you have received to previous guesses. A possible target is inconsistent with an answer you have received for a previous guess if the answer you would receive for that guess and that (possible) target is di↵erent from the answer you actually received for that guess.
You can use your GameState type to store your previous guesses and the corresponding answers. Or, possibly more ecient and just as easy, store the list of remaining possible targets in your GameState, and pare it down each time you receive feedback for a guess.
- The best results can be had by carefully choosing each guess so that it is most likely to leave a small remaining list of possible targets. You can do this by computing for each remaining possible target the maximum number of possible targets it will leave if you guess it. This you can do by computing, for each remaining possible target, the answer you will receive if it is the actual target, and then compute how many of the remaining possible targets would yield the same output, and take the maximum of all of these. Alternatively, you can take a more probabilistic approach, and compute the average number of possible targets that will remain after each guess, giving the expected number of remaining possible targets for each guess, and choose the guess with the smallest expected number of remaining possible targets.
- Unfortunately, this is much more expensive to compute, and you will need to be care- ful to make it ecient enough to use. In particular when the game size is large these approaches will fail early on. One thing you can do to speed it up is to laboriously (somehow) find the best first guess for each size and hard code that into your pro- gram. After the first guess, there are many fewer possible targets remaining, and your implementation may be fast enough then.
- You can also remove symmetry in the problem space. The key insight needed for this is that given any guess and an answer returned for it, the set of remaining possibilities after receiving that answer for that guess will be the same regardless of which target yielded that answer. This suggests collecting all the distinct answers for a given guess and for each answer, counting the number of targets that would give that answer. Since there are much fewer answers than possible targets, this can save significant work.
For example, suppose there are ten remaining candidate targets, and one guess gives the answer (3,0,0), three others give (1,0,2), and the remaining six give the answer (2,0,1). In this case, if you make that guess, there is a 1 in 10 chance of that being the right answer (so you are left with that as the only remaining candidate), 3 in 10 of being left with three candidates, and a 6 in 10 chance of being left with six candidates. This means on average you would expect this answer to leave you with
1 ⇥1+ 3 ⇥3+ 6 ⇥6=4.6 10 10 10
remaining candidates. You just need to select a guess that gives the minimum expected number of remaining candidates.
Also note that if you do this incorrectly, the worst consequence is that your program takes more guesses than necessary to find the target. As long as you only ever guess
5
a possible target, every guess other than the right one removes at least one possible target, so you will eventually guess the right target.
6. Note that these are just hints; you are welcome to use any approach you like to solve this, as long as it is correct and runs within the allowed time.
Note Well:
This project is part of your final assessment, so cheating is not acceptable. Any form of material exchange between teams, whether written, electronic or any other medium, is considered cheating, and so is the soliciting of help from elec- tronic newsgroups. Providing undue assistance is considered as serious as receiv- ing it, and in the case of similarities that indicate exchange of more than basic ideas, formal disciplinary action will be taken for all involved parties. If you have questions regarding these rules, please ask the lecturer.
6