# Implement Min-Max Function and Tic Tac Toe Game in Python Assignment Solution.

## Instructions

Objective
Write a python assignment program to implement min-max function and tic tac toe game.

## Requirements and Specifications

Source Code

```""" Tic Tac Toe Player """ import math import copy import random X = "X" O = "O" EMPTY = None def initial_state():     """     Returns starting state of the board.     """     return [[EMPTY, EMPTY, EMPTY],             [EMPTY, EMPTY, EMPTY],             [EMPTY, EMPTY, EMPTY]] def player(board):     """     Returns player who has the next turn on a board.     """     xCounter = 0     oCounter = 0     for i in range(0, len(board)):         for j in range(0, len(board[0])):             if board[i][j] == X:                 xCounter += 1             elif board[i][j] == O:                 oCounter += 1     if xCounter > oCounter:         return O     else:         return X def actions(board):     """     Returns set of all possible actions (i, j) available on the board.     """     possibleActions = set()     for i in range(0, len(board)):         for j in range(0, len(board[0])):             if board[i][j] == EMPTY:                 possibleActions.add((i, j))     return possibleActions def result(board, action):     """     Returns the board that results from making move (i, j) on the board.     """     # Create new board, without modifying the original board received as input     result = copy.deepcopy(board)     result[action[0]][action[1]] = player(board)     return result def winner(board):     """     Returns the winner of the game, if there is one.     """     # Check rows     if board[0][0] == board[0][1] and board[0][1] == board[0][2] and board[0][0] is not None:         return board[0][0]     elif board[1][0] == board[1][1] and board[1][1] == board[1][2] and board[1][0] is not None:         return board[1][0]     elif board[2][0] == board[2][1] and board[2][1] == board[2][2] and board[2][0] is not None:         return board[2][0]     # Check columns     if board[0][0] == board[1][0] and board[1][0] == board[2][0] and board[0][0] is not None:         return board[0][0]     elif board[0][1] == board[1][1] and board[1][1] == board[2][1] and board[0][1] is not None:         return board[0][1]     elif board[0][2] == board[1][2] and board[1][2] == board[2][2] and board[0][2] is not None:         return board[0][2]     # Check diagonals     elif board[0][0] == board[1][1] and board[1][1] == board[2][2] and board[0][0] is not None:         return board[0][0]     elif board[0][2] == board[1][1] and board[1][1] == board[2][0] and board[0][2] is not None:         return board[0][2]     else:         return None def terminal(board):     """     Returns True if game is over, False otherwise.     """     if winner(board) is None:         return False     else:         return True def utility(board):     """     Returns 1 if X has won the game, -1 if O has won, 0 otherwise.     """     if terminal(board):         if winner(board) == X:             return 1         elif winner(board) == O:             return -1         else:             return 0 def minimax(board):     """     the Minimax algorithm instead of selecting at random     """     if terminal(board):         print('Nodes traversed:', 1)         return None     else:         best_result = minimax_step(board, X == player(board))         print('Nodes traversed:', best_result[2])         return best_result[0] def minimax_step(board, maximizing):     if terminal(board):         return [None, utility(board), 1]     if maximizing:         value = -10         best_action = None         traversed = 0         for action in actions(board):             next_board = result(board, action)             next_result = minimax_step(next_board, not maximizing)             traversed += next_result[2]             if next_result[1] > value:                 value = next_result[1]                 best_action = action         return [best_action, value, traversed + 1]     else:         value = 10         best_action = None         traversed = 0         for action in actions(board):             next_board = result(board, action)             next_result = minimax_step(next_board, not maximizing)             traversed += next_result[2]             if next_result[1] < value:                 value = next_result[1]                 best_action = action         return [best_action, value, traversed + 1] def minimax_alphabeta(board):     """     the Minimax-alphabeta algorithm instead of selecting at random     """     if terminal(board):         print('Nodes traversed:', 1)         return None     else:         best_result = minimax_alphabeta_step(board, -100, 100, X == player(board))         print('Nodes traversed:', best_result[2])         return best_result[0] def minimax_alphabeta_step(board, alpha, beta, maximizing):     if terminal(board):         return [None, utility(board), 1]     if maximizing:         value = -10         best_action = None         traversed = 0         for action in actions(board):             next_board = result(board, action)             next_result = minimax_alphabeta_step(next_board, alpha, beta, not maximizing)             traversed += next_result[2]             if next_result[1] > value:                 value = next_result[1]                 best_action = action             alpha = max(alpha, value)             if value >= beta:                 break         return [best_action, value, 1+ traversed]     else:         value = 10         best_action = None         traversed = 0         for action in actions(board):             next_board = result(board, action)             next_result = minimax_alphabeta_step(next_board, alpha, beta, not maximizing)             traversed += next_result[2]             if next_result[1] < value:                 value = next_result[1]                 best_action = action             beta = min(beta, value)             if value <= alpha:                 break         return [best_action, value, 1 + traversed]```