The objectives of this assignment are:
● To gain experience in designing algorithms for a given problem description and implementing those algorithms in Python.
● To demonstrate your understanding on:
o Implementing problem solving strategies
o Recognizing the relationship between a problem description and program design
o Decomposing code into functions in Python.
Submission Procedure
Your assignment will not be accepted unless it meets these requirements:
1. Your name and student ID must be included at the start of every file in your submission.
2. Save your file(s) into a zip file called YourStudentID.zip
3. Submit your zip file containing your entire submission to Moodle.
Late Submission
Late submission will have 5% deduction of the total assignment marks per day (including weekends). Assignments submitted 7 days after the due date will not be accepted.
Important Notes
● Please ensure that you have read and understood the university’s procedure on plagiarism and collusion available
at https://www.monashcollege.edu.au/__data/assets/pdf_file/0005/1266845/Student-Academic-Integrity
Diplomas-Procedure.pdf . You will be required to agree to these policies when you submit your assignment.
● Your code will be checked against other students’ work and code available online by advanced plagiarism
detection systems. Make sure your work is your own. Do not take the risk.
● Your program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementation has bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. This is made difficult if code is poorly documented.
Assignment code interview
Each student will be interviewed during a lab session regarding their submission to gauge your personal understanding of your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand
the code submitted. Your assignment mark will be scaled according to the responses provided.
Interview Rubric
Marking Criteria
This assignment contributes to 10% of your final mark.
Task 1 – Initialize board: 1 mark
Task 2 – Print board: 2 marks
Task 3 – Check if the board is filled: 2 marks
Task 4 – Check if a player has won: 5 marks
Task 5 – Update the board: 2 marks
Task 6 – Next move of the computer: 6 marks
Task 7 – Play the game: 5 marks
Programming practice – 2 marks
● Decomposition (1 mark)
● Variable names and code Documentation (1 mark)
Total: 25 marks
Background Information
In this assignment you are going to implement the game Tic Tac Toe.. It is a 2-player game with the following rules.
● Player 1 uses a cross, X, to mark a cell on the board
● Player 2 uses an O to mark a cell on the board
● Board size is 3-by-3, with 9 cells altogether
● At the start the whole board is empty
● Player 1 places a X in one of the empty cells
● Player 2 will then place an O in one of the empty cells
● Both players repeat placing their sign in empty cells until one wins or until there are no available cells to fill in
● The goal of the players is to place their sign covering an entire row, an entire column or an entire diagonal.
The following diagrams show some of the winning arrangements.
In this assignment the user is expected to play the game against the computer. The user will be player 1 and the computer will be player 2.
Task 1: Initialize the board
Implement a function named init_board() which creates a 3x3 board. Fill in each cell with a hyphen, indicating that the cells are all empty. Implement the board as a table (ie. a list of lists) in python. This function should return the table (i.e. list of lists). It should not print the board.
Input: No input taken
Output: A table that represents the 3x3 tic-tac-toe board with all the cells filled with a hyphen
For example:
>>> board = init_board()
>>> board
[['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']]
Task 2: Print board
Write a function named print_board(board)that prints the given board in the format shown in the example below.
Input: The current status of the board
Output: Prints the current board to the screen
For example:
>>> board = init_board()
>>> print_board(board)
-------------
| - | - | - |
-------------
| - | - | - |
-------------
| - | - | - |
-------------
Task 3: Check if the board is filled
Write a function named is_filled(board)that returns True if the board is fully filled with X’s and/or O’s and False otherwise.
Input: The current status of the board
Output: True if the board is filled, False otherwise
For example:
>>> board = init_board()
>>> is_filled(board)
False
>>> test_board = [['X','O','X'],['O','X','O'],['X','O','X']]
>>> is_filled(test_board)
True
Task 4: Check if a player has won
Write a function named player_won(board)that checks if one of the players has won. If a player has won, the function should display on the screen which player has won and return True. If none of
the players has won the function should return False.
Note: You should consider decomposition in this task.
Input: The current status of the board
Output: True if the board is filled, False otherwise
For example:
>>> test_board = [['X','O','X'],['O','X','O'],['X','O','X']]
>>> player_won(test_board)
Congrats!! You win!
True
>>> test_board = [['O','X','O'],['X','O','X'],['O','X','O']]
>>> player_won(test_board)
I win! Nice try!
True
>>> test_board = [['X','-','O'],['X','-','O'],['X','-','-']]
>>> player_won(test_board)
Congrats!! You win!
True
>>> test_board = [['O','O','X'],['X','X','O'],['O','X','O']]
>>> player_won(test_board)
False
Task 5: Update the board
Write a function named update_board(board,row,col,player)that places the next ‘X’ or ‘O’ on the board. You need to check if the selected cell is empty before updating the board. If the chosen cell is not empty the function should return False. If the update was successful, the function should return True.
Input: The current status of the board, the row, column and the player (‘X’ or ‘O’) for the next move.
Output: True if the board is successfully updated, False otherwise.
For example:
>>> test_board = [['X','O','-'],['-','X','-'],['-','O','-']]
>>> update_board(test_board,1,0,'X')
True
>>> test_board = [['X','O','-'],['-','X','-'],['X','O','-']]
>>> update_board(test_board,2,1,'O')
False
Task 6: Next move of the computer
Now we need to decide on the position of the next move for the computer. We have two levels of difficulty for the user. The next move of the computer depends on the difficulty level chosen by the user at the beginning of the game.
Write a function named next_move(board,level)that returns the position (row,col) of the next placement of ‘O’ using the following recommendations based on the level selected
(Note: you should breakdown the problem and write other helper functions for this task, thus decomposing your code).
For the easy level, your code should randomly select one of the available positions.
For the hard level your code should try to find the best option at hand, using the following criteria in the given order (ie. you move to the next criterion only if the previous ones are not met).
1. If there are two ‘O’s in a row, column or a diagonal, the next move should fill the corresponding row, column or diagonal with another ‘O’ so that the computer wins.
2. If there are two ‘X’ s in a row, column or a diagonal, the next move should fill the corresponding row, column or diagonal with an ‘O’ so that the computer blocks the user’s next winning move.
3. If there is an ‘O’ in a row, column or a diagonal, the next move should place another ‘O’ on the same row, column or diagonal.
4. If there are no ‘O’s on the board, place an ‘O’ in any random available position.
Note: Only two test cases are provided. Some board configurations can result in more than one possible output. You should test your code with more configurations interactively via the play function which you will implement in task 7 below.
Input: The current status of the board and the difficulty level
Output: Position of the next move, as a tuple (row,column)
For example:
>>> test_board = [['X','-','-'],['X','O','-'],['O','-','-']]
>>> next_move(test_board,'hard')
(0, 2)
>>> test_board = [['-','X','-'],['-','X','O'],['O','-','-']]
>>> next_move(test_board,'hard')
(2, 1)
Task 7: Play the game
Finally, we can implement the play function. Write a function named play()that does the following.
1. Initialises the board
2. Lets the user choose the difficulty level and make the first move
3. Follow the game rules until a player wins or the game ends in a draw. Print the message “It’s a tie” if it is a draw.
4. If the user selects a cell that is already occupied or if it is out of the range of the board size, the code should display an error message and ask the user to enter another choice.
Test your code interactively by playing the game.