Tic-Tac-Toe Game Al To implement the full version of tic-tac-toe, you need to create an Al (Artificial Intelligence) Player that can play against the user. In this assignment, you have to create three different types of Al : a simple Al that chooses moves randomly, a sophisticated SmartAl that never looses a game because is heuristic approaches, and a MiniMax that also never looses a game because it precalculates all possible moves. All three Al classes should be placed in same module, the file player.py, where the class Player is written. Al should be a subclass of the class Player and should inherit all properties from its superclass Player. The init and choose methods should be overridden moves: in the beginning of the game, all moves are empty cells on the board, so you can create a list of all cells and then remove the occupied cells from the board as the game progresses. You can import choice from the random module to randomly choose a cell (a move) from the list of all possible cells (moves). The output of the program should be the same as before, the user plays as Alice and the Al plays as Bob. The only difference from the game is that the user does not have to play for Bob, the Al (your computer program) plays instead of the user. To do so, you need to modify tictac.py to create an Al object: you can achieve it by substituting player1 = Player("Bob", "X") to player1 = Al("Bob", "X", board) and the import statement from player import Player to from player import Player, Al. Minimax Algorithm To improve the performance of a random-choice Al, you can create another class, MiniMax that uses a minimax algorithm based on recursion. MiniMax should be a subclass of Al and inherit all methods from its superclass Al. The method choose should be overridden and should call the recursive minimax method. The pseudocode for minimax is shown below, "self" refers to the MiniMax player and "opponent" - to its opponent: Minimax: 1. Check the base case: if the game is over, then return -1 if self lost, 0 if it is a tie, or 1 if self won. 2. Set the min score to infinity and max score to -infinity 3. Choose a cell (or make a move): a. iterate through all available cells (9 cells) b. check if the cell is empty c. mark the cell with X or 0 (if self then mark it with its sign, otherwise mark it with another sign) d. get score by calling the minimax recursively (you need to alternate between self and opponent) e. update score: if self then use the max score (compare it to the max score), otherwise use the min score (compare it to the min score) f. update move: update the cell index g. unmark the cell (make it a space again " ") and reset all other variables that were affected by the game play 4. If it is the start level (the last level to be executed completely and the last score to be returned) return the move
