Java: game-tree search with minimax (negamax)
In a two-player game with perfect information, minimax searches the tree of moves. A player to move picks the move that is best for them, assuming the opponent also plays their best. Negamax is a compact form for zero-sum games: the value of a position for the player to move is the best of the negated values of the positions their moves lead to.
Java
class Main {
// Value for the player to move: +1 means a forced win, -1 means a forced loss.
static int negamax(int sticks) {
if (sticks == 0) {
return -1;
}
int best = -1;
for (int take = 1; take <= Math.min(3, sticks); take++) {
best = Math.max(best, -negamax(sticks - take));
}
return best;
}
public static void main(String[] args) {
for (int n = 1; n <= 8; n++) {
System.out.println("sticks " + n + ": " + (negamax(n) == 1 ? "win" : "lose"));
}
}
}