If you want to write a program that is able to play a strategy game, there are good chances that you will be looking at a Minimax algorithm. This is especially true when it comes to games like chess, where variations of the Minimax algorithm are what is used to build the strongest chess-playing programs in existence. In this article, I will look at implementing the basic version of the Minimax algorithm with Java.

## Minimax Algorithm – a quick introduction

Minimax is a simple algorithm that tells you which move to play in a game. A detailed explanation is available on Wikipedia, but here is my quick, less rigorous outline:

- Take a game where you and your opponent take alternate turns
- Each time you take a turn you choose the best possible move (max)
- Each time your opponent takes a turn, the worst move for you is chosen (min), as it benefits your opponent the most
- Looking forward and using these assumptions- which moves leads you to victory?

Minimax is basically doing what I described above, but with a simple algorithm. In this article, I will implement the most basic version of Minimax where I omit the two possible improvements:

- I will look forward through the entire game tree, finding the optimal strategy (impossible in more complicated games).
- I will not use any pruning of branches (inefficient in practical, non-trivial scenarios).

Stopping rules and pruning can be added in the future when I use the algorithm to play chess or work with another non-trivial game.

## Implementing Minimax with Java

Based on the pseudocode in “Artifical Intelligence: The Modern Approach” (Amazon), I have decided to implement the template for the algorithm. Written in Java, it can look like this:

public final class MinimaxTemplate { private MinimaxTemplate() {} public static State minimaxDecision(State state) { return state.getActions().stream() .max(Comparator.comparing(MinimaxTemplate::minValue)).get(); } private static double maxValue(State state) { if(state.isTerminal()){ return state.getUtility(); } return state.getActions().stream() .map(MinimaxTemplate::minValue) .max(Comparator.comparing(Double::valueOf)).get(); } private static double minValue(State state) { if(state.isTerminal()){ return state.getUtility(); } return state.getActions().stream() .map(MinimaxTemplate::maxValue) .min(Comparator.comparing(Double::valueOf)).get(); } //State Class }

You can call *minimaxDecision *with a *State* object representing the current state of the game.

To get a usable implementation of Minimax you need to implement this *State* object template:

public static class State { public State(){ //create a state } Collection<State> getActions(){ List<State> actions = new LinkedList<>(); //generate actions return actions; } boolean isTerminal() { //add some logic return false; } double getUtility() { //add some logic return 0; } }

## Solving a simple game with Minimax

While reading different articles on the subject I found Introduction to Minimax Algorithm by Baeldung which had a simple game described. This game inspired me to create something very similar:

- You start with the number
- Two players can reduce this number by the value 3, 4 or 5
- The number can’t go down below 0
- A player that can’t make a move loses

The Baeldung article uses Nodes explicitly while I just fill in my template coming up with the Class:

import java.util.*; public final class Minimax { private Minimax() {} public static State minimaxDecision(State state) { return state.getActions().stream() .max(Comparator.comparing(Minimax::minValue)).get(); } private static double maxValue(State state) { if(state.isTerminal()){ return state.getUtility(); } return state.getActions().stream() .map(Minimax::minValue) .max(Comparator.comparing(Double::valueOf)).get(); } private static double minValue(State state) { if(state.isTerminal()){ return state.getUtility(); } return state.getActions().stream() .map(Minimax::maxValue) .min(Comparator.comparing(Double::valueOf)).get(); } public static class State { final int state; final boolean firstPlayer; final boolean secondPlayer; public State(int state, boolean firstPlayer){ this.state = state; this.firstPlayer = firstPlayer; this.secondPlayer = !firstPlayer; } Collection<State> getActions(){ List<State> actions = new LinkedList<>(); if(state > 4){ actions.add(new State(state-5, secondPlayer)); } if(state > 3){ actions.add(new State(state-4, secondPlayer)); } if(state > 2){ actions.add(new State(state-3, secondPlayer)); } return actions; } boolean isTerminal() { return state < 3; } double getUtility() { if(firstPlayer) return -1; else return 1; } } }

That can be run by a Main class as follows:

public class Main { public static void main(String[] args){ System.out.println("Welcome to my minimax algorithm"); boolean end = false; int val = 21; boolean first = true; while(!end) { System.out.println("Current position = "+ val +", Player one: " + first); Minimax.State s = new Minimax.State(val, true); Minimax.State decision = Minimax.minimaxDecision(s); val = decision.state; if(decision.isTerminal()){ end = true; System.out.println("Current position = "+ val +", Player one won: " + first); System.out.println("Game over"); } first =! first; } } }

This algorithm perfectly solves this simple game.

## What next?

It is fun to use Minimax to solve simple games. In order to tackle something more serious there are three key improvements to be made:

- We should be able to evaluate game state before win-lose is decided. For example in chess- having more pieces usually means advantage etc.
- We need to be able to search only to a predetermined depth (this should be easy already with the template given).
- I need to look at Alpha-Beta Pruning algorithm to improve the performance
- Having an object representing the state is potentially slow, but this can be looked at last.

## Summary

A future part of this article is pretty much guaranteed as I still have quite a way to go on my quest for writing a semi-advanced game playing program.

I hope this was interesting and made you want to try to play with Minimax yourself. Good luck!