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

If a pile of matchboxes can learn to play Tic-Tac-Toe, then certainly I should be able to code a solution. With my predilection for databases, T-SQL was my tool of choice. But first, I needed to model the game with some sort of data structure. Unfortunately, as I learned, it’s not as simple as mapping some X and O values to a grid.

Data Model

Before we can analyze a game, we need to model it. We can visualize a grid of numbers labeling each square in a Tic-Tac-Toe game and we can imagine storing the character displayed (X or O) in each of those blocks, but that misses a critical aspect of the game.

Turn, turn, turn…

You can’t just look at a grid of X and O values and tell who won. Or rather, you can, if the game stops when someone wins. (Otherwise there might be more than one player with three in a row.) But that very concept– a stopping point– requires an understanding of turns.

In addition to the current game state– the values in each cell of our grid– we need to know how we got there.

General Purpose

If I were building a general purpose gaming engine, I’d want a flexible turn management system. I’d want to allow for any number of players making any number of plays. I’d want a big vertical list of every turn made in every game. It would look something like this:

This can handle a simple game like Tic-Tac-Toe, of course, but it can expand to any other type of game which has a concept of positions and sequential actions. It even allows the same player to play multiple times in a row, players to put a value in the same space more than once, and play values other than X and O. And therein lies one major weakness. It’s just a ledger; it has no inherent intelligence.

New rule!

We could give it some smarts. For example, we know that in our game, we can only choose X or O, so we could put a data constraint on the Play column. And we know that in our game, you can’t play on the same space more than once, so we could put a unique constraint on the combination of GameID and Position. You could even be really creative and enforce our game’s alternating player moves by putting a data constraint on the Player column such that it equaled 1 when (Turn Modulo 2) equaled 1 and 2 otherwise. (Really it wouldn’t need to be a data column at that point, just a calculated column.)

But imposing those restrictions robs our data structure from its raison d’être. It’s no longer a general purpose game play storage system; it only works for our game.

Instead of saddling the data storage itself with all of those rules, we could enforce all of the game mechanics through our data interpretation and manipulation logic. When we saved a game move, we could make sure that an X or O was played and it could check to see whether the specified square was already used. When we analyzed a game to determine a win, all of the criteria could be housed in that consuming query. But this flexible design isn’t done inflicting its complexity on us.

Squishy, squishy.

When your game data is spread across multiple rows, you have to gather all of those rows and intelligently interpret them as a group. This often involves “flattening” them into a single set of data.

For example, X wins if the value X is in position 1, 2, and 3 *before* O wins. Even just testing if X is in position 1, 2, and 3 involves checking for the existence of 3 different values in three different rows. You’d need to hit the table 3 times (one for each check), or use clever flattening logic to hit the table once, such as:

SELECT
	btWin123 = 
		CASE
			WHEN
				(
					SELECT
						COUNT(*)
					FROM	GamePlays
					WHERE	GameID = @GameID
					AND		Play = 'X'
					AND		Position IN (1,2,3)
				) = 3
			THEN
				'Win'
			ELSE
				''
		END;

And that’s just for 1 of the several ways X can win, and it doesn’t even account for the order of play. That’s Complex (with a capital C). So rather than repeatedly query the set of rows like this, we would probably gather all of the values up into a single “row”, exposing each move as a column. Checking for this same win would look something like this:

SELECT
	btWin123 =
		CASE
			WHEN
			(
				1 IN (FlatGame.a1, FlatGame.a2, FlatGame.a3, FlatGame.a4, FlatGame.a5)
			AND
				2 IN (FlatGame.a1, FlatGame.a2, FlatGame.a3, FlatGame.a4, FlatGame.a5)
			AND
				3 IN (FlatGame.a1, FlatGame.a2, FlatGame.a3, FlatGame.a4, FlatGame.a5)
			)
			THEN
				'Win'
			ELSE
				''
		END
FROM		(
				SELECT
					a1 = MAX(CASE WHEN Turn = 1 THEN Position ELSE '' END),
					b1 = MAX(CASE WHEN Turn = 2 THEN Position ELSE '' END),
					a2 = MAX(CASE WHEN Turn = 3 THEN Position ELSE '' END),
					b2 = MAX(CASE WHEN Turn = 4 THEN Position ELSE '' END),
					a3 = MAX(CASE WHEN Turn = 5 THEN Position ELSE '' END),
					b3 = MAX(CASE WHEN Turn = 6 THEN Position ELSE '' END),
					a4 = MAX(CASE WHEN Turn = 7 THEN Position ELSE '' END),
					b4 = MAX(CASE WHEN Turn = 8 THEN Position ELSE '' END),
					a5 = MAX(CASE WHEN Turn = 9 THEN Position ELSE '' END)
				FROM		@GamePlays
				WHERE		GameID = @GameID
			) AS FlatGame;

The columns in the derived table represent each successive move. First, player 1 (“a”) makes their first move (“a1”). Then, player 2 (“b”) makes their first move (“b1”). Then player 1 makes their second more (“a2”), etc. The values in the columns are what position was played. Our above game would result in these values when flattened to that single row:

Our “win” calculation involves checking whether all three squares– 1, 2, and 3– are present in any of X’s moves.

The code looks more complex at first blush, but importantly it allows us to check multiple conditions in our CASE statement. We can check for an X win with positions 1, 2, and 3, and then check for a win with positions 3, 4, and 5, etc., all without additional hits to the underlying table.

What’s more, we now have play order information embedded in the data as well; we can check if X’s win came before an O win, because we know when X and O made their respective plays.

Private Pragmatic

Now, I’m not building a general purpose game management system. I’m playing a game about playing a game because it seemed interesting. So let’s skip the elegant, extensible, vertical play table and go right to the single-row game representation. We’ll just store our games with each move represented with a column: a1, b1, a2, b2, etc.

Each move can be one of 9 different squares, and the smallest way to represent 1-9 is a tinyint. We can also add a column to record who won the game. Here’s our table:

CREATE TABLE AllGames
(
	a1 tinyint NOT NULL,
	b1 tinyint NOT NULL,
	a2 tinyint NOT NULL,
	b2 tinyint NOT NULL,
	a3 tinyint NOT NULL,
	b3 tinyint NOT NULL,
	a4 tinyint NOT NULL,
	b4 tinyint NOT NULL,
	a5 tinyint NOT NULL,
	winner bit -- NULL = none; 0 = A, 1 = B
);

We could even get clever and prevent mistakes by creating CHECK constraints to ensure no position is played more than once, which in our game would be invalid.

ALTER TABLE AllGames ADD CONSTRAINT u_a1 CHECK (a1 NOT IN (   b1,a2,b2,a3,b3,a4,b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_b1 CHECK (b1 NOT IN (a1,   a2,b2,a3,b3,a4,b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_a2 CHECK (a2 NOT IN (a1,b1,   b2,a3,b3,a4,b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_b2 CHECK (b2 NOT IN (a1,b1,a2,   a3,b3,a4,b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_a3 CHECK (a3 NOT IN (a1,b1,a2,b2,   b3,a4,b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_b3 CHECK (b3 NOT IN (a1,b1,a2,b2,a3,   a4,b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_a4 CHECK (a4 NOT IN (a1,b1,a2,b2,a3,b3,   b4,a5));
ALTER TABLE AllGames ADD CONSTRAINT u_b4 CHECK (b4 NOT IN (a1,b1,a2,b2,a3,b3,a4,   a5));
ALTER TABLE AllGames ADD CONSTRAINT u_a5 CHECK (a5 NOT IN (a1,b1,a2,b2,a3,b3,a4,b4   ));

At first blush, we might think we could store who wins a game as a bit, since either the first or second player will win. Except when they don’t. After all, Tic-Tac-Toe is designed such that perfect play will always result in a draw. So we must be able to represent that third possibility. Luckily, SQL Server allows NULLs, so our single bit column can play triple-duty.

Winning

In order to figure out who won a game, we at least have to be able to recognize a win– three of the same symbols in a row, horizontally, vertically, or diagonally. We saw (part of) one possible calculation above, where we check if one player has played all of the positions across the top row. But there are 8 ways to win, so our CASE statement would be at least 8 times as big. If only there were a way to compare a winning scenario with our actual game to see if there’s a match without several dozen ANDs, ORs, and repeated column lists.

I’m the map!

Fundamentally, a “bitmap” is a collection of bits. These days we think of bitmaps as images but that’s just a special case of the general idea. We can envision the X plays on a Tic-Tac-Toe board as a collection of bits– either an X was played or it wasn’t– in a numbered set of boxes. If we then imagine the boxes as powers of 2, we can see how any set of X plays can be represented as an integer.

If any collection of X plays can be represented as an integer, then it follows that a winning collection of X plays can be represented as an integer. And it just so happens that computers can easily check if all of the bits in one integer appear in another integer, using a concept called bitmasking.

You’re holding it wrong.

Remember that the way we typically represent numbers is “big-endian“, where the more significant digits are to the left. 100 is bigger than 001.

In decimal, the right-most digit is 10 to the 0th power (the ones); the next digit to the left is 10 to the 1st power (the tens); the next digit to the left is 10 to the 2nd power (the hundreds); and so on.

Similarly, we represent binary numbers with the more significant digits to the left. The right-most digit is 2 to the 0th power (the ones); the next to the left is 2 to the 1st power (the twos); the next digit to the left is 2 to the 2nd power (the fours); and so on.

(Interestingly, we can’t know the impact of the first digit in our number without knowing how many total digits there are going to be. And the way we represent numbers, right-to-left, flies in the face of our otherwise left-to-right language.)

One way to map our numbered squares to bits is to make the square number equal to the power of 2. So our winning state of the top row, consisting of squares 1, 2, and 3, would equal 21 + 22 + 23. We’d represent that as “1110”. Because we started counting from 1, we never use that 0th power, the right-most digit; it’s always 0. And because we know we’re going to have 9 total squares (10 total digits with our ignored 0th power), we’d probably write this number as “0000001110”.

Collection²

So we can represent a winning collection of bits with a single integer, and we can check our game against that easily, but there are multiple ways to win, so we need a collection of those collections.

Now a collection of integers sounds like a table to me. But we’re never going to change this data. It’s fundamental to the game; it’s not user editable. So we might as well “hard-code” the values. So let’s make an inline user-defined function which returns a list of the all of the winning conditions.

CREATE FUNCTION CalcWinList()
RETURNS TABLE
AS RETURN
(
	SELECT
		WinningBitmap = WinList.WinningBitmap
	FROM		(
					SELECT POWER(2,1) + POWER(2,2) + POWER(2,3) UNION ALL
					SELECT POWER(2,4) + POWER(2,5) + POWER(2,6) UNION ALL
					SELECT POWER(2,7) + POWER(2,8) + POWER(2,9) UNION ALL
					SELECT POWER(2,1) + POWER(2,4) + POWER(2,7) UNION ALL
					SELECT POWER(2,2) + POWER(2,5) + POWER(2,8) UNION ALL
					SELECT POWER(2,3) + POWER(2,6) + POWER(2,9) UNION ALL
					SELECT POWER(2,1) + POWER(2,5) + POWER(2,9) UNION ALL
					SELECT POWER(2,3) + POWER(2,5) + POWER(2,7)
				) AS WinList(WinningBitmap)
);

(We could have converted those values to actual integers for efficiency, but that would obfuscate what’s going on for code readers, and code is read more often than it’s written.)

Playing

So we we have a list of the bitmaps of all of the winning states. In order to check a player’s moves to see if they’ve won, we need to map their play bits as well.

Power to the Player

We’re modeling our game by representing each square as a power of 2, and we construct bitmaps by adding together all the powers represented by the played squares. Our data model represents a game as a row with a column for each play, but each player has their own bitmap. And that player’s bitmap evolves through the course of the game. So let’s build a function which computes a bitmap based on the player and the turn.

CREATE FUNCTION CalcTTTPlayerBitmap
(
	@player bit, /* player a = 1; player b = 0 */
	@turn tinyint,
	@a1 tinyint,
	@b1 tinyint,
	@a2 tinyint,
	@b2 tinyint,
	@a3 tinyint,
	@b3 tinyint,
	@a4 tinyint,
	@b4 tinyint,
	@a5 tinyint
)
RETURNS TABLE
AS RETURN
(
	SELECT
		PlayBitmap =
			CASE WHEN @player = 1 AND @turn >= 1 AND @a1 IS NOT NULL THEN POWER(2,@a1) ELSE 0 END +
			CASE WHEN @player = 0 AND @turn >= 1 AND @b1 IS NOT NULL THEN POWER(2,@b1) ELSE 0 END +
			CASE WHEN @player = 1 AND @turn >= 2 AND @a2 IS NOT NULL THEN POWER(2,@a2) ELSE 0 END +
			CASE WHEN @player = 0 AND @turn >= 2 AND @b2 IS NOT NULL THEN POWER(2,@b2) ELSE 0 END +
			CASE WHEN @player = 1 AND @turn >= 3 AND @a3 IS NOT NULL THEN POWER(2,@a3) ELSE 0 END +
			CASE WHEN @player = 0 AND @turn >= 3 AND @b3 IS NOT NULL THEN POWER(2,@b3) ELSE 0 END +
			CASE WHEN @player = 1 AND @turn >= 4 AND @a4 IS NOT NULL THEN POWER(2,@a4) ELSE 0 END +
			CASE WHEN @player = 0 AND @turn >= 4 AND @b4 IS NOT NULL THEN POWER(2,@b4) ELSE 0 END +
			CASE WHEN @player = 1 AND @turn >= 5 AND @a5 IS NOT NULL THEN POWER(2,@a5) ELSE 0 END
);

Importantly, the function only adds up those plays which belong to the specified player– hence the @player check on each play. Also, because we want a sense of time– we want to understand what the game state is as of a particular turn– we only count those plays which were made up to the requested turn.

Check 1 2…

So now we have a tool to understand the bitmap of any player at any turn (CalcTTTPlayerBitmap), and we have a list of all winning bitmaps (CalcWinList). We need to put those together to understand who won a particular game.

We understand that bitwise math allows us to quickly check if one bitmap is completely contained within another bitmap. If a winning bitmap is completely contained in the player’s bitmap at a particular point, they’ve won (provided they’re the first to achieve that).

So order matters here. We need to see who won first, so we need to check each player at each turn. We could do this with a very long, specially constructed CASE statement, repeatedly calculating the player’s bitmap at a particular turn with numerous calls to CalcTTTPlayerBitmap. But any time you find yourself calling the same function multiple times in a T-SQL statement, you should consider exploding some rows.

Naughts and CROSS JOINs

In order to check each player’s bitmap against the winning bitmaps at each stage of the game, we need a list of every play of the game. There are only 9 squares, so there are no more than 9 plays. Since the players take alternating turns, no player can play more than 5 times.

We want a list of turns 1 through 5 for player 1 and player 0 (aka player “O”– the second player). That means we want a row of 1 and a row of 0 for each of the numbers 1 through 5.

(We can ignore the last row as it’s impossible for the second player to move a fifth time, as there are no squares left.)

Any time you need to get every possible value in one collection (player table) matched with every possible value in another collection (turn table), you are making a cartesian product. You accomplish this in SQL with a CROSS JOIN.

For each row in that full list, we need to compute whether the player’s bitmap– up to that point– results in a win. As soon as we find a win (order matters), we have a winner (the player who just played).

CREATE FUNCTION CalcTTTWin
(
	@a1 tinyint,
	@b1 tinyint,
	@a2 tinyint,
	@b2 tinyint,
	@a3 tinyint,
	@b3 tinyint,
	@a4 tinyint,
	@b4 tinyint,
	@a5 tinyint
)
RETURNS TABLE
AS RETURN
(
	SELECT
		TOP 1
		Winner = CONVERT(bit,Players.Player)
	FROM		(
					SELECT 1 UNION ALL SELECT 0
				) AS Players(Player)
	CROSS JOIN	(
					/* We could omit 1 and 2 here, as we know no one can win before the third round. */
					SELECT 1 UNION ALL
					SELECT 2 UNION ALL
					SELECT 3 UNION ALL
					SELECT 4 UNION ALL
					SELECT 5
				) AS Turns(Turn)
	CROSS JOIN	CalcWinList() AS WinBitmaps
	CROSS APPLY	CalcTTTPlayerBitmap
				(
					Players.Player,
					Turns.Turn,
					@a1,
					@b1,
					@a2,
					@b2,
					@a3,
					@b3,
					@a4,
					@b4,
					@a5
				) AS PlayerBitMap
	WHERE		PlayerBitMap.PlayBitmap & WinBitmaps.WinningBitmap = WinBitmaps.WinningBitmap
	ORDER BY	Turns.Turn ASC,
				/*
					Player 1 is X; Player 2 (O) is represented as 0 here.
					Player 1 goes first, which is why this is DESC, because 1 > 0.
				*/
				Players.Player DESC
);

With our TOP 1, we will only get the first winning play. This simulates play stopping as soon as there is a winner; the additional plays are irrelevant, even if they are present. If there are no winning plays, nothing will be returned. That’s our draw.

So we now have a function which will compute a winner (or lack thereof) at any point of a game. Crucially, even if a game continues beyond the winning play, the correct winner will still be calculated.

Why is that crucial? Because we’re going to play a lot. Like, we’re going to play every possible game.

Brute Force

There are a lot of possible games of Tic-Tac-Toe. If we let gameplay continue until the board is full, regardless of whether a win occurs, there are 362,880. That’s because the first play can go in any of the 9 squares, the second play can go in any of the remaining 8 squares, the third play in any of the remaining 7, etc. The last play only has one option. So that’s 9 options times 8 options times 7 options, etc., or (9!).

We can make SQL Server do the work of creating all those possibilities. First, we make a “table on the fly” (otherwise known as a Common Table Expression or CTE) of our numbers 1 through 9. Then we can smash those tables together over and over– 9 times– using our CROSS JOIN trick. The problem is that this creates impossible games, such as when each player plays in square 1 on every play. We could weed those out at the end, or we could be more careful about how we create the big list in the first place.

Instead of creating all of the rows blindly and then removing the invalid rows with some criteria, we could combine values more selectively along the way. For example, instead of g CROSS JOIN g AS g2, we could have done the filtration during the JOIN process with an ON clause, limiting each successive combination so that none of its values occur in the previous values. For example, g JOIN g AS g2 ON g2.n <> g.n. That gets values 1 through 9 from the first “table” and for each of those values, it grabs 1 through 9 from the second “table”, so long as it doesn’t equal the first table’s value. Scale this up and we create T-SQL statement to create every row of our games table.

WITH g AS
(
	SELECT n = 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4 UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
)
INSERT INTO AllGames
(
	a1, b1, a2, b2, a3, b3, a4, b4, a5, winner
)
SELECT
	Game.a1,
	Game.b1,
	Game.a2,
	Game.b2,
	Game.a3,
	Game.b3,
	Game.a4,
	Game.b4,
	Game.a5,
	Winner.Winner
FROM		g
JOIN		g g2	ON g2.n NOT IN (g.n)
JOIN		g g3	ON g3.n NOT IN (g.n, g2.n)
JOIN		g g4	ON g4.n NOT IN (g.n, g2.n, g3.n)
JOIN		g g5	ON g5.n NOT IN (g.n, g2.n, g3.n, g4.n)
JOIN		g g6	ON g6.n NOT IN (g.n, g2.n, g3.n, g4.n, g5.n)
JOIN		g g7	ON g7.n NOT IN (g.n, g2.n, g3.n, g4.n, g5.n, g6.n)
JOIN		g g8	ON g8.n NOT IN (g.n, g2.n, g3.n, g4.n, g5.n, g6.n, g7.n)
JOIN		g g9	ON g9.n NOT IN (g.n, g2.n, g3.n, g4.n, g5.n, g6.n, g7.n, g8.n)
CROSS APPLY	(
				/* Alias each value according to the turn naming convention. */
				SELECT
					a1 = g.n,
					b1 = g2.n,
					a2 = g3.n,
					b2 = g4.n,
					a3 = g5.n,
					b3 = g6.n,
					a4 = g7.n,
					b4 = g8.n,
					a5 = g9.n
			) Game
OUTER APPLY	CalcTTTWin
			(
				Game.a1,
				Game.b1,
				Game.a2,
				Game.b2,
				Game.a3,
				Game.b3,
				Game.a4,
				Game.b4,
				Game.a5
			) AS Winner;

So we’re done now?

We’ve built a method of calculating the winner of a game, we’ve derived every possible game, and we’ve calculated the winner for each of those games. While that was a fun and educational exercise, we haven’t really taught the computer how to play Tic-Tac-Toe. In order for the computer to really be playing the game, the computer has to choose a play. We’ve done all of the choosing for it by “choosing” everything possible.

So I think we need to take this further. We need to write something which allows the system to choose what to do next. We need to imbue it with some artificial intelligence. And we’re going to do it with T-SQL.

Stay tuned.