3
\$\begingroup\$

(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:

Configuring a game

Playing

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/NoughtsAndCrosses

So, what do you think?

\$\endgroup\$
4
\$\begingroup\$

Thread safety is pretty poor.

Instead of making threads I suggest you change the WorkerThreads into Callable and make the call() do only a single workItemList and return the best move.

Then you can submit it to a ExecutorService's invokeAll() which will distribute the work over several cores automatically. (You can get a ExecutorService using Executors.newCachedThreadPool())

This should be created and held by canvas to allow the executor and it threads to be reused as needed.

for (int i = 0; i < cores; ++i) {
    workItemLists.add(new WorkerCallable(workItemListCapacity,
                                         moveGenerator,
                                         heuristicFunction,
                                         maximumDepth,
                                         progressBar));
}

canvas.getExecutorService().invokeAll(workItemLists);

TicTacToeGrid bestState = workItemLists.get(0).getBestState();
double bestValue = workItemLists.get(0).getBestValue();


for (WorkerCallable wt : workItemLists) {
    if (bestValue > wt.getBestValue()) {
        bestValue = wt.getBestValue();
        bestState = wt.getBestState();
    }
}
\$\endgroup\$
2
\$\begingroup\$

I call your attention to this code fragment here

    for (int i = 0; i < cores; ++i) {
        threads[i].start();
    }

    for (int i = 0; i < cores; ++i) {
        try {
            threads[i].join();
        } catch (InterruptedException ex) {

        }
    }

This says to me that you've got many units of work to do, and you are trying to do it in parallel only because you want to reduce the total time taken. That problem calls for a Runnable that represents a unit of work, submitted to an ExecutorService, rather than implementing your own threading.

Also, eating the InterruptedException is poor practice. A thread interrupt is the logical way of telling the AIThread that the user is no longer interested in the answer, which seems like an important feature.

import javax.swing.JOptionPane;
import javax.swing.JProgressBar;

class AIThread extends Thread {

This sets off alarm bells immediately - why on earth does the AI need to know about swing components? Especially if you are intending an MVC design.

Heuristic: the model should be agnostic about the details of the interface. You ought to be able to wire it up to a Swing UI, or a console window, or a test harness, without changing the model code at all. So any time you find the UI packages leaking into your model, you should challenge your current approach.

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);
}

There's a lot of duplication here, and you should be thinking to eliminate it. The sets of tuples can all be pre-computed; you know what they are as soon as the board dimensions have been defined, so you don't need to loop every time to get them. The scoring piece, however, needs to know where the marks are on the board to evaluate the position. The difference in timing strongly implies that you have two different ideas tangled in the same bit of code.

There's another way to write this code that may be a bit clearer, which is to use the state pattern to decide whether or not to continue evaluating positions. The basic notion is that you have three core states, an Xwins state that always returns itself, a Ywins state that always returns itself, and a calculating state that returns Xwins, Ywins, or a clone of itself with an updated score if the position is undetermined.

The pseudo code for that looks like

// The scorer will need a a fixed copy of where the marks are.
Scorer scorer = new Scorer(grid);
for(Tuple tuples : allTuples) {
    scorer = scorer.score(tuple);
}
return scorer.eval();

ComparisonChain demonstrates this approach pretty well.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.