What would be a good AI strategy to play Gomoku?

The traditional and rather effective strategy for writing AI for such games is the typical tree search strategy. That is, each board state forms a node in a graph, and a directed edge is placed between each node and states that can be resulted by a single move. In this way a tree is built with the root board being an empty node. Then, traverse the tree in some clever way to find what looks like a 'good' state. A 'good' state is usually measured by an evaluation function that uses some clever heuristics. Obviously you don't want to visit all the nodes in the tree -- that would be a lot of work! You just want something clever.

You can add in a pre-computed early game and end-game to speed up those scenarios and then rely on a well-optimized tree-traversal heuristic for the mid game.

The actual name of such tree traversal algorithms is the "Minimax" algorithm. Look for it on Wikipedia and you'll see a lot of rather decent material. There's some ways of boosting the efficiency of the algorithm, the most notable of which alpha-beta pruning, so be sure you take a look at that. You may want to take a look at connect-four heuristics and decide how you can apply them to your game. For example, a likely good heuristic for evaluation of board states would be to count the number of continuable 2-runs, 3-runs, and 4-runs and weight them into the score. (e.g. each 2-run would be worth 1 point, each 3 run would be worth 10 points, and each 4-run would be worth 1000 points)

Another optimization strategy is to develop a heuristic that prioritizes where the minimax algorithm should search more -- usually by estimating some sort of certainty of the board evaluation function.

With this strategy you should be able to get not-so-stupid AI in the same amount of time. However, really, really good AI takes a lot of effort to build, even in these sorts of "simple" games, and it still may take upwards of 10 seconds or more to get smart moves out of the way. On the other hand, there's some clever programming tricks such as pre-computing traversals through the tree while the human opponent is busy thinking. Hey, humans get to think while the computer does. Fair is fair!

For gomoku, winning strategy has been already found. See this paper: L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens, 1993. Go-Moku and Threat-Space Search. It helped me a lot when I was writting my own program. This way you'll be able to write program which is very good in attacking the opponent and finding winning combinations.