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.

bars search times arrow-up