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

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));elsereturn 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.

Copyright ©2024 Educative, Inc. All rights reserved

TRENDING TOPICS