C++: minimax with alpha-beta pruning
Minimax assumes two players alternate: the maximizing player picks the child with the highest value and the minimizing player picks the lowest. Alpha-beta pruning keeps two bounds: alpha, the best value the maximizer is already guaranteed, and beta, the best value the minimizer is already guaranteed.
C++
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
int visited = 0;
int search(const std::vector<int>& leaves, int depth, int index, bool maximizing,
int alpha, int beta, bool prune) {
if (depth == 3) {
++visited;
return leaves[index];
}
int best = maximizing ? INT_MIN : INT_MAX;
for (int child = 0; child < 2; ++child) {
int value = search(leaves, depth + 1, index * 2 + child, !maximizing, alpha, beta, prune);
if (maximizing) {
best = std::max(best, value);
alpha = std::max(alpha, best);
} else {
best = std::min(best, value);
beta = std::min(beta, best);
}
if (prune && beta <= alpha) {
break;
}
}
return best;
}
int main() {
std::vector<int> leaves = {3, 5, 6, 9, 1, 2, 0, -1};
visited = 0;
int plain = search(leaves, 0, 0, true, INT_MIN, INT_MAX, false);
std::cout << "minimax value " << plain << ", leaves visited " << visited << "\n";
visited = 0;
int pruned = search(leaves, 0, 0, true, INT_MIN, INT_MAX, true);
std::cout << "alpha-beta value " << pruned << ", leaves visited " << visited << "\n";
}