[2022] MCD4710 Introduction to Algorithms and Programming Assignment 2: Tic Tac Toe
MCD4710 - Introduction to Algorithms and Programming Assignment 2 (10%)
Due: Thursday, September 1, 2022, 11:55 pm - Week 10
Objectives
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:
- Your name and student ID must be included at the start of every file in your submission.
- Save your file(s) into a zip file called YourStudentID.zip
- Submit your zip file containing your entire submission to Moodle.
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.
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.
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')
