What would be a good AI strategy to play Gomoku?

I'm writing a game that's a variant of Gomoku. Basically a tic tac toe on a huge board.

Wondering if anyone knows a good AI strategy for the game. My current implementation is very stupid and takes a long time (O(n^3), approx 1-2 second to make a move):

-(void) moveAI {
    //check if the enemy is trying to make a line horizontally, vertically, or diagonally
    //O(n^3 * 3)
    [self checkEnemies];

    //check if we can make a line horizontally, vertically, or diagonally
    //O(n^3 * 3)
    [self checkIfWeCanMakeALine];

    //otherwise just put the piece randomly
    [self put randomly];
}

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.