How Can I Programme A Minimax Algorithm For Nim Game Python?

I tried to programme a minimax algorithm in python. But it is so confusing. I am new to recursion functions. My mind structure has some error at somewhere but I could not solve it.

Solution 1:

The code is correct from the perspective of the max player, if the min player goes first. The way minimax works, the min layer should return the minimum of all its possible states (because the min player is also optimizing their move). So you shouldn't switch your min and max calls, but rather which player goes first.

Here is your state tree visualized: https://imgur.com/a/0iRFc.jpg (I apparently don't have enough rep to display the image). The top layer of your recursion will take

max(-250, -100)

and return -100. Because the game starts with the max player finishing his move with 2 in the stack, this makes sense. If you want to switch the return value to 100, you need to change the game such that the max player goes first (because in this game scenario, whoever goes first wins).

Solution 2:

I solved my problem. I needed to change value = min(value, minimax(x)) to value = max(value, minimax(x)) and 250 to -250. Problem solved.