C++: minimax with alpha-beta pruning

Search a game tree and skip branches that cannot change the result.

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";
}

Output

minimax value 5, leaves visited 8
alpha-beta value 5, leaves visited 5

Explanation

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.

When beta becomes less than or equal to alpha, the remaining children of the current node cannot affect the final answer, so they are skipped. Pruning never changes the value at the root; it only avoids work. The tree here is a complete binary tree of depth 3 whose eight leaf values are stored in an array.

Explore the dry run

Guided walkthroughReady

1#include <algorithm>

2#include <climits>

3#include <iostream>

4#include <vector>

6int visited = 0;

8int search(const std::vector<int>& leaves, int depth, int index, bool maximizing,

9 int alpha, int beta, bool prune) {

10 if (depth == 3) {

11 ++visited;

12 return leaves[index];

13 }

14 int best = maximizing ? INT_MIN : INT_MAX;

15 for (int child = 0; child < 2; ++child) {

16 int value = search(leaves, depth + 1, index * 2 + child, !maximizing, alpha, beta, prune);

17 if (maximizing) {

18 best = std::max(best, value);

19 alpha = std::max(alpha, best);

20 } else {

21 best = std::min(best, value);

22 beta = std::min(beta, best);

23 }

24 if (prune && beta <= alpha) {

25 break;

26 }

27 }

28 return best;

29}

31int main() {

32 std::vector<int> leaves = {3, 5, 6, 9, 1, 2, 0, -1};

34 visited = 0;

35 int plain = search(leaves, 0, 0, true, INT_MIN, INT_MAX, false);

36 std::cout << "minimax value " << plain << ", leaves visited " << visited << "\n";

38 visited = 0;

39 int pruned = search(leaves, 0, 0, true, INT_MIN, INT_MAX, true);

40 std::cout << "alpha-beta value " << pruned << ", leaves visited " << visited << "\n";

41}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Depth 3 is a leaf: return its stored value and count the visit.	`—`	—
The maximizer records the best value it can already guarantee.	`—`	—
Once the minimizer can hold the value at or below what the maximizer already has, the siblings are irrelevant.	`—`	—
Plain minimax visits all 8 leaves.	`—`	minimax value 5, leaves visited 8
Alpha-beta reaches the same value 5 after visiting only 5 leaves: 3, 5, and 6 on the left, then 1 and 2 on the right.	`—`	minimax value 5, leaves visited 8 alpha-beta value 5, leaves visited 5

Cost and common mistakes

Plain minimax visits b^d leaves. With perfect ordering alpha-beta visits about b^(d/2).

Pruning works best when good moves are tried first. With worst-case ordering it prunes nothing.
The values are shared between both searches only through the visited counter, so remember to reset it between runs.

Try it yourself

Does pruning ever change the root value?

Reveal answer and reasoning

No. Alpha-beta returns exactly the minimax value; it only skips branches that cannot affect it.

C++: minimax with alpha-beta pruning

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading