Snake in a Block —How I Ran Snake on Ethereum

12 min readNov 23, 2021

Brief Introduction

Some months ago I and a friend decided to collaborate on an NFT. We wanted to create a piece of retro-game art that could be arcade in spirit. Something engaging, fun that would at the same time need to push the limits of its own technology to come to life. The same attitude that brought many legendary arcade games to existence. Remember how Nintendo managed to make the 1st 3D game for the SNES, when that was not even imaginable for that type of hardware?

So we created the ArcadeGlyphs. Simply put, it’s a generative NFT that, once minted, creates a Snake game. The twist is that the collectors only get the initial state of the snake. The creature will advance every hour, guided by a greedy search algorithm. At the end of the game, the NFT turns (magic) into an animation of the game itself. The cherry on the top: we wanted to have NFT-prizes that the owners of the best game could claim “for free”.

Where is the complication? We wanted it to sit 100% on-chain. In the old days, if you wanted to make a mind-blowing game for a certain console, you had to be able to do it with the hardware that was already out there in the gamers’ houses. We wanted to give ourselves the same challenge.

In this article, we will explain in technical details part of the journey to minimize the gas needed to run the game so as to fit all that was needed within the block.

Why Gas Matters

Quick intro about gas: it’s a unit of measurement of the amount of computation that some Solidity code requires. It is used to estimate the cost related to a Solidity function call. There are 2 potential issues related to it:

It determines how much the user will have to pay for a transaction (a “write call”). The more the gas consumed, the higher the transaction’s cost.
Read calls (so-called view functions in Solidity) should not be affected by gas, but each node may decide to still put some limits on it, to avoid resource exhaustion. These limits are not standard. Some allow double the actual gas limit, some less... It’s most importantly not clear what’s the Opensea configuration. One way to be safe is to keep it within the actual block gas limit.

Back to the NFT look: it shows the current state of the game if the game is in progress, and an animation otherwise.

Both cases require the contract to be able to calculate the current state by using only

the initial snake configuration (determined at minting time)
the current block.

In a nutshell: it needs to simulate the game up until the current block. This was the only way to avoid transactions and still provide through-time-mutability.

The problem is that the simulation is an O(N) function, with N the number of moves. In the best case, the snake collides right away and not much needs to be calculated, but in the worst case, we might need to run through the full number of iterations.

Imagine a very lucky game that runs quite long. On a grid 11x11 the game could run beyond 400 iterations. On top of calculating the outcome of the game, the contract has to generate the SVG animation if the game is over (very gas-intensive). This should give you a hunch of why even saving 700 gas (this is the cost for an optimized log2 computation) could have a pretty perceivable impact at the end of the simulation.

The other point of saving on gas though comes from an extra feature we implemented: the token owners can redeem trophies for the best games. For example, collectors with a 42-score game could redeem the 1st place trophy (requiring at least 40 points). This “proof-of-score” requires running the whole simulation again. It would be cost-irrelevant for a view call, but in this case, the function needs (after the verification) to change the state of the blockchain, by transferring the trophy to the token owner. The final gas fee will then include the overhead of the “proof-of-score”, which is one of the fundamental reasons why gas efficiency was vital.

Basic Operations

To simulate the snake game, the minimum set of operations that the logic has to support is:

Collision detection: this can be between single points (e.g. head and apple), or multi-point objects (head and snake body)
Movement: basically advancing the snake, either for real or while searching for the next best move
Extension: the snake needs to grow, the more apples it eats

We can then implement the simulation roughly like this:

1: for each iteration
2:    move snake according to strategy
3:    if collision with wall OR snake body
4:      then break
5:    else if collision with apple
6:      extend the snake
7:      move apple

When the collector wants to see the state of their snake after (say) 21 hours, the contract would run 21 such iterations to define how the game looks at that time. Let’s remember that that is an oversimplified version of the real algorithm. Line 2 and 7, for instance, are a whole piece of logic by their own. And ‘move snake’ is not merely 1 statement, but it involves advancing the head and the tail. This is just to say that there are a lot of devils in the details of that seemingly simple loop.

Data Structure

We will now show 2 different types of data structures that could be used to run the above-mentioned simulation. For each, we will show how the basic operations are implemented and the gas implications.

Most Naive Solution

Given that the Snake game-board is a grid, the most intuitive approach is to represent everything in a 2D coordinate system, where each element is either a point or a list of points. More specifically:

Apple and Snake Head: uint[2] , the (x, y) coordinate of the point
Snake: uint[][2] an arbitrarily long list of (x, y) coordinates representing the space that the snake occupies in the grid
Wall: although it occupies points in the system, for the sake of collision detection, it’s enough to know what the boundaries are, so 0 and GRID_SIZE

The different operations would then be implemented this way (pseudo-pseudo code):

// Extend Snake
snake[nextPosition] = newHead// Check apple-to-head collision
head[0] == apple[0] && head[1] == apple[1]// Check head-to-body collision
for (bodyPart in snake) { 
   head[0] == bodyPart[0] && head[1] == bodyPart[1]
}// Check collision between wall and head
(
    head[0] > 0 && head[0] < GRID_SIZE - 1 &&
    head[1] > 0 && head[1] < GRID_SIZE - 1
)// Check collision between apple and snake body (useful not to move // the apple over the body of the snake)
for (bodyPart in snake) { 
   apple[0] == bodyPart[0] && apple[1] == bodyPart[1]
}// Move head right, left, up and down
head[0] = head[0] + 1
head[0] = head[0] - 1
head[1] = head[1] + 1
head[1] = head[1] - 1

A quick benchmark on the different operations shows (very approximately) what they could cost in terms of gas

There is a clear point of optimization in the snake-to-point collision, but we should not underestimate all other operations, because they are repeated multiple times per iteration and they could have a snowballing effect.

With a 30M gas limit one could think this is still nothing to worry about, but the more precisely the simulation logic is implemented (including edge case handling, etc), the more operations like those listed above are needed, making it very likely that with a long game, the limit is breached. As mentioned already in the previous section, though, one other motivation to cut the cost is to allow a not-so-expensive trophy-claiming functionality.

Better Solution

The optimization objective was simple:

Critical: decrease the computational complexity of the snake-to-point collision detection
Very desirable: decrease the single operation gas

Decreasing the computational complexity of the snake-to-point collision is by itself easy. We could use a matrix where 1 indicates that the snake occupies that position in the grid, 0 otherwise.

We felt that there was an even more efficient way to work with this problem though.

The intuition was simple: what if every element in the game (snake, wall, apple, etc) could be represented by an integer such that all the snake-relevant functions could be then handled just with bitwise logic, executed straight into 1 processor instruction?

The solution was then to imagine the grid system as if it was 1 dimensional, with each coordinate (x, y) represented by a bit in a bit array.

Each bit would be set if that position was occupied. For instance, to represent a snake occupying the first 3 points in the grid:

A grid with 9 playable slots and a wall occupies 11x11 points, for a total of 121. We need 121 bits to be able to represent every possible element configuration within this system, which is achievable simply with a uint128 , which represents 128 bits integers.

To represent the snake above we would then use the number 14 ( 1 << 1 | 1 << 2 | 1 << 3) where 0 and 10 positions are occupied by the wall.

The operations with this new representation would be:

// Extend Snake
snake = snake | newHead// Remove tail
snake = snake ^ tail// Check apple-to-head collision
head & apple == 0// Check head-to-body collision
snake & head == 0// Check collision between wall and head
snake & wall == 0// Check collision between apple and snake body (useful not to move // the apple over the body of the snake)
snake & apple == 0// Move head right, left, up and down
head = head >> 1
head = head << 1
head = head >> GRID_SIZE
head = head << GRID_SIZE

Checking the benchmark

All collision operations became not only O(1) but also as gas-efficient as they can get and the other operations considerably improved as well. All those listed above are indeed a subset of everything that needs to be done. But with this data structure, we could handle almost everything with bitwise logic.

Way to go. In the next chapter, we will clarify how the search algorithm (“AI”) has been implemented. Another insidious issue was hiding there as well.

Greedy Search

We tried to make the snake move at least halfway decently. The best solution we found that could still be implemented on a contract was a greedy search strategy where the snake follows a couple of heuristics:

tries to decrease the Manhattan Distance from the apple
if not possible, try to decrease the Manhattan Distance from the tail
if not possible, “random” move

The main issue with this algorithm (paired with the solution described above) is that it requires knowledge of x and y to decide how to minimize the distance. Given that we deal mainly with uint representations of the snake (including the head), to get x and y we need to do the following

function getXY(uint coord) returns (uint x, uint y) {
    // Get bit position inside the int 
    uint position = log2(coord)    return position / GRID_SIZE, position % GRID_SIZE
}

The log2 is unfortunately not natively implemented in Solidity and the most efficient implementation still costs 700 gas.

The naive implementation of the “AI” would then be to try each single move and check if

a) it decreases either the x or y distance from the apple
b) it does not collide with either wall or snake itself

This of course requires to know exactly what x and y are. But we don’t, we only know the integer representation. And going back to the 2D system would cost quite some gas.

The idea was to see if we could find a way to perform this same logic without ever passing through the 2D coordinates data structure again.

If the grid was actually a line, this would be easy: different positions are already naturally sorted. If I have head on 2 and apple on 15, we can safely tell the head to increase (so to move towards the apple). Unfortunately, we have a grid, so numbers that are distant in the int realm might be close once transposed to the grid. Example: what’s closer to P1 ? P2 or P3 ?

Clearly P3. Let’s see how the integer representation of these coordinates is though:

From this perspective, P2 is closer to P1 than P3 .

The relations of distance in this representation do not allow us to make a proper calculation.

There is no way (to our knowledge) to have this information without first decoding the coordinates into x and y. BUT, there is another way to move the head in the right direction, still remaining in our efficient system.

What’s needed to know is whether the apple x is greater or smaller than the head’s x and just move accordingly. If smaller, move back, if greater, move forward. If the same, try with y .

Computing this information requires still a kind of decoding of x a y, but we don’t care about their exact value, we only care that the proportions between two decoded x are correct. If x1 > x2 in the 2D data structure, it should be the same in this newly decoded version.

Now, focus.

Let’s say the head is on (1,9) (end of the first row) and apple on (2,1) (beginning of the second row). 0 and 10 in both axes are occupied by walls. What we want is that the snake notices that the head’s y (9) is greater than the apple’s y(1) so that we can instruct the head to move left (backward).

The problem is that head is encoded as 1048576, apple as 8388608, which is the opposite of what we are looking for. The reason is that the x coordinate pushes the set bit 11 positions to the left (as many as the grid size). Visually:

// Spaces added to visualise the rows within the bit array
// head (1, 9)
00000000000 01000000000 00000000000// apple (2, 1)
00000000010 00000000000 00000000000

Every 11 bits refer to a row (x). What we need is a way to factor out the x part of the shift so that we can compare only the y part. Something that would bring us here

// head decoded
00000000000 00000000000 01000000000// apple decoded
00000000000 00000000000 00000000010

The way we found to achieve this was with some brainfucky masking

// --- This is the algorithm ---
// If it's the first row, we don't have to do anything
// If it's the second row, we should shift by GRID_SIZE * 1
// If it's the third row, we should shift by GRID_SIZE * 2
// ...// --- This is how we implement it in bitwise logic ---
// "If it's the first row" becomes:00000000000 00000000000 11111111111
                &
00000000000 01000000000 00000000000OR more simply 2047 & p // this would now compute to 0// "If it's the second row" becomes:
00000000000 11111111111 00000000000
                &
00000000000 01000000000 00000000000OR more simply 
4192256 & p // which computes to p// "we should shift by GRID_SIZE * 1" becomes:
p >> 11// How to make sure the shift happens only if the correct row is 
// found? (2047 & p)
| (4192256 & p) >> 11
| (8585740288 & p) >> 22
.....

At the end of the execution of this chain, we will get 2 comparable values of y. So head = 512 and apple = 2. Way more efficiently than going with the log2 decoding. We won’t know the position in the grid, but we will know enough to instruct the snake where to move. This way:

...
if(head > apple && !isCollision(p1 >> GRID_SIZE)) {
     return p1 >> GRID_SIZE; // this stands for "move backward"
}
...

From here on, it was possible to compute the next move mainly with bitwise logic.

Conclusion

Some non-thorough tests have been done to also check whether assembly optimized code would have worked as well, but we noticed a small if not irrelevant gain which did not justify the effort of rewriting everything in machine code. Definitely, a challenge we will consider for the next game, should this first project work.

Bitwise logic makes the code much harder to grasp, but its benefits in terms of efficiency gains are superb. With a technology where optimization saves actual money, it’s a no-brainer to go with it.

Keep in touch, we will make another article explaining how we could generate the SVG animation within the same function call, still remaining within limits.

Also, feel free to check out the NFT page and the mainnet contract, in case you’d like to give us any feedback or support.