A Most Magic TicTacToe solution with React and TS
Tags: react, typescript, gamedev, maths
Published: 2021-11-02 12:13:44

## 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](https://reactjs.org/) and [Typescript](https://www.typescriptlang.org/), and as always, full links and examples will be provided. If you just want to see the final solution, visit the sandbox [here](https://codesandbox.io/s/github/tkshill/Reac-tac-toe).

## 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](https://www.marvel.com/tv-shows/animation/what-if/1), but with a smaller animation budget.

So what do we have going on?

![tic tac toe game](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2ermxwp23zo31qf4yh55.png)

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 `null`s (for empty cells).

```typescript
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 |
```

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:

```typescript
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
}
```

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](https://media.giphy.com/media/10hexADl3Kl6SY/giphy.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](https://psychcentral.com/lib/patterns-the-need-for-order#3). 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](https://en.wikipedia.org/wiki/Magic_square#History) by Chinese mathematicians is the concept of a _Magic Square_. 

![picture of magic square](https://upload.wikimedia.org/wikipedia/commons/d/db/Magic_Square_24.png)

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](https://en.wikipedia.org/wiki/Tic-tac-toe#History), it didn't have anything to do with Magic Squares. Humans have just been enjoying patterns of squares in squares forever.

![best friends gif](https://media.giphy.com/media/kFIfiwvzJjbUsNbIg5/giphy.gif)

**Magic Squares** fall into the realm of [Recreational Mathematics](https://en.wikipedia.org/wiki/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](https://upload.wikimedia.org/wikipedia/commons/1/1a/Magic_Squares_-_3x3.svg)

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.

```typescript
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]...
```

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](https://www.npmjs.com/package/js-combinatorics) package. This package has a ton of useful tools for calculating [permutations and combinations](https://www.calculatorsoup.com/calculators/discretemathematics/combinations.php) 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](https://javascript.info/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]
```

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](https://media.giphy.com/media/b6iVj3IM54Abm/giphy.gif)

**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](https://media.giphy.com/media/3oz8xRF0v9WMAUVLNK/giphy.gif)

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](virtualcoffee.io) for encouraging me to do this (and debugging my css!)

## Resources
- See [here](https://github.com/tkshill/Reac-tac-toe) for the Github repo for this code.
- See [here](https://codesandbox.io/s/github/tkshill/Reac-tac-toe) for the editable, runnnable codesandbox where I made this.
- The [wikipedia](https://en.wikipedia.org/wiki/Magic_square) 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
```typescript
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>
  );
}
```

GameClass.ts
```typescript
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;
  }
}
```

Styles.scss
```css
.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;
}
```