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

[hezaplaya]

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]

Hmmm...how do you have it now?

 

[hezaplaya]

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]

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]

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]

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]

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]

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

 

[juiio]

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]

Can you explain how the base3 conversion to binary works??

 

[hezaplaya]

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]

6 bits is the best I can get.

 

[bleeb]

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

 

[RaynorWolfcastle]

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

-Ice

 

[charrison]

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.