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.
#include <cmath>
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::vector;
int minimax(int depth, int node_index, bool is_max, vector<int> scores,
int height) {
if (depth == height)
return scores[node_index];
int v1 = minimax(depth + 1, node_index * 2, !is_max, scores, height);
int v2 = minimax(depth + 1, node_index * 2 + 1, !is_max, scores, height);
return is_max ? max(v1, v2) : min(v1, v2);
}
int main() {
vector<int> scores = { 90, 23, 6, 33, 21, 65, 123, 34423 };
int height = log2(scores.size());
cout << "Optimal value: " << minimax(0, 0, true, scores, height) << endl;
}
