This is a reasonably simple program for playing an "n in a row" game using a depth first search to discover winning and losing moves. In these games players take turns placing a token on the board (usually one player places "x" tokens and the other places "o" tokens). Tokens are never removed from the board and the first player to complete a chain of sufficient length horizontally, vertically, or diagonally wins. These games are characterized by board dimension and the length of the chain required to win, and these characteristics determine the nature of the game. For example, classic tick-tack-toe, with a 3x3 board and three in a row to win is a futile game. More information about these games is available from this page. You can download my source code here.
Using my program I've verified that on a 5x5 board, with four in a row required to win, there is at most (up to rotation of the board) one correct reply to an initial move to the center square. I've seen references to a 2001 paper by C.Y. Lee, which proves that four in a row on a 5x5 board is futile, but I haven't located the original paper. To verify that all but one reply is a loss for the second player, I reduced the number of possibilities by taking advantage of the symmetries of the board after an initial move to the center. In the diagram below replies are labelled "1" through "5" where replies bearing the same label are equivalent.
1 2 3 2 1
2 4 5 4 2
3 5 x 5 3
2 4 5 4 2
1 2 3 2 1
Replies 1, 3, and 5 result in a win for x, 7-ply later. Reply 2 results in a win for x, 9-ply later, and that leaves move 4 as the only possible correct reply. It took my 2GHz Athlon a little less than three days to test reply 2, and an equally long (9-ply) search for the result of reply 4 turned up nothing. The running time of the N-ply search with M available moves remaining on the board grows like M!/(M-N)!, so since the 9-ply search with 23 moves remaining took about three days, the 23 ply search should take about 7 hundred million years.
The task of writing an artificial intelligence for an n in a row game with a large board is made quite difficult by the absence of tactics. Whereas in a game like Checkers a board can be scored for one player or the other according to number of pieces remaining, or number of squares attacked, there is no obviously correct heuristic for an n in a row game.