Problem description: The halving game

$$ Start with a number N

$$ Players take turns either decrementing N $($hint: N$-1)$ or replacing it with $($hint: N$/2)$

$$ The player that is left with $0$ wins

Requirement:

Write python codes to implement minimax policy.

$1.$ Let the player use human policy and the opponent use minimax policy

$2.$ Let both player and opponent use minimax policy

Hint:

Sample code has been provided in game.py$.$ Simply complete the recurse method in

minimaxPolicy$($game$,$ state$).$

Code:

class HalvingGame$($object$)$:

def $\_\_$init$\_\_($self$,$ N$)$:

self.N $=$ N

# state $=($player$,$ number$)$ where player $=+1($agent$)$ or $-1($opponent$)$

def startState$($self$)$:

return $(+1,$ self.N$)$

def actions$($self$,$ state$)$:

return $[\text{'}-\text{'},\text{'}/\text{'}]$

def succ$($self$,$ state, action$)$:

player, number $=$ state

if action$==\text{'}-\text{'}$:

return $(-$player, number $-1)$

elif action$==\text{'}/\text{'}$:

return $(-$player, number $//2)$

def isEnd$($self$,$ state$)$:

player, number $=$ state

return number $==0$

def utility$($self$,$ state$)$:

assert self.isEnd$($state$)$

player, number $=$ state

return player $*$ float$(\text{'}$inf$\text{'})$

def player$($self$,$ state$)$:

player, number $=$ state

return player

# policies

def simplePolicy$($game$,$ state$)$:

action $=\text{'}-\text{'}$

print$(\text{'}$simplePolicy: playing $\{\}\text{'}.$format$($action$))$

return action

def humanPolicy$($game$,$ state$)$:

while True:

action $=$ input$(\text{'}$humanPolicy: please input action: $\text{'})$

if action in game.actions$($state$)$:

return action

def minimaxPolicy$($game$,$ state$)$:

# recursively find $($utility$,$ bestAction$)$

def recurse$($state$)$:

# implement here

value, action $=$ recurse$($state$)$

print$(\text{'}$minimaxPolicy: action $=\{\},$ value $=\{\}\text{'}.$format$($action$,$ value$))$

return action

# main loop

policies $=\{$

#$+1$: humanPolicy,

$+1$: minimaxPolicy,

$-1$: minimaxPolicy

$\}$

game $=$ HalvingGame$(15)$

state $=$ game.startState$()$

while not game.isEnd$($state$)$:

print$(\text{'}=\text{'}*10,$ 'state $=\{\}\text{'}.$format$($state$))$

player $=$ game.player$($state$)$

policy $=$ policies$[$player$]$

action $=$ policy$($game$,$ state$)$

state $=$ game.succ$($state$,$ action$)$

print$(\text{'}$utility $=\{\}\text{'}.$format$($game$.$utility$($state$)))$