In this homework, you will develop a zero sum $($adversarial$)$ tic$-$tac$-$toe game $($noughts and crosses$)$ by implementing Minimax and its variation called Negamax algorithm which will consist of a MAX $($human$)$ and MIN $($a computer$)$ players. The human player MAX will play against the machine on a larger tic$-$tac$-$toe board where it will move first, and then the MIN player takes turns moving until the game is over. At the end of the game, points are awarded to the winning player and penalties are given to the loser. You will use the extensively studied elements to formulate your game scenario: S$0$: The initial state, which specifies how the game is set up at the start. TO$-$MOVE$($s$)$: The player whose turn it is to move in state s$.$ ACTIONS$($s$)$: The set of legal moves in state s$.$ RESULT$($s$,$a$)$: The transition model, which defines the state resulting from taking action a in state s$.$ IS$-$TERMINAL$($s$)$: A terminal test, which is true when the game is over and false otherwise. States where the game ended are called terminal states. UTILITY$($s$,$p$)$: A utility function $($also called an objective function or payoff function$),$ which defines the final numeric value to player p when the game ends in terminal state s$.$ In chess, the outcome is a win, loss, or draw, with values $1,0,$ or $1/22.$ Some games have a wider range of possible outcomesfor example, the payoffs in backgammon range from $0$ to $192.$Your solution should work for the board of any configuration from $3\backslash$times $3$ board size $5\backslash$times $5($or even larger size if your machine permits$).$ In a typical tic$-$tac$-$toe board game of size $3\backslash$times $3,$ the smart opponent $($utilizing Minimax$)$ tries for a draw $($i$.$e$.,$ the value of the root to be $0)$ which means at the end of the game no $3$ triplet cells $($in any of the horizontal, vertical, or diagonal direction$)$ have the connecting symbol chosen by a human player. In this game, you can either choose a nought $(0)$ or a cross $($X$)$ as your $($human player$)$ symbol. However, in a larger board, the end goal changes where the win is for the player who has the larger number of triplets with matching symbols. For example, in this sketch of a $4\backslash$times $4$ board on the right, both players still draw the game with the score of $3$ each.

Provide code for all provided variables

Add comments when possible

def get$\_$moves$($self$)$:

moved $=[]$

Code to add all the non empty cells to moves variables and return it to be used by your minimax or negax functions

return moves