A better way to design TicTacToe

[Junilu Lacar]

In recent weeks, I've been using an exercise to explore various aspects of design and the thought process developers use to design programs. The problem I use is quite simple: the lowly game of Tic Tac Toe. I say "lowly" because on one occasion, an experienced developer I was auditioning for a tech lead role actually seemed insulted that I would ask them to solve such a "trivial" problem. I didn't argue with him but obviously, he didn't make the cut. That might seem a bit harsh, to disqualify someone on the basis of their refusal to write a small program like Tic Tac Toe, but I have very good reasons. I'll talk about that later in this thread.

For now, I'd like to get some thoughts on what your approach would be. Where would you start? What if you were asked to do this in a TDD (Test-Driven Development) way? Would that make a difference?

One thing I see many people do is to start with the user interface or display. This invariably leads to code that is more complex than it needs to be. I also think it's the wrong way to start, especially if you're doing TDD. Part of the reason is that input is an edge concern, not a main concern. I'd rather focus on the processing logic. Input and output can be done in many different ways so I want to make the decisions on how to do those later, when I have a better understanding of the problem and the solution.

Here's a recent example of what can happen when you start with the UI: https://coderanch.com/t/755457/java/set-text-field-Draw-wins

[Junilu Lacar]

When programmers focus on the UI too early in the development of a program, the design invariable turns out poorly, with business logic becoming tightly coupled with the presentation logic/implementation. Listing down the reasons this isn't A Good Thing™ is a good learning exercise.

[Stephan van Hulst]

I start out with listing the requirements. Maybe even group the requirements into different phases/epics. Not all requirements need to be known ahead of time, but at the very least those that are necessary for the first version of the application.

Once the requirements for the first epic are known, I start by identifying which classes the business layer of the application will need. For a game of TicTacToe, I will probably end up with the following types:

Mark/Piece/Color

Board

Game

I could imagine that for a first version, the Game just keeps going until the Board is full. There are no computer players, and there are no checks to see if there are three marks in a row. I would write the relevant test cases, and then implement those types.

When I'm confident that my business layer works the way it's supposed to work for this version of the application, I would also add a main application class that allows the player to play a single "game" through the CLI.

Adding a GUI usually becomes the focus on the third or fourth version of the application, after most of the basic game rules have been implemented.

[Campbell Ritchie]

That sounds just like what I was taught. Making GUI display classes double up for business logic violates the Single Responsibility Principle, because now the display classes are also playing the game.

[Junilu Lacar]

Here's the general approach I'm starting to settle on in my mind:

1. Start simple - what's the simplest way to boil down the problem so that you can define it in terms of a small set of Input-Process-Output specs.
2. Sketch out your high-level design. Keep it simple. Avoid too many details, especially ones that have to do with implementation rather than intent.
3. Define your ideas as tests. Try to make the tests about intent, not implementation.
4. Incrementally add functionality to make your test(s) pass.
5. Continuously revisit the story you're trying to tell. Tell the story to others and have them tell it back to you so you know your ideas are understood properly.
6. Listen to the stories you're telling and refactor whenever you hear something off or confusing.
7. Keep refining the story and refactoring the code until there are no more tests you can think of to write.

I'll walk through these steps in this thread. This could get long.

[Junilu Lacar]

1. Start simple: define the problem in terms of Input-Process-Output

Input: Moves (a number from 1...9 representing a spot on the board)
Process: Evaluate the move(s) and evaluate whether to keep going or end the game
Output: The result of the evaluation - either no winner and the game goes on, the game ends with a winner, or the game ends in a draw.

[Junilu Lacar]

2. Sketch out your high-level design. Keep it simple. Avoid too many details, especially ones that have to do with implementation rather than intent.

For this problem, I'll use main() as my drawing board.

public static void main(String[] args) {
   TicTacToe game = new TicTacToe();
   while (game.isInPlay()) {
      System.out.println(game);
      game.makeNextMove();
   }
   System.out.println(game);
   System.out.println(game.results());
}

This gives me a high-level roadmap and a rough idea of what things can be done with a TicTacToe object. It also gives me a starting point for my tests when I do Test-Driven Development on the TicTacToe class.

[Junilu Lacar]

3. Define your ideas as tests. Try to make the tests about intent, not implementation.

One of the hardest things to figure out when you're new to TDD is the answer to what would seem like a very simple question: "Where do I start?"

That's a question many who try TDD often struggle with. Through practice, I've come to these answers:

1. It doesn't really matter where you start; what matters is that you start at all. The test doesn't even have to be right. In fact, you often end up deleting the first few tests that you write. Don't worry, that's just part of the process of discovery. The journey always starts with a first step. It doesn't matter if the first step is in the wrong direction because if you take care and keep your path clear and your code clean, you can always backtrack or take a different tack.

2. Start with the simplest scenarios. Use James Grenning's ZOMBIES (Zero-One-Many-Boundaries-Interfaces-Exceptions-Simple Scenarios/Solutions) as a guide for what tests to write. Keep everything as small and as simple as possible.

3. Use your high-level map from the previous step as a guide.

In this case, my high-level map/sketch says I could focus on the idea of the game being in play, as represented by the isInPlay() method. Here's the first test that comes to mind:

@Test
void new_game_is_in_play() {
   TicTacToe game = new TicTacToe();
   assertTrue(game.isInPlay());
}

I like this test for a couple of reasons:

1. It's simple - only a couple lines of code

2. It's one of the ZERO cases, where nothing besides creating a TicTacToe object has occurred. No moves have been made yet, the board is still empty, there's no winner. This gives me a number of things I can assert about a new game and leads me to more ideas for other tests I could write.

[Junilu Lacar]

4. Incrementally add functionality to make your test(s) pass.
The first test will fail, of course, because we don't have a TicTacToe class or an isInPlay() method yet.

That's easy enough to fix:

public class TicTacToe {
   public boolean isInPlay() {
      return false;
   }
}

With this increment, the test we wrote will fail because isInPlay() returns false and our test expected true. This isn't a bad thing. Our first goal in TDD is to quickly get to Red, where we have a small test that fails.

We make the test fail on purpose because we want to make sure that it targets a specific part of the production code. Right now, the test is telling us that there's something wrong in our implementation. Since the test is small, it clearly says there's something wrong in the implementation of isInPlay(). Fixing it is easy enough:

   public boolean isInPlay() {
      return true;
   }

Now the test passes. We've got Green!

You might be thinking "Well, that's still wrong though" and you'd be absolutely correct. We know it's wrong, but the tests obviously don't. That tells us that we need more tests. The next test should make it clear that we still have a buggy implementation.

[Junilu Lacar]

Sidebar: Where's the input part?

I wrote:For this problem, I'll use main() as my drawing board.

public static void main(String[] args) {
   TicTacToe game = new TicTacToe();
   while (game.isInPlay()) {
      System.out.println(game);
      game.makeNextMove();
   }
   System.out.println(game);
   System.out.println(game.results());
}

At first glance, you might think my high-level sketch is missing the Input part of the Input-Process-Output specification I mentioned earlier. It's not explicit as the Process and Output parts, but it's implied by game.makeNextMove(), which kind of lumps together Input and Process.

Experience tells me I'm going to need a few ways to give a game the information it needs to progress. For testing, I'm going to need a way to tell the game what moves the players are making. I need this so I can keep the tests automated and fast and not have to revert to slow and error-prone manual testing.

For regular play, whether that's with a person playing against another person or the computer, or the computer simulating a game between two players, I will probably need a different way of giving the game the information of what move to make next.

These are implementation details though. My problem solving guideline says to try to stay with intent rather than implementation, at least while you're still exploring your ideas and trying to discover what the code wants to be.

"Discover what the code wants to be" may seem like a strange way of describing what we're doing but I like to think of it as how some artists think about what they do: a sculptor is really just taking a block of marble and revealing the statue that's inside it by chipping away everything that isn't part of the statue. A potter is simply helping the lump of clay become what it wants to be. An origamist (is that a word?) is just folding the paper into the shape it wants to be.

As a practitioner of TDD, I'm just using the tests to discover what the program wants to be.

[Junilu Lacar]

Speaking of input, I'd like to pause here to ask for your input. If you've been following along, try out the first few steps yourself. Have a conversation with yourself and talk yourself through the process. In my practice, I have found that having that internal conversation helps to firm up the idea. I like to think that it creates new neural pathways for reasoning.

What would your next failing test look like that would tell us there's still a bug in the isInPlay() method? Or maybe there's a different test you can write that would indirectly lead us to the test that shows us the bug? Maybe there's a different aspect of the TicTacToe class we need to detail out first?

What would your next move be?

[Junilu Lacar]

Stephan van Hulst wrote:I could imagine that for a first version, the Game just keeps going until the Board is full. There are no computer players, and there are no checks to see if there are three marks in a row. I would write the relevant test cases, and then implement those types.

This seems like a reasonable idea for a next move.

Any other ideas?

[Junilu Lacar]

Sidebar: Keeping things simple

Another thing I've noticed is the tendency to try to model everything as a class. Take this thread, for example: https://coderanch.com/t/620503/java/Tic-tac-toe-Design where the OP suggests this design:

Prasanna Raman wrote:I thought about the design and have come up with the following classes:

Game
 Attributes - Board and players.
 Behaviour - update the board, check if game has ended and/or find a winner and regulate players' turns.

Board
       Attributes - rows and columns. So I will need a data structure to store the board in.
       Behaviour - get updated by the game to reflect its latest state

Player
 Attributes - symbol
 Behaviour - play

Symbols - an enum class storing "X" and "O"

Please take a look and let me know the flaws in this design.

The reply to this was that there were no flaws but maybe there were a couple of classes missing. I'm not sure what those two classes would be myself as the proposed design seems to be already a few steps ahead in the evolution of the game.

I can see how at some point you might need to represent Players with a separate class. Same thing with the symbols because I can think of at least one interesting behavior for it. The Game vs Board, however, doesn't make sense to me. OP declares the Board's behavior as "get updated by the game to reflect its latest state" which hints at two violations of design principles: encapsulation and cohesion. I don't even see that as a proper behavior: it's something being done to you, whereas a behavior is something that you do in response to some stimulus. And to say the Game has behavior that includes "update the board" also smells inappropriate if you're thinking of the Game and Board as separate classes.

All of that hints at unnecessary complexity to me. I prefer to keep things simple then as ideas start to become unwieldy and certain behaviors start to exhibit a desire to be lumped together with certain data elements, that's when I start thinking about introducing another class to encapsulate them and improve cohesiveness.

[Stephan van Hulst]

For almost every board game I've ever programmed, I've found it immensely useful to separate a Board from a Game.

The Board class simply acts as a component of the game. It encapsulates all the logic and for interacting with a grid-like data structure, for games with a variable board size it performs range checking on positions, and it makes it explicit how coordinates relate to squares on the board. Another big benefit is that you can pass copies of the Board off to player strategies, who can inspect the Board to see what the next move is that they will make.

The Board doesn't care about legal moves. It just lets you put anything you want anywhere. In games such as Chess, that's very useful for setting up an interesting starting situation.

The Game class is what keeps track of the principal Board, and enforces the rules so that the Board is modified only in specific ways.

I really don't see how having a separate Board and Game class violates "encapsulation". On the other hand, I can easily see how putting an array inside the Game class could lead to violating "single responsibility". After all, besides controlling the flow of the game and enforcing the game's rules, it now also has to provide methods such as one to see if a square is occupied by a certain mark.

[Junilu Lacar]

Stephan van Hulst wrote:it now also has to provide methods such as one to see if a square is occupied by a certain mark.

Why? If your design respects the object's encapsulation, wouldn't you just say something like mark(spot) and the class will simply refuse to comply and/or emit an error message in response if the spot cannot be marked?

[Stephan van Hulst]

How is the outside world to know what spots it can mark without causing an error?

[Junilu Lacar]

Stephan van Hulst wrote:How is the outside world to know what spots it can mark without causing an error?

If it's a human player, by looking at the current representation of the game:

System.out.println(game);

. X .
O . .
. . .

X's turn to move(1, 3, 5-9): ?

You might also allow it to be queried with List<Integer> legalMoves().

[Junilu Lacar]

Junilu Lacar wrote:You might also allow it to be queried with List<Integer> legalMoves().

That might actually be useful in expressing a draw:

boolean isDraw() {
   return hasNoWinner() && legalMoves().isEmpty();
}

boolean hasNoWinner() {
   return !hasWinner();
}

boolean hasWinner() {
   return completedRow() || completedColumn() || completedDiagonal();
}

[Junilu Lacar]

Refactoring that a little more (optimizing compiler will most likely inline the method)

private boolean isDraw() {
   return hasNoWinner() && hasNoLegalMoves();
}

private boolean hasNoLegalMoves() {
   return legalMoves().isEmpty();
}

public List<Integer> legalMoves() {
   return IntStream.rangeClosed(1, 9)
       .filter(i -> board[i-1] == unmarked)
       .collect(toList());
}

[Campbell Ritchie]

Would you want 1‑based numbers?
Using the int literals 1 and 9 restricts you to a 3×3 board.

[Stephan van Hulst]

Campbell Ritchie wrote:Would you want 1‑based numbers?

Here, from the perspective of the client of the Game class, the integer is just a symbol that identifies the square. It's not necessarily an index. Labeling the top-left square with '1' is in line with common human expectations.

I do think though that if that IS the case, then int is not the correct data type for this parameter. The parameter should either be String, or a custom Position type. Using int is leaky abstraction.

Using the int literals 1 and 9 restricts you to a 3×3 board.

I think that's a fine limitation for a first version of the game. However, those values should probably be defined as constants.

[Campbell Ritchie]

I might have called the squares a1...c3.
Agree about using constants; that will allow you to enlarge the board later on.

[Liutauras Vilda]

Junilu Lacal wrote:

@Test
void new_game_is_in_play() {
   TicTacToe game = new TicTacToe();
   assertTrue(game.isInPlay());
}

If I would need to understand the rules, I would ask someone (in addition to How the game is played in general):
- When the game is considered finished?
instead of
- When the game is considered still in play?

What your thoughts on that? Because that question describes the exact condition(s) when the game is finished and hence what needs to be coded in.

I personally like more (at the moment) game.isFinished()

[Liutauras Vilda]

Junilu Lacar wrote:

private boolean isDraw() {
   return hasNoWinner() && hasNoLegalMoves();
}

private boolean hasNoLegalMoves() {
   return legalMoves().isEmpty();
}

Regarding the legal moves... That implies to me, that there are some illegal moves as well, however, we are just not dealing with them here (for now..).

For me personally:

private boolean isDraw() {
   return hasNoWinner() && boardIsAllMarked()
}

Adds a bit more clarity what's potentially going on behind the hoods. Doesn't that mean code is better readable?

What about availableMoves()?

What are your thoughts?

[Liutauras Vilda]

A bit philosophical...

I'm thinking now about the legalMoves or availableMoves here.

In chess seems natural to think about the moves, because figures are moving from one location in the board to another.

Over here, nothing moves nowhere. Players i.e. just marking the board.

But perhaps that word "moves" is a bit ambiguous in general when used in the sentence.

[Liutauras Vilda]

And no, TDD is not easy, which seems to be conceptually a trivial thing, practically is very difficult.

I find myself constantly consulting myself with my just previously written code, so I could think about the next needed step to take, so I could write a next test first.

I'm not even sure if after few/several years of not practicing it you can actually convert your habits. Probably it takes way more effort than it would take for some other habit to change.

It is very weird feeling, I feel that I very well envision and understand the value of practicing TDD, but yet, couldn't make it in practice.

[Junilu Lacar]

Liutauras Vilda wrote:
For me personally:

private boolean isDraw() {
   return hasNoWinner() && boardIsAllMarked()
}

Adds a bit more clarity what's potentially going on behind the hoods. Doesn't that mean code is better readable?

What about availableMoves()?

What are your thoughts?

I think all that is what makes for an interesting conversation when you're doing pairing. That's exactly what I would expect in a productive pair or ensemble session: an exchange of ideas, some discussion, and then a decision on which way to go.

One thing I've learned is that it's best to try the idea out. Often, people will just throw something out there for consideration and someone will say "No" and override the suggestion. I say "Try it out. You never really know until you see it in the code."

If you're the driver or senior developer, you can still override it if you prefer not to go with the suggestion, but at least you've shown a willingness to try it before rejecting it.

If the difference is insignificant and the code still looks good, I'll offer defer to what others find easier to read and understand. I don't always have to have it my way. If someone else's way works better for others, I have to stay true to my word of wanting to make the code easy for others to read.

[Junilu Lacar]

Liutauras Vilda wrote:And no, TDD is not easy, which seems to be conceptually a trivial thing, practically is very difficult.

Changing established neural pathways, especially ones that have helped you succeed in the past, and creating new ones that haven't been proven out, is very difficult. I think that's why younger developers who have yet to establish their heuristics find learning TDD easier than more experience developers. That's my experience in the field at least.

It is very weird feeling, I feel that I very well envision and understand the value of practicing TDD, but yet, couldn't make it in practice.

It absolutely is a weird feeling, one I've often compared to that of learning how to ride a backwards bicycle.

[Junilu Lacar]

Liutauras Vilda wrote:A bit philosophical...
...
Over here, nothing moves nowhere. Players i.e. just marking the board.

But perhaps that word "moves" is a bit ambiguous in general when used in the sentence.

Again, this is part of the conversation you have. My guideline is to use whatever ubiquitous language you're dealing with. Observe people doing the thing and listen to their conversation. What words do they use? Do they say "your move" or "your turn" or "you make the mark" or "what spot are you going to mark"? If you use the words that would normally be used in an actual situation, you can make the program more in line with the way people normally talk about the concepts.

Barring that, have a discussion on the taxonomy of ideas and the terminology you want to use. Create a glossary of common words and be consistent in using the words from that glossary. If you keep introducing different ways to refer to the same concept, the program becomes confused and incoherent. The program code should help people understand; if it confuses people instead, that's technical debt.

[Junilu Lacar]

Campbell Ritchie wrote:Would you want 1‑based numbers?
Using the int literals 1 and 9 restricts you to a 3×3 board.

Using 1-9 as identifiers for the spots is a design decision that's open for discussion. We could just as well use letters. The decision to use 1-9 was driven by a desire to make it more natural for the outside, non-programmer world to understand. Non-programmers don't usually think in the 0-based way programmers think about positions. A-J A-I might work but I think 1-9 is a more natural choice.

Also, TicTacToe games are constrained to a 3x3 grid. If there are different constraints, that wouldn't be a TicTacToe but rather something else, like Connect Four or Five or however many.

ZOMBIES says to start with simple scenarios to get simple solutions. If we're only talking about TicTacToe, I'd rather stick with its constraints instead of trying to think about how to accommodate other kinds of constraints.

[Campbell Ritchie]

Thank you, Junilu.

[Junilu Lacar]

Junilu Lacar wrote:ZOMBIES says to start with simple scenarios to get simple solutions. If we're only talking about TicTacToe, I'd rather stick with its constraints instead of trying to think about how to accommodate other kinds of constraints.

This highlights a programmer tendency I often see: saying "Well, what if..."

This isn't necessarily a bad thing because you can find many different edge cases by asking that question. However, when it leads to scope creep and additional complexity that wasn't really part of the original problem, it becomes an important discussion and decision point. In the real world, you have to deliver to what the current requirements are. If you keep worrying about the future, you're going to impact your ability to get done with your current task. I like how Sandi Metz said it in a tweet:

Sandi Metz (@sandimetz) wrote:Don't write code that guesses the future, arrange code so you can adapt to the future when it arrives."

[Liutauras Vilda]

Thanks Junilu, very useful insights.

[Junilu Lacar]

Here's one question I would ask:

Between hasLegalMoves() and boardAllMarked which one is more aligned with intent rather than implementation?

[Junilu Lacar]

Thank you for your participation in the discussion. It's nice to have real others to discuss with rather than imagined others, which I often have to resort to when I'm practicing solo.

[Liutauras Vilda]

Junilu Lacar wrote:Here's one question I would ask:

Between hasLegalMoves() and boardAllMarked which one is more aligned with intent rather than implementation?

Well, I agree with you to some good extent. While boardAllMarked() literally means what is exactly happening, but yes, it is sort of representing an idea at a lower abstraction.

Taking about the abstraction, hasLegalMoves() or availableMoves() are so abstract, along with other your demonstrated code, that you almost could reuse its structure as is (of course with different low level impl) in some other game, not even necessarily played on the board. So it is very interesting.

[Junilu Lacar]

Yes, I find that the strategy of focusing on intent rather than implementation for high-level code really opens up many possibilities and enables many "-ity"s, like quality, reliability, reusability, etc.

[Junilu Lacar]

Another strategy that allows for flexibility is ignoring edge infrastructure concerns for as long as possible. When you do need things like printing out your object or saving it somewhere, I try to keep it as simple and generic as possible. For example, instead of putting a bunch of System.out.println() statements inside the class, like in a show() method for example, I just make the class emit a String representation of itself and let the client worry about what to do with that representation.

This strategy keeps at least two options open: for testing, it allows you to easily write approval tests and other kinds of tests that check String values. For "production" runs, you can do things like System.out.println(myObject). That's how I sketched it in main() for this example:

while (game.isInPlay()) {
   System.out.println(game); // string representation of current state
   ...
}

I find this easier than adding a bunch of getter methods to be used to query the object's state. To give even more options, I might think of emitting the object's representation as a JSON string. That's further down the line though; the simplest thing in the beginning would be to just override toString().

[Stephan van Hulst]

Junilu Lacar wrote:Another strategy that allows for flexibility is ignoring edge infrastructure concerns for as long as possible. When you do need things like printing out your object or saving it somewhere, I try to keep it as simple and generic as possible. For example, instead of putting a bunch of System.out.println() statements inside the class, like in a show() method for example, I just make the class emit a String representation of itself and let the client worry about what to do with that representation.

Be careful with this approach. If you don't provide a way for the client to query certain properties about the object (such as how each square is marked, which will be useful when the application is expanded with a GUI), people WILL eventually end up parsing the toString() return value to get what they want. I think Joshua Bloch even warns about this in Effective Java.

In my personal experience, it's also not a good idea to return multi-line strings from toString(). This method is used by debugging tools in IDEs extensively, and returning multiple lines often interferes with this important matter.

I've found that the best approach to print a grid-like object is to provide the class with a printTo() method that accepts a PrintWriter:

var printer = new PrintWriter(System.out, true);

...

while (game.isInPlay()) {
  game.printTo(printer);
  ...
}

When testing, you can supply the printTo() method with a PrintWriter that wraps around a StringWriter.

I find this easier than adding a bunch of getter methods to be used to query the object's state. To give even more options, I might think of emitting the object's representation as a JSON string.

And I think this violates single responsibility. If you let the game output its state as a JSON string, then why not also XML? And why not some binary format? It's not the game's responsibility to serialize itself in some particular way. Instead, it would be the responsibility of some JsonGameSerializer class, for example. This necessitates that the Game class exposes some of its interesting properties. If you don't feel comfortable exposing those properties at this project phase, then leave them out, but do NOT expose that information through toString(), because people WILL abuse it.