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

10 replies to this topic

### #1patishi  Members

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

### #2Álvaro  Members

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.

### #3patishi  Members

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.

### #4patishi  Members

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.

### #5patishi  Members

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

### #6patishi  Members

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  Members

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.

### #8patishi  Members

Posted 12 September 2013 - 03:41 PM

Thank you very much,  great ideas!

### #9patishi  Members

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  Members

Posted 13 September 2013 - 03:25 AM

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

### #11patishi  Members

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.