MiniMaxAlgorithm.java

package com.thealgorithms.others;

import java.util.Arrays;
import java.util.Random;

/**
 * MiniMax is an algorithm used in artificial intelligence and game theory for
 * minimizing the possible loss for the worst case scenario. It is commonly used
 * in two-player turn-based games such as Tic-Tac-Toe, Chess, and Checkers.
 *
 * <p>
 * The algorithm simulates all possible moves in a game tree and chooses the
 * move that minimizes the maximum possible loss. The algorithm assumes both
 * players play optimally.
 *
 * <p>
 * Time Complexity: O(b^d) where b is the branching factor and d is the depth
 * <p>
 * Space Complexity: O(d) for the recursive call stack
 *
 * <p>
 * See more:
 * <ul>
 * <li><a href="https://en.wikipedia.org/wiki/Minimax">Wikipedia - Minimax</a>
 * <li><a href=
 * "https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/">
 * GeeksforGeeks - Minimax Algorithm</a>
 * </ul>
 *
 * @author aitofi (https://github.com/aitorfi)
 */
public final class MiniMaxAlgorithm {

 private static final Random RANDOM = new Random();

 /**
 * Game tree represented as an int array containing scores. Each array
 * element is a leaf node. The array length must be a power of 2.
 */
 private int[] scores;

 /**
 * The height of the game tree, calculated as log2(scores.length).
 */
 private int height;

 /**
 * Initializes the MiniMaxAlgorithm with 8 random leaf nodes (2^3 = 8).
 * Each score is a random integer between 1 and 99 inclusive.
 */
 public MiniMaxAlgorithm() {
 this(getRandomScores(3, 99));
 }

 /**
 * Initializes the MiniMaxAlgorithm with the provided scores.
 *
 * @param scores An array of scores representing leaf nodes. The length must be
 * a power of 2.
 * @throws IllegalArgumentException if the scores array length is not a power of
 * 2
 */
 public MiniMaxAlgorithm(int[] scores) {
 if (!isPowerOfTwo(scores.length)) {
 throw new IllegalArgumentException("The number of scores must be a power of 2.");
 }
 this.scores = Arrays.copyOf(scores, scores.length);
 this.height = log2(scores.length);
 }

 /**
 * Demonstrates the MiniMax algorithm with a random game tree.
 *
 * @param args Command line arguments (not used)
 */
 public static void main(String[] args) {
 MiniMaxAlgorithm miniMaxAlgorithm = new MiniMaxAlgorithm();
 boolean isMaximizer = true; // Specifies the player that goes first.
 int bestScore;

 bestScore = miniMaxAlgorithm.miniMax(0, isMaximizer, 0, true);

 System.out.println();
 System.out.println(Arrays.toString(miniMaxAlgorithm.getScores()));
 System.out.println("The best score for " + (isMaximizer ? "Maximizer" : "Minimizer") + " is " + bestScore);
 }

 /**
 * Returns the optimal score assuming that both players play their best.
 *
 * <p>
 * This method recursively evaluates the game tree using the minimax algorithm.
 * At each level, the maximizer tries to maximize the score while the minimizer
 * tries to minimize it.
 *
 * @param depth The current depth in the game tree (0 at root).
 * @param isMaximizer True if it is the maximizer's turn; false for minimizer.
 * @param index Index of the current node in the game tree.
 * @param verbose True to print each player's choice during evaluation.
 * @return The optimal score for the player that made the first move.
 */
 public int miniMax(int depth, boolean isMaximizer, int index, boolean verbose) {
 int bestScore;
 int score1;
 int score2;

 if (depth == height) { // Leaf node reached.
 return scores[index];
 }

 score1 = miniMax(depth + 1, !isMaximizer, index * 2, verbose);
 score2 = miniMax(depth + 1, !isMaximizer, (index * 2) + 1, verbose);

 if (isMaximizer) {
 // Maximizer player wants to get the maximum possible score.
 bestScore = Math.max(score1, score2);
 } else {
 // Minimizer player wants to get the minimum possible score.
 bestScore = Math.min(score1, score2);
 }

 // Leaf nodes can be sequentially inspected by
 // recursively multiplying (0 * 2) and ((0 * 2) + 1):
 // (0 x 2) = 0; ((0 x 2) + 1) = 1
 // (1 x 2) = 2; ((1 x 2) + 1) = 3
 // (2 x 2) = 4; ((2 x 2) + 1) = 5 ...
 if (verbose) {
 System.out.printf("From %02d and %02d, %s chooses %02d%n", score1, score2, (isMaximizer ? "Maximizer" : "Minimizer"), bestScore);
 }

 return bestScore;
 }

 /**
 * Returns an array of random numbers whose length is a power of 2.
 *
 * @param size The power of 2 that will determine the length of the array
 * (array length = 2^size).
 * @param maxScore The maximum possible score (scores will be between 1 and
 * maxScore inclusive).
 * @return An array of random numbers with length 2^size.
 */
 public static int[] getRandomScores(int size, int maxScore) {
 int[] randomScores = new int[(int) Math.pow(2, size)];

 for (int i = 0; i < randomScores.length; i++) {
 randomScores[i] = RANDOM.nextInt(maxScore) + 1;
 }

 return randomScores;
 }

 /**
 * Calculates the logarithm base 2 of a number.
 *
 * @param n The number to calculate log2 for (must be a power of 2).
 * @return The log2 of n.
 */
 private int log2(int n) {
 return (n == 1) ? 0 : log2(n / 2) + 1;
 }

 /**
 * Checks if a number is a power of 2.
 *
 * @param n The number to check.
 * @return True if n is a power of 2, false otherwise.
 */
 private boolean isPowerOfTwo(int n) {
 return n > 0 && (n & (n - 1)) == 0;
 }

 /**
 * Sets the scores array for the game tree.
 *
 * @param scores The array of scores. Length must be a power of 2.
 * @throws IllegalArgumentException if the scores array length is not a power of
 * 2
 */
 public void setScores(int[] scores) {
 if (!isPowerOfTwo(scores.length)) {
 throw new IllegalArgumentException("The number of scores must be a power of 2.");
 }
 this.scores = Arrays.copyOf(scores, scores.length);
 height = log2(this.scores.length);
 }

 /**
 * Returns a copy of the scores array.
 *
 * @return A copy of the scores array.
 */
 public int[] getScores() {
 return Arrays.copyOf(scores, scores.length);
 }

 /**
 * Returns the height of the game tree.
 *
 * @return The height of the game tree (log2 of the number of leaf nodes).
 */
 public int getHeight() {
 return height;
 }
}