Artificial Intelligence - Chapter 5 with Java
MINES Saint-Etienne

Table of Contents

Introduction

The goal of this tutorial is to understand how to (i) model adversarial games to solve and (ii) implement the search algorithms as described in AIMA. We take inspiration here from the algorithm provided by AIMA-Java Project. The slides containing the pseudocode are available here.

Simple Minimax implementation

As to check your understanding of the Minimax procedure, we will first implement a function that returns the minimax value of a tree. We use here a simple two-ply game tree : 

package fr.emse.ai.util;

import java.util.ArrayList;
import java.util.List;

public class SimpleTwoPlyGameTree<V> {

    private V value;
    private boolean max;
    private ArrayList<SimpleTwoPlyGameTree<V>> children;

    public SimpleTwoPlyGameTree(V value, boolean max) {
        this.value = value;
        this.max = max;
        children = new ArrayList<SimpleTwoPlyGameTree<V>>();
    }

    public SimpleTwoPlyGameTree(V value,
                                boolean max,
                                List<SimpleTwoPlyGameTree<V>> children) {
        this(value, max);
        for (SimpleTwoPlyGameTree<V> child : children)
            this.children.add(child);
    }

    public boolean isLeaf() {
        return children.isEmpty();
    }

    public boolean isMax() {
        return max;
    }

    public void addChild(SimpleTwoPlyGameTree<V> child) {
        this.children.add(child);
    }

    public V getValue() {
        return this.value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public ArrayList<SimpleTwoPlyGameTree<V>> getChildren() {
        return children;
    }

    public void setChildren(ArrayList<SimpleTwoPlyGameTree<V>> children) {
        this.children = children;
    }

    public String toString() {
        String s = "";
        s += "value = " + value + " | ";
        s += "child = " + children;
        return s;
    }
}

To instanciate such a tree, we can do the following: 

ArrayList<SimpleTwoPlyGameTree<Integer>> sublist1 = 
   new ArrayList<SimpleTwoPlyGameTree<Integer>>();
sublist1.add(new SimpleTwoPlyGameTree<Integer>(3,true));
sublist1.add(new SimpleTwoPlyGameTree<Integer>(12,true));
sublist1.add(new SimpleTwoPlyGameTree<Integer>(8,true));
SimpleTwoPlyGameTree<Integer> subtree1 = 
   new SimpleTwoPlyGameTree<Integer>(Integer.MIN_VALUE,false,sublist1);
ArrayList<SimpleTwoPlyGameTree<Integer>> sublist2 = 
   new ArrayList<SimpleTwoPlyGameTree<Integer>>();
sublist2.add(new SimpleTwoPlyGameTree<Integer>(2,true));
sublist2.add(new SimpleTwoPlyGameTree<Integer>(4,true));
sublist2.add(new SimpleTwoPlyGameTree<Integer>(6,true));
SimpleTwoPlyGameTree<Integer> subtree2 = 
   new SimpleTwoPlyGameTree<Integer>(Integer.MIN_VALUE,false,sublist2);
ArrayList<SimpleTwoPlyGameTree<Integer>> sublist3 = 
   new ArrayList<SimpleTwoPlyGameTree<Integer>>();
sublist3.add(new SimpleTwoPlyGameTree<Integer>(14,true));
sublist3.add(new SimpleTwoPlyGameTree<Integer>(5,true));
sublist3.add(new SimpleTwoPlyGameTree<Integer>(2,true));
SimpleTwoPlyGameTree<Integer> subtree3 = 
   new SimpleTwoPlyGameTree<Integer>(Integer.MIN_VALUE,false,sublist3);
tree1.addChild(subtree1);
tree1.addChild(subtree2);
tree1.addChild(subtree3);

This tree corresponds to the one used as an example in AIMA chapter 5.

Exercise 1

Download the SimpleTwoPlyGameTree class here. Implement the minimax function that returns the minimax value of a given instance of SimpleTwoPlyGameTree<Integer>.

Exercise 2

Implement the alphabeta function that returns the minimax value of a given instance of Tree<Integer> using alphabeta pruning technique, by extending minimax. Compare the results with minimax.

Modeling games

Let's now implement real games!

As to focus one the game modeling and the implementation of search algorithms, we provide here some reusable code.

The Game interface

The first important structure we use is the Game interface. To define a particular problem to solve, you must implement this interface. 

package fr.emse.ai.adversarial;

import java.util.List;

public interface Game<STATE, ACTION, PLAYER> {

        STATE getInitialState();
        PLAYER[] getPlayers();
        PLAYER getPlayer(STATE state);
        List<ACTION> getActions(STATE state);
        STATE getResult(STATE state, ACTION action);
        boolean isTerminal(STATE state);
        double getUtility(STATE state, PLAYER player);
}

This interface is parametric: its definition relies on the type of the states, the type of the actions and the type of the players.

This interface defines a game as stated in AIMA chapter 5:

  • getInitialState returns the initial state of the game,
  • getPlayers returns the set of players (usually two, like 0 and 1, or max and min),
  • getPlayer returns the active player of a given state,
  • getActions returns the list of possible actions for a given state,
  • getResult returns the state resulting from performing a given action to a given state,
  • isTerminal checks if a state is terminal,
  • getUtility return the utility value of a given state.

An example of game modeling

To be more concrete, let's take an example of a simple game, the Nim Game (more precisely Subtraction Game): 

package fr.emse.ai.adversarial.nim;

import fr.emse.ai.adversarial.Game;

import java.util.ArrayList;
import java.util.List;

public class NimGame implements Game<List<Integer>, Integer, Integer> {

    public final static Integer[] players = {0, 1};
    public final static List<Integer> initialState = new ArrayList<Integer>();

    public NimGame(int size) {
        initialState.add(0);
        initialState.add(size);
    }

    @Override
    public List<Integer> getInitialState() {
        return initialState;
    }

    @Override
    public Integer[] getPlayers() {
        return players;
    }

    @Override
    public Integer getPlayer(List<Integer> state) {
        return state.get(0);
    }

    @Override
    public List<Integer> getActions(List<Integer> state) {
        ArrayList<Integer> actions = new ArrayList<Integer>();
        for (int i = 1; i <= Math.min(3, state.get(1)); i++)
            actions.add(i);
        return actions;
    }

    @Override
    public List<Integer> getResult(List<Integer> state, Integer action) {
        ArrayList<Integer> newState = new ArrayList<Integer>();
        newState.add(1 - state.get(0));
        newState.add(state.get(1) - action);
        return newState;
    }

    @Override
    public boolean isTerminal(List<Integer> state) {
        return state.get(1) == 0;
    }

    @Override
    public double getUtility(List<Integer> state, Integer player) {
        if (state.get(0) == 1 - player) {
            if (state.get(1) == 1)
                return Double.POSITIVE_INFINITY;
            else if (((state.get(1) - 1) % 4) == 0)
                return 1;
            else
                return -1;
        } else {
            if (state.get(1) == 1)
                return Double.NEGATIVE_INFINITY;
            else if (((state.get(1) - 1) % 4) == 0)
                return -1;
            else
                return 1;
        }
    }
}

In this game, two players (represented by Integer values, 0 and 1) alternatively pick 1, 2 or 3 sticks from a pool of sticks. The player who removes the last stick from the pool loses the game. Here the state of the game is represented by a List<Integer>, with first cell containing the player, and the second cell containing the number of remaining stick. Actions are represented by Integer values, i.e. the number of sticks removed by the player.

Look carefully at this example. The rationale behing the utility function is subject to your investigation…

Decision making algorithms

Playing games against a machine now requires equiping it with proper decision making mechanisms.

The AdversarialSearch interface

To implement game algorithms, we provide the AdversarialSearch interface: 

package fr.emse.ai.adversarial;

import fr.emse.ai.adversarial.core.Metrics;

public interface AdversarialSearch<STATE, ACTION> {

        ACTION makeDecision(STATE state);
        Metrics getMetrics();
}

This interface is used to implement a game solver for a given state type and action type. It requires a method to make decision, i.e. returns an action to perform given a game state. The getMetrics method will be used later on.

Some implementations of AdversarialSearch

As to focus on modeling games and analyzing the performances of different algorithms to play them, we provide some already implemented versions of Minimax search, alpha-beta search and iterative deepening Minimax search with alpha-beta pruning.

Here is the Minimax code: 

package fr.emse.ai.adversarial;

import fr.emse.ai.adversarial.core.Metrics;

public class MinimaxSearch<STATE, ACTION, PLAYER> implements
                AdversarialSearch<STATE, ACTION> {

        private Game<STATE, ACTION, PLAYER> game;
        private int expandedNodes;

        public MinimaxSearch(Game<STATE, ACTION, PLAYER> game) {
                this.game = game;
        }

        @Override
        public ACTION makeDecision(STATE state) {
                expandedNodes = 0;
                ACTION result = null;
                double resultValue = Double.NEGATIVE_INFINITY;
                PLAYER player = game.getPlayer(state);
                for (ACTION action : game.getActions(state)) {
                        double value = minValue(game.getResult(state, action), 
                                                player);
                        if (value > resultValue) {
                                result = action;
                                resultValue = value;
                        }
                }
                return result;
        }

        public double maxValue(STATE state, PLAYER player) { // returns an utility
                                                             // value
                expandedNodes++;
                if (game.isTerminal(state))
                        return game.getUtility(state, player);
                double value = Double.NEGATIVE_INFINITY;
                for (ACTION action : game.getActions(state))
                        value = Math.max(value,
                                        minValue(game.getResult(state, action), 
                                                 player));
                return value;
        }

        public double minValue(STATE state, PLAYER player) { // returns an utility
                                                             // value
                expandedNodes++;
                if (game.isTerminal(state))
                        return game.getUtility(state, player);
                double value = Double.POSITIVE_INFINITY;
                for (ACTION action : game.getActions(state))
                        value = Math.min(value,
                                        maxValue(game.getResult(state, action), 
                                                 player));
                return value;
        }

        @Override
        public Metrics getMetrics() {
                Metrics result = new Metrics();
                result.set("expandedNodes", expandedNodes);
                return result;
        }
}

You can download all the search algorithms and required classes here.

Playing against the computer

Our agent is now able to make good decisions, let's now play against it!

As to do so, we must implement a main program that implement the two-ply game. For instance, for the Nim game, we can use the following code: 

package fr.emse.ai.adversarial.nim;

import fr.emse.ai.adversarial.AlphaBetaSearch;
import fr.emse.ai.adversarial.IterativeDeepeningAlphaBetaSearch;
import fr.emse.ai.adversarial.MinimaxSearch;

import java.util.List;
import java.util.Scanner;

public class NimGameplay {

    public static void main(String[] args) {
        NimGame game = new NimGame(20);
        MinimaxSearch<List<Integer>, Integer, Integer> minimaxSearch = 
            MinimaxSearch.createFor(game);
        AlphaBetaSearch<List<Integer>, Integer, Integer> alphabetaSearch = 
            AlphaBetaSearch.createFor(game);
        IterativeDeepeningAlphaBetaSearch<List<Integer>, Integer, Integer> 
            iterativeDeepeningAlphaBetaSearch = 
                IterativeDeepeningAlphaBetaSearch.createFor(game, -1, 1, 10);
        List<Integer> state = game.getInitialState();
        while (!game.isTerminal(state)) {
            System.out.println("======================");
            System.out.println(state);
            int action = -1;
            if (state.get(0) == 0) {
                //human
                List<Integer> actions = game.getActions(state);
                Scanner in = new Scanner(System.in);
                while (!actions.contains(action)) {
                    System.out.println("Human player, what is your action?");
                    action = in.nextInt();
                }
            } else {
                //machine
                System.out.println("Machine player, what is your action?");
                action = minimaxSearch.makeDecision(state);
                System.out.println("Metrics for Minimax : " + 
                   minimaxSearch.getMetrics());
                alphabetaSearch.makeDecision(state);
                System.out.println("Metrics for AlphaBeta : " + 
                   alphabetaSearch.getMetrics());
                iterativeDeepeningAlphaBetaSearch.makeDecision(state);
                System.out.println("Metrics for IDAlphaBetaSearch : " + 
                   iterativeDeepeningAlphaBetaSearch.getMetrics());
            }
            System.out.println("Chosen action is " + action);
            state = game.getResult(state, action);
        }
        System.out.print("GAME OVER: ");
        if (state.get(0) == 0)
            System.out.println("Human wins!");
        else
            System.out.println("Machine wins!");

    }
}

Exercises

Exercise 3

Model and implement the tic-tac-toe game. Compare the performance of the different provided algorithms.

Exercise 4

Model and implement the Connect Four game. Compare the performance of the different provided algorithms.

Author: Gauthier Picard

Created: 2019-04-03 Wed 08:36

Validate