C: game search with negamax and a memo table
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.
C
#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;
}