C: game search with negamax and a memo table

Before you start

C recursion and arrays.

Solve a take-away game and count how many positions memoization saves.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

In the take-away game a pile has n sticks, a move takes one to three sticks, and the player who takes the last stick wins. Negamax scores a position from the point of view of the player to move: +1 for a forced win and −1 for a forced loss. A position is worth the best of the negated values of the positions each move leads to.

Plain recursion explores the same smaller piles again and again, so the number of calls grows exponentially. A memo table stores the value of every pile once it is computed, which turns the search into a linear number of calls. The result is the same: piles that are multiples of four are lost for the player to move.

Code example

#include <stdio.h>

static long calls = 0;
static int memo[64];
static int known[64];

static int negamax(int sticks) {
  calls++;
  if (sticks == 0) {
    return -1;
  }
  int best = -1;
  for (int take = 1; take <= 3 && take <= sticks; take++) {
    int value = -negamax(sticks - take);
    if (value > best) {
      best = value;
    }
  }
  return best;
}

static int negamax_memo(int sticks) {
  calls++;
  if (sticks == 0) {
    return -1;
  }
  if (known[sticks]) {
    return memo[sticks];
  }
  int best = -1;
  for (int take = 1; take <= 3 && take <= sticks; take++) {
    int value = -negamax_memo(sticks - take);
    if (value > best) {
      best = value;
    }
  }
  known[sticks] = 1;
  memo[sticks] = best;
  return best;
}

int main(void) {
  for (int n = 1; n <= 8; n++) {
    printf("%d:%s ", n, negamax(n) == 1 ? "win" : "lose");
  }
  printf("\n");

  calls = 0;
  int plain = negamax(20);
  long plain_calls = calls;

  calls = 0;
  int cached = negamax_memo(20);
  long memo_calls = calls;

  printf("n=20 same answer: %d\n", plain == cached);
  printf("calls: plain %ld, memoized %ld\n", plain_calls, memo_calls);
  return 0;
}

Output

1:win 2:win 3:win 4:lose 5:win 6:win 7:win 8:lose
n=20 same answer: 1
calls: plain 266079, memoized 58

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <stdio.h>

3static long calls = 0;

4static int memo[64];

5static int known[64];

7static int negamax(int sticks) {

8 calls++;

9 if (sticks == 0) {

10 return -1;

11 }

12 int best = -1;

13 for (int take = 1; take <= 3 && take <= sticks; take++) {

14 int value = -negamax(sticks - take);

15 if (value > best) {

16 best = value;

17 }

18 }

19 return best;

20}

22static int negamax_memo(int sticks) {

23 calls++;

24 if (sticks == 0) {

25 return -1;

26 }

27 if (known[sticks]) {

28 return memo[sticks];

29 }

30 int best = -1;

31 for (int take = 1; take <= 3 && take <= sticks; take++) {

32 int value = -negamax_memo(sticks - take);

33 if (value > best) {

34 best = value;

35 }

36 }

37 known[sticks] = 1;

38 memo[sticks] = best;

39 return best;

40}

42int main(void) {

43 for (int n = 1; n <= 8; n++) {

44 printf("%d:%s ", n, negamax(n) == 1 ? "win" : "lose");

45 }

46 printf("\n");

48 calls = 0;

49 int plain = negamax(20);

50 long plain_calls = calls;

52 calls = 0;

53 int cached = negamax_memo(20);

54 long memo_calls = calls;

56 printf("n=20 same answer: %d\n", plain == cached);

57 printf("calls: plain %ld, memoized %ld\n", plain_calls, memo_calls);

58 return 0;

59}

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
With no sticks left the previous player took the last one, so the player to move has lost: −1.	`—`	—
The value of a move is the negation of the opponent's value in the resulting position.	`—`	—
Positions 4 and 8 are lost for the player to move; all the others are wins.	`—`	1:win 2:win 3:win 4:lose 5:win 6:win 7:win 8:lose
A position solved before is answered from the table without searching again.	`—`	1:win 2:win 3:win 4:lose 5:win 6:win 7:win 8:lose
Both searches agree, so memoization changes the cost, not the result.	`—`	1:win 2:win 3:win 4:lose 5:win 6:win 7:win 8:lose n=20 same answer: 1
The memoized search needs far fewer calls.	`—`	1:win 2:win 3:win 4:lose 5:win 6:win 7:win 8:lose n=20 same answer: 1 calls: plain 266079, memoized 58

Behind the scenes

How C processes this code

The C compiler produces a native program. Variables occupy memory, and execution enters main.

Cost and common mistakes

Plain: exponential, about 1.84ⁿ calls. Memoized: O(n) calls.

Forgetting to reset the calls counter between the two runs would mix their counts.
A memo table indexed by the pile size only works because the position is fully described by that number. Games with larger states use a hash table keyed by the position.

Try it yourself

Which pile sizes are losing for the player to move?

Reveal answer and reasoning

The multiples of four. Whatever the player takes, the opponent takes the complement to four and keeps the pile a multiple of four.