Java: game-tree search with minimax (negamax)
Search every move in a take-away game to find which positions are winning for the player to move.
On this page
Java recursion.
- Search every move in a take-away game to find which positions are winning for the player to move.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
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.
The game is Nim with a pile of sticks. A move takes one, two, or three sticks, and whoever takes the last stick wins. When the pile is empty, the player to move has already lost, so the value is -1. The search shows that the multiples of four are lost positions for the player to move, because whatever they take, the opponent can restore a multiple of four.
Code example
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"));
}
}
}sticks 1: win sticks 2: win sticks 3: win sticks 4: lose sticks 5: win sticks 6: win sticks 7: win sticks 8: lose
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
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")); } }}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
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| No sticks left means the previous player took the last one and won, so the player to move loses. | — | — | |
| Try each move and negate the opponent's value; keep the best for the current player. | value of a move = -(value of the opponent's position) | — | |
| For 1 to 3 sticks the mover takes them all and wins. For 4 every move leaves the opponent a win. | losing positions: 4 and 8 | sticks 1: win sticks 2: win sticks 3: win sticks 4: lose sticks 5: win sticks 6: win sticks 7: win sticks 8: lose |
Behind the scenes
How Java processes this code
The Java compiler produces bytecode. The JVM loads the class and invokes its main method.
Cost and common mistakes
Exponential: the tree has up to 3^n nodes, which is why pruning and memoization matter.
- Plain minimax revisits the same positions many times. Memoization or alpha-beta pruning makes bigger games feasible.
- Negamax only works for zero-sum games where one player's gain is exactly the other's loss.
Try it yourself
Which move should a player make with 6 sticks?
Reveal answer and reasoning
Take 2, leaving 4 sticks, which is a lost position for the opponent.