You can make an interesting AI by implementing minimax search and assigning +1000 to winning, -1000 to losing and a random number R (with abs( R ) < 1000) for draws. The program will play optimally (never lose, win if it can), and it will also play in ways that reduce the options of the opponent, most of the time.
So you'd enumerate the open cells, then assign each one a score based on how valuable a play there would be, considering wins, then blocks, then moves that would lead toward wins, right? (I've never implemented a minimax.) That would be easily extensible to larger board sizes too.
Oi, don't give away my secret move.