Your goal in this assignment is
to implement the algorithm of checking an outcome of the game
of “noughts and crosses” (also called “tic-tac-toe” — hence the
function name ttt_check
). The game is represented as a nested list
on integers. You will have to use standard list operations. Defining
additional helper functions can be beneficial for simplifying the logic
of ttt_check
function.
Practical information#
The assignment is due on Saturday the 25th of March, at 11.55pm.
To submit your solution, you will upload a single Python file noughts_and_crosses.py
via Wattle.
Here is the assignment submission link.
In addition to submitting your solution, you may attend the lab in week 5. In the lab, you will have a chance to discuss some questions about the assignment. Your tutor may also ask you some questions about your solution, and give you feedback if there is anything you need to improve. This discussion is NOT part of the assessment.
The homework is individual. You must write your own solution, and you are expected to be able to explain every aspect of it. Also remember that you are not allowed to share your solution (code) with other students; this includes posting it (or parts of it) to the discussion forum, or to any other on-line forum.
As usual, you should have followed last week’s lectures and worked through the exercises in lab 3 before starting on the assignment. The assignment should not take more than one or two hours to complete. The Wattle submission is:
The problem#
You are probably familiar with the game of “Noughts and Crosses” (also known
as “Tic-Tac-Toe”, see the Wikipedia Page
for details and references), in which two players mark the originally blank cells on
a 3-by-3 grid. One player, who marks the field with a cross, 'x'
,
starts first. Every “cross move” is followed by another player who marks any of
the remaining empty field with a nought, 'o'
. The winner is the one who first
puts their symbol on a column, or a row, or one of the diagonals. If nobody is able to
achieve such a “line-up” when the last empty field is marked, the game is a draw.
The game isn’t particular difficult from the Game Theory point of view. There is
an algorithm (“strategy”) to always lead the game to a draw for the “noughts” player,
who is formally disadvantaged by starting second. This is a futile game.
In this homework, your goal will be to simply determine what is the outcome
given the state of the game. The game is described by a 3x3
“grid” which is a nested
list of lists, where all inner list elements
values are either 1, -1 or 0. These values represent the cells with
nought, or cross, or an unmarked cell, respectively. You should write an implementation of the
function ttt_check(game)
which will return a string with one of the possible
values: Crosses
, Noughts
, or Draw
. We will assume, that the game state is the result
of playing the game without violation of its rules.
What you need to know to implement the ttt_check
function is explained
in the lectures of Week 1–5. Namely, knowledge of these language features
is useful to construct your solution.
- how to check variables of
int
type for their value - how to program conditional branches, the
if
-control flow - how to define a function
- how to define a function which returns a value
- how to index a list (extract a value of list element given its index)
- how to sum a list elements
- how to slice a list
The function which will check the game outcome is called ttt_check(game)
, where
the parameter game
is a 3-element long list of 3-element lists (nested list 3x3
),
which describes the state of game as explained above (the first element-list
describes the state of first row, and so on).
The function prototype is included in the
file noughts_and_crosses.py
.
The “prototype” here means that there is a declaration
of the function ttt_check(game)
, but its body is incomplete — it contains
a statement pass
(a “do nothing” statement in Python), which must be
replaced with the specified implementation. The program file
noughts_and_crosses.py
also contains a test function test_ttt_check
(this one is complete and must
not be modified), which can be used to verify your solution
(once you completed it).
Remember, that even if the test function says that tests are passed, this does not guarantee the functional correctness. The testing can only reveal errors, it cannot prove the program correctness.
We will test your submission with other tests, not just the one given in the
noughts_and_crosses.py
file.
Remember to write your university ID and name in the beginning of the
file which you will submit. Do not change the file name (leave it noughts_and_crosses.py
as it was originally).
Code Quality#
Starting from this homework, you will be awarded an additional code quality mark, which will be 1 mark for homework 3, and 2 marks for the last two homework assignments. To get the code quality mark, your code should satisfy the following criteria:
- variable names are chosen well (they convey information about the value they represent, including their type);
- function names (if you define additional functions to help with implementation of the
function
ttt_check
) are also chosen well (they convey the meaning of operation that the function carries out); - your code is appropriately commented (and the comments are not excessive or redundant); these
can be inline comments (preceded by the
#
symbol), you are not required to include docstrings for every function which is in your program (writing docstrings will be a required feature in the remaining homeworks and the project assignment); - your code is well structured, it does not have redundant or artificially complex statements, and your data structures are chosen and used appropriately (a general rule — the code complexity must not exceed the complexity of problem it tries to solve).
The lectures discuss the code quality. You may also find a suitable discussion in recommended textbooks and elsewhere.
Marking#
What to submit
You should edit the file noughts_and_crosses.py
that you downloaded, then upload
only this file with your solution using the
assignment submission link
on Wattle.
The file that you submit must meet the following requirements:
- It must be named
noughts_and_crosses.py
. - It must be syntactically correct Python code.
- Like the file you downloaded, your solution should be implemented
in one or more function; anything outside of function definitions in the
file will be ignored. The file can include the
import
statements, and you can (and should!) use comments. - The function
test_ttt_check()
must not be modified (that is, it should be exactly the same as in the file you downloaded). We will test if you have solved the problem using the same testing procedure (ie, by calling test functions), but we will extend the number of tests, and your solution, even if it passes the original test, may fail the newly added ones, if it is not logically correct. - Your program is written in accordance with code quality guidelines described above.
As mentioned above, you will also attend the lab (in week 5) where you will have a chance to discuss your solution. This discussion is NOT part of the assessment. These are some of the questions which you can discuss:
- How to download the file that you submitted from Wattle?
- How to run that file in the Python interpreter using an IDE of your choice?
- Can you explain the algorithm of your solution in simple terms? Can you think of a different approach to the problem? Can you decide which of the approaches are better?
- If the file has syntax errors, can you use the error messages from the interpreter or IDE to identify where the syntax errors are?
- Does your submitted file meet the requirements stated above? Does
it contain anything that is not a function definition, an optional
import
statement, or a comment? If so, can you point it out? - Can your submitted solution of the
ttt_check
function be generalised easily to larger grids (4x4
and higher)?
In marking this assignment we will consider the following:
- Does your submitted file satisfy the requirements specified above?
- Does your program pass the
test_ttt_check
test cases? - Does your program pass our other tests?
- Does your program satisfy the Code Quality factors described above?
The assignment is worth 3% of your final mark.