Jump to content

  • Log In with Google      Sign In   
  • Create Account


Generate moves in Gomoku


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 05 September 2013 - 08:28 AM

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).



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 11877

Like
0Likes
Like

Posted 05 September 2013 - 04:54 PM

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.

#3 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 05 September 2013 - 06:05 PM

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


Edited by patishi, 05 September 2013 - 06:05 PM.


#4 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 06 September 2013 - 01:49 PM

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;

 

            while(currentDepth <= MAX_DEPTH){
                if(currentDepth == 1){   //In the first iteration I set alpha and beta to be -INF, +INF
                    alpha = -1000001;
                    beta = 1000001;
                    b = chooseMove(currentDepth,alpha,beta,TRUE);
                   currentDepth++;
                }
                else{   //If Depth > 1, I take the previews iteration's evaluation and set the new window.  (WINDOW_SIZE is set to 50 right now..but i am experimanting)
                    alpha = b.score-WINDOW_SIZE;
                    beta = b.score+WINDOW_SIZE;
                    b = chooseMove(currentDepth,alpha,beta,TRUE);
                   
                    if(b.score <= alpha || b.score >= beta){ // If the score returned is outside of the window, set alpha and beta back to original values and search again
                        alpha = -1000001;
                        beta = 1000001;
                        b = chooseMove(currentDepth,alpha,beta,TRUE);
                       currentDepth++;
                    }
                    else{
                        currentDepth++;
                    }
                }
            }

Edited by patishi, 07 September 2013 - 07:00 PM.


#5 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 08 September 2013 - 09:30 PM

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...



#6 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 11 September 2013 - 10:14 PM

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).  

 

int isValuableSquare(int square){
    if(board[square] != 0){       //  0 is an empty square,  1 for computer player and -1 for human opponent. 
        return 0;                        // if square != 0 that means that it is not playable so i return 0;
    }
    else{
        int point;
        point = square;
        //check left
       while(!isBorder(point,LEFT) && point > square-2){
            point--;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check right
        while(!isBorder(point,RIGHT) && point < square+2){
            point++;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check top
       while(!isBorder(point,TOP) && point > square-30){
            point-=15;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check bottom
        while(!isBorder(point,BOTTOM) && point < square+30){
            point+=15;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check up left
        while(!isBorder(point,TOP) && !isBorder(point,LEFT) && point > square-32){
            point-=16;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check up right
       while(!isBorder(point,TOP) && !isBorder(point,RIGHT) && point > square-28){
            point-=14;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check down right
       while(!isBorder(point,BOTTOM) && !isBorder(point,RIGHT) && point < square+32){
            point+=16;
            if(board[point] != 0){
                return 1;
            }
        }
 
        point = square;
        //check down left
        while(!isBorder(point,BOTTOM) && !isBorder(point,LEFT) && point < square+28){
            point+=14;
            if(board[point] != 0){
                return 1;
            }
        }
 
        return 0;
    }
}
 
 
 I have another function that tells me if a certain square is a border square.  this is the isBorder()  function:  it takes the square and an  enum Direction {TOP,BOTTOM,LEFT,RIGHT}  as parameters.
 
int isBorder(int square,Direction direction){
    switch(direction){
        case TOP:
            return square/15 == 0;
        case BOTTOM:
            return square/15 == 14;
        case LEFT:
            return square%15 == 0;
        case RIGHT:
            return square%15 == 14;
    }
}
 
I hope that this code is not too messy..I would like to get better suggestions and corrections for this method.  thx!
 

Edited by patishi, 11 September 2013 - 10:15 PM.


#7 Álvaro   Crossbones+   -  Reputation: 11877

Like
0Likes
Like

Posted 12 September 2013 - 03:53 AM

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
}


Edited by Álvaro, 13 September 2013 - 06:54 AM.


#8 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 12 September 2013 - 03:41 PM

Thank you very much,  great ideas!



#9 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 12 September 2013 - 08:39 PM

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


Edited by patishi, 12 September 2013 - 09:25 PM.


#10 Álvaro   Crossbones+   -  Reputation: 11877

Like
0Likes
Like

Posted 13 September 2013 - 03:25 AM

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

#11 patishi   Members   -  Reputation: 211

Like
0Likes
Like

Posted 13 September 2013 - 04:35 AM

Oh..that's ok :) just wanted to make sure i am not missing something.   Thx a lot !






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS