game.py:

import math import time from player import HumanPlayer, RandomComputerPlayer class TicTacToe(): def __init__(self): self.board = self.make_board() self.current_winner = None @staticmethod def make_board(): return [' ' for _ in range(9)] def print_board(self): for row in [self.board[i*3:(i+1) * 3] for i in range(3)]: print('| ' + ' | '.join(row) + ' |') @staticmethod def print_board_nums(): # 0 | 1 | 2 number_board = [[str(i) for i in range(j*3, (j+1)*3)] for j in range(3)] for row in number_board: print('| ' + ' | '.join(row) + ' |') def make_move(self, square, letter): if self.board[square] == ' ': self.board[square] = letter if self.winner(square, letter): self.current_winner = letter return True return False def winner(self, square, letter): #this function should have the logic to check for the winning condition #for instance, three O's in a straight line def empty_squares(self): return ' ' in self.board def num_empty_squares(self): return self.board.count(' ') def available_moves(self): #this function should compute the available moves on the board def play(game, x_player, o_player, print_game=True): #the complete logic for the game should be defined here if __name__ == '__main__': x_player = RandomComputerPlayer('X') o_player = HumanPlayer('O') t = TicTacToe() play(t, x_player, o_player, print_game=True) 

player.py:

import math import random class Player(): def __init__(self, letter): self.letter = letter def get_move(self, game): pass class HumanPlayer(Player): def __init__(self, letter): super().__init__(letter) def get_move(self, game): valid_square = False val = None while not valid_square: square = input(self.letter + '\'s turn. Input move (0-9): ') try: val = int(square) if val not in game.available_moves(): raise ValueError valid_square = True except ValueError: print('Invalid square. Try again.') return val class RandomComputerPlayer(Player): def __init__(self, letter): super().__init__(letter) def get_move(self, game): square = random.choice(game.available_moves()) return square 

The objective of this assignment is to implement and use the Minimax algorithm to develop an AI that always plays Tic-Tac-Toe optimally, or in other words; an AI that cannot be defeated in this game (the AI would either win or force a draw).

There are two main files in this project: game.py and player.py. player.py contains a parent class - Player with child classes (HumanPlayer and RandomComputerPlayer) that comprise the code for the user to provide input as well as for the computer to play by selecting an available location on the Tic Tac Toe board in a random manner. These two child classes are already developed for you. A child class SmartComputerPlayer should be created in this file that implements the minimax algorithm and decides the next move on the board in an optimal manner. The game.py file has a couple of functions that develop the Tic Tac Toe board and print the Tic Tac Toe board. The incomplete functions such as def play(game, x_player, o_player, print_game=True), def winner(self, square, letter), and def available_moves(self) should be completed. These functions should comprise the logic for the game, the logic for computing the available moves on the board, and the logic for checking for the winning condition. Every function

in this file that should be completed has a comment line indicating what the function should comprise. Upon completion of these functions and the correct implementation of the minimax algorithm in the child class SmartComputerPlayer, you should be able to update the following two statements in the game.py file From: x_player = RandomComputerPlayer('X') o_player = HumanPlayer('O') To: x_player = SmartComputerPlayer('X') o_player = HumanPlayer('O') and play against an AI that always selects the most optimal move to either win or force a draw. Or in other words, the AI playing the game will be undefeatable! Specifications Playing the game: In the initial game state, X (computer) gets the first move. Subsequently, the player alternates with each additional move. The user is expected to provide input in the range of 0 to 8, and the corresponding square will be marked O during the game. The program should check if the input entered for the move is incorrect (for instance if the user enters a special character) and/or if that space on the board is already occupied. A proper error message should be displayed for such a scenario. The game should NOT terminate, and it should ask the user to enter the input again. Winning and Losing: One can win the game with three of their moves in a row horizontally, vertically, or diagonally. You may assume that there will be at most one winner (that is, no board will ever have both players with three in a row since that would be an invalid board state). If the X player has won the game, your program should show a proper output message to indicate that the computer has won. If the result is a draw, your program should also display a proper output message that indicates that the result is a draw. The program should terminate after there is a result (win, loss, or draw). The utility function should accept a state of the board as input and compute the utility of the board as per the following formula: Utility for a State = (A * B) A = value for X wins (+1) or value for O wins (-1) or value for a Draw (0) B = number of remaining squares + 1 (to win in the minimum number of turns)

The minimax function should take a board as input and return the optimal move for the player to move on that board. Additional Functions: You are welcome to create any additional function(s) in any of these files. However, there should be a comment line outlining the purpose of these function(s). Modifying the code: You may add new statements to the functions (that are completed for you) as well as update any of the existing statements. However, there should be a comment line outlining any such update. Comments: There should be proper comments in your code. Lack of proper comments may result in the deduction of points.

Thank you! Love you!