How to achieve a value in recursion function?

Question

I have tried to program minimax nim game with Python. I am almost done with the codes. However, I could not solve a problem, which is so tricky. I could not reach 'best movement' of the algorithm. I started with (5, Max) position and the algorithm output should be (4, Min). My algorithm solves whole trees with utility values but could not return to the best movement.

def startposition():
    return 5, 'max'


def terminalstate(state):
    if state == (0, 'min') or state == (0, 'max'):
        return True
    else:
        return False


def minimax(state):
    turn,heap=state
    if terminalstate(state):
        return utilitystatic(state)
    else:
        if heap == 'min':
            value = 250
            for x in successorsgenerator(state):
                value = min(value, minimax(x))
            result = state, value
        elif heap == 'max':
            value = -250
            for x in successorsgenerator(state):
                value = max(value, minimax(x))
            result = state, value

        print(result)
    return value


def utilitystatic(state):
    turn, heap = state
    assert terminalstate(state)
    if state[1] == 'max':
        return -100
    elif state[1] == 'min':
        return 100
    assert False


def successorsgenerator(state):
    successors = []
    state = toggle(state)
    newstate = decrease(state)
    i = 0
    while newstate[0] >= 0 and i < 3:
        successors.append(newstate)
        i += 1
        newstate = decrease(newstate)
    print('successors:', successors)
    return successors


def toggle(state):
    state = list(state)
    state[1] = 'min' if state[1] == 'max' else 'max'
    state = tuple(state)
    return state


def decrease(state):
    state = state[:0] + (state[0] - 1,) + state[1:2]
    return state


stick = startposition()
result = minimax(stick)
print('result:', result)

Possible duplicate of [How can I programme a minimax algorithm for nim game python?](https://stackoverflow.com/questions/48957432/how-can-i-programme-a-minimax-algorithm-for-nim-game-python) — Mulan, Feb 24 '18 at 19:27
@naomik they both belong to me. But this is a different question. — Vural Erdogan, Feb 25 '18 at 01:55

score 1 · Answer 1 · answered Mar 30 '18 at 23:24

If you don't want to store the entire sequence of moves in memory (which is often/usually unnecessary), just start off by generating the possible children of your current game state. Don't run minimax on your current state, just find the possible next moves. Let's imagine there are 3 possible moves from where you are (A, B, C). Now run the minimax algorithm on A and store the result along with a description of move A. Repeat for B and C. Now you should have something like:

A: 3.5
B: 1.2
C: -7.1

Remember these are not the heuristic values of the game states that immediately result from taking these actions. From the maximizing player's point of view, they represent the minimum value that the other player can force the current player to receive in the future once the current player chooses that move.

In this example, move A is the best for the maximizing player and move C is the best for the minimizing player.

Dennis Soemers · Accepted Answer · 2018-02-24T16:14:02.560

In minimax(), you're currently only finding the best (min or max values depending on player) values of successor states, but not yet memorizing exactly which successor states were the best at every depth level. If you don't store that information in memory, you won't be able to tell which move was the best. So, you'll want to try something like:

def minimax(state):
    turn,heap=state
    if terminalstate(state):
        return utilitystatic(state), _
    else:
        if heap == 'min':
            value = 250
            best_succ = None
            for x in successorsgenerator(state):
                val, _ = minimax(x)
                if val < value:
                    value = val
                    best_succ = x
            result = state, value
        elif heap == 'max':
            value = -250
            best_succ = None
            for x in successorsgenerator(state):
                val, _ = minimax(x)
                if val > value:
                    value = val
                    best_succ = x
            result = state, value

        print(result)
    return value, best_succ

With a few small changes, we now store the successor x that led to the best value in best_succ, and will therefore also be able to tell exactly which successor was the best (instead of only being able to tell what its value is)

How to achieve a value in recursion function?

2 Answers2