16
\$\begingroup\$

Description

This is my code for the Weekend Challenge Reboot - Tic Tac Toe Ultimate.

The game can be played here: http://www.zomis.net/ttt (along with some other variations that are also use the same code base, but with other 'controllers').

This question contains the game model and a 'controller' for the TicTacToe Ultimate game.

The classic TTT is 3*3. TTT Ultimate is a 3*3 grid of classic TTTs, so 3*3 * 3*3. As usual I wanted this code to be flexible, so technically it should be possible to extend it to a TTTUltimatePlus which would be a 3*3 grid of TTTUltimate games, or 3*3 * 3*3 * 3*3. I have not done a controller for TTTUltimatePlus yet, but the TTBase system would support it. When I started this project, I did not expect myself to make it work with Reversi (a.k.a. Othello), or Quantum Tic-Tac-Toe but well... when I realized how I could structure this I thought "Why not?".

My first code, having a TTUltimateGame, TTBoard and a TTField class had a lot of code duplication which I wanted to avoid. This made me want to make this code. The TTBase class is the most important one, to support any number of recursiveness (by making a TTTUltimatePlus for example) I made it as a recursive class. Each clickable field is a TTBase, each area containing the fields is a TTBase, and the outermost game itself is a TTBase.

Class Summary (695 lines in 12 files, making a total of 18218 bytes)

  • HasSub.java: Interface indicating that a class contains smaller parts, 'subs' (a small field is a sub to a 3x3 area for example).
  • TicFactory.java: Interface for creating TTBase objects.
  • TicUtils.java: Utility methods, including code to create the Win Conditions for a TTBase.
  • TTBase.java: Class that can contain more TTBases in a rectangular grid. Can be won and played by players.
  • TTController.java: Abstract class for determining which TTBases that can be played and for playing at them.
  • TTFactories.java: Code to instanciate variations of TTBases.
  • TTMNKParameters.java: Parameters for creating a TTBase. Determines the size of the board and the number of consecutive fields that must be won by the same player.
  • TTMoveListener.java: Interface for when a move has been made
  • TTPlayer.java: An enum for players; X or O, and none, or both.
  • TTUltimateController.java: Provides a TTController for TTT Ultimate.
  • TTWinCondition.java: A rule for determining if a board is won by checking a number of fields. A classic TTT board for example has 8 win conditions: 3 rows, 3 columns and 2 diagonals.
  • Winnable.java: Interface for something that can be won by a TTPlayer.

Code

This code can also be downloaded from GitHub

HasSub.java: (15 lines, 369 bytes)

/**
 * Interface for classes that can contain other objects, 'subs', in a rectangular way
 *
 * @param <T> Type of sub
 */
public interface HasSub<T> extends Winnable {
    T getSub(int x, int y);
    Iterable<TTWinCondition> getWinConds();
    int getSizeX();
    int getSizeY();
    int getConsecutiveRequired();
    boolean hasSubs();
}

TicFactory.java: (5 lines, 117 bytes)

public interface TicFactory {
    TTBase construct(TTBase parent, int x, int y);
}

TicUtils.java: (140 lines, 4211 bytes)

public class TicUtils {
    /**
     * Get which board a tile will send the opponent to (in a TTTUltimate context)
     * 
     * @param tile The tile to be played
     * @return The board which the tile directs to
     */
    public static TTBase getDestinationBoard(TTBase tile) {
        TTBase parent = tile.getParent();
        if (parent == null)
            return null;
        TTBase grandpa = parent.getParent();
        if (grandpa == null)
            return null;
        return grandpa.getSub(tile.getX(), tile.getY());
    }
    /**
     * Find the win conditions which contains a specific field
     * 
     * @param field The field to look for
     * @param board Where to look for win conditions
     * @return A collection which only contains win conditions which contains the field 
     */
    public static <E extends Winnable> Collection<TTWinCondition> getWinCondsWith(E field, HasSub<E> board) {
        Collection<TTWinCondition> coll = new ArrayList<>();
        for (TTWinCondition cond : board.getWinConds()) {
            if (cond.hasWinnable(field))
                coll.add(cond);
        }
        return coll;
    }

    /**
     * Get all smaller tiles/boards in a board
     * 
     * @param board Board to scan
     * @return Collection of all smaller tiles/boards contained in board.
     */
    public static <T> Collection<T> getAllSubs(HasSub<T> board) {
        List<T> list = new ArrayList<>();
        int sizeX = board.getSizeX();
        int sizeY = board.getSizeY();
        for (int x = 0; x < sizeX; x++) {
            for (int y = 0; y < sizeY; y++) {
                list.add(board.getSub(x, y));
            }
        }
        return list;
    }

    /**
     * Recursively scan for smaller subs
     * 
     * @param game The outermost object to scan
     * @return A collection containing all fields within the specified 'game' which do not have any subs
     */
    public static Collection<TTBase> getAllSmallestFields(TTBase game) {
        Collection<TTBase> all = new ArrayList<>();

        for (TTBase sub : TicUtils.getAllSubs(game)) {
            if (sub.hasSubs())
                all.addAll(getAllSmallestFields(sub));
            else all.add(sub);
        }
        return all;
    }
    /**
     * Create win conditions
     * 
     * @param board The board to create win conditions for
     * @return A list of all WinConditions that was created
     */
    public static List<TTWinCondition> setupWins(final HasSub<? extends Winnable> board) {
        if (!board.hasSubs()) {
            ArrayList<TTWinCondition> list = new ArrayList<>();
            list.add(new TTWinCondition(board));
            return list;
        }

        int consecutive = board.getConsecutiveRequired();
        List<TTWinCondition> conds = new ArrayList<>();

        // Scan columns for a winner
        for (int xx = 0; xx < board.getSizeX(); xx++) {
            newWin(conds, consecutive, loopAdd(board, xx, 0, 0, 1));
        }

        // Scan rows for a winner
        for (int yy = 0; yy < board.getSizeY(); yy++) {
            newWin(conds, consecutive, loopAdd(board, 0, yy, 1, 0));
        }

        // Scan diagonals for a winner: Bottom-right
        for (int yy = 0; yy < board.getSizeY(); yy++) {
            newWin(conds, consecutive, loopAdd(board, 0, yy, 1, 1));
        }
        for (int xx = 1; xx < board.getSizeX(); xx++) {
            newWin(conds, consecutive, loopAdd(board, xx, 0, 1, 1));
        }

        // Scan diagonals for a winner: Bottom-left
        for (int xx = 0; xx < board.getSizeY(); xx++) {
            newWin(conds, consecutive, loopAdd(board, xx, 0, -1, 1));
        }
        for (int yy = 1; yy < board.getSizeY(); yy++) {
            newWin(conds, consecutive, loopAdd(board, board.getSizeX() - 1, yy, -1, 1));
        }

        return conds;
    }

    private static void newWin(List<TTWinCondition> conds, int consecutive, List<Winnable> winnables) {
        if (winnables.size() >= consecutive) // shorter win conditions doesn't need to be added as they will never be able to win
            conds.add(new TTWinCondition(winnables, consecutive));
    }

    private static List<Winnable> loopAdd(HasSub<? extends Winnable> board,
            int xx, int yy, int dx, int dy) {
        List<Winnable> winnables = new ArrayList<>();

        Winnable tile;
        do {
            tile = board.getSub(xx, yy);
            xx += dx;
            yy += dy;
            if (tile != null)
                winnables.add(tile);
        }
        while (tile != null);

        return winnables;
    }

}

TTBase.java: (149 lines, 3623 bytes)

public class TTBase implements Winnable, HasSub<TTBase> {
    // Container
    private final TTBase[][] subs;
    private final TTMNKParameters mnkParams;
    private final List<TTWinCondition> winConditions;

    // Winnable
    private final TTBase parent;
    private final int x;
    private final int y;
    private TTPlayer playedBy = TTPlayer.NONE;

    public TTBase(TTBase parent, TTMNKParameters parameters, TicFactory factory) {
        this(parent, 0, 0, parameters, factory);
    }
    public TTBase(TTBase parent, int x, int y, TTMNKParameters parameters, TicFactory factory) {
        this.parent = parent;
        this.mnkParams = parameters;
        this.x = x;
        this.y = y;

        this.subs = new TTBase[parameters.getWidth()][parameters.getHeight()];
        for (int xx = 0; xx < parameters.getWidth(); xx++) {
            for (int yy = 0; yy < parameters.getHeight(); yy++) {
                this.subs[xx][yy] = factory.construct(this, xx, yy);
            }
        }
        this.winConditions = Collections.unmodifiableList(TicUtils.setupWins(this));
    }

    public void determineWinner() {
        TTPlayer winner = TTPlayer.NONE;
        for (TTWinCondition cond : this.winConditions) {
            winner = winner.or(cond.determineWinnerNew());
        }
        this.playedBy = winner;
    }

    @Override
    public TTBase getSub(int x, int y) {
        if (!hasSubs() && x == 0 && y == 0)
            return this;
        if (x < 0 || y < 0)
            return null;
        if (x >= getSizeX() || y >= getSizeY())
            return null;
        return subs[x][y];
    }

    @Override
    public List<TTWinCondition> getWinConds() {
        return winConditions;
    }

    @Override
    public TTPlayer getWonBy() {
        return this.playedBy;
    }

    @Override
    public int getSizeX() {
        return this.mnkParams.getWidth();
    }

    @Override
    public int getSizeY() {
        return this.mnkParams.getHeight();
    }

    @Override
    public int getConsecutiveRequired() {
        return this.mnkParams.getConsecutiveRequired();
    }

    public TTMNKParameters getMNKParameters() {
        return this.mnkParams;
    }

    public TTBase getParent() {
        return parent;
    }

    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }

    public boolean isWon() {
        return playedBy != TTPlayer.NONE;
    }

    public void setPlayedBy(TTPlayer playedBy) {
        if (playedBy == null && this.hasSubs() && parent != null)
            new Exception().printStackTrace();
        this.playedBy = playedBy;
    }

    public boolean hasSubs() {
        return getSizeX() != 0 && getSizeY() != 0;
    }

    @Override
    public String toString() {
        return "{Pos " + x + ", " + y + "; Size " + getSizeX() + ", " + getSizeY() + "; Played by " + getWonBy() + ". Parent is " + parent + "}";
    }

    public void reset() {
        this.setPlayedBy(TTPlayer.NONE);
        for (int xx = 0; xx < getSizeX(); xx++) {
            for (int yy = 0; yy < getSizeY(); yy++) {
                this.getSub(xx, yy).reset();
            }
        }
    }
    public int getGlobalX() {
        if (parent == null)
            return 0;
        if (parent.getParent() == null)
            return x;
        return parent.getX() * parent.getParent().getSizeX() + this.x;
    }

    public int getGlobalY() {
        if (parent == null)
            return 0;
        if (parent.getParent() == null)
            return y;
        return parent.getY() * parent.getParent().getSizeY() + this.y;
    }

    public TTBase getSmallestTile(int x, int y) {
        int subX = x / getSizeX();
        int subY = y / getSizeY();
        TTBase board = getSub(subX, subY);
        if (board == null)
            throw new NullPointerException("No such smallest tile found: " + x + ", " + y);

        return board.getSub(x - subX*getSizeX(), y - subY*getSizeY());
    }

}

TTController.java: (110 lines, 2867 bytes)

public abstract class TTController {

    protected final TTBase game;
    protected TTPlayer currentPlayer = TTPlayer.X;
    private TTMoveListener  moveListener;
    private StringBuilder history;

    public TTController(TTBase board) {
        this.game = board;
        this.history = new StringBuilder();
    }

    public abstract boolean isAllowedPlay(TTBase tile);

    public final boolean play(TTBase tile) {
        if (tile == null)
            throw new IllegalArgumentException("Tile to play at cannot be null.");

        if (!isAllowedPlay(tile)) {
            System.out.println("Warning: Move was not made. Unable to play at " + tile);
            return false;
        }
        TTBase playedTile = tile;
        if (!this.performPlay(tile))
            return false;

        this.addToHistory(tile);

        if (this.moveListener != null)
            this.moveListener.onMove(playedTile);

        return true;
    }

    private void addToHistory(TTBase tile) {
        if (history.length() > 0)
            history.append(",");
        history.append(Integer.toString(tile.getGlobalX(), Character.MAX_RADIX));
        history.append(Integer.toString(tile.getGlobalY(), Character.MAX_RADIX));
    }

    protected abstract boolean performPlay(TTBase tile);

    public boolean play(int x, int y) {
        return this.play(game.getSmallestTile(x, y));
    }

    public TTPlayer getCurrentPlayer() {
        return currentPlayer;
    }

    protected void nextPlayer() {
        currentPlayer = currentPlayer.next();
    }

    public TTBase getGame() {
        return game;
    }

    public boolean isGameOver() {
        return game.isWon();
    }

    public TTPlayer getWonBy() {
        return game.getWonBy();
    }

    public void setOnMoveListener(TTMoveListener moveListener) {
        this.moveListener = moveListener;
    }


    public void makeMoves(String history) throws IllegalStateException, IllegalArgumentException {
        for (String move : history.split(",")) {
            if (move.isEmpty())
                continue;
            if (move.length() != 2)
                throw new IllegalArgumentException("Unexcepted move length. " + move);

            int x = Integer.parseInt(String.valueOf(move.charAt(0)), Character.MAX_RADIX);
            int y = Integer.parseInt(String.valueOf(move.charAt(1)), Character.MAX_RADIX);

            TTBase tile = game.getSmallestTile(x, y);
            if (!this.play(tile))
                throw new IllegalStateException("Unable to make a move at " + x + ", " + y + ": " + tile);
        }
    }
    public String saveHistory() {
        return this.history.toString();
    }

    public void reset() {
        this.currentPlayer = TTPlayer.X;
        this.history = new StringBuilder();
        this.game.reset();
        this.onReset();
    }

    protected abstract void onReset();

    public String getViewFor(TTBase tile) {
        return tile.isWon() ? tile.getWonBy().toString() : "";
    }
}

TTFactories.java: (52 lines, 1616 bytes)

public class TTFactories {
    private static final TTMNKParameters mnkEmpty = new TTMNKParameters(0, 0, 0);

    private static final TicFactory lastFactory = new TicFactory() {
        @Override
        public TTBase construct(TTBase parent, int x, int y) {
            return new TTBase(parent, x, y, mnkEmpty, null);
        }
    };
    private static final TicFactory areaFactory = new TicFactory() {
        @Override
        public TTBase construct(TTBase parent, int x, int y) {
            return new TTBase(parent, x, y, parent.getMNKParameters(), lastFactory);
        }
    };

    public static class Factory implements TicFactory {
        private final TTMNKParameters   mnk;
        private final TicFactory    next;
        public Factory(TTMNKParameters mnk, TicFactory nextFactory) {
            this.mnk = mnk;
            this.next = nextFactory;
        }
        @Override
        public TTBase construct(TTBase parent, int x, int y) {
            return new TTBase(parent, x, y, mnk, next);
        }
    }

    public TTBase classicMNK(int width, int height, int consecutive) {
        return new TTBase(null, new TTMNKParameters(width, height, consecutive), lastFactory);
    }
    public TTBase classicMNK(int mnk) {
        return classicMNK(mnk, mnk, mnk);
    }
    public TTBase ultimate(int mnk) {
        return ultimate(mnk, mnk, mnk);
    }
    public TTBase ultimate(int width, int height, int consecutive) {
        return new TTBase(null, new TTMNKParameters(width, height, consecutive), areaFactory);
    }
    public TTBase ultimate() {
        return ultimate(3);
    }
    public TTBase othello(int size) {
        return new TTBase(null, new TTMNKParameters(size, size, size + 1), lastFactory);
    }


}

TTMNKParameters.java: (27 lines, 533 bytes)

public class TTMNKParameters {

    private final int width;
    private final int height;
    private final int consecutiveRequired;

    public TTMNKParameters(int width, int height, int consecutiveRequired) {
         this.width = width;
         this.height = height;
         this.consecutiveRequired = consecutiveRequired;
    }

    public int getConsecutiveRequired() {
        return consecutiveRequired;
    }

    public int getHeight() {
        return height;
    }

    public int getWidth() {
        return width;
    }

}

TTMoveListener.java: (5 lines, 104 bytes)

public interface TTMoveListener {
    void onMove(TTBase playedAt);
}

TTPlayer.java: (54 lines, 1273 bytes)

public enum TTPlayer {

    NONE, X, O, XO;

    public TTPlayer next() {
        if (!isExactlyOnePlayer())
            throw new UnsupportedOperationException("Only possible to call .next() on a real player but it was called on " + this);
        return this == X ? O : X;
    }

    /**
     * Determine if this player is (also) another player.<br>
     * This is the same as <code>this.and(other) == other</code>
     * 
     * @param other
     * @return
     */
    public boolean is(TTPlayer other) {
        return this.and(other) == other;
    }

    public TTPlayer and(TTPlayer other) {
        if (this == NONE || other == NONE || other == null)
            return NONE;
        if (isExactlyOnePlayer() && other.isExactlyOnePlayer())
            return this == other ? this : NONE;
        if (this == XO)
            return other;
        return other.and(this);
    }

    public boolean isExactlyOnePlayer() {
        return this == X || this == O;
    }

    public static boolean isExactlyOnePlayer(TTPlayer winner) {
        return winner != null && winner.isExactlyOnePlayer();
    }

    public TTPlayer or(TTPlayer other) {
        if (this == NONE || other == null)
            return other;
        if (other == NONE)
            return this;
        if (this == XO)
            return this;
        if (this != other)
            return XO;
        return this;
    }

}

TTUltimateController.java: (53 lines, 1386 bytes)

public class TTUltimateController extends TTController {
    // TODO: Try making it even more Ultimate by adding one more dimension, and use Map<TTBase, TTBase> activeBoards. Just for fun.
    private TTBase activeBoard = null;

    public TTUltimateController(TTBase board) {
        super(board);
    }

    @Override
    public boolean isAllowedPlay(TTBase tile) {
        TTBase area = tile.getParent();
        if (area == null)
            return false;
        TTBase game = tile.getParent().getParent();

        if (!tile.getWonBy().equals(TTPlayer.NONE))
            return false;
        if (area.getWonBy().isExactlyOnePlayer())
            return false;
        if (game.isWon())
            return false;

        return activeBoard == null || activeBoard == area || activeBoard.getWonBy() != TTPlayer.NONE;
    }

    @Override
    public boolean performPlay(TTBase tile) {
        tile.setPlayedBy(currentPlayer);
        activeBoard = TicUtils.getDestinationBoard(tile);
        nextPlayer();

        // Check for win condition on tile and if there is a win, cascade to it's parents
        do {
            tile.determineWinner();
            tile = tile.isWon() ? tile.getParent() : null;
        }
        while (tile != null);

        return true;
    }

    @Override
    protected void onReset() {
        this.activeBoard = null;
    }

}

TTWinCondition.java: (78 lines, 2026 bytes)

public class TTWinCondition implements Iterable<Winnable> {

    private final List<Winnable> winnables;
    private final int consecutive;

    public TTWinCondition(Winnable... winnables) {
        this(Arrays.asList(winnables));
    }

    public TTWinCondition(List<? extends Winnable> winnables) {
        this(winnables, winnables.size());
    }

    public TTWinCondition(List<? extends Winnable> winnables, int consecutive) {
        if (winnables.isEmpty())
            throw new IllegalArgumentException("Can't have an empty win condition!");
        this.winnables = Collections.unmodifiableList(new ArrayList<Winnable>(winnables));
        this.consecutive = consecutive;
    }

    public int neededForWin(TTPlayer player) {
        return winnables.size() - hasCurrently(player);
    }
    public boolean isWinnable(TTPlayer byPlayer) {
        return hasCurrently(byPlayer.next()) == 0;
    }
    public int hasCurrently(TTPlayer player) {
        int i = 0;
        for (Winnable winnable : winnables) {
            if (winnable.getWonBy().and(player) == player)
                i++;
        }
        return i;
    }

    public TTPlayer determineWinnerNew() {
        TTPlayer winner = TTPlayer.NONE;

        int[] consecutivePlayers = new int[TTPlayer.values().length];
        for (Winnable winnable : winnables) {
            TTPlayer current = winnable.getWonBy();
            for (TTPlayer pl : TTPlayer.values()) {
                int i = pl.ordinal();
                if (pl.and(current) == pl) {
                    consecutivePlayers[i]++;
                }
                else consecutivePlayers[i] = 0;

                if (consecutivePlayers[i] >= this.consecutive) {
                    winner = winner.or(pl);
                }
            }
        }
        return winner;
    }

    public boolean hasWinnable(Winnable field) {
        return winnables.contains(field);
    }

    public int size() {
        return winnables.size();
    }

    @Override
    public Iterator<Winnable> iterator() {
        return new ArrayList<Winnable>(this.winnables).iterator();
    }

}

Winnable.java: (7 lines, 93 bytes)

public interface Winnable {

    TTPlayer getWonBy();

}

Usage / Test

You can play the game on http://www.zomis.net/ttt . The GUI checks with the controller if a field can be played or not and uses the methods provided by the controller to make a move on a field. The GUI is written using GWT (Google Web Toolkit) which compiles my Java code to JavaScript and obfuscates it for me.

Questions

Things I am quite proud of includes the TTWinCondition class, especially the way TTWinConditions is created.

I am also quite proud of the TTPlayer enum and how it includes both NONE and XO (both), and it's and and or methods.

Things I am not so proud of includes the TTBase class. It is the best thing I could come up with though (and it is probably the most unique way of all the challenge implementations). I really couldn't come up with a more flexible way that would support any number of recursiveness, and at the same time removing code duplication.

This project uses Java 7. It also needs to support GWT so I cannot use String.format.

I'd mostly like comments about how I have designed these classes and interfaces. And if anyone knows a better way to do things than what I have done here, I'd love to hear them.

You may not agree with my naming of classes to start with TT, but I do this to make it easier for me to find my TTT-specific classes when using Eclipse's Ctrl + Shift + T keyboard shortcut.

\$\endgroup\$
12
\$\begingroup\$

There is not much to criticize in your code.... and there is a lot of code to go though.

Mostly really neat, and, it takes a while to 'grok' it, but it comes together OK.

Here's a laundry-list of small items (there are no big Items I can see):

  • In TTUtils:

    • getWinCondsWith is a method that is never called from anywhere
    • getAllSmallestFields should be called getAllSmallestSubs to match other methods.
  • In TTBase:

    • Unmodifiable in constructor:

      this.winConditions = Collections.unmodifiableList(TicUtils.setupWins(this));
      

      I would expect the unmodifiable constraint to be set in setupWins(), in other words it should return an unmodifyable list rather than having that imposed outside the call.

    • in setPlayedBy() you have:

      if (playedBy == null && this.hasSubs() && parent != null)
           new Exception().printStackTrace();
      

      No Braces is against Java code-style

      You are printing a stack trace, but continuing to set the value null anyway.

      This would be a good location for an assert.

  • TTFactories

    • all the private-static-final fields should be ALL_UPPERCASE per the Java Guidelines
  • TTPlayer

    • un-braced 1-liner if statements again:

    • or - if this==NONE and other == null, then why return null instead of NONE?

          public TTPlayer or(TTPlayer other) {
              if (this == NONE || other == null)
                  return other;
              if (other == NONE)
                  return this;
              if (this == XO)
                  return this;
              if (this != other)
                  return XO;
              return this;
          }
      
\$\endgroup\$
4
\$\begingroup\$

More than four years later... I discovered a bug in the code below:

// Scan diagonals for a winner: Bottom-left
for (int xx = 0; xx < board.getSizeY(); xx++) {
    newWin(conds, consecutive, loopAdd(board, xx, 0, -1, 1));
}
for (int yy = 1; yy < board.getSizeY(); yy++) {
    newWin(conds, consecutive, loopAdd(board, board.getSizeX() - 1, yy, -1, 1));
}

When you mix x and y on the same line, it's usually an indication that you are doing something wrong. Your code can be used in any MNK-game which is nice, but this code will not check for a winning condition in this case for a 7,6,4 game (Connect Four):

0000000
0000000
0000X00
000XO00
00XOO00
0XOOX00

Because the last bottom-left scan is missing because of getSizeY() being one less than getSizeX(), correct would be:

for (int xx = 0; xx < board.getSizeX(); xx++) {

(Seems like I have a thing for finding bugs four years later)

\$\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.