Tic Tac Toe Samples

readme.md

Overview

These samples partially implement the game of tic tac toe, with specific focus on validating and placing submitted placements. The purpose of this exercise is to evaluate design tradeoffs within a small, easily-consumable domain. The ultimate goal is to determine: Is one design more suitable than the others when considering things like coupling, cohesion, thread safety, etc.? Are they all equally valid and just a matter of personal opinion?

The samples are designed specifically to hide information within objects and to disallow getter and setter methods. The Placement object in particular, is an abstraction derived from the domain of "a player submits a placement to the game". The purpose of introducing the Placement abstraction is to a) create an abstraction that ignores details until they are needed, b) create a situation where data is hidden a layer deeper in the object graph, i.e., we have Game::submit(Placement placement) instead of Game::submit(Mark mark, Position position). It is also true that a Mark and Position are closely related, so can be passed through the system together as members of a single abstraction.

Feel free to comment on any merits or faults to the designs for any observed reasons, or personal preferences.

Note that some methods, for example the printing methods, reference classes and interfaces that are not included. The printing methods were kept to show how the objects might be printed, but the other interfaces were left out to avoid clutter.

Note also that some of the particulars of my evaluation are pointless considerations for a small application like this, but the point is to pretend we are making decisions about real code, in a real domain that requires these considerations.

Notes on Each Sample

Sample 1

A typical implementation for validating a Placement would be to have a method:

bool Placement::isValid(Mark playingMark, Grid grid)

However, the goal is to eliminate state-based metaphors. If we were to read this method literally, it says "produce an integer in the range of 0 to 1 representing the validity of the placement". This is using tools outside the domain (integers/booleans) to implement a domain concept.

The solution in this sample is to tell the Placement to validate, keeping track of the result.

Placement Placement::validate(Mark playingMark, Grid grid)

The method simply returns itself instead of void, but void could have been used as well.

I noticed two effects:

1. The method, when read literally, remains within the domain: "validate the placement".
2. We've turned an immutable operation into a mutable one.

Item number two is the concern in this design, as pushing behavior into objects like this causes objects to tend toward mutability. We didn't really intend to change the state of the placement. It's state is its mark and position, which don't change. We really want to ask it the question "are you valid?" without altering it. While the design eliminates the state-based metaphor for the caller, we have to manage state within the object. I think it's better to keep state inside an object, but managing mutability can still be troublesome. It also has the effect of making what was a threadsafe operation, non-threasafe. We could always create a threadsafe wrapper using synchronization or locks.

Note that the methods:

Mark Mark::validate(Mark playingMark, Placement placement) and Grid Grid::validate(Position position, Placement placement)

are immutable operations because the objects don't change state. They pass their validation result to the placement object. Sample 2 takes this concept further by passing more objects as continuations.

Sample 2

This sample is reminiscient of Continuation-Passing Style (CPS). Results are not returned and objects don't change state. Instead, the results of operations are sent to an object passed in the initial method call specifically to accept the result. This object in turn does the same.

In this sample, we accept that the Game will change state. We intend for the game to change state by calling the mutator:

Game Game::submit(Placement placement)

We also accept that the Grid will change state when we finally place a valid Placement on it.

The difference is operations that are simply computing an answer to a question, that shouldn't change any object's state, don't change those objects while they are computing.

I noticed three effects:

1. Methods gain an extra dependency, increasing coupling.
2. We gain back threadsafety, as methods, e.g. Placement::validate, don't alter the objects that are computing the answer.
3. We have more methods to coordinate communication.

The question here is: Are the extra dependencies and coupling worth it?

The threadsafety would allow a developer to reuse the Placement to validate multiple games, without having to worry about the Placement's state changing.

// We accept that the Game will capture the end result of our continuations,
// eventually changing state, but nothing else (placement, mark, or grid) will.
Game game1;
Game game2;
placement.validate(aPlayingMark, aGrid, game1)
placement.validate(aPlayingMark, aGrid, game2)

You'll notice a few extra methods on the Mark, Grid, and Placement to coordinate the process of validating and continuing. I also included symmetric methods on the Mark an Grid. The reason can be seen from the implementation of

Placement Placement::validate(Mark playingMark, Grid grid, Game game) {
    mark.validateAndContinue(playingMark, this, grid, game);
    return this;
}

Here we ask the Mark to initiate the validation, but only implementing this would preclude a developer from validating by starting with the Grid first. So, the validateAndContinue methods on Grid and Mark begin the validation and continue until one of their validate methods are called.

This adds back the flexibility we had in Sample 1, where we could implement Placement::validate as:

(method implementation inlined for clarity)

public Placement Placement::validate(Mark playingMark, Grid grid) {
    mark.validate(mark, this);
    grid.validate(position, this);
}

or

public Placement Placement::validate(Mark playingMark, Grid grid) {
    grid.validate(position, this);
    mark.validate(mark, this);
}

because Placement collects the results.

The difference is it requires a few extra methods in Sample 2 to do this.

Ultimately, I wonder if Sample 2's communication pattern is too confusing to follow easily.

Sample 3

In this sample, just about everything is immutable.

I noticed two effects:

1. Instead of methods coupling to an new dependency to use as a continuation, methods of different classes are coupled to returning collaborating object types.
2. Overhead of creating lots of new objects.

In this case, methods needs to return collaborating types to maintain a "tell, don't ask" style and maintain immutability.

Is this a better option compared to just adding synchronization to Sample 1?

Sample 1 (mutable Placement).java

// Game
public class Game {

    private final Grid grid;
    private final PlacementError placementError;
    private Mark playingMark;
    
    public Game(PlacementError placementError) {
        grid = new Grid();
        playingMark = Mark.x();
        this.placementError = placementError;
    }
    
    public Game submit(Placement placement) {
        return validate(placement)
                .placePlacement(placement)
                .switchPlayers();
    }
    
    private Game validate(Placement placement) {
        placement.validate(playingMark, grid);
        return this;
    }

    private Game placePlacement(Placement placement) {
        placement.place(this, placementError);
        return this;
    }
    
    public Game place(Placement placement) {
        placement.place(grid);
        return this;
    }
    
    private Game switchPlayers() {
        playingMark = playingMark.opponent();
        return this;
    }

    public Game printOn(GameMedia gameMedia) {
        grid.printOn(gameMedia);
        return this;
    }
}

// Placement
public class Placement {

    private final Mark mark;
    private final Position position;
    private boolean canPlayMark;
    private boolean canPlayPosition;
        
    public Placement(Mark mark, Position position) {
        this.mark = mark;
        this.position = position;
        canPlayMark = false;
        canPlayPosition = false;
    }
    
    public Placement validate(Mark playingMark, Grid grid) {
        return canPlayMark(playingMark).canPlayPosition(grid);
    }

    private Placement canPlayMark(Mark playingMark) {
        mark.validate(playingMark, this);
        return this;
    }

    private Placement canPlayPosition(Grid grid) {
        grid.validate(position, this);
        return this;
    }
    
    public Placement validMark() {
        canPlayMark = true;
        return this;
    }
    
    public Placement validPosition() {
        canPlayPosition = true;
        return this;
    }
    
    public Placement place(Game game, PlacementError placementError) {
        if(canPlayMark && canPlayPosition)
            game.place(this);
        else
            placementError.report(this);
        
        return this;
    }
    
    public Placement place(Grid grid) {
        grid.place(mark, position);
        return this;
    }
    
    public Placement printOn(PlacementMedia placementMedia) {
        placementMedia.printMarkAndPosition(mark, position);
        return this;
    }
}

// Mark
public class Mark {

    private static Mark X = new Mark("X");
    private static Mark O = new Mark("O");
    private static Mark Empty = new Mark(" ");
    
    private final String symbol;
    
    private Mark(String symbol) {
        this.symbol = symbol;
    }

    public void printOn(MarkMedia markMedia) {
        markMedia.printMark(symbol);
    }

    public static Mark x() {
        return Mark.X;
    }

    public static Mark o() {
        return Mark.O;
    }

    public static Mark empty() {
        return Mark.Empty;
    }

    public Mark opponent() {
        return this.equals(x()) ? Mark.o() : Mark.x();
    }

    public Mark validate(Mark playingMark, Placement placement) {
        if(this.equals(playingMark)) {
            placement.validMark();
        }
        return this;
    }
}

// Grid
public class Grid {

    private final HashMap<Position, Mark> gridPositions;
    private final Mark nullMark;
    
    public Grid() {
        this.nullMark = Mark.empty();
        gridPositions = new HashMap<Position, Mark>();
    }
    
    public Grid validate(Position position, Placement placement) {
        if(isPositionAvailable(position)) {
            placement.validPosition();
        }
        
        return this;
    }

    private boolean isPositionAvailable(Position position) {
        return !gridPositions.containsKey(position) && gridPositions.get(position) == null;
    }

    public Grid place(Mark mark, Position position) {
        gridPositions.put(position, mark);
        return this;
    }

    public Grid printOn(GridMedia gridMedia) {
        gridMedia.printRow(markAt(Position.TopLeft()), markAt(Position.TopCenter()), markAt(Position.TopRight()));
        gridMedia.printRowDivider();
        gridMedia.printRow(markAt(Position.MiddleLeft()), markAt(Position.MiddleCenter()), markAt(Position.MiddleRight()));
        gridMedia.printRowDivider();
        gridMedia.printRow(markAt(Position.BottomLeft()), markAt(Position.BottomCenter()), markAt(Position.BottomRight()));
        gridMedia.printBreak();
        return this;
    }
    
    private Mark markAt(Position position) {
        Mark mark = gridPositions.get(position);
        return mark != null ? mark : nullMark;
    }
}

// Main
public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        ConsoleGameMedia consoleGameMedia = new ConsoleGameMedia();
        Game game = new Game(new ConsolePlacementError());
        game.submit(new Placement(Mark.x(), Position.TopLeft()));
        game.printOn(consoleGameMedia);
        game.submit(new Placement(Mark.o(), Position.MiddleCenter()));
        game.printOn(consoleGameMedia);
        game.submit(new Placement(Mark.o(), Position.TopRight())); // Try out of turn player, valid position
        game.printOn(consoleGameMedia);
        game.submit(new Placement(Mark.x(), Position.TopLeft())); // Try correct player, invalid position
        game.printOn(consoleGameMedia);
    }
}

// Output
 X |   |   
---+---+---
   |   |   
---+---+---
   |   |   

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Invalid placement: O at TR

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Invalid placement: X at TL

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Sample 2 (immutable Placement + CPS-ish).java

// Game
public class Game {

    private final Grid grid;
    private final PlacementError placementError;
    private Mark playingMark;
    
    public Game(PlacementError placementError) {
        grid = new Grid();
        playingMark = Mark.x();
        this.placementError = placementError;
    }
    
    public Game submit(Placement placement) {
        placement.validate(playingMark, grid, this);
        return this;
    }
    
    public Game validPlacement(Placement placement) {
        place(placement).switchPlayers();
        return this;
    }

    private Game place(Placement placement) {
        placement.place(grid);
        return this;
    }
    
    public Game invalidPlacement(Placement placement) {
        placementError.report(placement);
        return this;
    }
    
    private Game switchPlayers() {
        playingMark = playingMark.opponent();
        return this;
    }

    public Game printOn(GameMedia gameMedia) {
        grid.printOn(gameMedia);
        return this;
    }
}

// Placement
public class Placement {

    private final Mark mark;
    private final Position position;
        
    public Placement(Mark mark, Position position) {
        this.mark = mark;
        this.position = position;
    }
    
    public Placement validate(Mark playingMark, Grid grid, Game game) {
        mark.validateAndContinue(playingMark, this, grid, game);
        return this;
    }

    public Placement validMarkContinueWith(Grid grid, Game game) {
        grid.validate(position, this, game);
        return this;
    }
    
    public Placement validPositionContinueWith(Mark playingMark, Game game) {
        mark.validate(playingMark, this, game);
        return this;
    }
    
    public Placement validPosition(Game game) {
        game.validPlacement(this);
        return this;
    }
    
    public Placement validMark(Game game) {
        game.validPlacement(this);
        return this;
    }
    
    public Placement place(Grid grid) {
        grid.place(mark, position);
        return this;
    }
    
    public Placement printOn(PlacementMedia placementMedia) {
        placementMedia.printMarkAndPosition(mark, position);
        return this;
    }
}

// Mark
public class Mark {

    private static Mark X = new Mark("X");
    private static Mark O = new Mark("O");
    private static Mark Empty = new Mark(" ");
    
    private final String symbol;
    
    private Mark(String symbol) {
        this.symbol = symbol;
    }

    public void printOn(MarkMedia markMedia) {
        markMedia.printMark(symbol);
    }

    public static Mark x() {
        return Mark.X;
    }

    public static Mark o() {
        return Mark.O;
    }

    public static Mark empty() {
        return Mark.Empty;
    }

    public Mark opponent() {
        return this.equals(x()) ? Mark.o() : Mark.x();
    }

    public Mark validateAndContinue(Mark playingMark, Placement placement, Grid grid, Game game) {
        if(this.equals(playingMark)) {
            placement.validMarkContinueWith(grid, game);
        }
        else {
            game.invalidPlacement(placement);
        }
        return this;
    }

    public Mark validate(Mark playingMark, Placement placement, Game game) {
        if(this.equals(playingMark)) {
            placement.validMark(game);
        }
        else {
            game.invalidPlacement(placement);
        }
        return this;
    }
}

// Grid
public class Grid {

    private final HashMap<Position, Mark> gridPositions;
    private final Mark nullMark;
    
    public Grid() {
        this.nullMark = Mark.empty();
        gridPositions = new HashMap<Position, Mark>();
    }
    
    public Grid validate(Position position, Placement placement, Game game) {
        if(isPositionAvailable(position)) {
            placement.validPosition(game);
        }
        else {
            game.invalidPlacement(placement);
        }
        return this;
    }
    
    public Grid validateAndContinue(Position position, Placement placement, Mark playingMark, Game game) {
        if(isPositionAvailable(position)) {
            placement.validPositionContinueWith(playingMark, game);
        }
        else {
            game.invalidPlacement(placement);
        }
        return this;
    }

    private boolean isPositionAvailable(Position position) {
        return !gridPositions.containsKey(position) && gridPositions.get(position) == null;
    }

    public Grid place(Mark mark, Position position) {
        gridPositions.put(position, mark);
        return this;
    }

    public Grid printOn(GridMedia gridMedia) {
        gridMedia.printRow(markAt(Position.TopLeft()), markAt(Position.TopCenter()), markAt(Position.TopRight()));
        gridMedia.printRowDivider();
        gridMedia.printRow(markAt(Position.MiddleLeft()), markAt(Position.MiddleCenter()), markAt(Position.MiddleRight()));
        gridMedia.printRowDivider();
        gridMedia.printRow(markAt(Position.BottomLeft()), markAt(Position.BottomCenter()), markAt(Position.BottomRight()));
        gridMedia.printBreak();
        return this;
    }
    
    private Mark markAt(Position position) {
        Mark mark = gridPositions.get(position);
        return mark != null ? mark : nullMark;
    }
}

// Main
public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        ConsoleGameMedia consoleGameMedia = new ConsoleGameMedia();
        Game game = new Game(new ConsolePlacementError());
        game.submit(new Placement(Mark.x(), Position.TopLeft()));
        game.printOn(consoleGameMedia);
        game.submit(new Placement(Mark.o(), Position.MiddleCenter()));
        game.printOn(consoleGameMedia);
        game.submit(new Placement(Mark.o(), Position.TopRight())); // Try out of turn player, valid position
        game.printOn(consoleGameMedia);
        game.submit(new Placement(Mark.x(), Position.TopLeft())); // Try correct player, invalid position
        game.printOn(consoleGameMedia);
    }
}

// Output
 X |   |   
---+---+---
   |   |   
---+---+---
   |   |   

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Invalid placement: O at TR

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Invalid placement: X at TL

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Sample 3 (more immutable).java

// Game
public class Game {

    private final Grid grid;
    private final PlacementError placementError;
    private final Mark playingMark;
    
    public Game(PlacementError placementError) {
        grid = new Grid();
        playingMark = Mark.x();
        this.placementError = placementError;
    }
    
    private Game(Grid grid, Mark playingMark, PlacementError placementError) {
        this.grid = grid;
        this.playingMark = playingMark;
        this.placementError = placementError;
    }

    public Game submit(Placement placement) {
        placement = placement.validated(playingMark, grid);
        return placement.placed(this, placementError);
    }

    public Game withPlaced(Placement placement) {
        Grid placedGrid = grid.withPlacement(placement);
        return new Game(placedGrid, playingMark.opponent(), placementError);
    }

    public Game printOn(GameMedia gameMedia) {
        grid.printOn(gameMedia);
        return this;
    }
}

// Placement
public class Placement {

    private final Mark mark;
    private final Position position;
    private final boolean canPlayMark;
    private final boolean canPlayPosition;
        
    public Placement(Mark mark, Position position) {
        this(mark, position, false, false);
    }
    
    private Placement(Mark mark, Position position, boolean canPlayMark, boolean canPlayPosition) {
        this.mark = mark;
        this.position = position;
        this.canPlayMark = canPlayMark;
        this.canPlayPosition = canPlayPosition;
    }
    
    public Placement validated(Mark playingMark, Grid grid) {
        Placement validatedPlacement = this;
        validatedPlacement = mark.validatedPlacement(playingMark, validatedPlacement);
        validatedPlacement = grid.validatedPlacement(position, validatedPlacement);
        return validatedPlacement;
    }
    
    public Placement withValidMark() {
        return new Placement(mark, position, true, canPlayPosition);
    }
    
    public Placement withValidPosition() {
        return new Placement(mark, position, canPlayMark, true);
    }
    
    public Game placed(Game game, PlacementError placementError) {
        if(canPlayMark && canPlayPosition)
            return game.withPlaced(this);
        
        placementError.report(this);
        return game;
    }
    
    public Grid placedGrid(Grid grid) {
        return grid.with(mark, position);
    }
    
    public Placement printOn(PlacementMedia placementMedia) {
        placementMedia.printMarkAndPosition(mark, position);
        return this;
    }
}

// Mark
public class Mark {

    private static Mark X = new Mark("X");
    private static Mark O = new Mark("O");
    private static Mark Empty = new Mark(" ");
    
    private final String symbol;
    
    private Mark(String symbol) {
        this.symbol = symbol;
    }

    public void printOn(MarkMedia markMedia) {
        markMedia.printMark(symbol);
    }

    public static Mark x() {
        return Mark.X;
    }

    public static Mark o() {
        return Mark.O;
    }

    public static Mark empty() {
        return Mark.Empty;
    }

    public Mark opponent() {
        return this.equals(x()) ? Mark.o() : Mark.x();
    }

    public Placement validatedPlacement(Mark playingMark, Placement placement) {
        if(this.equals(playingMark)) {
            return placement.withValidMark();
        }
        return placement;
    }
}

// Grid
public class Grid {

    private final HashMap<Position, Mark> gridPositions;
    private final Mark nullMark;
    
    public Grid() {
        this(new HashMap<Position, Mark>());
    }
    
    private Grid(HashMap<Position, Mark> gridPositions) {
        this.nullMark = Mark.empty();
        this.gridPositions = gridPositions;
    }
    
    public Placement validatedPlacement(Position position, Placement placement) {
        if(isPositionAvailable(position)) {
            return placement.withValidPosition();
        }

        return placement;
    }
    
    public Grid withPlacement(Placement placement) {
        return placement.placedGrid(this);
    }

    private boolean isPositionAvailable(Position position) {
        return !gridPositions.containsKey(position) && gridPositions.get(position) == null;
    }

    public Grid with(Mark mark, Position position) {
        HashMap<Position, Mark> newGridPositions = new HashMap<Position, Mark>(gridPositions);
        newGridPositions.put(position, mark);
        return new Grid(newGridPositions);
    }

    public Grid printOn(GridMedia gridMedia) {
        gridMedia.printRow(markAt(Position.TopLeft()), markAt(Position.TopCenter()), markAt(Position.TopRight()));
        gridMedia.printRowDivider();
        gridMedia.printRow(markAt(Position.MiddleLeft()), markAt(Position.MiddleCenter()), markAt(Position.MiddleRight()));
        gridMedia.printRowDivider();
        gridMedia.printRow(markAt(Position.BottomLeft()), markAt(Position.BottomCenter()), markAt(Position.BottomRight()));
        gridMedia.printBreak();
        return this;
    }
    
    private Mark markAt(Position position) {
        Mark mark = gridPositions.get(position);
        return mark != null ? mark : nullMark;
    }
}

// Main
public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        ConsoleGameMedia consoleGameMedia = new ConsoleGameMedia();
        Game game = new Game(new ConsolePlacementError());
        game = game.submit(new Placement(Mark.x(), Position.TopLeft()));
        game.printOn(consoleGameMedia);
        game = game.submit(new Placement(Mark.o(), Position.MiddleCenter()));
        game.printOn(consoleGameMedia);
        game = game.submit(new Placement(Mark.o(), Position.TopRight())); // Try out of turn player, valid position
        game.printOn(consoleGameMedia);
        game = game.submit(new Placement(Mark.x(), Position.TopLeft())); // Try correct player, invalid position
        game.printOn(consoleGameMedia);
    }
}

// Output
 X |   |   
---+---+---
   |   |   
---+---+---
   |   |   

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Invalid placement: O at TR

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |   

Invalid placement: X at TL

 X |   |   
---+---+---
   | O |   
---+---+---
   |   |