This game is special in that it allows the user to specify the height and the width of the board, and then the number of marks in a row that make up a win. The Web version also allows the user to specify whether the computer or the user goes first, and allows the user to pick his mark, X or O. A simple 'undo' facility is provided by pressing the 'back' button on our web browser when playing via the web interface.
The lower limit of the board size (3) was chaosen beacuse the game is not much fun at anything smaller. At 2 or 1, the first player wins. 10 was chosen as the upper limit because at high numbers, it gets hard to play. The board limit can be changed simply by changing the MAXSIZE define statement at the beginning of the the code.
To determine the computer's move, I used a 2 level minimax search. The computer first builds a list for possible moves, then lists the moves the user can make after it has made its move. It finds the maximum board value for each case, assuming that is the move the user will take. It then makes the move that will give the smallest maximum for the user.
All this calculation is rather expensive. In fact, it takes n^6 time every time it is used. Therefore, I added some heuristics to make it quicker and smarter. First, it looks to see if there is a move it can make that will result in an immediate win. If it finds one, it makes it. If not, it looks to find a move that will block a win for the user. It then looks if the center cell is available. If no case is found, it uses the minimax.
Boards are valued exponentially. Right now, the factor is set to 5. For example, if a row is found to contain 1 mark for the user, it will be valued as 5. A row with 2 will be 25 and so on.
The command line interface also limits the value of the number needed in a row to win. The web interface does not provide this limitation, but if a size is set to anything greater than the greatest X-Y dimension, the game will always tie.
I learned a great deal about minimax searching while working on this program and also a lot about programming cgi-bin compliant programs. Thanks to Dave Maher for helping out with the stickier parts of the web interface.
In the future, I might implement a prettier interface (possilbly use HTML tables) and search down further using minimax. There are several other Tic-Tac-Toe games listed at Yahoo, but of course, mine is the coolest. It uses the POST form method, and is greatly customizable.