# Tac-Tac-Toe

This version of Tic-Tac-Toe is different than other computerized versions you might have seen, as it is handled entirely through hyperlinking to HTML pages, and does not require any computer processing to choose a response to your move. By clicking a square, you are merely asking the WWW page to display a different (previously written) page, just as clicking a link works everywhere else on the Web. So, in a very real sense, you are playing against yourself.

The trick is that on this WWW site there is a collection HTML pages, one for every possible board position in every possible game! Or, it be exactly, every possible board possible in every possible game played against a computer. As we'll see, that facet makes all the difference.

But first, let's consider how many different possible Tic-Tac-Toe games there are. The obvious approach would be to say that the "X" player can make any of 9 moves to open, and then "O" can move to any of 8 squares to respond. Hence, there could be 72 (9*8) possible boards with one "X" and one "O". Continuing this, "X" can choose any of the 7 remaining spots for his next move, and "O" has 6 options for his next response. So, we now have 3024 (9*8*7*6) possible boards with two Xs and two Os. If we then carry this to the end of the game, we find that there are 362,880 (9! or 9*8*7*6*5*4*3*2*1) different complete games.

That seems to be any an awful high number for such a simple game, and as it turns out, it is. Let's now consider this a different way. There are 9 positions on a Tic-Tac-Toe board, and each can be either an X, an O, or open. So, there can only be 19,683 (39 or 3*3*3*3*3*3*3*3*3) different board images. And many of those are impossible to achieve in a normal Tic-Tac-Toe game, such as one with all 9 squares filled with Xs. In fact, only a very small subset of those 19,683 could be part of an actual game. This number is compatible with the total we found before, because many of those 362,880 different game paths will converge to the same board image. But still, the possibility of up to 19,000 HTML pages would make this project impractical. I needed to know there was a definite, manageable number of pages required.

This bring us to one of my first thoughts about computer-based Tic-Tac-Toe games. They always seemed to me to be wasting a lot of effort. Given the same input, a program will come up with the same answer. So, if the human player choose the upper right corner as it's first move, a normal Tic-Tac-Toe program would grind for moment, evaluating each of it's possible moves, and than always choose the same "best" one. Hence, while there may be 72 possible boards with one X and one O, only 9 will ever be needed by this game. In the chess world, this idea has been known for years, and codified as the "Opening Book" where the "best" response to each possible opening move is listed. The simplicity of Tic-Tac-Toe allows the concept to be extended to the entire game.

So, instead of 9*8 boards with one X and one O, we have only 9. Likewise, instead of 3024 (9*8*7*6) boards with two Xs and two Os, we only need 63 (9*7). Continuing, every possible game can therefore be represented by only 9*7*5*3*1 boards. That comes out to only 945 pages needed, and as we've already seen, many of those will converge.

That reduced the problem to writing a program which would play every game for the human player, deduce a response for each move, and generate the set of HTML pages needed, skipping duplicates.

Now, when you click on a square, you are merely asking that a new (but predefined) page be displayed. That page happens to have an additional X and O on it, but clicking on that square on that page will always call up the same page. The choice of which page is completely up to you, hence you are playing against yourself.

The final total: 293 separate HTML pages, made of 139 boards in the middle of a game, 140 boards with O winning (you losing), 2 with X (you) winning, and 12 ties.

If this game has an impressive Win/Lose record, remember that it has to play every game, and can't assume that you won't make a lot of stupid moves. The number that I find fascinating is that there are only 12 ties, despite the fact that's how most games end. And, yes, you can beat it two different ways (One is actually a mirror image of the other). One hint: for your second move, you must do something illogical.

Another aspect you may have noticed (if you were using Microsoft's Internet Explorer), is that all the pages for the game are displayed in a "floating frame" in the center of a different page, with the text around it. This allowed me to keep each of the individual board HTML pages very small, between 500 and 800 bytes each. This serves the dual purpose of having the next move load and display quickly, while keeping the total size of all the pages down. This is important, as you'll recall, this requires nearly 300 pages, and this website was first on CompuServe, where, like most Internet Presence Providers, they enforce total space limitations. Nevertheless, as it is, this entire Website will still fit on a single 3½" floppy.

The C++ code to play all the games and generate the HTML pages is available here. It was written as a Win32 Console application using Visual C++ 5.0, but should be portable to any C++ which is following the draft ANSI/ISO Standard. (It does use the standard string & STL classes). On a Pentium 133, it requires about 20 seconds to play every game and generate every HTML page! Tictacto.zip (8k).

If you deduce a better playing strategy for it, please let me know.