CODEWITHSUNDEEP
pythonminimax
amitt1236
amitt1236

Reputation: 29

minimax algorithm understanding

I'm having a hard time understanding the recursive part of the minimax Algorithm.

def minimax(state, depth, player):
    if player == MAX:
        best = [-1, -1, -infinity]
    else:
        best = [-1, -1, +infinity]

    if depth == 0 or game_over(state):
        score = evaluate(state)
        return [-1, -1, score]

    for cell in empty_cells(state):
        x, y = cell[0], cell[1]
        state[x][y] = player
        score = minimax(state, depth - 1, -player)
        state[x][y] = 0
        score[0], score[1] = x, y

        if player == MAX:
            if score[2] > best[2]:
                best = score
        else:
            if score[2] < best[2]:
                best = score

    return best

for example this code. when the function calls itself inside the loop, the loop keeps going to state[x][y] = 0 ? what's stooping the function? or what actions the recursive part of the function does? tnx

Upvotes: 1

Views: 145

Answers (1)

jferard
jferard

Reputation: 8180

You have recursive function, that is a function that calls itself with (hopefully) different arguments. The question is: how do we prove that such a function ever stops? The generic proof is a proof by induction: let n be an argument of the function f. If you can show that:

  • f(0) is defined
  • recursive calls inside f(n) are always of type f(k) where 0 <= k < n

You have a proof by induction (strong version) that f(n) is defined for every n >= 0.

In your function, depth is a good candidate for n. But len(empty_cells(state)) too. Look at the two statements that surround the recursive call:

state[x][y] = player
...
state[x][y] = 0

This is a common technique: you update the state before the call, and restore the state after the call (assumption: a cell (x, y) is empty if state[x][y] == 0). Hence, the number of empty cells of the recursive call is lower than the current number of empty cells.

And you might have a game_over state.

Without additional information, it is impossible to say what will stop the recursive calls: depth reaches 0, there's a game_over or there are no empty cells left.

Note that depth might be negative at the beginning, game_over might never occur, but it is certain that the function will stop when the number of empty cells is 0 (if it has not stopped before).

I think you're having a hard time understanding this piece of code because the score variable is sometimes a number, sometimes a 3 elements list (and should probably be a tuple in this case). Furthermore, the stop condition could be at the beginning of the function.

This version should be clearer because it hides the behavior variations caused by +/-player:

def minimax(state, depth, player):
    if depth == 0 or game_over(state):
        score = evaluate(state)
        return [-1, -1, score]

    best = [-1, -1, initial_score(player)]
    for x, y in empty_cells(state):
        state[x][y] = player # fill this cell
        _, _, score = minimax(state, depth - 1, -player) # extract the score
        cur = [x, y, score]
        state[x][y] = 0 # restore state

        if is_better(player, cur, best):
            best = cur

    return best

def initial_score(player):
    if player == MAX:
        return -infinity
    else 
        return +infinity

def is_better(player, first, second):
    if player == MAX:
        return first[2] > second[2]
    else:
        return first[2] < second[2]

Much could be rewritten, but we're not https://codereview.stackexchange.com...

Upvotes: 2

Related Questions