minimax Algorithm
The minimax algorithm is a decision-making strategy used in various applications, particularly in two-player, zero-sum games such as chess, tic-tac-toe, and connect four. It is a recursive algorithm that explores all possible moves in a game tree, assuming that both players are playing optimally to minimize their opponent's chances of winning while maximizing their own. The algorithm evaluates the game's state at each level of the tree, assigning a numerical value to represent the advantage or disadvantage of a given position. By traversing the tree and selecting the move that leads to the best possible outcome, the minimax algorithm aims to identify the optimal move for a player in any given game state.
In the minimax algorithm, each level of the game tree represents a turn for one of the players, with the root node representing the current game state. The algorithm proceeds by exploring the tree in a depth-first manner, evaluating the leaf nodes (i.e., game states where the game has ended or a predefined depth limit has been reached) and propagating the values up the tree. At each level, the player whose turn it is will choose the move that results in the best score for them. If it is the maximizing player's turn, they will select the move with the highest score, while the minimizing player will choose the move with the lowest score. This back-and-forth evaluation continues until the algorithm reaches the root node, at which point the optimal move is selected based on the propagated scores. By considering all possible moves and assuming perfect play from both players, the minimax algorithm allows a player to make the best possible decision in a competitive game environment.
import math
""" Minimax helps to achieve maximum score in a game by checking all possible moves
depth is current depth in game tree.
nodeIndex is index of current node in scores[].
if move is of maximizer return true else false
leaves of game tree is stored in scores[]
height is maximum height of Game tree
"""
def minimax(Depth, nodeIndex, isMax, scores, height):
if Depth == height:
return scores[nodeIndex]
if isMax:
return max(
minimax(Depth + 1, nodeIndex * 2, False, scores, height),
minimax(Depth + 1, nodeIndex * 2 + 1, False, scores, height),
)
return min(
minimax(Depth + 1, nodeIndex * 2, True, scores, height),
minimax(Depth + 1, nodeIndex * 2 + 1, True, scores, height),
)
if __name__ == "__main__":
scores = [90, 23, 6, 33, 21, 65, 123, 34423]
height = math.log(len(scores), 2)
print("Optimal value : ", end="")
print(minimax(0, 0, True, scores, height))
