# Tic$-$Tac$-$Toe with Minimax Algorithm and Alpha$-$Beta Pruning

import numpy as np

# Initialize the board $($empty $=0,$ X $=1,$ O $=-1)$

def initialize$\_$board$()$:

return np$.$zeros$((3,3),$ dtype$=$int$)$

# Check for win condition $(1$ for X$,-1$ for O$,0$ for draw or incomplete$)$

def check$\_$winner$($board$)$:

for i in range$(3)$:

# Check rows and columns

if abs$($sum$($board$[$i$,$ :$]))==3$:

return board$[$i$,0]$

if abs$($sum$($board$[$:$,$ i$]))==3$:

return board$[0,$ i$]$

# Check diagonals

if abs$($sum$($board$.$diagonal$()))==3$:

return board$[0,0]$

if abs$($sum$($np$.$fliplr$($board$).$diagonal$()))==3$:

return board$[0,2]$

# No winner

return $0$

# Check if the board is full $($draw$)$

def is$\_$board$\_$full$($board$)$:

return not $($board $==0).$any$()$

# Minimax function with Alpha$-$Beta Pruning

def minimax$($board$,$ depth, alpha, beta, is$\_$maximizing$)$:

winner $=$ check$\_$winner$($board$)$

if winner $!=0$:

return winner # return the utility value: $+1$ for X$,-1$ for O

if is$\_$board$\_$full$($board$)$:

return $0$ # Draw case

if is$\_$maximizing: # Maximizing for X

max$\_$eval $=-$np$.$inf

for i in range$(3)$:

for j in range$(3)$:

if board$[$i$,$ j$]==0$: # Check if the cell is empty

board$[$i$,$ j$]=1$ # X makes a move

eval $=$ minimax$($board$,$ depth $+1,$ alpha, beta, False$)$

board$[$i$,$ j$]=0$ # Undo move

max$\_$eval $=$ max$($max$\_$eval, eval$)$

alpha $=$ max$($alpha$,$ eval$)$

if beta $<=$ alpha:

break # Beta cut$-$off

return max$\_$eval

else: # Minimizing for O

min$\_$eval $=$ np$.$inf

for i in range$(3)$:

for j in range$(3)$:

if board$[$i$,$ j$]==0$: # Check if the cell is empty

board$[$i$,$ j$]=-1$ # O makes a move

eval $=$ minimax$($board$,$ depth $+1,$ alpha, beta, True$)$

board$[$i$,$ j$]=0$ # Undo move

min$\_$eval $=$ min$($min$\_$eval, eval$)$

beta $=$ min$($beta$,$ eval$)$

if beta $<=$ alpha:

break # Alpha cut$-$off

return min$\_$eval

# Best move for X $($Maximizing player$)$

def best$\_$move$($board$)$:

best$\_$val $=-$np$.$inf

move $=(-1,-1)$

for i in range$(3)$:

for j in range$(3)$:

if board$[$i$,$ j$]==0$: # If cell is empty

board$[$i$,$ j$]=1$ # X makes a move

move$\_$val $=$ minimax$($board$,0,-$np$.$inf, np$.$inf, False$)$

board$[$i$,$ j$]=0$ # Undo move

if move$\_$val $>$ best$\_$val:

move $=($i$,$ j$)$

best$\_$val $=$ move$\_$val

return move

# Display the board

def display$\_$board$($board$)$:

chars $=\{1$: $\text{'}$X$\text{'},-1$: $\text{'}$O$\text{'},0$: $\text{'}\text{'}\}$

for row in board:

print$(\text{'}|\text{'}.$join$([$chars$[$cell$]$ for cell in row$]))$

print$(\text{'}-\text{'}*9)$

# Simulate a game

def play$\_$game$()$:

board $=$ initialize$\_$board$()$

current$\_$player $=1$ # X starts

while check$\_$winner$($board$)==0$ and not is$\_$board$\_$full$($board$)$:

display$\_$board$($board$)$

if current$\_$player $==1$: # X$\text{'}$s turn $($AI$)$

i$,$ j $=$ best$\_$move$($board$)$

print$($f$"$X moves to $(\{$i$\},\{$j$\})")$

board$[$i$,$ j$]=1$

else: # O$\text{'}$s turn $($random play for demo purposes$)$

i$,$ j $=$ np$.$random.choice$($np$.$where$($board $==0)[0]),$ np$.$random.choice$($np$.$where$($board $==0)[1])$

print$($f$"$O moves to $(\{$i$\},\{$j$\})")$

board$[$i$,$ j$]=-1$

current$\_$player $*=-1$ # Switch players

display$\_$board$($board$)$

winner $=$ check$\_$winner$($board$)$

if winner $==1$:

print$("$X wins!"$)$

elif winner $==-1$:

print$("$O wins!"$)$

else:

print$("$It$\text{'}$s a draw!"$)$

# Run the simulation

play$\_$game$()$

give the decision tree precisely according to the code and output for the code hand drawn according to these rules:

Decision Tree:

A hand$-$drawn or digital decision tree that represents a full or partial game of Tic$-$Tac$-$Toe.Clearly indicate where the Minimax algorithm evaluated game states and where Alpha$-$beta pruning was applied.