hide me

Programming Tic Tac Toe: Magic Square

Programming Tic Tac Toe: Magic Square

There is an expression, “Form follows function” that is often used with architecture, product, and sometimes software design. It suggests a single solution. Depending on the software implementation, its target and the way the problem is perceived, among other variables, the internal “form” can be radically altered.

Tic-tac-toe (naughts and crosses) seems to be a fairly simple game. There are three starting moves, nine positions to select from, eight possible combinations to win, so how difficult could it be to program? (If the numbering on the grid is ignored and the grid rotated, there are ony three positions; the corner, edge or center to start)

How to number the board, in order to solve the game
One question, which can change the way the problem is approached, is how do you represent the board? Numbering it 1 through 9 in rows, or around the outside with the last number in the center are possibilities. What strategy do you use to pick the next move? Do you scan all possible combinations, try a recursive approach, figure some way of weighting the moves or a combination of techniques, or possibly reduce the game down to a formula? How do you determine who won?

It would be convenient if each position on the grid could be mapped to the square that was just selected. This would require quite a bit of overhead with the sequential numbering 1 through 9. Numbering one through eight around the perimeter makes the job simpler, but using 0 through 8 makes the job even easier. That way the next corner is (X + 2) AND 6, the previous square = (X – 1) AND 7. This simplifies things quite a bit, but it’s still difficult to determine when you have three in a row other than scanning or building a table. One also has a tendency to think of a position occupied with a zero as either that position being empty, or a naught. This leads us to a magic square, where the sum of any three positions, row, column or diagonal, add up to 15. The relative positions become a little trickier to map. If the magic square numbering is flipped on either diagonal axis, the clockwise and counterclockwise positions, if you think of them that way, reverse. The magic square does make it much simpler to determine if you have three in a row or what the next move should be. This approach allows the game to be reduced to a number of formulas making a solution fairly straight forward.

Using the magic square shown, some of the relative positions from a position X would be:

Across = 10 - X

Corner previous				// if not center (5)
Cp =	if odd(X)			// then odd is an edge
	then Cp = Across((X+X) mod 10)
	else Cp = (X*3) mod 10		// if even, X is a corner

Corner next
Cn =	if odd(X)
	then Cn = Across((X*4) mod 10)	// from edge
	else Cn = (X+X) mod 10		// from corner

Edge previous
Ep =	if odd(X)
	then Ep = (X*3) mod 10		// Ep(7) = 1
	else Ep = 15 - Cp - X		// Ep(6) = 1

Edge next
En =	if odd(X)
	then En = Across(Ep)
	else En = 15 - X - Cn

Knight previous
Kp =	if odd(X)
	then Kp =  (X*4) mod 10		// Kp(9) = 6
	else Kn = 5 + X - Cp		// Kp(8) = 9

Knight next
Kn =	if odd(X)
	then Kp =  (X+X) mod 10		// Kn(9) = 8
	else Kn = 5 + X - Cn		// Kn(8) = 7

The possible second moves without losing the game

If the first move is “X”, as shown, the second move MUST be to a position occupied by a “O” or the second player will lose (if no mistakes are made). Mapping the combinations for the first example, starting with an upper left corner move, using the magic square shown, produce: (We will skip the other three corners for now)

1	2	3	4	5	6
X1	O1	X2	O2	X3	O3
2	1	456	987	564
2	X
2	3	456	987	864
2	4	8	5	6
2	5	The only safe move
2	6	48	95	84   35|39
2	7	45	98	58|49
2	8	46	97	64   57|59
2	9	56	87	67|58

Example: (For the bolded line)
1. X1 = upper left corner = 2.
2. O1 = opposite corner = 8.
3. X2 = adjacent corners either 4 or 6, lets pick 6.
4. O2 = 7 to block. If X2 had = 4 then O2 must be 9 to block.
5. X3 = remaining corner, Across(X2) or 4, which produces a fork.
6. O3 = must block with either 5 or 9.
7. X4 = Wins

With the first move X being a corner, any of the first O edge moves have one of the options being X2 = 5. So to simplify this example, we’ll use X2 selecting the center (5):

X2 =
If O1 = 5
then Center-move
else if odd(O1)				// O selected edge
     then X2 =  5			// X = center
     else if O1 = Across( X1)
          then X2 = Cn(X1) >
          else X2 = Across(X1)

O2 =					// for everything except O1 = 5
if X2 = 5				// O1 = odd(O1) = edge
then O2 = 10 - X1			// to block
else O2 = 15 - X1 - X2			// to block

X3 =
If X2 = 5				// if O1 = edge, test if need to block
then if X1 = ((O1 + O1) mod 10) or = 10 - X1 = ((O1 + O1) mod 10)
     then X3 = Cp			// yes, block
     else X3 = Cn			// no
else if O2 = Across( X1)
     then X3 = Across(O2)
     else X3 = Across(X2)

If X2 = 5				// we now have a fork
then O3 must be = (10 - X3) OR = (15 - X3 - X1)
else if O2 = Across(X1)
     then O3 must be = En OR = Ep
     else O3 must be = (15 - X2 - X1) or = (15 - X3 - X1)

X4 selects the other side of the fork and wins.

Center-move : If O1 move is to the center (5) we will have a tie.
X2 = Across(X1)				// was Cn but this way code is simpler
O2 must = edge OR corner		// four positions to chose from
X3 must be = Across(O2)			// to block
If even(O2)
then O3 must = (15 - X1 - X3) OR = (15 - X2 - X3)
else  O3 must be to a corner to block

if even(O2)
then X4 = other side of fork, Wins
else  X4 = Across(O3)

O3 must block

X5 = Across(O3) to block, Tie.

Since the center first keeps all other moves around the perimeter, with fewer options to win, the programming becomes simpler. However if the next move selected is always the next corner, the game seems rather predictable. To introduce the appearance of a little randomness, the formula abs(10 -2*X) is used rather than Cn. This way half the time Cn will be used, and the other half will be Cp. For this example, we will have the computer go first.

The computer moves first to center, X1 = 5.
Human goes to O1, random(1-4,6-9)
If (O1 = even) then a corner was selected
else an edge was selected.     // where O will lose on X4
Computer selects X2 where X2 = abs(10-2*O1)   // Example: if O1 = 6 then X2 = 2 , *2 forces a corner
Human must select O2 where O2 = Across(X2), or lose.

Computer selects X3 where
if odd(O1)   // O first move was an edge
then X3 = Nc(O2)
else X3 = 15 – O2 – O1

Human selects O3 where if odd(O1) then selection is a fork.
if odd(O1)
then O3 must = (15 – X2 – X3) or = Across(X3)
else O3 = Across(X3)

if odd(O1)
then computer wins, with other side of fork. Game ends
else X4 = 15 – Across(O1) – O2

If still playing, Human must select O4 = 10 – X4

Computer selects remaining corner location to tie

The programming is much more straight forward if you can pick a move that forces the next player to select a particular position. With that thought and since this explanation is running a little long, I will leave the edge as the first move for the reader to work out.

  • Theloop
  • The BPDS newsletter