Ponder in Late Move Reductions

[outAtime]

Hi all. Ive been trying to add some LMR function to "Faile 1.4.4" after finally getting it to ponder (yaa!). Im having a hard go of it though, because although I think Ive got the basics down, something is definitely not working. It compiles fine, no errors or warnings, but the code just isn't working. I've already spent about 35 hours on this and any help or direction would be great! The engine starts and will play the book but once it has to find a move on its own it does nothing. On occasion I get a stack overflow file in the .exe directory, and I did have one version which made some moves on its own, but the eval was totally out of whack - stuck on +314.00 or somthing nutty. Here's the code bit and just so you know, Ive deleted the reduction rules e.g. if its a capture move or in_check() or whatever just because I was trying to see if that was an issue.

Code: Select all

  /* check to see if we can get a quick cutoff from our null move: */
      if (null_score >= beta)
	return beta;
      
      if (null_score < -INF+10*maxdepth)
	extensions++;
    }
  }

  /* generate and order moves: */
  gen (&moves[0], &num_moves);
  order_moves (&moves[0], &move_ordering[0], num_moves, &h_move);

  /* loop through the moves at the current node: */
  while (remove_one (&i, &move_ordering[0], num_moves)) {

     make (&moves[0], i);
     assert (cur_pos.x1 == compute_hash ().x1 &&
	    cur_pos.x2 == compute_hash ().x2);	
     ply++;
     legal_move = FALSE;
	 
	if (moves_searched == 0) {
    
     /* go deeper if it's a legal move: */
        if (check_legal (&moves[0], i)) {
	      nodes++;
          score = -search (-beta, -alpha, depth-1+extensions, TRUE);  
		  
		  
		 /* Late Move Reductions */
		} 
	    else
		{		
	        if (moves_searched >= FullDepthMoves && depth >= ReductionLimit) {
				score = -search (-alpha-1, -alpha, depth-2, TRUE);
	        }  
            else score = alpha+1; 
			
		    /* PVS */	
	        if (score > alpha) { 
	         score = -search(-alpha-1, -alpha, depth-1+extensions, TRUE);
               if (score > alpha && score < beta)
                 score = -search(-beta, -alpha, depth-1+extensions, TRUE);
            }
	    }
	}	
		
		else {
		    if (check_legal (&moves[0], i)) {
	            nodes++;
            score = -search (-beta, -alpha, depth-1+extensions, TRUE);  
			
			 no_moves = FALSE;
            legal_move = TRUE;
		  
	  		}
		}
	}
	 	moves_searched++;
        ply--;
        unmake (&moves[0], i);
        ep_square = ep_temp;
        cur_pos = temp_hash;
      
	   
    
	
    /* return if we've run out of time: */
    if (time_exit) return 0;

	/* check our current score vs. alpha: */
    if (score > alpha && legal_move) {
      
      /* update the history heuristic since we have a cutoff: */
       history_h[moves[i].from][moves[i].target] += depth;

      /* try for an early cutoff: */
      if (score >= beta) {
	u_killers (moves[i], score);
	store_hash (i_alpha, depth, score, l_bound, moves[i]);
	return beta;
      }
      alpha = score;
	  
      /* update the pv: */
      pv[ply][ply] = moves[i];
      for (j = ply+1; j < pv_length[ply+1]; j++)
	pv[ply][j] = pv[ply+1][j];
      pv_length[ply] = pv_length[ply+1];
    } 
	
  

  /* check for mate / stalemate: */
  if (no_moves) {
    if (in_check ()) {
      alpha = -INF+ply;
    }
    else {
      alpha = 0;
    }
  }
  else {
    /* check the 50 move rule if no mate situation is on the board: */
    if (fifty > 100) {
      return 0;
    }
  }

  /* store our hash info: */
  if (alpha > i_alpha)
    store_hash (i_alpha, depth, alpha, exact, pv[ply][ply]);
  else
    store_hash (i_alpha, depth, alpha, u_bound, dummy);

  return alpha;

}


move_s search_root (int alpha, int beta, int depth) {

  /* search the root node using alpha-beta with negamax search */

[Aaron Becker]

The structure of the code you posted is all messed up. Here's my pseudocode interpretation of what you posted:

Code: Select all

if this is the first move:
    if the move is legal:
        normal search
    otherwise:
        try reduced search
otherwise:
    if the move is legal:
        normal search

It should be clear why this doesn't work--you're applying LMR to illegal moves and only using normal search for legal moves. Here's the relevant snippet of the code you posted, with the indentation corrected and some lines trimmed for clarity:

Code: Select all

/* loop through the moves at the current node: */ 
while (remove_one (&i, &move_ordering[0], num_moves)) { 
    make (&moves[0], i); 
    legal_move = FALSE; 
    if (moves_searched == 0) { 
        /* go deeper if it's a legal move: */ 
        if (check_legal (&moves[0], i)) { 
            nodes++; 
            score = -search (-beta, -alpha, depth-1+extensions, TRUE);  
            /* Late Move Reductions */ 
        } else {       
            if (moves_searched >= FullDepthMoves && depth >= ReductionLimit) { 
                score = -search (-alpha-1, -alpha, depth-2, TRUE); 
            }  
            else score = alpha+1; 

            /* PVS */    
            if (score > alpha) { 
                score = -search(-alpha-1, -alpha, depth-1+extensions, TRUE); 
                if (score > alpha && score < beta) 
                    score = -search(-beta, -alpha, depth-1+extensions, TRUE); 
            } 
        } 
    } else { 
        if (check_legal (&moves[0], i)) { 
            nodes++; 
            score = -search (-beta, -alpha, depth-1+extensions, TRUE);  
        } 
    } 
}

edit: I'll add that mistakes like this are a lot easier to find if you use an editor that will handle indentation for you. I suspect you would have found the problem yourself a lot more easily if the code was indented properly to show its structure.

[outAtime]

Thankyou!! Thats what I was wondering, but I wasn't sure if I needed to check legality on each search. Hopefully I can get this to go now. Many thanks.

[outAtime]

Well, Ive been working away to the bone at this, but something still isn't right here with this LMR attempt. It just dosen't want to fly. No moves are being made at all once out of book.

Code: Select all

 moves_searched = 0;
  num_moves = 0;
  no_moves = TRUE;
  /* generate and order moves: */
  gen (&moves[0], &num_moves);
  order_moves (&moves[0], &move_ordering[0], num_moves, &h_move);

  /* loop through the moves at the current node: */
  while (remove_one (&i, &move_ordering[0], num_moves, alpha < beta)) {
     make (&moves[0], i);
     assert (cur_pos.x1 == compute_hash ().x1 &&
	 cur_pos.x2 == compute_hash ().x2);	
     ply++;
     legal_move = FALSE; 
	 
	 if (moves_searched > 0) {
        
	 	   /* Late Move Reductions */
            if (check_legal (&moves[0], i)) {
			if (moves_searched >= FullDepthMoves && depth >= ReductionLimit) {
	
				score = -search (-alpha-1, -alpha, depth-2, TRUE);
				no_moves = FALSE;
                legal_move = TRUE;
	        }  
            else score = alpha+1; 
			
		    /* PVS */	
			if (check_legal (&moves[0], i)) {
	        if (score > alpha) { 	
               nodes++;			
	           score = -search(-alpha-1, -alpha, depth-1+extensions, TRUE);
			   no_moves = FALSE;
               legal_move = TRUE;
			    }
               if (score > alpha && score < beta);
			      nodes++;
                  score = -search(-beta, -alpha, depth-1+extensions, TRUE);
                  no_moves = FALSE;
                  legal_move = TRUE;			  
				} 
            }		
	    }else{ 
		    if (check_legal (&moves[0], i)) {
	        nodes++;
            score = -search (-beta, -alpha, depth-1+extensions, TRUE);  
			no_moves = FALSE;
            legal_move = TRUE;		  
	  		}
		}
	} 
        	moves_searched++;
            ply--;
            unmake (&moves[0], i);
            ep_square = ep_temp;
            cur_pos = temp_hash;  			
    	    
        
			
    /* return if we've run out of time: */
    if (time_exit) return 0;

	/* check our current score vs. alpha: */
    if (score > alpha && legal_move) {

Any ideas? Thanks!

[Aaron Becker]

You're not calling unmake() inside your move loop. You're calling make() on each move in the list in turn, then calling unmake() once at the end. You also don't increment moves_searched until after all the moves have been searched, so it doesn't have the effect you intend. You also check move legality twice when you try LMR.

It seems like you've been cutting and pasting code to move things around, but it's not ending up in the right place, and you end up with control flow that doesn't make any sense. I recommend compiling with debugging information, then stepping through your code in a debugger to make sure it's actually doing what you want.

[outAtime]

Thankyou very much! I really appreciate your help! I'll try fixing those problems and see what happens next. Hopefully this time it will run
I really appreciate your help and experience, Im just learning so hopefully someday I can help others too. Cheers! Glad you got back to me because I was just beginning the process of changing the code completely, heh.

[Aaron Becker]

No problem. A lot of the time when I try to make big changes like this, the results are totally broken. I think this is just the nature of making significant changes to complicated code. Often, I'm tempted to just start changing things and hope for the best or to unroll all my changes and start again from scratch. This is, in my experience, almost always a bad idea. The thing to do is sit down and walk through your code very carefully without making new changes until you understand what it's doing. Without doing this, the odds of fixing the problem properly are very bad. Stepping through the code line by line and figuring out why it's not working the way you expect is a slow, tedious job, but it will eventually pay off. Good luck!