KIT107 Programming 2018
Assignment 3
Due Date
The assignment is due at 3PM Wednesday May 30th 2018 and should be completed in pairs using
the Pair Programming Technique.
Context
Nim is a game played between two players. 21 objects (matches, coins, or lollies) are placed in
front of the players and, having decided who will go first, each player removes one, two, or three
objects in alternating turns. The goal is to force the other player to remove the final object — the
player to remove the final object is the loser!
This assignment uses many data structures (trees, linked-lists, and stacks) to implement a human-
versus-computer version of the game. The game will be text only.
The computer will choose its move by creating a game tree. A game tree consists of all the possible
states of the game (moves) and the computer determines the outcome of particular choices to guide
which choice is the best. The state of the game — values in the nodes of the game tree — is
defined as comprising how many objects remain in the game and how good (or bad) the outcome
looks (an int from –9 to +9). Each node of the game tree has children that indicate the states of
the game that follow from the state of the parent for each possible move, i.e. there are likely to be
2/5
three children for each node, one with one additional object removed, one with two, and one with
three.
You will need to create the game tree (using a depth-first approach) after each move. This is called
building the tree. It needs to be done in stages. For a given tree node you should create the level
underneath it by creating child nodes with one, two, or three objects removed and link them to their
parent. Each one should have its worth evaluated (to indicate if each is a good move or a bad
move). You should push them onto a stack of trees which indicate which ones have been seen but
not expanded, just like the traversal shown in lectures. Some optimisations may be possible. For
example, if the given game tree already has multiple levels, then these could be used instead of re-
creating them. Additionally, once the user has moved, their move could be found in the existing
game tree rather than re-creating it.
A sample run of the game is shown below.
A Visual Studio project has been created as a starting point and is available for download on
MyLO. The project contains many files. All required files are present. Your task is simply to
complete the functions within the program files which have been declared but for which the
function bodies are missing. Do not change any code which has been given to you (other than the
settings in assig_three118.h).
Program Style.
Your program should follow the following coding conventions:
const variable identifiers should be used as much as possible, should be written all in
upper case and should be declared before all other variables;
Variable identifiers should only contain lower case letters and the underscore (_), be
meaningful, and variables should only be declared at the top of a function (i.e. before other
statements);
Every if and if-else statement should have a block of code (i.e. collections of lines
surrounded by { and }) for both the if part and the else part (if used);
Every loop (do, while, for) should have a block of code;
3/5
The keyword continue should not be used;
The keyword break should only be used as part of a switch statement;
Opening and closing braces of a block should be aligned;
All code within a block should be aligned and indented 1 tab stop (or 4 spaces) from the
braces marking this block;
Commenting:
o There should be a block of header comment which includes at least
file name
student names
student identity numbers
a statement of the purpose of the program
date
o Each variable declaration should be commented
o There should be a comment identifying groups of statements that do various parts of
the task
o Comments should describe the strategy of the code and should not simply translate
the C into English
o Pre-conditions may be assumed, and if true, the function should produce the post-
condition
o You don’t have to comment the code which is provided to you
Style. marks will be awarded proportionally, i.e. if you attempt only half the coding you can expect
only half the style. marks.
Marking scheme
Task/Topic Maximum
mark
Program operates as specified
node.c correctly completed 6
stack.c correctly completed 6
gameState.c correctly completed 7
tNode.c correctly completed 14
gameTree.c correctly completed 31
Program Style.
Does not unnecessarily repeat tests or have other redundant/confusing code 8
Uses correctly the C naming conventions 8
Alignment of code and use of white space makes code readable 8
Always uses blocks in branch and loop constructs 8
Meaningful identifiers 8
Variables declared at the top of functions 8
Each variable declaration is commented 8
Comments within the code indicate the purpose of sections of code (but DO
NOT just duplicate what the code says)
What and how to submit
Only one submission is required for the pair but both paper and electronic submissions are required
for each pair.
What to submit
Paper submission
A signed cover page (blanks can be collected from the ICT Reception/Help Desk or from
the ICT web site at
http://www.utas.edu.au/__data/assets/pdf_file/0005/161375/GroupAssignmentCover.pdf);
A landscape-orientation print-out of the five ‘.c’ source code files for the program. Your
assignment will not be marked unless these are present; and
A statement from each person indicating what proportion of the work was theirs. If the
work was done equally, then each person should claim 50% of the effort. It is expected that
this will be the case and this will be assumed if no statement is submitted. If, however, one
person has done very little, then this should be stated. A reason why this is the case should
be given. For example, if one student does 80% of the work because their partner did not
turn up to meetings, complete work by the agreed time, etc. then this should be stated. If
one student does 30% of the work because the other student simply went off and did it all by
themselves and without consultation then this should be stated.
Electronic submission
You should submit the entire Visual Studio project folder.
How to submit
Paper submission
Firmly staple together all of the required documents (with the signed cover page on top) and
place them in the appropriate submissions box near the ICT Discipline Help Desk.
Electronic submission
The entire Visual Studio project folder should be converted into a ZIP file and the ZIP file
should be submitted via MyLO by one member of the pair. Only one submission is
required.
The program is required to work under the Visual Studio environment in the labs. Any
development environment may be used; once the programming is complete replace the
altered programs in the downloaded Visual Studio project and submit it.
Plagiarism and Cheating:
Practical assignments are used by the School of Technology, Environments and Design for students
to both reinforce and demonstrate their understanding of material which has been presented in class.
They have a role both for assessment and for learning. It is a requirement that work you hand in for
assessment is substantially your own.
Working with others
One effective way to grasp principles and concepts is to discuss the issues with your peers and/or
friends. You are encouraged to do this. We also encourage you to discuss aspects of practical
assignments with others. However, once you have clarified the principles, your pair must express
them in writing or electronically entirely by yourselves. In other words you must develop the
algorithm to solve the problem and write the program which implements this algorithm with your
partner and no one else (other than staff).
Cheating
Cheating occurs if you claim work as your own when it is substantially the work of someone
else.
Cheating is an offence under the Ordinance of Student Discipline within the
University. Furthermore, the ICT profession has ethical standards in which cheating has no
place.
Cheating involves two or more parties.
o If you allow written work, computer listings, or electronic version of your code to be
viewed, borrowed, or copied by another student you are an equal partner in the act of
cheating.
o You should be careful to ensure that your work is not left in a situation where it may
be viewed/stolen by others.
Where there is a reasonable cause to believe that a case of cheating has occurred, this will be
brought to the attention of the unit lecturer. If the lecturer considers that there is evidence of
cheating, then no marks will be given to any of the students involved. The case will be
referred to the Head of School for consideration of further action.
Julian Dermoudy, May 8th 2018.