May-22-2021, 11:04 AM
(This post was last modified: May-22-2021, 11:04 AM by supuflounder.)
That helps a lot. I also added statements to print the result on each return statement, and got
The key takeaway here is the use of print statements to tell you what is really happening.
Output:Enter total number of leaf nodes=8
Enter Leaf Value 1/8: 3
Enter Leaf Value 2/8: 5
Enter Leaf Value 3/8: 6
Enter Leaf Value 4/8: 9
Enter Leaf Value 5/8: 1
Enter Leaf Value 6/8: 2
Enter Leaf Value 7/8: 0
Enter Leaf Value 8/8: -1
minimax(depth= 0 , nodeindex= 0 , True , [3, 5, 6, 9, 1, 2, 0, -1] , -1000 , 1000 )
.minimax(depth= 1 , nodeindex= 0 , False , [3, 5, 6, 9, 1, 2, 0, -1] , -1000 , 1000 )
..minimax(depth= 2 , nodeindex= 0 , True , [3, 5, 6, 9, 1, 2, 0, -1] , -1000 , 1000 )
...minimax(depth= 3 , nodeindex= 0 , False , [3, 5, 6, 9, 1, 2, 0, -1] , -1000 , 1000 )
... => [ 0 ] 3
...minimax(depth= 3 , nodeindex= 1 , False , [3, 5, 6, 9, 1, 2, 0, -1] , 3 , 1000 )
... => [ 1 ] 5
.. => 5
..minimax(depth= 2 , nodeindex= 1 , True , [3, 5, 6, 9, 1, 2, 0, -1] , -1000 , 5 )
...minimax(depth= 3 , nodeindex= 2 , False , [3, 5, 6, 9, 1, 2, 0, -1] , -1000 , 5 )
... => [ 2 ] 6
.. => 6
. => 5
.minimax(depth= 1 , nodeindex= 1 , False , [3, 5, 6, 9, 1, 2, 0, -1] , 5 , 1000 )
..minimax(depth= 2 , nodeindex= 2 , True , [3, 5, 6, 9, 1, 2, 0, -1] , 5 , 1000 )
...minimax(depth= 3 , nodeindex= 4 , False , [3, 5, 6, 9, 1, 2, 0, -1] , 5 , 1000 )
... => [ 4 ] 1
...minimax(depth= 3 , nodeindex= 5 , False , [3, 5, 6, 9, 1, 2, 0, -1] , 5 , 1000 )
... => [ 5 ] 2
.. => 2
. => 2
=> 5
The optimal value is : 5
This does not correspond to your output, but since I made no real changes in the code, I'm putting the code here:MAX, MIN = 1000, -1000 def indent(depth): for i in range(depth): print(".",sep="", end="") # Returns optimal value for current player # (Initially called for root and maximizer) def minimax(depth, nodeIndex, maximizingPlayer, values, alpha, beta): indent(depth) print("minimax(depth=", depth, ", nodeindex=", nodeIndex, ", ", maximizingPlayer, ", ", values, ", ", alpha, ", ", beta, ")" ) # Terminating condition. i.e # leaf node is reached if depth == 3: indent(depth) print(" => [", nodeIndex, "] ", values[nodeIndex]) return values[nodeIndex] if maximizingPlayer: best = MIN # Recur for left and right children for i in range(0, 2): val = minimax(depth + 1, nodeIndex * 2 + i, False, values, alpha, beta) best = max(best, val) alpha = max(alpha, best) # Alpha Beta Pruning if beta <= alpha: break indent(depth) print(" => ", best) return best else: best = MAX # Recur for left and # right children for i in range(0, 2): val = minimax(depth + 1, nodeIndex * 2 + i,True, values, alpha, beta) best = min(best, val) beta = min(beta, best) # Alpha Beta Pruning if beta <= alpha: break indent(depth) print(" => ", best) return best # Driver Code if __name__ == "__main__": scr = [] # List for Leaf Nodes x = int(input("Enter total number of leaf nodes=")) for i in range(0,x): y = int(input("Enter Leaf Value "+ str(i + 1) + "/" + str(x) + ": ")) scr.append(y) print("The optimal value is :", minimax(0, 0, True, scr, MIN, MAX))I do not understand why MIN and MAX are global variables, but I didn't try to debug the code. Looking at the output, perhaps you can figure out why it does not deliver the same result as you indicated that it should. I am very suspect of your use of MIN and MAX which you never change. But that's just a guess.
The key takeaway here is the use of print statements to tell you what is really happening.