position is a board object. This is the current board configuration. Given the current board configuration, the minimax should provide the optimal board configuration $($best board configuration$)$ as we play.In this assignment, you will be able to develop an AI Checkers application using minimax algorithm.

The zip file contains $3$ folders $($assets$,$ checkers, minimax$)$ and the $.$py file main.py

assets folder: contains resources for the game

checkers folder: contains the following $.$py files

py $=$ the state of the board and board graphics

py $=$ defines constant parameters for the game

py $=$ defines the rules of the game

py $=$ defines piece drawing instructions and moving rules

minimax folder: contains the following $.$py file

py $=$ contains the minimax algorithm. This is the file you should modify.

main.py $=$ file needed to run the simulation.

Part $1)$ In this part, you need to complete the minimax algorithm in the algorithm.py file. The current function is defined as:

def minimax$($position$,$ depth, max$\_$player, game$)$:

# if we are in the root node $($depth $==0)$ and the game hasn't finished yet $($position$.$winner$()!=$ None$)$

# we return the current board position and the evaluation of that position.

if depth $==0$ or position.winner$()!=$ None:

return position.evaluate$(),$ position

if max$\_$player:

# initialize the max evaluation at $-$inf. This is needed when we compare with next evaluations.

maxEval $=$ float$(\text{'}-$inf'$)$

# best$\_$move will store the best move we could make. It is initialized as None

best$\_$move $=$ None

# the function get$\_$all$\_$moves will provide all possible moves of a given player $($WHITE$,$ in this case$)$

# from its current position. The third argument $("$game$")$ is used so that we can draw and update the board game.

for move in get$\_$all$\_$moves$($position$,$ WHITE, game$)$:

# This is a recursive call

# Remember: we only evaluate a position using the minimax algorithm when we reach the end of the tree $($root node$).$

# Note: minimax returns the best reward $($maxEval in this case, the maximum$)+$ the best move that led to that reward.

# In this way, the $[0]$ below means that we only pick the first output $($maxEval$).$

evaluation $=$ minimax$($move$,$ depth$-1,$ False, game$)[0]$

maxEval $=$ max$($maxEval$,$ evaluation$)$

# If the maximum reward we found is equal to the current reward,

# this means that the best move is the current move.

# In this way, we can keep track of the best moves the AI agent can make during the game.

if maxEval $==$ evaluation:

best$\_$move $=$ move

return maxEval, best$\_$move

else:

#### INSERT CODE HERE ####

return minEval, best$\_$move

where:

$->$depth represents how far we are extending the minimax tree. Every time we evaluate the minimax algorithm, we will decrease the depth by $1.$ Remember: we only evaluate a position when we reach the end of the tree $($root node$).$

$->$max$\_$player is a boolean value $($True$/$False$)$ that selects the player $($max$\_$player, if we are maximizing or min$\_$player if we are minimizing the reward.

$->$game is an object defined in py and is used to draw and update the board as we play.

Given the max$\_$player script, add the min$\_$player part to complete the minimax algorithm.

Part $2)$ Now that the algorithm is completed and running, change the depth parameter of the minimax tree main.py to $3$ and then to $4,$ and discuss your findings.

main.py:

import pygame

from checkers.constants import WIDTH, HEIGHT, SQUARE$\_$SIZE, RED, WHITE

from checkers.game import Game

from minimax.algorithm import minimax

FPS $=60$

WIN $=$ pygame.display.set$\_$mode$(($WIDTH$,$ HEIGHT$))$

pygame.display.set$\_$caption$(\text{'}$Checkers$\text{'})$

def get$\_$row$\_$col$\_$from$\_$mouse$($pos$)$:

x$,$ y $=$ pos

row $=$ y $//$ SQUARE$\_$SIZE

col $=$ x $//$ SQUARE$\_$SIZE

return row, col

def main$()$:

run $=$ True

clock $=$ pygame.time.Clock$()$

game $=$ Game$($WIN$)$

depth $=2$

while run:

clock.tick$($FPS$)$

if game.turn $==$ WHITE:

value, new$\_$board $=$ minimax$($game$.$get$\_$board$(),$ depth, WHITE, game$)$

game.ai$\_$move$($new$\_$board$)$

if game.winner$()!=$ None:

print$($game$.$winner$())$

run $=$ False

for event in pygame.event.get$()$:

if event.type $==$ pygame.QUIT:

run $=$ False

if event.type $==$ pygame.MOUSEBUTTONDOWN:

pos $=$ pygame.mouse.get$\_$pos$()$

row, col $=$ get$\_$row$\_$col$\_$from$\_$mouse$($pos$)$

game.select$($row$,$ col$)$

game.update$()$

pygame.quit$()$

main$()$