# Optimized tic-tac-toe game in Solidity Building on Ethereum can be expensive, and many times it intuitive to gain control over your code and one way to achieve this is by utilzing bit operations. Many developers use it as a means of optimization, expecially in the case of ethereum when you code now cost you money. Here I'd be explaining a program I wrote not long ago, just so you'd gain an understanding of a simple use case of bit operations. Also, I assume you understand how to work with bitwise operators, and if you don't check out my [article on how they work here](https://hackmd.io/@0xosas/B1H8OY03c). ## What is Tic-tac-toe Tic-tac-toe is a 2 player game where players take turns to make a finite amount of moves until either all moves has been exhausted (its a draw) or a player has won. Here is a typical tic-tac-toe game. ``` # an empty game # game where play x won [ ] [ ] [ ] [x] [ ] [o] [ ] [ ] [ ] [ ] [x] [o] [ ] [ ] [ ] [o] [ ] [x] # Win is diagonal # a draw [x] [x] [o] [o] [x] [x] [x] [o] [o] ``` From the example above, 2 players are represented using to letters `X` and `O` and each take turns to win and also prevent the other player from winning. ## Naive approach With zero knowledge of bit operations, here is a typical representation of a game session: ```solidity struct Game { uint8[9] board; bool turn; // false = player 1, true = player 2 bool hasGameEnded; bool playerOneWon; bool playerTwoWon; bool isDraw; address playerOne; address playerTwo; } ``` However, we don't need 8 bits to store data for each position on the board in `uint8[9] board;` since 8 bits is allocated to each position which gives us ($8 * 9$) bits for a board that can be packed in just 18 bits, `bool turn;` is binary i.e 1 for `true` and 0 for `false`; Also, `bool hasGameEnded;`, `bool playerOneWon;`, `playerTwoWon` and `isDraw` are 4 situation a game can be and this can be represented in just 2 bits: * the game is ongoing (`10`), * player zero has won (`00`), * player one has won (`01`), * and game is a draw (`11`). So here is how we'd store a game in bits ``` 21 bits for each game 00 00 00 | 00 00 00 |= first 18 bits [000000000000000000] 00 00 00 | [00] [0] [00 00 00 00 00 00 00 00 00] ------ ------ ------------------------------ STATE TURN BOARD ``` ## Bit packing in solidity :package: ```solidity contract Tictactoe { uint256 gameBoard = 0; address internal playerOne; address internal playerTwo; constructor(address _playerTwo) { require(_playerTwo != address(0)); playerOne = msg.sender; playerTwo = _playerTwo; } /// @notice a new game is created by appending 21 bits to the current board function newGame() external isPlayer(msg.sender) returns (uint256){ if(gameBoard > 0){ gameBoard = gameBoard << 21 | 1 << 20; }else{ gameBoard = gameBoard | 1 << 20; } return gameBoard; } ``` From the example above you'd see the operation `gameBoard | 1 << 20`, this basically creates sort of a new 21 bits space for a new game. So here is a little break down of what is happening: ```solidity // intially gameBoard = 0 // then add 21 bits (1 << 20) = 100000000000000000000 (21 bits) // then gameBoard = gameBoard | (1 << 20) // 0 | 1 << 20 // gameboard = 100000000000000000000 ``` ## Making moves and turns :weight_lifter: When a player chooses to make a move he'd choose which place to play the move and indicate that it's the next players turn. Each move would be represented by a number like so: ``` [0] [1] [2] | => { [8] [7] [6] [5] [4] [3] [2] [1] [0] } [3] [4] [5] | -------------------------------------- [6] [7] [8] | BOARD ``` So typically a game play would be: Given that player1 is `X` and player2 is `O` ``` - player1 makes more 0 - player2 makes more 4 - player1 makes more 3 - player2 makes more 6 - player1 makes more 1 - player2 makes more 2 [x1] [x3] [o3] [x2] [o1] [ ] [o2] [ ] [ ] player 2 won :) ``` So I think you have a base understanding of how it works now, back to coding. ```solidity // full code @ https://github.com/0xosas/tictactoe.sol/blob/master/contracts/Tictactoe.sol contract Tictactoe { ... function move(uint256 _move) external returns (uint256) { uint256 _playerId = playerId(msg.sender); /// Since we can locate a position by a number /// keep in mind that for position 0 played by `player1` is different /// from position 0 player by `player2` /// /// In each position there are 2 points [0 0] lets say [a'p, a'p] /// where `a` is the position and `p` is the player. /// /// Now, position zero `0` == [0'2 (player 2), 0'1 (player 1)] /// /// If player one plays on position zero /// 00 00 00 00 00 00 00 00 00 /// ^ /// spot zero /// Then we'd just flip the bit there, there using /// (1 << (position << 1)) gameBoard = gameBoard ^ (1 << ((_move << 1) + _playerId)); /// Keeping tracking of who to play next /// Next to play is represented by the /// 00 0 00 00 00 00 00 00 00 00 00 /// ^ /// play next /// flips the bit for the next player /// 0 => `player1` turn /// 1 => `player2` turn gameBoard = gameBoard ^ (1 << 18); /// checks if `_playerId` has made win /// 1 => means the `_playerId` has won /// 2 => means no more fields to play, then it's a draw } ``` ## Winning :trophy: Now, players can make moves and switch turns but they'd keep playing if we don't stop them when a player has won or it's a draw. So a player's win can either be `HORIZONTAL`, `VERTICAL` or `DIAGONAL`. Representing these in the board would look like: #### Horizontal ``` HORIZONTAL_MASK = 0x3f 11 11 11 | 00 00 00 | => 000000000000111111 = 0x3f 00 00 00 | These are the HORIZONTAL wins 1. x x x 2. | 0 0 0 3. | 0 0 0 0 0 0 | x x x | 0 0 0 0 0 0 | 0 0 0 | x x x For player 1 H1. 10 10 10 00 00 00 = 000000000000010101 00 00 00 H2. 00 00 00 10 10 10 = 000000010101000000 : H1 << 6 00 00 00 H3. 00 00 00 00 00 00 = 010101000000000000 : H2 << 6 or H1 << 12 10 10 10 Note: HORIZONTAL_MASK / 3 == H1 ``` #### Vertical ``` VERTICAL_MASK = 0x3f 00 00 11 | 00 00 11 | => 0b11000011000011 = 0x30C3 00 00 11 | These are the VERTICAL wins 1. x 0 0 2. | 0 x 0 3. | 0 0 x x 0 0 | 0 x 0 | 0 0 x x 0 0 | 0 x 0 | 0 0 x For player 1 V1. 10 00 00 10 00 00 = 000001000001000001 10 00 00 V2. 00 10 00 00 10 00 = 000100000100000100 : V1 << 2 00 10 00 V3. 00 00 10 00 00 10 = 010000010000010000 : V2 << 2 or V1 << 4 00 00 10 Note: VERTICAL_MASK / 3 == V1 ``` ### Diagonal ``` 11 00 00 | 00 11 00 | => 0b110000001100000011 = 0x30303 00 00 11 | 00 00 11 | 00 11 00 | => 0b1100110011 = 0x3330 11 00 00 | These are the DIAGONAL wins 1. x 0 0 2. | 0 0 x 0 x 0 | 0 x 0 0 0 x | x 0 0 For player 1 D1. 10 00 00 00 10 00 = 010000000100000001 00 00 10 D2. 00 00 10 00 10 00 = 000001000100010000 10 00 00 BL_TO_TR_DIAGONAL_MASK / 3 == D1 BR_TO_TL_DIAGONAL_MASK / 3 == D2 ``` ### Code ```solidity contract Tictactoe { ... function checkState(uint _playerId) public view returns (uint256){ uint256 _gameBoard = gameBoard; unchecked { if ((_gameBoard & HORIZONTAL_MASK) == ((HORIZONTAL_MASK / 3) << _playerId)){ return 1; }else if((_gameBoard & (HORIZONTAL_MASK << 6)) == ((HORIZONTAL_MASK / 3) << _playerId) << 6){ return 1; }else if((_gameBoard & (HORIZONTAL_MASK << 12)) == ((HORIZONTAL_MASK / 3) << _playerId) << 12){ return 1; } if((_gameBoard & VERTICAL_MASK) == (VERTICAL_MASK / 3) << _playerId){ return 1; }else if((_gameBoard & (VERTICAL_MASK << 2)) == (VERTICAL_MASK / 3) << _playerId << 2){ return 1; }else if((_gameBoard & (VERTICAL_MASK << 4)) == (VERTICAL_MASK / 3) << _playerId << 4){ return 1; } if ((gameBoard & BR_TO_TL_DIAGONAL_MASK) == (BR_TO_TL_DIAGONAL_MASK / 3) << _playerId){ return 1; } if ((gameBoard & BL_TO_TR_DIAGONAL_MASK) == (BL_TO_TR_DIAGONAL_MASK / 3) << _playerId){ return 1; } /// Checks if all fields has been played for(uint x=0; x < 9; x++){ if(~(_gameBoard & 0xF) & 0x3 == 0x3) { return 0; } _gameBoard = _gameBoard >> 2; } /// A Draw return 2; } } } ``` ## Conclusion Having a good knowledge of bit operations is really great! also keep in mind almost all programming languages implement the operations, so it's basically applicable in most languages. These tricks are great but many times they have extremely niche applications, and that is up to you to choose when and when not to apply them. Also, check out a similar article by [fivenine here](https://hackmd.io/@fiveoutofnine/Skl9eRbX9) as it inspired this article. ---- If you found this helpful, consider following me on Twitter [@0xosas](https://twitter.com/0xosas).
Last changed by  
 
0xosas
692

Read more

An experimental minsweeper implementation

Well, this article is relating to my last article on tictactoe game and this is because of similar logic being used. A Minsweeper Game The objective of the game is to clear a board that contains hidden "mines" or "bombs" without detonating any of them, and they are randomly placed in a 9x9 grid (beginners level). On every right opeing there's a clue which indicate how many bombs are in the adjacent cells. At any point, you can perform 2 actions: Marking a cell - marking or flagging a cell that you think might be a bomb Revealing a cell - revealing the cell. If it is an empty cell, then all of the surrounding empty cells will also be revealed. Revealing a cell containing a bomb is game over.

8/17/2022
Why you should revert early

Ethereum transactions that revert still have to pay the gas used up until the revert was triggered; If they run out of gas they pay the full limit. If they hits a revert opcode, probably from a require statement as a result of maybe an integer overflow check, they'd pay the gas up until the revert opcode was hit. They don't pay for the gas afterwards. The implication is we should revert as early as possible in the execution to save the users gas incase a transaction reverts. Here are two (2) example contracts: // DO NOT USE IN PRODUCTION // USED FOR EXPLANATION ONLY contract Example1 { uint256 public a;

8/4/2022
Ethereum block limit

The first crypto-currency Bitcion has limited a block size to 1-MB, and this is beacause if a block is too large it becomes expensive to store or sync with other nodes across the world or the blockchain. Ethereum doesn't place a block limit like Bitcion does, it just limits the total amount of computation on a single block since each computation has a gas cost. And the reason for this is, if a block has too much computation on it, it becomes difficult for nodes to verify the transactions quickly. So with a block limit set, if a transactions requires too much gas the transactions gets reverted. What is gas? Gas is a transaction unit that represents computational effort. It’s the fuel you must buy to get miners to add your transaction to a block. At the time of writting the block limit is 30 million (30,000,000) gas; An eth transfer cost 21 thousand (21,000) gas, so doing the math you'd see that a single block can hold just 1,428 transfers approximately. A few relating terms.

8/3/2022
Bit Operations

This is an introduction to using bitwise operators and you'd learn how to do magical stuffs with them. So basically bit operations are used to manipulate bits (binary numbers) and here are the signs used: Bitwise AND & A bitwise AND is a binary operation that takes two bits and performs the logical AND operation on them. If the bits compared are 1, then bit in the resulting binary representation is 1 (1 & 1 = 1); otherwise, the result is 0 (1 & 0 = 0 and 0 & 0 = 0) source. Here is a typical example: A B A & B

7/27/2022
Read more from 0xosas
Published on HackMD