In the game of tic-tac-toe, a single row has many different possible states. Each cell can either have X, O, or remain blank. It is a trinary number system. The number of unique states in one row is 3 to the power of 3 (3*3*3), or simply 27.
I am looking into this because I am interested in making a game of tic-tac-toe in an environment where image size and count mean everything. The less data that is needed to be transferred, the better. I could create an image for the entire grid, but that would result in 3 to the power of 9 images (19,683 images). I could dumb it down to just 3 images of an X, O, or empty spot, but the format of what is available would require me to use more resources to display 9 separate images at one time. The optimal method to use limited resources is to display 3 rows as 3 separate images.
I could go ahead and create 27 different images to load up in each row. However, the key idea here is the use less data that is needed to be transferred. My take on it is that I’ll use the same image for each row, but only show part of that image. So if I have an image that says “XXOXOXOXX”, and I want to show “XOX”, then I’ll stretch the image and center it on the “XOX” so that all of the other characters are outside of the visible area.
This is good, but I had one last thing to focus on. 27 different images all streamed together would result in an image with 81 characters. Surely their is a lot of repetitive characters? Take my example: “XXOXOXOXX”. You’ll notice that “XOX” is repeated three times, and “OXO” is repeated twice. I could try eye-balling it to cut it down to size, but we have computers for that sort of thing.
I started generating a random string of ” “, X, and O with 81 characters. As soon as I found a string that suited all possabilities that a row would have, I would generate another random string with 1 less character. It took much longer as I tried to generate less characters. I could only get down to 29 characters “O-OOX-O—X-XXX–OXO-XOXXOOO-”. This was very interesting to me because I was starting to see a significant pattern here. 29 is very close to 27, and as I noted earlier, the total number of possible combinations is … 27.
Doing the same for 2^2 is something I could do in my head. Possible combinations are 00, 01, 10, and 11. I came up with 10011. Only off by one (2^2 = 4), but if I wrap the text to repeat itself, I get “1001″ – 4 characters! Note “11″ is “wrapped” with the two ends. Now, with that knowledge in hand, look at the pattern that I had with 29 characters. Notice that the last 2 characters matches the first 2. From here, I can wrap the text around to reduce 2 additional characters resulting in 27! My final pattern was “O-OOX-O—X-XXX–OXO-XOXXOO”.
This reduces the total size of my image by almost 67%. The “wrapping” effect already happens with images in the environment that I work with and is known as “tiling”. If an image does not cover an entire area, the same image is placed next to itself, essentially causing a tiling effect over the whole area.
The next steps are to actually make the image, detect where a person has touched the game, and map the image to reflect the actual state of the game in each row.
At one point, I did try creating a string of values and incrementing them as a trinary number (—, –O, –X, -O-, -OO, -OX), however this actually took a lot of time to do. After letting it run for a couple hours with no results, I abandoned it all together and went for a randomized “fuzzy” approach. Randomly, I was finding different combinations of 29 characters each in about 2 minutes each. The lack of speed may have been because I was dealing with strings rather then an array of numbers. I’ll look into different possabilities next time.
