How to implement the minimax algorithm in Java

The minimax algorithm seeks to identify the optimum move for a player by taking into account all feasible moves and their results. The algorithm makes the assumption that both players are attempting to maximize their individual gains or minimize their losses while playing optimally.

Note: This answer is just about the implementation of the minimax algorithm.

The fundamental premise of the minimax algorithm is to construct a game treeThe game tree exemplifies all the possible moves that is the current position and the results that spring from them. It can gauge strategies and make decisions on valuable information by representing the whole game state almost all the time. that depicts all potential moves and their outcomes. The program iteratively searches the game tree, assessing each node in light of the viewpoint of the current player. Each node is given a value that reflects the desirability of that specific move for the player.

Code example

Let’s look at the following code example in Java containing the implementation of the minimax algorithm.

import java.io.*;
class MiniMax {
static int minimax(int currdepth, boolean isMax,
			int scores[], int currnodeIndex, int h)
{
	
	if (currdepth == h)
		return scores[currnodeIndex];
	
	if (isMax)
	return Math.max(minimax(currdepth+1, false, scores, currnodeIndex*2, h),
			minimax(currdepth+1, false, scores, currnodeIndex*2 + 1, h));
    
	else
		return Math.min(minimax(currdepth+1, true, scores, currnodeIndex*2, h),
			minimax(currdepth+1, true, scores, currnodeIndex*2 + 1, h));
}
static int calculateHeight(int n)
{
return (n==1)? 0 : 1 + calculateHeight(n/2);
}
public static void main (String[] args) {
	
	int scores[] = {1, 1, 2, -3, 5, 7, -2, -4};
	int n = scores.length;
	int h = calculateHeight(n);
	int res = minimax(0, true, scores, 0, h);
	System.out.println( "The optimal value is : " +res);
	}
}

Let’s explain the above code:

Line 1: We import the necessary classes for input/output operations.
Line 3: We declare a class named MiniMax.
Lines 6–7: We declare the static method minimax(), which accepts the following arguments:
- currdepth: The current depth in the game tree
- currnodeIndex: The index of the current node in the scores array
- isMax: A boolean indicating whether the current move is for a maximizer
- scores: An array storing the game tree’s leaves
- h: The maximum height of the game tree
Lines 10–11: We determine whether the game tree’s maximum height, h, and currdepth are equivalent. If so, the procedure indicates that it has arrived at a leaf node by returning the value contained at the current node index in the scores array.
Lines 14–16: If the current move is for a maximizer, this line gets executed. In order to mimic both potential moves that the maximizer could make, it calls the minimax algorithm twice in a recursive fashion with updated parameters. It returns the highest number received from the two Math.max calls made recursively.
Lines 19–21: If the current move is for a minimizer and not a maximizer, then this line is executed. In order to simulate both potential steps that the minimizer could make, the minimax algorithm is called twice recursively with updated parameters. It gives back the lowest number produced by the two Math.min recursive calls.
Lines 25–28: We declare a static method named calculateHeight that takes an integer n as input. It recursively calculates the height of the game tree based on the number of elements (n) in the scores array. It returns the height of the game tree.
Lines 32–39: We have our main function. It invokes the minimax function to find the best value after initializing the scores array with numbers and using the calculateHeight method to figure out the height of the game tree. The best value is then printed to the console.

To better understand the implementation of this code example, see a visual dry run of this example.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments