On-Chain Chess: Smart Contract Breakdown

How someone decided to put an entire chess game on-chain

Today, we’ll be reviewing the smart contract behind the first-ever on-chain chess engine. It’s called 5/9 (fiveoutofnine). The creator just decided: screw it, I’m gonna put an entire chess game on-chain. And it’s not just the AI for playing the game, he also put the art (NFTs) totally on-chain.

There are many examples of putting various things on-chain, such as SVG data and 3D data of NFTs. Even the SVG and 3D renderers as well. I’m always fascinated by these. It reminds me of the 90s when computing resources were scarce and people came up with various tricks/optimizations to support the game on slow hardware. The same is happening with blockchains where every single performance and gas bit is squeezed out for max performance.

Let’s dive into the optimizations that 5/9 had to make in order to run chess on Ethereum. Here is the outline of this article:

• Game dynamics — what is it about?
• The smart contract source code
• On-chain data representation
• Generating NFTs
• Game engine

Game dynamics

• The game consists of you (player) playing against the AI that is programmed into the smart contract. The AI always plays black.
• You can make a move, and the engine will respond with its own move. Making a move requires gas, but you get an NFT in return.

I think that the onboarding on the homepage deserves separate applause — can make a move right away and mint an NFT.

• All the games and moves are recorded on the blockchain. There are 59 games max and 59 moves per game max.
• There is just one game being played at a time. Anyone can make the next move and the game will continue.
• Everything’s on-chain: the engine, the NFT data, and the image (in the form of HTML)
• There is an interesting adaption to NFT/web3 world: Each move (and the corresponding counter move by the AI) will be minted as an NFT:

Noticed the owner?

The NFT is interactive

The smart contract source code

There are 4 smart contracts:

1. Chess.sol — for data representation. How the chessboard, chess pieces, and moves are represented on-chain.
2. Engine.sol— the AI that can make moves, capture pieces, etc
3. fiveoutofnine.sol— ERC-721 implementation allowing to mint moves
4. fiveoutofnineART.sol — helper used by the above contract for generating the metadata and images for NFTs

The source code can be found on the 5/9 website or on Etherscan.

The creator also translated the first 2 smart contracts (data representation and the engine) to Python for easier readability and understanding. You can’t run them on the blockchain, but logically they are equivalent to the actual Solidity contracts. Check them out on Github.

Now let’s break down the contracts one by one.

On-chain data representation

Chess.sol defines the data structures for the chessboard, pieces, and moves. A piece is represented using 4 bits:

Board representation is a little more complicated. The entire board fits into a 256-bit integer (8x8 board=64 cells at 4 bit for each piece → 64*4=256). You access the cells in the board using bit shifts and bit masks:(board >> (27 << 2)) & 0xFis the same as board[27] if board was just a flat array.

Why is the actual board6x6 rather than8x8? Because we need to keep the outermost rows and columns empty for efficient computation of whether a move is within the board bounds (isValid function)

Also, the bit on the bottom right corner of the board represents whose turn it is to move:

The moves are represented compactly in 12 bits.

The moves are not stored one-by-one because there is no efficient data structure for storing 12 bits in Solidity. Instead, 21 moves are packed into a single 256-bit integer (21*12=252<256). The game assumes that there are 105 moves max per game:

index is the index of the 256-bit integer currently in use

The append function adds a move to MovesArray:

Checks if the current partition is full. If full, just add the move. Otherwise, shift existing moves before adding

The rest of the Chess.sol contract are just helper functions that allow you to do things like/manipulate board, apply moves, etc. Here are all these functions (I skipped implementation of some of them for brevity):

The Chess.sol contract is used as a library for uint256 and movesArray so that the helper functions (rotate, applyMove, etc) are attached to uint256 and movesArray:

This allows you to do things like:

Generating NFTs

Let’s move on to the next contracts:

• fiveoutofnine.sol — implementation of the ERC-721 standard.
• fiveoutofnineART.sol — a collection of helper functions for generating the NFT art — called by fiveoutofnine.sol.

Here is the annotated fiveoutofnine.sol:

The contract above keeps track of the game index, move index, all the moves that have been made, external and internal token ids, etc. It calls the Engine.sol contract (the game AI) to search for the best counter move.

Each move (which actually consists of white’s and black’s moves) has a token id and can be minted as an NFT. The art for the NFT is generated in the _tokenURI function which itself calls the getMetadata function of fiveoutofnineART.sol.

getMetadata manually constructs the HTML for the NFT image. As you would expect, there are lots of if statements and strings concatenations to generate the HTML and its inline CSS. This gist has a shortened version of this code.

getMetadata also manually creates the JSON for the attributes of the NFT. The attributes are:

• name: string in the format “Game #X, Move #Y”
• description: shown in the image below

• bit border, color generation, dimension, gap, and height: explained below

Here are some pictures with various attributes from the OpenSea page:

Game engine

Now, onto the last contract: Engine.sol. This contract has the searchMove function that is used by fiveoutofnine.sol to make a counter move.

I won’t get into the details of this contract because it has lots of chess-specific algorithms. But the high-level strategy is clear from the above code snippet: generated all possible moves, evaluate each move according to some heuristic, and select the best move.

Closing thoughts

This is a pretty cool project demonstrating what’s possible on blockchains. The author put a great effort into gas optimization by bit-packing everything as efficiently as possible. This is so hardcore and reminds me of C. Yes, it makes the code hard to read, but you save so much gas with this type of code. (It costs around 0.06ETH to mint a move=$175 as of now. Pretty good for such a complex contract).

The author also made the game 100% trustless: meaning no one, not even the author can change the logic of the game. There is no upgrade mechanism or anything like that. Yes, it resulted in bugs that are can’t be fixed now, but it’s 100% trustless.

The project also has very cool-looking art/NFT for each move, allowing you to own a piece of chess history.

And the most fascinating part is that all of this was done by a college student. This was their way of learning Solidity. The project already inspired others (MateInEight) to build on top of 5/9.

That’s it for the 5/9 contract breakdown! I hope this was helpful. Let me know in the comments if you have any questions.

I am planning to do more breakdowns of popular smart contracts like ArtBlocks and DAI Stablecoin, so follow me either on Medium or Twitter to get updates.

You can also check out breakdowns of other smart contracts and more stuff for Solidity noobs at solidnoob.com.

Want to Connect?
Follow me on Twitter.