Have you ever wondered how small the needed storage for a game of tictactoe (including its history) is? This project tries to tackle that question
This project is a proof-of-concept on how small a game of tictactoe (including move history) can be encoded without any extra overhead like a Huffman-Tree.
This project brings a game down to 23 bits, but the storage is done in an u32 (unsigned 32bit integer), as machines cannot assign single bits.
If you want to get the project onto your own machine, you have two options: Clone and build it yourself or download it for your machine.
If you just want to download the project, please do that here for your machine:
Keep in mind: These were only tested for certain versions of the operating systems listed. There is a chance it won't work for you.
If you want to build it yourself, you first need to pull it:
git clone git@github.com:aneshodza/minimal-tictactoe.git
cd ../minimal-tictactoe
Then you build the project using cargo
:
cargo build --release
cd target/release/
To then run the project, you move into the folder you downloaded it into and run it using the following command:
./minimal-tictactoe
There is a possibility that it won't let you run the program, as its permissions are not correct. To fix that run:
chmod +x minimal-tictactoe
If you retry running the code, it should work.
Important: Currently, the project doesn't support really playing the game, but rather just inputting the moves or game that needs to be encoded or decoded. After running the project, you will be greeted with the following screen:
Tictactoe encoded in only 23 bits
What do you want to do?
1. Decode your game
2. Encode a game
3. Exit
Here you can choose between either encoding or decoding the game. For the instructions of each, please refer to the following sections.
When you want to encode a game, the following prompt will appear:
Tictactoe encoded in only 23 bits
What do you want to do?
1. Decode your game
2. Encode a game
3. Exit
2
Please enter 1 to 9 numbers (1-9) separated by spaces:
There you need to give the program all the moves you made separated by spaces. The game from the explanation below would look like this:
Please enter 1 to 9 numbers (1-9) separated by spaces:
1 4 5 3 2 3 2 1 1
Then the program will output the encoded game:
Your encoded number is: 4310116
It's binary representation: 10000011100010001100100 (23 bit)
X O X
O O X
X O X
When you want to decode a game, the following prompt will appear:
Tictactoe encoded in only 23 bits
What do you want to do?
1. Decode your game
2. Encode a game
3. Exit
1
Please enter your game (in decimal)
There you need to give the program the encoded game. If we want to decode the game from the example above, we would give it the following input:
Please enter your game (in decimal)
4310116
Then the program will output the decoded game:
X O X
O O X
X O X
The game numbers all squares on the ticktacktoe board from one to nine, as follows:
1 | 2 | 3
-----------
4 | 5 | 6
-----------
7 | 8 | 9
When a user then plays a move, like on field 3, that index gets popped off the list, and the list gets re-numbered:
1 | 2 | X
-----------
3 | 4 | 5
-----------
6 | 7 | 8
And so-on and so forth for every of the 9 moves.
In the end, there should be an Array of nine numbers:
[1, 4, 5, 3, 2, 3, 2, 1, 1]
Every index of the array gets subtracted by one, as the binary representation can be shorter that way:
[0, 3, 4, 2, 1, 2, 1, 0, 0]
Every number occupies as little bits as are needed to represent all options.
As the board starts with nine options (zero to eight), the first number needs four bit.
The second then only needs three, as there are only eight options left (zero to seven), etc.
The constant BIT_SIZES
is used to represent that:
pub const BIT_SIZES: [u8; 9] = [4, 3, 3, 3, 3, 2, 2, 1, 1];
The reason the last move cannot be left out (as there is only one option left) is that the game can end before the last move is played. Giving it one bit is far more efficient than any other option (like showing the running length).
The concept is that there is a shift
that pinpoints where in the number we currently are.
It can be imagined as follows:
The encoding starts by finding out how long our number will be and storing it into the
shift
:
let mut shift: u8 = BIT_SIZES[..moves.len()].iter().sum();
This looks as follows (if our game is all nine moves long):
Then we take a
SIGNIFIER
, which is just a one and shift it by the shift
:
output |= (SIGNIFIER as u32) << shift;
The purpose of the signifier is to make a certain number of moves always have the same number of bits used, as a game where every move is on the first field would lose information to zero-padding. We also have to subtract the shift by the size of the first move, to prepare space for the next move:
shift -= BIT_SIZES[0];
This looks as follows:
Then we loop through every move in the
moves
array and follow the same procedure:
- Take the current move and subtract one from it
- Shift it by the
shift
- Add it to the
output
, using a bitwise OR - Subtract the
shift
by the size of the next move - Repeat until all moves are encoded
Implemented in rust, it looks as follows:
for (idx, element) in moves.iter().enumerate() {
output |= (((element - 1) as u32) << shift) as u32;
if shift > 0 {
shift -= BIT_SIZES[idx + 1];
}
}
And visually, every move does about this:
Coming soon...
Made with <3 by Anes Hodza