By Riley Major, 2018-05-18 | Tic-Tac-Toe Series Part 1 (this article) / Part 2

Known as Noughts and Crosses across the pond, Tic-Tac-Toe is considered a “solved game“– meaning we can predict the outcome of the game assuming perfect play. In fact, Wikipedia says “it is straightforward to write a computer program to play tic-tac-toe perfectly“. Well then as a programmer, I ought to be able to do it.

Now I could have probably found a complete programmatic solution in short order, but I wanted to try it myself. MPR was having their member drive, so I didn’t bother turning it on for my drive home. (I already have a monthly contribution.) Instead, I couldn’t stop thinking about how to model the game. I realized that it was many orders of magnitude easier than games like Chess, Checkers, and– gasp— Go, so it seemed like something I could tackle.

Model

My initial plan was to “brute force” all of the possible games. But first, I would need a way to represent the physical reality of the game as data. Obviously, I needed some representation of each square and whether or not it held an X, O, or nothing. “Normal” programmers would start thinking about two-dimensional arrays or other memory constructs. Me? I think about data tables and SQL Server.

While the game itself looks like a table, I wasn’t about to have thousands of tables, one for each game state. Even if that were technically feasible, you can’t dynamically access tables without dynamic SQL, and that’s a pain I didn’t want to subject myself to. So I needed a way to put all of the game states in one table.

Au Naturel

One way to store this information would look a lot like the game itself:

However, that means any time I want to analyze an entire game, I’d have to load three rows of data into a specialized set of variables. And if we’re going that far, why not dispense with those pesky, fixed columns and make this extensible. We all love the entity-attribute-value (EAV) pattern, right?

EAVy Peavy

Now we can support Tic-Tac-Toedecahedron– 4×4, 5×5, 6×6, whatever you have the compute power for. But it also means analyzing a game’s worth of data requires a maze of comparisons across rows to determine whether you have N in a row. And I was not planning on building a maintainable enterprise solution. Rather, I was playing a game– the game of seeing if I could make a game. So rather than representing this data vertically across multiple rows, I thought it might be faster and easier to code if we squished it down to one row per game.

Horizontal

Ok, so if we’re only going to support 3×3, and we want to have everything in one row so we can grab it easily for processing, then we just need 9 columns, one for each cell in a game. And because I’m human, not a computer, I start counting at 1. (Narrator: he should have tried counting like a computer.)

Game board, labeled:

Flat game board table model:

X = 1

Those of you with classical computer science backgrounds might recognize this as a collection of bits (X or O). There are some other things which are collections of bits– every integer ever. After all, (current) computers are fundamentally bit processors. Everything comes down to true or false. All digital data is just a really, really long series of ones and zeroes. We derive meaning by applying context to all those bits.

When we store numbers in binary format, we’re storing them in base 2. The number 7, for example, is “111”, which means it’s 1 (2 to the 0th power) + 2 (2 to the 1st power) + 4 (2 to the 2nd power). So “101” translates to 5. So any string of 1’s and 0’s can be construed as an integer. The more bits, the bigger the numbers. For our game, we have 9 bits, and every end game state can be represented by a string of ones and zeroes. (You can pick either X or O to represent as 1. We’re picking 1 for X because O looks like 0.)

So we can assign each of our 9 cells to the 9 bits in a 9-bit binary number. Binary numbers are typically written with the less significant digits to the right. So if we labeled each of our bits, it would look like this “987654321”. The first game listed above has an X in the 1st, 3rd, 5th, and 8th cells. So let’s replace those bits with “X”, yielding “9X76X5X2X”. If we assign 1 to X, then our binary number ends up being “010010101”. Now, that works just fine, but then we have to remember that our 1st cell is represented by 2 to the 0th power and our 9th cell is represented by 2 to the 8th power. That seems like a recipe for off-by-one errors (one of the two big problems in computer science). If we’re willing to throw another bit into the mix, we can represent our cells as “9876543210”. We’ll just never put anything in the 0th cell/power. (Maybe we should have counted from 0.)

With that scheme, our first game is encoded as “0100101010”. You can figure out that’s 298 in decimal either using your calculator app or your favorite programming language, like T-SQL:

SELECT
	POWER(2,1) +
	POWER(2,3) +
	POWER(2,5) +
	POWER(2,8);

So by translating these 9 separate bits into a single integer, we’ve reduced our 9 table columns to 1. But we’ve made something which was visually easy to understand into something inscrutable to humans. And depending on your database engine, you might actually be using more space. For example, in order to have numbers up to “1111111111” (1023 in decimal), we need to use a numeric or smallint, which SQL Server stores with a minimum of 5 or 2 bytes, respectively. 2 Bytes is 16 bits, which is more space than our 9 bit fields would have required. (There is some column overhead, but I still think the bit fields would be less space.) So why would we bother?

Zoro!

In order to figure out if someone won our game, we need to check if there are three in a row of the same player’s mark. None of the storage mechanisms we’ve considered have any native understanding of “in a row”. For any game state, we’d end up checking if a one particular row and column was X and then another, adjoining row and column was X, and then another, etc. You’d select the winning games with something like “(this and this and this) or (this and this and this) or…”. That gets messy fast.

Imagine if you had a bunch of cardboard cut-outs you could put over your game which would expose only the squares required for a win. The cardboard would “mask” the squares you didn’t care about so you could see just the potentially winning values.

It turns out there’s a concept called bitmasking which can work a lot like this cardboard cut-out process. (Props to Dylan Beattie for his quick visual demonstration at NDC Minnesota which drove this point home.) First, you represent your game state with a bunch of bits (“OXOOOXXXX” yields “0100011110” for our example above, remembering that we’re padding that last 0 just to make the powers 1-based instead of 0-based) and then you represent your winning state with a bunch of bits (“0000001110” for our example winning state here). Now you use the magic of “bitwise math” to compare the two.

For our use, we want to find out whether our mask exposes the winning three bits. We want to block everything else out. With bits, to check if both items are true, you use “AND” (0 and 0 is 0; 0 and 1 is 0; 1 and 1 is 1). If we apply that “AND” concept to each bit in our game, it will squash out any values which don’t match. If what we have left matches the mask (fills in all of the space we can see through), then we have a match and a win.

Most programming languages have this capability built-in. In T-SQL, the “bitwise AND operator” is the ampersand. If we convert our example binary game state of “0100011110” to decimal, we get 286. For our mask, “0000001110”, we get 14. We see that we get a matching result of 14 when we compare them in T-SQL using an ampersand:

SELECT
	CASE
		WHEN 286 & 14 = 14 THEN
			'Win!'
		ELSE
			'Not a win'
	END;

Result:

Win!

Tic-Tac-Tie

If we make a small adjustment to our example ending game state, swapping the 5th and 8th cell contents to yield “0100111010” (decimal 314), we’d have a tie.

We can verify this with T-SQL:

SELECT
	CASE
		WHEN 314 & 14 = 14 THEN
			'Win!'
		ELSE
			'Not a win.'
	END;

Result:

Not a win.

Hugs or Kisses?

It would be nice if we could just presume O won when X didn’t win, but as we just saw there are those pesky ties, where nobody wins. So we have to specifically check if O won.

Let’s take our earlier example, “OXOOOXXXX”, where X won, and turn it into an O victory by switching everything around, yielding “XOXXXOOOO”. Using our binary encoding, we’d get “1011100000” (decimal 736). (Remember that extra 0 at the end; thanks 1-based counting decision.)

How can we tell if O won?

Absolutely Nothing

Well, if O won, then when we look through our mask, we should see only O values– that is, all zeros. So when we perform a “bitwise AND” on our game state and our winning mask, we should see all zeros.

We can also verify this with T-SQL:

SELECT
	CASE
		WHEN 736 & 14 = 0 THEN
			'Win!'
		ELSE
			'Not a win.'
	END;

Result:

Win!

If we use this same methodology with the tie game above, we can see that applying the winning bitmask not only doesn’t result in a match (indicating an X win), but it also doesn’t result in all zeros (indicating an O win).

Don’t be so negative.

There’s actually another method for checking for an O victory. Instead of looking for all zeros with our match, we could first flip all of the bits, essentially remapping O to 1 and X to O. Then we would apply the same logic as we did for an X victory, where we checked that the bitwise AND with the winning bitmask resulted in a match.

It’s pretty easy to do this in T-SQL as well, thanks to the bitwise NOT operator, a tilde (~). We take our original decimal value for our O-winning game, 736, flip its bits with the tilde, and then check to make sure it matches our winning bitmask (decimal 14).

SELECT
	CASE
		WHEN (~736) & 14 = 14 THEN
			'Win!'
		ELSE
			'Not a win.'
	END;

Result:

Win!

O boy.

So to determine if O won a game, we can either use the zero-match method (use AND and look for all zeroes) or the bitwise-NOT method (flip the bits, then use AND and check for a full match as with X).

SELECT
	Zero_Match = CASE WHEN 736 & 14 = 0 THEN 'Win' ELSE 'No win.' END,
	Bitwise_Not = CASE WHEN (~736) & 14 = 14 THEN 'Win' ELSE 'No win.' END

Results:

Win!

This way and that.

Wait, all that, and we’ve only checked for one winning condition (as it happens, across the bottom row). But there are actually 8 winning methods– all three rows across, all three columns, and then the two diagonals. So to calculate the overall winner for a game, we need to check the game’s bitmask against each of the eight winning bitmasks for X, and then if none match, we check for O (using whichever method), and then if none match, it’s a tie.

Tic-Tac-D’oh!

Ok, so we think we have a good way to record our game states– as a bitmask where the bits represent “X” when they’re on and “O” when they’re off, and each bit corresponds to one of our labeled squares.

And we think we have a good way to detect whether X or O won the game– we compare the game’s bitmask to the winning bitmask and check if there’s a match for X or an inverse match for O.

So tell me, who won this game?

It’s a trick question. You can’t.

In some sense, it might not even be a valid game state. After all, if we define the game as ending as soon as there are three-in-a-row, then we can have finished games which don’t have all of the squares completed. That’s a big problem for our data model. Because we’re storing bits in a bitmask, they have only two values, true or false. There’s no concept of “not specified” (NULL). We’d have to go back to bit fields for that, since in SQL Server they can have a NULL state. (That’s thanks to some of that extra columnar overhead hinted at earlier, since there’s a NULL bitmask in the row storage mechanism.)

But even if we didn’t say the game ended as soon as there were three in a row, and play continued until every box was filled, you still don’t know who won this game, because you don’t know who got three-in-a-row first. Even if you assume that X always goes first, you can’t assume that X was the first to get three-in-a-row. Yes, it’s very likely, but we can’t presume perfect players when we’re building a system to manage game-play.

So any storage system for this game must include a concept of turns, so that we know how the game looked throughout time and can detect the first point at which a player achieved three-in-a-row. (Ideally, it would also prevent invalid game states from being stored, such as a board with all X or all O plays.)

So what we have built simply won’t do.

But why!?

I do have a solution which I think works, but obviously this isn’t it. I plan to share that in a follow-up post.

So why did I go through all of this explanation if ultimately it was unsuccessful? Several reasons.

First, this is really how I thought this through originally. And I think showing skilled failure helps others realize that failure isn’t a catastrophe but rather a learning experience. (Unless, of course, you’re talking about pacemakers or bridge safety systems, etc.) By “skilled failure”, I don’t mean being sloppy or careless, but rather applying your skills in a reasonable manner and considering each decision. Even by doing everything “right”, in the context of your knowledge at the time, you can still be “wrong”. And that’s ok, because now your knowledge has expanded. Exposing this process shows that even those who have been around the block a few times still make wrong turns. Besides, it’s all about the journey, right?

Second, breaking apart this background from the solution and its explanation allows me to explain some of the concepts (like the storage mechanism choice and bitmasking) in a simpler context. And the turn-based game model is more complex, so the more you understand going into it, the easier it will be to follow.

Third, planting these seeds might cause some ideas to grow in readers’ heads. You might get more benefit thinking about possible solutions without seeing what I came up with.

Fourth, I think having the background and solution all in one post might make it so big that no one would bother reading it. And having this background separate gave me the space to indulge in a little more detail and some asides which might have been overwhelming in an even bigger combined post.

Fifth, this allows me to provide something which has some inherent value before the rest of the solution and explanation is ready for publication. (And I can show some results for the work which has gone into this.)

Finally, breaking things at this point provides a little teaser for the next post where I will show (what I believe to be) a working solution. (It also forces me to write the rest and not abandon the idea, because I’ve made a public commitment.)

Same bat channel…

So the next post on this subject will contain a working game storage mechanism, a function to determine the result of the game (X win, O win, or tie), and even some primitive artificial intelligence and some really simplistic machine learning, all done in T-SQL.