LMR algorithm

[Aaron Becker]

I assume check_legal returns true if the move is legal, false otherwise. Then the "if (!check_move(...)) continue;" says to skip the search and just pick the next move if the current move is not legal. It's equivalent to "if (check_move(...) == FALSE) continue;". I would advise you to work on getting LMR working on interior nodes, and not worry about the root until after you have the basic implementation working the way you want.

[outAtime]

cool idea. ok, here goes nothing!

[outAtime]

Won't compile...undefined reference to '_check'. I guess I'll try removing the ! and maybe adding == FALSE or somthing...

[outAtime]

Never Mind. Was a small bug somewhere else...gonna try again with your !check_legal idea.

[outAtime]

Well, I tested that, but the engine didn't make any moves...I wonder what was wrong.

[Aaron Becker]

Ok, I've gotten myself too deep into this to walk away. The following code actually works in faile. I've tried it, and while I have no idea what effect it has on strength, it compiles correctly and moves as expected. I changed the LMR condition somewhat just to make something that would compile for me.

Code: Select all

  int msearch = 0;
  /* ... */
  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);

    /* go deeper if it's a legal move: */
    legal_move = FALSE;
    ply++;
    if (check_legal (&moves[0], i)) {
        nodes++; 
        msearch++; 

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

    /* return if we've run out of time: */
    /* ... */

[outAtime]

I got it to work just now too, although in a slightly different fashion:

Code: Select all

int msearch = 0;
  /* 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 (check_legal (&moves[0], i) && msearch == 1) {
            nodes++;
            score = -search (-beta, -alpha, depth-1+extensions, TRUE);
			msearch++;
			no_moves = FALSE;
            legal_move = TRUE;
		}  
				
	     else {
		     
	 	    /* Late Move Reductions */
            if (check_legal (&moves[0], i) && msearch >= FDMoves && depth >= 4 && 
			    moves[i].from == 0 && !in_check() && !evade && !extensions)  {
       		    
			nodes++;
		    score = -search (-alpha-1, -alpha, depth-2, TRUE);
			msearch++;
		    no_moves = FALSE;
            legal_move = TRUE;
		    
         	} 	
   			          
			
	     else if (check_legal (&moves[0], i));
		         score = alpha+1;
						
		        /* PVS */	
	             if (check_legal (&moves[0], i) && score > alpha) {  
                 nodes++;			
	             score = -search(-alpha-1, -alpha, depth-1+extensions, TRUE);
				 msearch++;
		         no_moves = FALSE;
                 legal_move = TRUE;
							
                if (check_legal (&moves[0], i) && score > alpha && score < beta) {
			     nodes++;
                 score = -search(-beta, -alpha, depth-1+extensions, TRUE);
				 msearch++;
		         no_moves = FALSE;
                 legal_move = TRUE;
                } 		 
	  	    } 			 		  	  
     
    }
	   
				   		
		ply--;
        unmake (&moves[0], i);
        ep_square = ep_temp;
        cur_pos = temp_hash;  	

[outAtime]

I wonder if in your version, if the move is illegal it might get a value of alpha +1?...or maybe even get searched...are you getting any illegal move bugs? Id rather not check legality on every line, maybe yours works fine, which means it looks cleaner.

[Aaron Becker]

In the code I posted, the alpha+1 bit, and all the other searching code, is inside the "if (check_legal...)" loop. So I'm not sure where you're getting the idea that illegal moves will get a score of alpha+1, or get searched.

[outAtime]

How is your version doing .vs Faile without LMR?