2
\$\begingroup\$

I like toy AI and what can be better than starting from Tic Tac Toe. Basically, this is a command line program that asks the user to input

  1. the height of the game field,
  2. the width of the game field,
  3. the length of the winning pattern,
  4. the depth of the game search.

(Some good configuration would be 5, 5, 4, 5, respectively.)

Bot.java:

package net.coderodde.tictactoe;

/**
 * This interface defines the API for computer simulated player.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public interface Bot {

    /**
     * Given the input state {@code state}, computes the next state obtained by
     * marking a new mark.
     * 
     * @param  state the source state.
     * @return the next state.
     */
    public TicTacToeGrid move(TicTacToeGrid state);
}

AlphaBetaBot.java:

package net.coderodde.tictactoe.support;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.tictactoe.Bot;
import net.coderodde.tictactoe.HeuristicFunction;
import net.coderodde.tictactoe.Mark;
import net.coderodde.tictactoe.MoveGenerator;
import net.coderodde.tictactoe.TicTacToeGrid;

/**
 * This class implements a bot relying on Alpha-beta pruning.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class AlphaBetaBot implements Bot {

    private static final double LARGE = 1e10;
    private final HeuristicFunction heuristicFunction;
    private final MoveGenerator moveGenerator;
    private final int maximumDepth;

    public AlphaBetaBot(int maximumDepth, 
                        HeuristicFunction heuristicFunction,
                        MoveGenerator moveGenerator,
                        int winningLength) {
        this.heuristicFunction = heuristicFunction;
        this.moveGenerator = moveGenerator;
        this.maximumDepth = maximumDepth;
    }

    @Override
    public TicTacToeGrid move(TicTacToeGrid state) {
        TicTacToeGrid bestState = null;
        List<TicTacToeGrid> nextStateList = moveGenerator.generateMoves(state, 
                                                                        Mark.O);
        if (nextStateList.isEmpty()) {
            return null;
        }

        double min = Double.POSITIVE_INFINITY;
        long startTime = System.currentTimeMillis();

        for (TicTacToeGrid s : nextStateList) {
            double value = alphabeta(s, maximumDepth);

            if (min > value) {
                min = value;
                bestState = s;
            }
        }

        long endTime = System.currentTimeMillis();
        System.out.println("Computation took " + (endTime - startTime) +
                           " milliseconds.");
        return bestState;
    }

    double alphabeta(TicTacToeGrid node, 
                     int depth, 
                     double alpha, 
                     double beta, 
                     Mark player) {
        double estimate = heuristicFunction.estimate(node);

        if (Double.isInfinite(estimate)) {
            // Once here, the game is over.

            if (estimate > 0.0) {
                // The human player won.
                return LARGE + depth;
            } else {
                // The AI bot won.
                return -LARGE - depth;
            }
        }

        if (depth == 0) {
            return estimate;
        }

        List<TicTacToeGrid> children = moveGenerator.generateMoves(node, 
                                                                   player);
        Comparator<TicTacToeGrid> comparator = 
                new ChildComparator(heuristicFunction,children);

        Collections.<TicTacToeGrid>sort(children, comparator);

        if (player.equals(Mark.X)) {
            Collections.<TicTacToeGrid>reverse(children);

            for (TicTacToeGrid child : children) {
                alpha = Math.max(alpha, alphabeta(child, 
                                                  depth - 1, 
                                                  alpha, 
                                                  beta, 
                                                  Mark.O));

                if (beta <= alpha) {
                    return alpha;
                }
            }

            return alpha;
        }

        for (TicTacToeGrid child : children) {
            beta = Math.min(beta, alphabeta(child,
                                            depth - 1,
                                            alpha,
                                            beta,
                                            Mark.X));

            if (beta <= alpha) {
                return alpha;
            }
        }

        return beta;
    }

    double alphabeta(TicTacToeGrid state, int depth) {
        return alphabeta(state, 
                         depth, 
                         -Double.MAX_VALUE, 
                         Double.MAX_VALUE, 
                         Mark.X);
    }

    private final class ChildComparator 
    implements Comparator<TicTacToeGrid> {

        private final Map<TicTacToeGrid, Double> heuristicMap = new HashMap<>();

        ChildComparator(HeuristicFunction heuristicFunction,
                        List<TicTacToeGrid> grids) {
            for (TicTacToeGrid grid : grids) {
                heuristicMap.put(grid, 
                                 heuristicFunction.estimate(grid));
            }
        }

        @Override
        public int compare(TicTacToeGrid o1, TicTacToeGrid o2) {
            return Double.compare(heuristicMap.get(o1), heuristicMap.get(o2));
        }
    }
}

HeuristicFunction.java:

package net.coderodde.tictactoe;

/**
 * This interface defines the API for heuristic function.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public interface HeuristicFunction {

    /**
     * Computes the heuristic estimate of the input state.
     * 
     * @param  grid the input state.
     * @return the heuristic estimate.
     */
    public double estimate(TicTacToeGrid grid);
}

DefaultHeuristicFunction.java:

package net.coderodde.tictactoe.support;

import net.coderodde.tictactoe.HeuristicFunction;
import net.coderodde.tictactoe.Mark;
import net.coderodde.tictactoe.TicTacToeGrid;

/**
 * Implements a default heuristic function.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 4, 2015)
 */
public class DefaultHeuristicFunction implements HeuristicFunction {

    /**
     * Returns the heuristic estimate for {@code grid}. If the returned value is
     * positive infinity, the <tt>X</tt> player wins. If the returned values is
     * a negative infinity, the <tt>O</tt> player wins. If none wins, returns 
     * the heuristic estimate of {@code grid}, which will be finite.
     * 
     * @param grid the state to estimate.
     * @return a heuristic estimate.
     */
    @Override
    public double estimate(TicTacToeGrid grid) {
        double sum = checkDiagonalLR(grid);

        if (Double.isInfinite(sum) && sum > 0.0) {
            return sum;
        }

        double sum2 = checkDiagonalRL(grid);

        if (Double.isInfinite(sum2) && sum2 > 0.0) {
            return sum2;
        }

        double sum3 = checkVertical(grid);

        if (Double.isInfinite(sum3) && sum3 > 0.0) {
            return sum3;
        }

        return sum + sum2 + sum3 + checkHorizontal(grid);
    }

    private double checkDiagonalLR(TicTacToeGrid grid) {
        int width = grid.getWidth();
        int height = grid.getHeight();
        int winLen = grid.getWinningLength();

        double value = 0.0;

        for (int y = 0; y < height - 1; ++y) {
            for (int x = 0; x < width - 1; ++x) {
                Mark mark = grid.read(x, y);

                if (mark == null) {
                    continue;
                }

                int scanned = 1;

                while (scanned < winLen
                        && y + scanned < height
                        && x + scanned < width) {
                    if (mark.equals(grid.read(x + scanned, y + scanned))) {
                        scanned++;
                    } else {
                        break;
                    }
                }

                if (scanned == winLen) {
                    return mark.equals(Mark.X) ? 
                            Double.POSITIVE_INFINITY : 
                            Double.NEGATIVE_INFINITY;
                } else if (scanned > 1) {
                    if (mark.equals(Mark.X)) {
                        value += scanned * scanned;
                    } else {
                        value += scanned * scanned;
                    }
                }
            }
        }

        return value;
    }

    private double checkDiagonalRL(TicTacToeGrid grid) {
        int width = grid.getWidth();
        int height = grid.getHeight();
        int winLen = grid.getWinningLength();

        double value = 0.0;

        for (int y = 0; y < height - 1; ++y) {
            for (int x = 1; x < width; ++x) {
                Mark mark = grid.read(x, y);

                if (mark == null) {
                    continue;
                }

                int scanned = 1;

                while (scanned < winLen 
                        && y + scanned < height 
                        && x - scanned >= 0) {
                    if (mark.equals(grid.read(x - scanned, y + scanned))) {
                        scanned++;
                    } else {
                        break;
                    }
                }

                if (scanned == winLen) {
                    return mark.equals(Mark.X) ? 
                            Double.POSITIVE_INFINITY : 
                            Double.NEGATIVE_INFINITY;
                } else if (scanned > 1) {
                    if (mark.equals(Mark.X)) {
                        value += scanned * scanned;
                    } else {
                        value -= scanned * scanned;
                    }
                }
            }
        }

        return value;
    }

    private double checkVertical(TicTacToeGrid grid) {
        int width = grid.getWidth();
        int height = grid.getHeight();
        int winLen = grid.getWinningLength();

        double value = 0.0;

        for (int y = 0; y < height - 1; ++y) {
            for (int x = 0; x < width; ++x) {
                Mark mark = grid.read(x, y);

                if (mark == null) {
                    continue;
                }

                int scanned = 1;

                while (scanned < winLen && y + scanned < height) {
                    if (mark.equals(grid.read(x, y + scanned))) {
                        scanned++;
                    } else {
                        break;
                    }
                }

                if (scanned == winLen) {
                    return mark.equals(Mark.X) ? 
                            Double.POSITIVE_INFINITY :
                            Double.NEGATIVE_INFINITY;
                } else if (scanned > 1) {
                    if (mark.equals(Mark.X)) {
                        value += scanned * scanned;
                    } else {
                        value -= scanned * scanned;
                    }
                }
            }
        }

        return value;
    }

    private double checkHorizontal(TicTacToeGrid grid) {
        int width = grid.getWidth();
        int height = grid.getHeight();
        int winLen = grid.getWinningLength();

        double value = 0.0;

        for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width - 1; ++x) {
                Mark mark = grid.read(x, y);

                if (mark == null) {
                    continue;
                }

                int scanned = 1;

                while (scanned < winLen && x + scanned < width) {
                    if (mark.equals(grid.read(x + scanned, y))) {
                        scanned++;
                    } else {
                        break;
                    }
                }

                if (scanned == winLen) {
                    return mark.equals(Mark.X) ? 
                            Double.POSITIVE_INFINITY :
                            Double.NEGATIVE_INFINITY;
                } else if (scanned > 1) {
                    if (mark.equals(Mark.X)) {
                        value += scanned * scanned;
                    } else {
                        value -= scanned * scanned;
                    }
                }
            }
        }

        return value;
    }
}

MoveGenerator.java:

package net.coderodde.tictactoe;

import java.util.List;

/**
 * This interface the API for child node generation classes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 4, 2015)
 */
public interface MoveGenerator {

    /**
     * Generates the moves of {@code player}.
     * 
     * @param state  the source state.
     * @param player the player who is moving.
     * @return the list of some next states.
     */
    public List<TicTacToeGrid> generateMoves(TicTacToeGrid state, Mark player);
}

DefaultMoveGenerator.java:

package net.coderodde.tictactoe.support;

import java.util.ArrayList;
import java.util.List;
import net.coderodde.tictactoe.Mark;
import net.coderodde.tictactoe.MoveGenerator;
import net.coderodde.tictactoe.TicTacToeGrid;

/**
 * This class generates next states from a given state for a particular player.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 4, 2015)
 */
public class DefaultMoveGenerator implements MoveGenerator {

    @Override
    public List<TicTacToeGrid> generateMoves(TicTacToeGrid state, Mark player) {
        int width = state.getWidth();
        int height = state.getHeight();

        int minX = width;
        int maxX = 0;

        int minY = height;
        int maxY = 0;

        for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width; ++x) {
                Mark mark = state.read(x, y);

                if (mark == null) {
                    continue;
                }

                if (minX > x) {
                    minX = x;
                } 

                if (maxX < x) {
                    maxX = x;
                }

                if (minY > y) {
                    minY = y;
                }

                if (maxY < y) {
                    maxY = y;
                }
            }
        }

        minX = Math.max(0, minX - 2);
        maxX = Math.min(width - 1, maxX + 2);
        minY = Math.max(0, minY - 2);
        maxY = Math.min(height - 1, maxY + 2);

        List<TicTacToeGrid> next = new ArrayList<>((maxX - minX + 1) *
                                                   (maxY - minY + 1));

        for (int y = minY; y <= maxY; ++y) {
            for (int x = minX; x <= maxX; ++x) {
                Mark mark = state.read(x, y);

                if (mark == null) {
                    TicTacToeGrid grid = new TicTacToeGrid(state);
                    grid.mark(x, y, player);
                    next.add(grid);
                }
            }
        }

        return next;
    }
}

Mark.java:

package net.coderodde.tictactoe;

/**
 * This enumeration enumerates the marks "X" and "O" for Tic Tac Toe.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Oct 4, 2015)
 */
public enum Mark {
    X,
    O,
}

TicTacToeGrid.java:

package net.coderodde.tictactoe;

import java.util.Objects;

/**
 * This class implements the field of the Tic Tac Toe game.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class TicTacToeGrid {

    /**
     * The minimum allowed number of rows in the grid.
     */
    private static final int MINIMUM_ROWS = 3;

    /**
     * The minimum allowed number of columns in the grid.
     */
    private static final int MINIMUM_COLUMNS = 3;

    /**
     * The actual grid holding the cells.
     */
    private final Mark[][] grid;

    private final int winningLength;

    public TicTacToeGrid(int rows, int columns, int winningLength) {
        checkNumberOfRows(rows);
        checkNumberOfColumns(columns);
        checkWinningLength(winningLength, rows, columns);
        this.grid = new Mark[rows][columns];
        this.winningLength = winningLength;
    }

    public TicTacToeGrid(TicTacToeGrid grid) {
        this.grid = new Mark[grid.getHeight()][grid.getWidth()];
        this.winningLength = grid.winningLength;

        for (int y = 0; y < grid.getHeight(); ++y) {
            for (int x = 0; x < grid.getWidth(); ++x) {
                this.grid[y][x] = grid.read(x, y);
            }
        }
    }

    public boolean isFull() {
        for (int y = 0; y < getHeight(); ++y) {
            for (int x = 0; x < getWidth(); ++x) {
                if (grid[y][x] == null) {
                    return false;
                }
            }
        }

        return true;
    }

    public int getWinningLength() {
        return winningLength;
    }

    public int getHeight() {
        return grid.length;
    }

    public int getWidth() {
        return grid[0].length;
    }

    public void mark(int x, int y, Mark player) {
        Objects.requireNonNull(player, "The input player is null.");
        checkXCoordinate(x);
        checkYCoordinate(y);

        if (grid[y][x] != null) {
            throw new IllegalArgumentException(
                    "The cell at (x = " + x + ", y = " + y + ") is occupied.");
        }

        grid[y][x] = player;
    }

    public Mark read(int x, int y) {
        checkXCoordinate(x);
        checkYCoordinate(y);
        return grid[y][x];
    }

    @Override
    public String toString() {
        int width = grid[0].length;
        int height = grid.length;

        StringBuilder sb = new StringBuilder((width + 1) * height);

        for (int y = 0; y < height; ++y) {
            for (int x = 0; x < width; ++x) {
                if (grid[y][x] == null) {
                    sb.append('.');
                } else if (grid[y][x].equals(Mark.X)) {
                    sb.append('X');
                } else if (grid[y][x].equals(Mark.O)) {
                    sb.append('O');
                } else {
                    throw new IllegalStateException(
                            "Unknown enumeration: " + grid[y][x].toString());
                }

                sb.append(' ');
            }

            sb.append('\n');
        }

        return sb.toString();
    }

    private void checkNumberOfRows(int rows) {
        if (rows < MINIMUM_ROWS) {
            throw new IllegalArgumentException(
                    "Too few rows requested: " + rows + ". Must be at " +
                    "least " + MINIMUM_ROWS + ".");
        }
    }

    private void checkNumberOfColumns(int columns) {
        if (columns < MINIMUM_COLUMNS) {
            throw new IllegalArgumentException(
                    "Too few columns requested: " + columns + ". Must be at " +
                    "least " + MINIMUM_COLUMNS + ".");
        }
    }

    private void checkWinningLength(int winningLength, int rows, int columns) {
        int maxAllowedWinningLength = Math.min(rows, columns);

        if (winningLength > maxAllowedWinningLength) {
            throw new IllegalArgumentException(
                    "The grid cannot accommodate a winning patter of length " +
                    winningLength + ". Maximum allowed length is " +
                    maxAllowedWinningLength);
        }
    }

    private void checkXCoordinate(int x) {
        if (x <  0) {
            throw new IndexOutOfBoundsException(
                    "The X-coordinate is negative: " + x + ".");
        }

        if (x >= grid[0].length) {
            throw new IndexOutOfBoundsException(
                    "The X-coordinate is too large: " + x + ". Must be at " +
                    "most " + (grid[0].length - 1));
        }
    }

    private void checkYCoordinate(int y) {
        if (y <  0) {
            throw new IndexOutOfBoundsException(
                    "The Y-coordinate is negative: " + y + ".");
        }

        if (y >= grid.length) {
            throw new IndexOutOfBoundsException(
                    "The Y-coordinate is too large: " + y + ". Must be at " +
                    "most " + (grid.length - 1));
        }
    }
}

App.java:

package net.coderodde.tictactoe;

import java.util.Scanner;
import net.coderodde.tictactoe.support.AlphaBetaBot;
import net.coderodde.tictactoe.support.DefaultHeuristicFunction;
import net.coderodde.tictactoe.support.DefaultMoveGenerator;

/**
 * This class implements the actual Tic Tac Toe game.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class App {

    /**
     * The entry point into the program.

     * @param args the command line arguments.
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        TicTacToeGrid current;
        int winningLength;
        int depth;

        while (true) {
            System.out.print("Type in the amount of rows in the field: ");
            int rows = scanner.nextInt();

            System.out.print("Type in the amount of columns in the field: ");
            int columns = scanner.nextInt();

            System.out.print("Type in the length of winning pattern: ");
            winningLength = scanner.nextInt();

            System.out.print("Type in the AI depth: ");

            depth = scanner.nextInt();

            if (depth < 1) {
                depth = 2;
            }

            depth = Math.min(depth, rows * columns);

            try {
                current = new TicTacToeGrid(rows, columns, winningLength);
                break;
            } catch (IllegalArgumentException ex) {
                error(ex.getMessage());
            }
        }

        HeuristicFunction heuristicFunction = new DefaultHeuristicFunction();
        MoveGenerator moveGenerator = new DefaultMoveGenerator();
        Bot bot = new AlphaBetaBot(depth, 
                                   heuristicFunction, 
                                   moveGenerator, 
                                   winningLength);
        System.out.println(current);

        while (true) {
            System.out.print("> ");

            int x = 0;
            int y = 0;

            String sx = null;
            String sy = null;

            try {
                sx = scanner.next();
                x = Integer.parseInt(sx);
            } catch (NumberFormatException ex) {
                error("Bad x-coordinate: " + sx);
                continue;
            }

            try {
                sy = scanner.next();
                y = Integer.parseInt(sy);
            } catch (NumberFormatException ex) {
                error("Bad y-coordinate: " + sy);
                continue;
            }

            try {
                current.mark(x - 1, y - 1, Mark.X);
            } catch (IllegalArgumentException ex) {
                error("The cell at (x = " + x + ", y = " + y + ") is " +
                      "occupied.");
                continue;
            }

            System.out.println(current);

            double estimate = heuristicFunction.estimate(current);

            if (Double.isInfinite(estimate)) {
                System.out.println(current);

                if (estimate > 0.0) {
                    status("You won!");
                } else {
                    status("You lost.");
                }

                return;
            }

            current = bot.move(current);

            estimate = heuristicFunction.estimate(current);

            if (Double.isInfinite(estimate)) {
                System.out.println(current);

                if (estimate > 0.0) {
                    status("You won!");
                } else {
                    status("You lost.");
                }

                return;
            }

            System.out.println(current);

            if (current.isFull()) {
                status("It's a draw.");
                return;
            }
        }
    }

    private static void status(String message) {
        System.out.println("STATUS: " + message);
    }

    private static void error(String message) {
        System.out.println("ERROR: " + message);
    }
}

My main concerns are API design and performance. Please, tell me anything else that comes to mind.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.