The board in gomoku is very large (15x15), and it takes a lot of time for the computer to think when analyzing the whole board. Even static ordering of the moves from the middle rows (let's say the inner 9x9 board than expanding out) is not much of the help.

what is the preferred way to generate the moves so that the space search will be minimized as much as possible, but at the same time, I don't want the engine to underestimate the opponent's threats in the sidelines of the board. Right now I am searching the whole board and even at depth 5 it is starting to take a long time (with killer moves).

My first thought is that moves that are far away from any pieces can be reduced one ply or two in a style similar to LMR in chess: Implement PVS search and use the reduced depth for moves far away from any pieces when you do the null-window search, then search with full depth if the null-window reduced-depth search indicates the move seems good.

If you need some pseudo-code I can write some for you.

Thank you for the response. I have zero experience with those techniques (PVS search, null window) except only read about them. I will take a closer look and re-read about them more deeply.. This time i guess i have no choice since transposition table and killer moves alone aren't gonna cut it.
A psuedo code will be nice, But I am afraid that i will not understand anything before i do a little read about the theory and general ideas

Another question, when implementing PVS search, does this come hand in hand with Iterative deepening?

Can i implement iterative deepening without time management? in that case,what should be the condition for the iterative deepening loop? should i just iterate until i reach a desired depth?

EDIT: I am trying to implement Iterative deepening with Aspirarion windows but I don't see any improvement. am i doing it right?

Right now, my code looks like this:

Best b; // The chooseMove() method returns a struct (typedef Best) holding the best move and the best score.

int MAX_DEPTH = 6;

int currentDepth = 1;

So right now I am trying another scheme for reducing the search space. only empty squares that are within two steps away for an existing mark (computer or opponent)

will be considered. I hope that it is not to dangerous though...

I wonder if any of you can suggest a better and faster way to do the "valuable square" checking routine that i do. what i do is, i pass through all the 225 squares on the board,and check if a certain square is "valuable" . a "valuable" square is a square that is no more than two steps away from an existing token on the board..computer's or opponent's. And it is also has to be empty.

I am using a single dimension array in size 225 for the board representation, and this is how it looks like:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 16 17...

and 13 more rows like this

My checkValuableSquare(int square) method is as follows: I simply pass thourgh all possible 8 directions away from the square, and if i stumble upon a player i return true (e.g 1).

You can get rid of all the verifications of whether a square is on a border by making your array slightly larger (say, 19 rows and 17 columns) and filling the entries outside the board with a special code (e.g., empty=0, black=1, white=2, outside=-1).

bool is_valuable_square(int square) {
  if (board[square] > 0)
    return false;
 
  for (int direction : {-Width-1, -Width, -Width+1, -1, +1, +Width-1, +Width, +Width+1}) { // if you are not using C++11, use an array instead
    if (board[square+direction] > 0 || board[square+2*direction] > 0)
      return true;
  }
 
  return false;
}

EDIT: Alternatively, if you are going to be calling this function a lot (as I suspect), you could keep a parallel array indicating the number of occupied neighbors in the relevant pattern, which will be updated whenever you make or undo a move. Again, you need to make the array large enough that you don't need to do anything special at the borders.

void make_move(int square, int color) {
  board[square] = color;
  
  for (int direction : {-Width-1, -Width, -Width+1, -1, +1, +Width-1, +Width, +Width+1}) {
    neighbor_count[square+direction]++;
    neighbor_count[square+2*direction]++;
  }
}

void undo_move(int square) {
  board[square] = 0;
  
  for (int direction : {-Width-1, -Width, -Width+1, -1, +1, +Width-1, +Width, +Width+1}) {
    neighbor_count[square+direction]--;
    neighbor_count[square+2*direction]--;
  }
}

bool is_valuable_square(int square) {
  return board[square] == 0 && neighbor_count[square] > 0; // Edited
}

Thank you very much, great ideas!

I don't understand something in the second option. let's say i played a move on the board, and than raised the relevant indexes in the neighbor_count array. shouldn't I mark squares that are already been played at? (e.g make them not valuable). right now, I just keep the counter in the neighbor_count array as it is for squres that were valuable in the past and are not anymore. when i pass through the neighbor_count array looking for playable squares, i don't want to play in a square that has already been played.

Or maybe I should check if board[square] == 0 also?

I hope i made myself clear

Yes, of course you want to check board[square]==0. Sorry about that.