## Logicquasifractals

A Fractal Guide to Tic-Tac-Toe

Ian Stewart finds a familiar shape in unexpected places

I am being haunted by a fractal. In a recent column [see "Sierpinski's Ubiquitous Gasket," August 1999] I described several occurrences of the fractal known as Sierpinski's gasket, which can be obtained from a triangle by successively deleting an inverted triangle half its size. Ever since, readers have been alerting me to new sightings of this versatile figure. Its latest incarnation is in the field of mathematical logic. Patrick Grim and Paul St. Denis of the State University of New York at Stony Brook sent me a paper entitled "Fractal Images of Formal Systems" (Journal of Philosophical Logic, Vol. 26, No. 2, pages 181-222; 1997).

A fractal is a shape that can be divided into parts that are smaller versions of the whole. A genuine fractal such as Sierpin-ski's gasket has detailed structure on all scales of magnification: any piece of it, no matter how small, will resemble the whole. A quasi-fractal, in contrast, is an approximation of a true fractal—it has detailed structure over a large but finite range of magnification scales. The patterns of a quasi-fractal do not continue to infinitely fine scales, but because the human eye cannot distinguish such small details, quasi-fractals look convincingly fractal. One of the accomplishments of Grim and St. Denis was to devise a quasi-fractal diagram that represents all the possible games of tic-tac-toe.

As everyone knows, tic-tac-toe is played on a 3-by-3 grid of squares by two players, X and O. Each player takes turns marking squares, and the first to get three in a row (across, down or diagonally) wins. Traditionally, X goes first, and optimal play always results in a draw. But exactly how many games are possible? At X's first turn, he chooses among nine squares; then O chooses among eight, and so on. So the total number of games is 9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880.

Here's how Grim and St. Denis built their quasi-fractal. Start with a big 3-by-3 square grid, and divide each square into a 3-by-3 subgrid [see illustration on opposite page]. Player X has nine opening moves, corresponding to the positions in the larger grid. One possible move is that X chooses to mark the top left corner. Find the 3-by-3 subgrid in the top left corner of the big grid and draw an X in the sub-grid's top left corner. The subgrid is now a picture of the game after this opening move. Another possibility is that X opens with the bottom center square; to represent this move, find the subgrid in the bottom center square of the big grid and draw an X in the subgrid's bottom center square. In this way, each of the nine sub-grids receives an X in a different subsquare.

Now concentrate on the subgrid in the top left corner of the big grid. X's first move is already drawn in the top left corner; the other eight subsquares represent 