6.7.5 Minimax and Alpha-Beta Pruning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

/*

Searches a finite two-player, zero-sum, perfect-information game tree using minimax and alpha-beta
pruning. Minimax assumes both players play optimally: the maximizing player chooses the child with
largest value, and the minimizing player chooses the child with smallest value.

Alpha-beta pruning computes the same value as minimax, but avoids exploring branches that cannot
affect the final answer. It is most effective when good moves are searched first.

The example game is "take $1$ or $2$ stones": starting with `stones` stones, players alternate
taking $1$ or $2$ stones, and the player who takes the last stone wins. The evaluation returns $1$
when the maximizing player wins and $-1$ when the minimizing player wins.

- `minimax(stones, maximizing)` returns the exact game-tree value, where `maximizing` indicates
  whose turn it is.
- `alpha_beta(stones, maximizing)` returns the same value using alpha-beta pruning.
- `best_take(stones)` returns an optimal first move using alpha-beta pruning, either $1$ or $2$, for
  positive `stones`.

Time Complexity:
- O(b^d) per call in the worst case, where $b$ is branching factor and $d$ is search depth.
  Alpha-beta can achieve O(b^{d/2}) with optimal move ordering.

Space Complexity:
- O(d) auxiliary recursion stack space.

*/

#include <algorithm>

int minimax(int stones, bool maximizing) {
  if (stones == 0) {
    return maximizing ? -1 : 1;
  }
  int best = maximizing ? -2 : 2;
  for (int take = 1; take <= 2 && take <= stones; take++) {
    int child = minimax(stones - take, !maximizing);
    best = maximizing ? std::max(best, child) : std::min(best, child);
  }
  return best;
}

int alpha_beta(int stones, bool maximizing, int alpha = -2, int beta = 2) {
  if (stones == 0) {
    return maximizing ? -1 : 1;
  }
  int value = maximizing ? -2 : 2;
  for (int take = 1; take <= 2 && take <= stones; take++) {
    int child = alpha_beta(stones - take, !maximizing, alpha, beta);
    if (maximizing) {
      value = std::max(value, child);
      alpha = std::max(alpha, value);
    } else {
      value = std::min(value, child);
      beta = std::min(beta, value);
    }
    if (alpha >= beta) {
      break;
    }
  }
  return value;
}

int best_take(int stones) {
  int best_move = 1, best_value = -2;
  for (int take = 1; take <= 2 && take <= stones; take++) {
    int value = alpha_beta(stones - take, false);
    if (value > best_value) {
      best_value = value;
      best_move = take;
    }
  }
  return best_move;
}

/*** Example Usage ***/

#include <cassert>

int main() {
  assert(minimax(1, true) == 1);
  assert(minimax(3, true) == -1);
  for (int stones = 1; stones <= 10; stones++) {
    assert(minimax(stones, true) == alpha_beta(stones, true));
  }
  assert(best_take(4) == 1);  // Move to losing state with 3 stones.
  assert(best_take(5) == 2);  // Move to losing state with 3 stones.
  return 0;
}