DEV Community

Kirk Shillingford
Kirk Shillingford

Posted on • Updated on

A Most Magic TicTacToe solution with React and TS

Synopsis

My name is Kirk. I like making small games with code. And today's game is Tic-Tac-Toe. Specifically, this is a post about an alternative algorithm for finding winning combos in Tic-Tac-Toe using a concept called Magic Squares, but also about burnout, productivity, and finding joy in code. The code is all done in React and Typescript, and as always, full links and examples will be provided. If you just want to see the final solution, visit the sandbox here.

1. Starting from the end with sensible solutions.

Now, normally we'd start a post like this at the beginning; we'd talk about the domain of the physical game, and what elements we'd need in our digital solution. But today we're gonna start at the end; we're gonna take an existing solution and look at what if we just changed a small bit in an interesting way. Like Marvel's What-If, but with a smaller animation budget.

So what do we have going on?

tic tac toe game

My take on Tic-Tac-Toe. Does it work? Yes. A bit plain? Also yes.

This is our basic Tic-Tac-Toe implementation in React. Each turn a user clicks a cell in the grid, and the game checks to see if they've won.

Under the hood, our "grid" is just an object whose fields are the numbers of the cells and who's values are "X"s, "O"s, and nulls (for empty cells).

type Grid = { [key: number]: "X" | "O" | null };

const grid:Grid = {
  1: "X",
  2: null,
  3: null,
  4: "X",
  5: "O",
  6: "O",
  7: null,
  8: "X",
  9: null
}

// this grid would be rendered as the following

 x |   |
 x | o | o
   | x |
Enter fullscreen mode Exit fullscreen mode

For our Tic-Tac-Toe implementation, we need a function that checks whether a player has won after each turn, hasWinner(). That function can accept a grid and determine if there's a winning set of moves in the grid.

The win function looks like this:

const winningCombos = [
  [1,2,3], // top row
  [4,5,6], // middle row
  [7,8,9], // bottom row
  [1,4,7], // left column
  [2,5,8], // middle column
  [3,6,9], // right column
  [1,5,9], // descending diagonal
  [3,5,7] // ascending diagonal
]

const hasWinner = (grid: Grid): boolean => {
  // map the grid values to the combo keys
  const comboValues = winningCombos.map(
    (comboKeys) => comboKeys.map(
      (key) => grid[key]
    )
  )

  // find returns a value or undefined
  const maybeWinner = comboValues
    .find(
      (comboValues) =>
        comboValues.every((v) => v === "X") ||
        comboValues.every((v) => v === "O")
    );

   // convert this value to a boolean
   return !!maybeWinner
}
Enter fullscreen mode Exit fullscreen mode

So what's happening here?

First, we create a list of lists representing all the potential winning sequences of cells, all the rows and columns and the two diagonals.

In the hasWinner() function:

  • We use map() over our combos to get the grid values for every cell
  • Then we use find() to look for a group which has all X's or all O's
  • If we find one, that means there's three of the same value in a row on the board, and we have a winner.

it is known gif

And this works and performs fine. It does the job. But maybe we can do something a bit more fun that does the job. Not with how hasWinner() works, but with how we get those winningCombos.

Here, we basically just wrote them out by hand. And eight wasn't really so bad.

But what if we had a 4x4 board? That's 10 solutions. And a 5x5 board is twelve. It would be nice if there was a way to just know the ways to solve without having to look at the grid and then write them all out.

And luckily, there just so happens to be a way (or this would be the end of this blog post).

And that solution, involves magic squares

2. Answers with no questions.

Now, this is meant to be a technical article, but it's worth taking a bit of time to talk about why this is an article about Tic-Tac-Toe, and why this solution even exists.

I tend to think that Human being like patterns. We're designed to find patterns and solve problems. Sometimes, our brains pattern matching inclinations can get us in trouble; conspiracies are essentially just us finding patterns even when they aren't there. Some patterns we've been picking apart and working on for thousands of years.

One such pattern discovered at least as early as 190 BCE by Chinese mathematicians is the concept of a Magic Square.

picture of magic square

Tada? Yes it's just a box.

"But Kirk," you ask, "what's so special about this square?"

Well you see, all magic squares (including this one) have three (3) very interesting properties.

  • All the digits in the rows of the square add to a particular number.
  • All the digits in the columns of the square must add to that same number.
  • And all the digits in the diagonals add to that number too!

Do these rules feel familiar?

Magic Squares care about the same patterns in grids made from squares that Tic-Tac-Toe does!

And the best part is, they have nothing to do with each other! When Tic-Tac-Toe started showing up in Ancient Egypt, it didn't have anything to do with Magic Squares. Humans have just been enjoying patterns of squares in squares forever.

best friends gif

Magic Squares fall into the realm of Recreational Mathematics, which is maths done at least partially for the purposes of entertainment, as opposed to research of practical application. It's also the maths most frequently done by amateur (unpaid mathematicians). Throughout history though, Mathematicians, Philosophers, and even Religious figures have studied and teased apart the nature of magic squares. Beyond 3x3 grids, they've looked at 4x4 and larger magic squares. They've looked at semi-magic squares and pseudo magic squares, and even some things given the brilliant name of Most-Perfect Magic Squares.

Throughout history the patterns of magic squares have been claimed to have use in astronomical calculations, and even occult powers. There's quite a large body of examples, computations, and algorithms based on them. We've taken them apart and put them together over and over in the pursuit of understanding what do these patterns of numbers mean? And that's been terribly fun for everyone involved, but for the most part, generally, they have absolutely no purpose at all.

They're just numbers in squares, with no more meaning than what we give them. Just some silly nonsense that we like to look at. Answers with no questions.

Except for today. Today they're helping us solve Tic-Tac-Toe.

3. Making winning magic combos

So now we know there are magic squares, which care about the same arbitrary patterns that Tic Tac Toe cares about. How does that help us get to a solution.

Well, let's look at the magic square for a 3x3 grid.

magic square 3x3

While magic squares get more complex in 4x4 grids and higher, with 3x3 grids we can confidently say a few things:

  • All the rows, columns, and diagonals in a 3x3 magic square add to fifteen (15)
  • As importantly, any other 3 number combo in a 3x3 magic square Does Not add up to 15.
  • There's only one (1) way to align the numbers in a 3x3 grid to get a magic square (You can rotate the numbers around the center or flip them on an axis but it's still the same arrangement).

This means if we can programatically get all the 3 digits combos that sum to 15, we can get all the relevant rows, columns, and diagonals in Tic-Tac-Toe.

The implementation of this ends up being far shorter that the lead up.

import { Combination } from "js-combinations"

const keys = [1, 2, 3, 4, 5, 6, 7, 8, 9]

const uniqueTriples = new Combination(keys, 3).toArray()
// [[1, 2, 3], [1, 2, 4], [1, 2, 5] ...

const winningCombos = uniqueTriples.filter(
  (nums) => nums.reduce((acc, num) => acc + num) === 15
);
// [[1, 5, 9], [1, 6, 8], [2, 4, 9], [2, 5, 8]...
Enter fullscreen mode Exit fullscreen mode

This is only a few lines of code but there's a lot going on here so let's break it down step by step.

The first thing we do is import the Combination class from the js-combinatorics package. This package has a ton of useful tools for calculating permutations and combinations of items.

We're using to the Combination class to create all the valid, unique combinations of 3 numbers from the set of numbers from 1 to 9.

The Combination class from this library is a Javascript Iterable.

Each value is the same shape as the ones we saw in one original winning combos; an array of three (3) numbers.

We convert our combination class to an array so we can do the next step; filtering those unique pairs down to just the values that add to 15. Thanks to magic squares we know those values will be the rows, columns, and diagonals of our solution.

To the filter method, we pass a callback inline that uses reduce() to sum all the values in our triple and see if they add to 15.

And our hasWinner() function is none the wiser.

The final part is the arrangement of our cells in the UI. The only way this method works is if on the UI side, our cells are displayed in the right order. There are a few ways to accomplish this but the simplest is just to order our keys in the magic square arrangement so whatever calls the API gets them out in the order they're meant to be displayed.

const keys = [2, 7, 8, 9, 5, 1, 4, 3, 6]
Enter fullscreen mode Exit fullscreen mode

And that's all it takes. No more manually writing out winning combos. And we can scale this for 4x4, 5x5, 6x6 etc...

4. So What's the Takeaway

Honestly, I started this project planning to talk about object-oriented vs functional API design. And I might still do that. I had written the first version of this solution, and it worked really well, and that was going to be it.

But then, at 2:00 a.m. in the morning when I should've been asleep, I was instead thinking about how tic-tac-toes remind me of tiny sudoku tables. And I remembered doing a cool sudoku once that had a Magic Square.

woken up

I have always felt like coding is a creative endeavour. I remember being told once, that "creativity is just novel juxtapositions". I could've done this the regular way, but this way, with this weird fact about magic squares, it just seemed a little more fun.

It just felt like something to explore. I am far from the first person to make a Tic-Tac-Toe game. And I'm definitely not the first person to think of Magic Squares.

But maybe I'm the first one to put them together like this. With React. With Typescript. And that was fun for me.

So I hope this post and this code can provide you some measure of joy and insight. And even if you don't care about the squares stuff, I don't think it's a half bad implementation of Tic-Tac-Toe. It's got all the function composition and expression based logic I also enjoy. And I hope it inspires you to do things you enjoy as well. Not everything we do needs to have a direct purpose.

You can just do things, and write code, because it makes you happy. In between all the React fundamentals, and AWS fundamentals, and Docker fundamentals, and practicality and hireability, we should sneak in some time just for us.

And like me and the folks who first thought about Magic squares, maybe 2000 years from now, someone will find the things you did just for fun, and use them to have fun too.

flower costume dancing

Let me know if you have any questions about the code, the squares, or the strategy, or if there's anything else you'd like me to cover.

Thank you for your time.

*Special thank you to all my friends at Virtual Coffee for encouraging me to do this (and debugging my css!)

Resources

  • See here for the Github repo for this code.
  • See here for the editable, runnnable codesandbox where I made this.
  • The wikipedia article about magic squares has a lot more cool info about their history and properties.

And finally, here's the main code for the solution if you'd just like to see what's going on here.

App.tsx

import "./styles.css";
import Game from "./GameClass";
import { useState } from "react";

const initialGame = () => ({ game: new Game() });

export default function App() {
  const [state, setState] = useState(initialGame());

  // this is where we update the state of our application
  const update = (value: number | "Restart") => {
    if (value !== "Restart") {
      state.game.setCell(value);
      setState({ ...state });
    } else setState(initialGame());
  };

  // our tiny little cell component
  const Cell = (key: number) => (
    <button key={key} id={`cell${key}`} onClick={() => update(key)}>
      {state.game.getCell(key) ?? ""}
    </button>
  );

  // I really dislike curly braces
  const statusMessage = () => {
    if (state.game.winner) return `${state.game.winner} won the game!`;
    else if (state.game.isFull) return "The game is a draw!";
    else return `${state.game.turn}'s turn to play!`;
  };

  // Putting it all together
  return (
    <div className="App">
      <h1>ReacTacToe</h1>
      <div id="gamebox">{state.game.cellNames.map(Cell)}</div>
      <div id="status">{statusMessage()}</div>
      <button onClick={() => update("Restart")}>Restart</button>
    </div>
  );
}
Enter fullscreen mode Exit fullscreen mode

GameClass.ts

import { Combination } from "js-combinatorics";

type Grid = { [key: number]: "X" | "O" | null };

const keys = [2, 7, 6, 9, 5, 1, 4, 3, 8];

// get every unique combination of 3 numbers and only keep the ones that sum to 15
const winningCombos = new Combination(keys, 3).toArray().filter(
  (nums) => nums.reduce((acc, num) => acc + num) === 15
);

const hasWinner = (grid: Grid) =>
  !!winningCombos
    // get the corresponding grid items
    .map((comboNumbers) => comboNumbers.map((key) => grid[key]))
    // if you find at least one with all Xs or all Os, there's a winner!
    .find(
      (comboValues) =>
        comboValues.every((v) => v === "X") ||
        comboValues.every((v) => v === "O")
    );

export default class Game {
  private _grid: Grid;

  constructor() {
    // using reduce to add all our keys to an object with initial values of null;
    this._grid = keys.reduce(
      (grid, key) => Object.assign(grid, { [key]: null }),
      {}
    );
  }

  get turn() {
    // get the grid values
    const counts = Object.values(this._grid)
      // use reduce to make an object that counts all the Xs and Os
      .reduce(
        (acc, value) => {
          if (value === "X") acc.Xs += 1;
          else if (value === "O") acc.Os += 1;
          return acc;
        },
        { Xs: 0, Os: 0 }
      );
    // if there are more Xs on the board, it's O's turn.
    return counts.Xs > counts.Os ? "O" : "X";
  }

  get winner() {
    if (!hasWinner(this._grid)) return null;
    // if there's a winner and it's X's turn, that means O just won. Otherwise, X just won.
    else return this.turn === "X" ? "O" : "X";
  }

  get isFull() {
    // no null values in the grid? board must be full
    return Object.entries(this._grid).every(([_, value]) => !!value);
  }

  getCell = (key: number) => (key in this._grid ? this._grid[key] : null);

  setCell = (key: number) => {
    // no winner yet, a valid name and an empty cell? Set grid cell to whoever's turn this is.
    if (!this.winner && key in this._grid && !this._grid[key])
      this._grid[key] = this.turn;
  };

  get cellNames() {
    return keys;
  }
}
Enter fullscreen mode Exit fullscreen mode

Styles.scss

.App {
  display: flex;
  flex-direction: column;
  align-items: center;
  justify-content: space-around;
}

#gamebox {
  display: grid;
  width: 80vw;
  height: 80vw;
  max-width: 600px;
  max-height: 600px;
  min-width: 150px;
  min-height: 150px;
  grid-template-areas:
    ". . ."
    ". . ."
    ". . .";
}

#status {
  margin: 5px;
}
Enter fullscreen mode Exit fullscreen mode

Discussion (8)

Collapse
nickytonline profile image
Nick Taylor

I look forward to your Connect 4 game post. 😎

Collapse
kirkcodes profile image
Kirk Shillingford Author • Edited on

Connect four is actually a very interesting game from a dev perspective, since simple solvers would take... a long time to get to the right solution. So that could be really fun.

Collapse
nickytonline profile image
Nick Taylor

It'd be fun to pair on if you're up for it. 😎

Thread Thread
kirkcodes profile image
Kirk Shillingford Author

Always down to pair with you, friend. We could even do it in Rust if you'd like :)

Collapse
rpresb profile image
Rodrigo De Presbiteris • Edited on

Everything looks great, one thing that I think you don't need to do is spread the array for filtering. Filter doesn't mutate the array, so it's a bit of a waste of memory.

Collapse
kirkcodes profile image
Kirk Shillingford Author

Hey Rodrigo, do you mean the spread of the Combination object? IIRC, I spread into an array because the filter method isn't available on the combination directly.

But maybe there's a more efficient way to do that?

Collapse
rpresb profile image
Rodrigo De Presbiteris

You are right, this object doesn't generate a pure array.

it has the toArray function, but it does the same you did there.

 toArray() {
        return [...this];
    }
Enter fullscreen mode Exit fullscreen mode

I should have checked this before commenting

Thread Thread
kirkcodes profile image
Kirk Shillingford Author

No worries. I didn't even check to see if it implemented toArray(). That's probably the clearer way to express that intent. I'll use that instead. Thanks!