LMR algorithm

[outAtime]

Hi. Most of the programs I've seen use some type of *PLY in their LMR and NULL algorithms , however my program doesn't and I'm having difficulty getting it to think for the right side in LMR.

if my NULL move search looks like this, (where null_red = 2)

Code: Select all

 null_score = -search (-beta, -beta+1, depth-null_red-1, FALSE);

and my regular search looks like this:

Code: Select all

 score = -search (-beta, -alpha, depth-1+extensions, TRUE);

what should the LMR algorithm look like?

I was trying -search (-alpha-1, -alpha, depth-2, TRUE), but that seems to make it think for the wrong side. Thanks. [/code]

[Aaron Becker]

If it's thinking for the wrong side in LMR, you probably neglected to make a move at the current ply before calling the reduced search.

[outAtime]

this is so confusing. Ive been at this for over a week.

[outAtime]

What am I doing wrong here? Is it the algorithm? Something with make?

Code: Select all

 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 (check_legal (&moves[0], i)) {
	if (time_exit && no_moves)
	time_failure = TRUE;
	no_moves = FALSE;
	legal_move = TRUE;
	msearch++;
	}
  
	
	
            if (msearch == 1) {
            nodes++;

           root_score = search (-beta, -alpha, -depth-1+extensions);
                    		                        
		}  
				
	  else {
		     
	 /* Late Move Reductions */
         if (msearch >= FDMoves && depth >= 4 && moves[i].from == 0 && 
	    !in_check() && !evade && !extensions)  {
       		    
	 nodes++;
          root_score = -search (-alpha-1, -alpha, depth-2-1, TRUE);
		    
         	} 			
	  else root_score = alpha+1;
						
          /* PVS */	
	 if (root_score > alpha) {  
         nodes++;			
	 root_score = -search(-alpha-1, -alpha, depth-1+extensions, TRUE); 
				
							
          if &#40;root_score > alpha && root_score < beta&#41; &#123;
          nodes++;
          root_score = -search&#40;-beta, -alpha, depth1+extensions,TRUE&#41;;
				
                &#125; 		 
	  &#125; 			 		  	  
     
    &#125;
				   

    ply--;	
    unmake (&moves&#91;0&#93;, i&#41;;
    ep_square = ep_temp;
    cur_pos = temp_hash;
&#91;code/&#93;

[outAtime]

depth -2-1 was just a recent try, to get it to work.

[outAtime]

maybe I need to go back to a previous version where I checked legality on every line before calling serach(). maybe illegal moves are getting into the search somehow.... but it never makes the move, so its almost as though its pondering or something, but its not allowed to ponder on its own move so...

[outAtime]

I think I will change where I count moves searched, and also change how Im checking legality.

[Aaron Becker]

You have some pretty crazy stuff in there, such as searching by negating the depth. After taking a quick look at Faile's search, this is how I would add your LMR code to it. Take it with a massive grain of salt, since I'm not familiar with how the whole program works:

Code: Select all

int msearch = 0;
while (remove_one (&i, &move_ordering[0], num_moves)) {

    if (!check_legal(&moves[0], i)) continue;
    ply++;
    nodes++;
    msearch++;

    if (msearch == 1) { 
        score = -search (-beta, -alpha, depth-1+extensions, TRUE); 
    } else { 
        /* Late Move Reductions */ 
        if (msearch >= FDMoves && depth >= 4 && moves[i].from == 0 && 
                !in_check() && !evade && !extensions)  { 
            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 = -search(-beta, -alpha, depth-1+extensions,TRUE); 
            }        
        }                        
    }

    no_moves = FALSE;
    legal_move = TRUE;

    ply--;    
    unmake (&moves[0], i); 
    ep_square = ep_temp; 
    cur_pos = temp_hash; 

    // Check score against alpha, update pv, etc.
    // ...
}

[outAtime]

I like the continue; idea...saves checking legality on every line in the code...im just wondering where to try this, because I can put it in search, which includes the null move and quiesce, or in the search_root section, which actually calls search(). e.g. in search its: score = -search (-beta, -alpha, depth-1+extensions, TRUE); while in root_score its: root_score = -search (-beta, -alpha, depth-1+extensions, TRUE); .... Which is different than other programs where most search the root differently...with a different algorithm. think() calls search_root like this: temp_move = search_root (-INF, INF, i_depth);

So I guess I'll put it in search. And keep the search_root as a full window search without any reductions or PVS. Just seems odd to me, Sjeng free does PVS (no reductions) in root_and search. hmmm.

[outAtime]

why the ! in if (!check_legal(&moves[0], i)) continue; ?
I thought that means if the legal move isn't checked...or an illegal move
shouldn't it just be: if (check_legal(&moves[0], i)) continue; ?