(See also Noughts and Crosses GUI game in Java - Part 2/2: GUI)I was working on a GUI game of Noughts and Crosses, and this is what I finally got:Unfortunately, the entire source code for the program does not fit in a single, so I have to try to split them in logical parts: this post is about Model and a little bit of Controller in MVC-pattern.AIThread.java:package net.coderodde.game.crosses;import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.HashMap;import java.util.List;import java.util.Map;import javax.swing.JOptionPane;import javax.swing.JProgressBar;/** * This thread is responsible for running the AI. *  * @author Rodion rodde Efremov * @version 1.6 (Oct 7, 2015) */class AIThread extends Thread {    private static final double LARGE = 1e10;    private final ConfigurationFrame configurationFrame;    private final GameFrame gameFrame;    private final JProgressBar progressBar;    private final TicTacToeGrid grid;    private final TicTacToePanel canvas;    private final MoveGenerator moveGenerator;    private final HeuristicFunction heuristicFunction;    private final int maximumDepth;    AIThread(ConfigurationFrame configurationFrame,             GameFrame gameFrame,             TicTacToeGrid grid,              TicTacToePanel canvas,             JProgressBar progressBar,             MoveGenerator moveGenerator,             HeuristicFunction heuristicFunction,             int maximumDepth) {        this.configurationFrame = configurationFrame;        this.gameFrame = gameFrame;        this.grid = grid;        this.canvas = canvas;        this.progressBar = progressBar;         this.moveGenerator = moveGenerator;        this.heuristicFunction = heuristicFunction;        this.maximumDepth = maximumDepth;    }    @Override    public void run() {        canvas.lock(); // Make sure that the user's clicks do not modify the                        // grid.        progressBar.setValue(0);        progressBar.setVisible(true);        List<TicTacToeGrid> nextStateList = moveGenerator.generateMoves(grid,                                                                         Mark.O);        if (nextStateList.isEmpty()) {            return;        }        progressBar.setMaximum(nextStateList.size());        int cores = Runtime.getRuntime().availableProcessors();        List<List<TicTacToeGrid>> workItemLists = new ArrayList<>(cores);        int workItemListCapacity = nextStateList.size() / cores + 1;        for (int i = 0; i < cores; ++i) {            workItemLists.add(new ArrayList<TicTacToeGrid>                             (workItemListCapacity));        }        // Distribute the work items.        for (int i = 0; i < nextStateList.size(); ++i) {            workItemLists.get(i % cores).add(nextStateList.get(i));        }        long startTime = System.currentTimeMillis();        WorkerThread[] threads = new WorkerThread[cores];        for (int i = 0; i < cores; ++i) {            threads[i] = new WorkerThread(workItemLists.get(i),                                          moveGenerator,                                          heuristicFunction,                                          maximumDepth,                                          progressBar);        }        for (int i = 0; i < cores; ++i) {            threads[i].start();        }        for (int i = 0; i < cores; ++i) {            try {                threads[i].join();            } catch (InterruptedException ex) {            }        }        long endTime = System.currentTimeMillis();        System.out.println(Computation took  + (endTime - startTime) +                            milliseconds.);        TicTacToeGrid bestState = threads[0].getBestState();        double bestValue = threads[0].getBestValue();        for (WorkerThread wt : threads) {            if (bestValue > wt.getBestValue()) {                bestValue = wt.getBestValue();                bestState = wt.getBestState();            }        }        grid.set(bestState);        Mark winner = grid.getWinner();        String message = null;        if (winner != null) {            message = winner.equals(Mark.X) ? You won! : You lost.;        } else if (grid.isFull()) {            message = It's a tie.;        }        if (message != null) {            JOptionPane.showMessageDialog(canvas,                                          message,                                          Game over,                                           JOptionPane.INFORMATION_MESSAGE);            gameFrame.setVisible(false);            configurationFrame.setHeight(grid.getHeight());            configurationFrame.setWidth(grid.getWidth());            configurationFrame.setPatternLength(grid.getWinningLength());            configurationFrame.setDepth(this.maximumDepth);            configurationFrame.setVisible(true);        } else {            canvas.unlock();        }        progressBar.setVisible(false);        canvas.repaint();    }    private static final class WorkerThread extends Thread {        private final List<TicTacToeGrid> workItemList;        private final MoveGenerator       moveGenerator;        private final HeuristicFunction   heuristicFunction;        private final int                 maximumDepth;        private final JProgressBar        progressBar;        private TicTacToeGrid             bestState;        private double                    bestValue;        WorkerThread(List<TicTacToeGrid> workItemList,                     MoveGenerator moveGenerator,                     HeuristicFunction heuristicFunction,                     int maximumDepth,                     JProgressBar progressBar) {            this.workItemList = workItemList;            this.moveGenerator = moveGenerator;            this.heuristicFunction = heuristicFunction;            this.maximumDepth = maximumDepth;            this.progressBar = progressBar;        }        @Override        public void run() {            bestValue = Double.POSITIVE_INFINITY;            for (TicTacToeGrid s : workItemList) {                double value = alphabeta(s, maximumDepth);                if (bestValue > value) {                    bestValue = value;                    bestState = s;                }                progressBar.setValue(progressBar.getValue() + 1);            }        }        double getBestValue() {            return bestValue;        }        TicTacToeGrid getBestState() {            return bestState;        }        private 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;        }        private 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.game.crosses;/** * Implements a default heuristic function. *  * @author Rodion rodde Efremov * @version 1.6 (Oct 4, 2015) */public class 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.     */    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.game.crosses;import java.util.ArrayList;import java.util.List;/** * 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 MoveGenerator {    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;    }}TicTacToeGrid.java:package net.coderodde.game.crosses;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];    }    public Mark getWinner() {        int width = getWidth();        int height = getHeight();        int patternLength = getWinningLength();        // Check diagonal patterns from top-left to bottom-right.        for (int y = 0; y <= height - patternLength; ++y) {            label1:            for (int x = 0; x <= width - patternLength; ++x) {                Mark mark = read(x, y);                if (mark == null) {                    continue;                }                for (int i = 1; i < patternLength; ++i) {                    if (read(x + i, y + i) != mark) {                        continue label1;                    }                }                return mark;            }        }        // Check diagonal patterns from top-right to bottom-left.        for (int y = 0; y <= height - patternLength; ++y) {            label2:            for (int x = patternLength - 1; x < width; ++x) {                Mark mark = read(x, y);                if (mark == null) {                    continue;                }                for (int i = 1; i < patternLength; ++i) {                    if (read(x - i, y + i) != mark) {                        continue label2;                    }                }                return mark;            }        }        // Check vertical patterns.        for (int y = 0; y <= height - patternLength; ++y) {            label3:            for (int x = 0; x < width; ++x) {                Mark mark = read(x, y);                if (mark == null) {                    continue;                }                for (int i = 1; i < patternLength; ++i) {                    if (read(x, y + i) != mark) {                        continue label3;                    }                }                return mark;            }        }        // Check horizontal patterns.        for (int y = 0; y < height; ++y) {            label4:            for (int x = 0; x <= width - patternLength; ++x) {                Mark mark = read(x, y);                if (mark == null) {                    continue;                }                for (int i = 1; i < patternLength; ++i) {                    if (read(x + i, y) != mark) {                        continue label4;                    }                }                return mark;            }        }        // No winner yet.        return null;    }    public void set(TicTacToeGrid other) {        if (getWidth() != other.getWidth()) {            throw new IllegalArgumentException(                    Width mismatch: copying  + other.getWidth() +                      columns to  + this.getWidth());        }        if (getHeight() != other.getHeight()) {            throw new IllegalArgumentException(                    Height mismatch: copying  + other.getHeight() +                     rows to  + this.getHeight());        }        for (int y = 0; y < getHeight(); ++y) {            for (int x = 0; x < getWidth(); ++x) {                this.grid[y][x] = other.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));        }    }}If you wish to run the program, its home page is at https://github.com/coderodde/NoughtsAndCrossesSo, what do you think?
Noughts and Crosses GUI game in Java - Part 1/2: AI
java;game;tic tac toe;ai