This exercise consisted of creating a tic-tac-toe game for a website. The challenge was to develop a pure HTML version (no cgi, no Java) by simply having each possible board configuration stored as a web page, with links to the next position. But, would it work? How many pages?
There are nine choices for the first move, then 8 possible responses, then 7 replies, and 6 countermoves, and so on. This implies that potentially there are 9x8x7x6x5x4x3x2x1 = 362,880 board positions in the game of tic-tac-toe. Not all board positions are possible, of course. The game stops when somebody wins, usually with unfilled squares available. Consequently, the above result is an upper limit on the number of webpages necessary to create the game. Fortunately, the actual number required is much smaller.
PLAYER GOES SECOND
If the first move is already made (player goes second), that eliminates 9 choices for the first move. And since the computer will always respond the same way, the only real 'choices' are by the player. So the above result can be reduced to 8x6x4x2 = 384 board positions. This is still an upper limit. The actual number of pages required can only be found by playing through all possible games.
Example showing there are 96 boards starting from the center square.
A 'tic-tac-toe engine' (written in C) was developed to generate winning game moves. There are really only three distinct games, depending on whether the first move is in the center [5], in a corner [1,3,7,9], or on a side [2,4,6,8], as shown below.
1 2 3 4 5 6 7 8 9Analysis shows the number of legal board positions are:
PLAYER GOES FIRST
If the player goes first, there are 9 possible opening moves. Again, since the computer will always respond in the same way, the only real 'choices' are by the player. So the total becomes 9x7x5x3= 945 board postions. Because many of these games will play out to a full-board 'tie' position, this part of the game contains another 712 webpages.
--- YOU FIRST ---
Enjoy!