How to represent a game of Tic-tac-toe with just 2.25 bytes:

How to represent a game of Tic-tac-toe with just 2.25 bytes:

https://zora.co/collect/base:0x93625454e26f407ad6c3f62b3245bb197af44e80/3

First, you may come up with something like the following as your first representation.

Besides the player addresses, this representation uses 104 bits and 2 storage slots.

After tightly packing the struct, the representation is actually quite good already.

On the EVM, setting empty storage slots costs a lot more gas than setting nonzero ones, and you need a minimum of 2 storage slots to store the player addresses (i.e. no significant savings).

However, it's a fun exercise to understand for when you *do* need that extra granularity/control in your code, so let's continue exploring ways to reduce the representation :)

To start, take a look at `uint8[9] board`. We definitely don't need 8 bits to store data for a position on the board.

There are only 3 valid states, so 2 bits are enough:
* Empty (00)
* Occupied by "O" (01)
* Occupied by "X" (10)

The next `turn` can easily be represented with 1 bit:
* 0 if it's player 0's turn
* 1 if it's player 1's turn

Because the next 3 `bool`s `hasGameEnded`, `playerZeroWon`, and `playerOneWon` work in conjunction to express the 4 possible states of a game, we can reduce them into 2 bits:
* the game is ongoing (00)
* player zero has won (10)
* player one has won (11)
* drawn game (01)

With our changes so far, we can go from 104 bits to 21 bits!

With our changes so far, we can go from 104 bits to 21 bits!

https://zora.co/collect/base:0x93625454e26f407ad6c3f62b3245bb197af44e80/4

With each game only requiring 21 bits, it's worth bitpacking consecutive games' data before storing them to storage.

This way, only every 12th game will write to a zero slot, and every other game will write to a nonzero slot.

The idea is to reduce as many zero slot writes as possible because writing to zero slots costs 20k gas, whereas writing to nonzero slots only costs 5k gas.

It might look a little complicated, but if you break it down, it's not too bad:

You may have realized we use 2 bits (yields 4 values) per position, despite there only being 3 possibilities.

We can actually get the # of bits used further if we represent the board in base 3 representation.

If I were to implement this for real, I'd pack the board with the players' addresses.

As noted earlier, we need 2 storage slots anyway, so we really only needed to get the representation down to 96 bits (256-160) for anything significant.

It also makes for much cleaner code:

In this example, we optimized for storage space, but that's not always gonna lead to the optimal output.

When coming up with a representation, it's important to consider factors like how often it'll be read/written/manipulated/etc., and optimize for the specific scenario.

However, encoding/decoding is considerably more complex and computationally expensive.

Also, 21 bits is already quite good; using 18 bits only improves writing to a zero slot to every 14th, instead of every 12th slot (aka ≈449 gas in storage costs).