# store a tic-tac-toe board in 2 bytes or less?

#### hezaplaya

##### Member
Can n e one store the info in a tic-tac-toe board in 2 bytes or less? including whose turn it is.... i have it down to exactly 2 bytes (16 bits) but i cant get it n e lower

#### b0mbrman

##### Lifer
Hmmm...how do you have it now?

#### hezaplaya

##### Member
right now i am storing the board in base 3 (2 stands for O, 1 stands for X and 0 stands for blank) then converting that number to binary and i get 15 bits plus 1 more to determine who's move it is

#### dman

##### Diamond Member
There's 9 spots, so, 9 digits there (0 or 1 for x/o). Then 1 bit for who's turn it is 0 is player a, 1 is player b. That'd be 10 digits or 1byte + 2 bits. Without compression that seems to be the lowest number to me, but, I'm no expert.

#### hezaplaya

##### Member
you cant do it that way because if you only have X and O then how can u have a blank space? there need to be at least 3 characters in the number system which is y base 3 is ideal..... also i would like to try to get it down to 8 bits... because when using memory u cant use less then 8 bits (1 byte) so storing it in 10 bits is just like using 16

#### rgwalt

##### Diamond Member
Are the memory bits initally 0 or 1 or blank? If you could reinitialize the memory each time, you could get it down to 9. You could compare the number of X's and O's to determine who is next (if X>O, its is O's turn. If O=X it is X's turn).

Also, do you ever fill up the entire board in any game? If not, then you need to write an algorithm to determine who is the winner or if there is a scratch game. But you would be down to 8 bits

Ryan

#### hezaplaya

##### Member
the memory is initially a zero... and whos turn it is must be stored in the memory.... i cant use an algorythm to determine whos turn it is..... so basically i have 7 bits to work with..... if u can figure out how to encrypt the data better than i have it i think that will work best..... are there more than 255 possible combinations on a tic-tac-toe board?? if not i could say each different combo of bits is a different combo on the board and that could work

#### Killbat

##### Diamond Member
3 possible values (X, O, blank) ^ 9 spaces = 19683 combinations
You need 15 bits to contain that, in raw data.

#### juiio

##### Golden Member
The total number of combinations of Xs, Os, and blanks is somewhere between 2048 and about 4048 (Estimating here. The total combination is 19683, but since the number of Xs and Os will always be equal or off by 1, many cases are eliminated). Thus you could represent the board in 11 or 12 bits.

You could also deduce whose turn it was based on the number of Xs and the number of Os (assuming X always go first), thus eliminating the need for a bit to keep track of the turn.

#### yata

##### Senior member
Can you explain how the base3 conversion to binary works??

#### hezaplaya

##### Member
its basically the same as binary..... in base 3 the max integer is 2 leaving 3 characters 0... 1.... and 2... the first column is the ones column.... the second is the 3's the third is the 9ths the next it the 27ths the next is 81st and so on.... u just convert whatever num u get to binary to store it and then to read it make an algorythm that decrypts it

#### lo5750ul

##### Senior member
6 bits is the best I can get.

#### bleeb

##### Lifer
All that bit twiddling might reduce the performance of the game. (All the sub functions to manipulate the bytes)

#### RaynorWolfcastle

##### Diamond Member
Feeling limited by hard drive space?
2 bytes seems to be the easiest most practical way

-Ice

#### charrison

##### Lifer
bleeb,

It will kill performance.
It is far faster to do store the arrays in a 32 bit int array, than to do bit bashing.