# 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:

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:

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:

// 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.

// 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

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).