The Compleat

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 (3 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 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 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, |

All rights reserved.

Revised: December 27, 2006.