// EXchess source code, (c) Daniel C. Homan  1997-2011
// Released under the GNU public license, see file license.txt

/* Search Functions */

#include <iostream>
#include <cstdio>
#include <fstream>
using namespace std;

#if DEBUG_SEARCH
 #include <string.h>
 #include <stdlib.h>
#endif

#include "define.h"
#include "chess.h"
#include "const.h"
#include "funct.h"
#include "hash.h"
#include "search.h"
#include "extern.h"

/*----------------------- Search function ---------------------*/
// Driver for the search process.  1st initialize important data
// structures, the do iterative deeping until time runs out.
move tree_search::search(position p, int time_limit, int T, game_rec *gr)
{
   char outstring[400], mstring[10];
   int g, done, pvi;
   int elapsed;
   position pv_pos;
   move nomove; nomove.t = NOMOVE;

   turn = T;
   root_wtm = p.wtm;
  
#if DEBUG_SEARCH
 search_outfile.open("search_debug.log");
#endif

  //------------------------------------------------------------------
  //  Log the current position in FEN format
  //------------------------------------------------------------------
  write_out("---------------------------------------------------------------\n");
  write_out("Starting search on position:\n");
  int lcount; square lsqr;
  for(int rank = 7; rank >= 0; rank--) {
    lcount = 0;
    for(int file = 0; file < 8; file++) {
      lsqr = p.sq[SQR(file,rank)];
      if(lsqr.type) {
        if(lcount) { 
 	 sprintf(outstring, "%i", lcount); 
 	 write_out(outstring); 
 	 lcount = 0; 
        }
        if(lsqr.side) {
 	 sprintf(outstring, "%c", name[lsqr.type]);
 	 write_out(outstring);
        } else { 
 	 sprintf(outstring, "%c", bname[lsqr.type]);
 	 write_out(outstring);
        }
      } else lcount ++;
    }
    if(lcount) { 
      sprintf(outstring, "%i", lcount); 
      write_out(outstring); 
      lcount = 0; 
    }
    if(rank) write_out("/");
  } 
  if(p.wtm) write_out(" w ");
  else write_out(" b ");
  if(p.castle&1) write_out("K");
  if(p.castle&2) write_out("Q");
  if(p.castle&4) write_out("k");
  if(p.castle&8) write_out("q");
  if(!p.castle)  write_out("-");
  if(p.ep) {
    sprintf(outstring, " %c%i", char(FILE(p.ep) + 97), (RANK(p.ep) + 1));
    write_out(outstring);
  } else write_out(" -");
  write_out("\n");


  //------------------------------------------------------------------
  //  Initialize variables and position for search 
  //------------------------------------------------------------------

  // Set start of search depth
  //  -- may be modified below as a result of successful
  //     pondering or play along the expected pv
  start_depth = 1;

  // setting counts to zero
  node_count = 0; eval_count = 0; interrupt_check_count = 0;
  phash_count = 0; hash_count = 0; hmove_count = 0; q_count = 0;
  null_cutoff = 0; extensions = 0; singular_extensions = 0; internal_iter = 0;
  egtb_probes = 0; egtb_hits = 0; fail_high = 0; first_fail_high = 0;

  // setup some search parameters - for old hash entries
  if(h_id > 100 || h_id < 0) h_id = 1;
  h_id++;

  // is this a pondering session, if so - make the move from the pv
  if(ponder) {
   if(gr->book && !pc[0][1].t) ponder_move = opening_book(p.hcode, p, gr);
   else ponder_move = pc[0][1];
   print_move(p, ponder_move, mstring);
   if(ponder_move.t) {
     if(!p.exec_move(ponder_move, 0)) { ponder_time = 0; return nomove; }
     root_wtm = p.wtm;
   } else { ponder_time = 0; return nomove; }
   if(!ALLEG && post) {
    cout << "Hint: " << mstring << "\n";
    cout.flush();
   }
   sprintf(outstring, "***** Ponder Move: %s *****\n", mstring);
   write_out(outstring);
   // add ponder move to position list
   gr->plist[T-1] = p.hcode;
   // set ponder time doubling
   ponder_time_double = 0;
  }

  //---------------------------------------------  
  // checking tablebases at root
  //---------------------------------------------
#if TABLEBASES
  if(p.pieces[0] + p.pieces[1]
      + p.plist[0][PAWN][0] + p.plist[1][PAWN][0] <= EGTB) {
   root_tb_score = probe_tb(&p, 0);
  } else root_tb_score = -1;
#else 
  root_tb_score = -1;
#endif  /* TABLEBASES */

  //-----------------------------  
  // checking book
  //-----------------------------  
  if(gr->book && !ponder) {
    bookm = opening_book(p.hcode, p, gr);
    if(bookm.t) {
     pc[0][0] = bookm; pc[0][1].t = 0;
     // output the book move to log or search screen
     print_move(p, bookm, mstring);
     sprintf(outstring, "Book Move Found: %s\n", mstring);
     write_out(outstring);
     cout.flush();
     gr->learn_positions[T-1].hcode = ZERO;
     return pc[0][0];
    } else {
     no_book++;
     if(no_book >= 3) gr->book = 0;
    }
  }

  //------------------------------------------------------------------
  //   React appropriately based on whether we pondered previously
  //------------------------------------------------------------------

  // if last search was a ponder and if user made expected move and
  // if ponder time is greater than limit, return best move
  if(last_ponder && ponder_time >= (time_limit<<ponder_time_double) &&
     p.last.t == ponder_move.t && pc[0][0].t) {
    // output move to log or search screen
    print_move(p, pc[0][0], mstring);
    sprintf(outstring, "Guessed Last Move! Returning: %s\n", mstring);
    write_out(outstring);
    cout.flush();
    // for learning we need to recorded that we predicted the last move
    if(T>2 && T<MAX_GAME_PLY-1) gr->predicted[T-3] = 1;  
    return pc[0][0];
  }

  // if last search was a ponder, user made the expected move, but we
  // didn't search deep enough, continue search
  if(last_ponder && p.last.t == ponder_move.t && pc[0][0].t) {
    start_depth = MAX(last_depth-1,1);
    h_id--; // reset hash id to mark entries as current
    write_out("Guessed last move, but searching deeper...\n");
    cout.flush();
    // set target time
    limit = (time_limit<<ponder_time_double) - ponder_time;
    // for learning we need to recorded that we predicted the last move
    if(T>2 && T<MAX_GAME_PLY-1) gr->predicted[T-3] = 1;  
  } 
  // else if we are in analysis mode or pondering we can keep  
  //   searching at the same depth if the user made the pv move.
  else if((analysis_mode && pc[0][0].t == p.last.t && pc[0][0].t) || ponder) {
    start_depth = MAX(last_depth-1, 1);
    pc[0][0].t = NOMOVE;
    limit = time_limit;
  }
  // else if we had no pondering but are still in the pv,
  //   we can make use of the results of the previous 
  //   search to speed things up...  but we must have a
  //   valid move to search first at this move, so pc[0][2] must
  //   have a move in it
  else if(pc[0][1].t == p.last.t && pc[0][1].t && !last_ponder) {
    if(pc[0][2].t) start_depth = MAX(last_depth-2, 1);
    pc[0][0].t = NOMOVE;
    limit = time_limit;
    // for learning we need to recorded that we predicted the last move
    if(T>2 && T<MAX_GAME_PLY-1) gr->predicted[T-3] = 1;  
  }
  // else just clear the first move in the pv
  //  and set the target time
  else {  
    pc[0][0].t = NOMOVE;     // clear first move in the pv
    limit = time_limit;      // set target time
    if(T>2) gr->predicted[T-3] = 0;  // last move wasn't predicted
  }

  //------------------------------------------------------------------
  //   Initialize search loop
  //------------------------------------------------------------------
 
  start_depth = 1;  // always force start_depth = 1 to test if this has been a problem
  
  // set the learn position information to zero unless
  // we have something to put in
  if(!tsuite && !analysis_mode && T < MAX_GAME_PLY-1 && T) {
   gr->learn_positions[T-1].hcode = ZERO;
  }

  last_ponder = 0;
  ponder_time = 0;
  max_limit = int(MIN(4.0*time_limit, gr->timeleft[p.wtm]/6.0));
  if(!gr->mttc && !xboard) {max_limit = int(gr->timeleft[p.wtm]);}
  max_limit = MIN(max_limit, max_search_time*100);
  if(!tsuite && !analysis_mode) {
   limit = MIN(max_limit, limit);
   if(gr->timeleft[p.wtm] < 1000) {
    start_depth = 1;
   }
  }
  start_time = GetTime();

  last_depth = 1;

  // initialize history table
  for(int i = 0; i < 64; i++)
   for(int j = 0; j < 64; j++) history[i][j] = 0;

  //------------------------------------------------------------------
  //   Log the search conditions
  //------------------------------------------------------------------   
  sprintf(outstring, "Target search time: %i, max %i, timeleft (%i %i)\n", 
	  time_limit, max_limit, int(gr->timeleft[0]), int(gr->timeleft[1])); 
  write_out(outstring);
  sprintf(outstring, "Starting depth: %i\n", start_depth); 
  write_out(outstring);

  //------------------------------------------------------------------
  //
  // Main search loop for iterative deeping
  //  - The iteration limit of 127 is set by hash depth storage limit
  //
  //------------------------------------------------------------------
  for(max_ply = start_depth; max_ply < MIN(127,max_search_depth+1); max_ply++)
  {
    n[0].pos = p;
    node_count++;

    max_depth = max_ply;

    if(max_ply != start_depth)
     { root_alpha = g_last-25; root_beta = g_last+25; }
    else
     { root_alpha = -MATE; root_beta = +MATE; }

    done = 2;

    while(1) {
     g = n[0].pvs(root_alpha, root_beta, (max_ply-1)*UNIT_DEPTH+INIT_EXT);
     if(g == -TIME_FLAG) break;
     if(g <= root_alpha) {
      if(done == 2) {
       root_beta = root_alpha+1; root_alpha = -MATE;
      } else if(done == 1) {
       root_beta = +MATE; root_alpha = -MATE;
      } else break;
      done--;
     } else if(g >= root_beta) {
      if(done == 2) {
       root_alpha = root_beta-1; root_beta = +MATE;
      } else if(done == 1) {
       root_beta = +MATE; root_alpha = -MATE;
      } else break;
      done--;
     } else break;
    }

	
    if(!pc[0][0].t && start_depth != 1) {
	 start_depth = 1;
	 max_ply = 0;
	 continue;
    } 
	

    // writing pv into hash table to be searched first

    pv_pos = p; pvi = 0;

    while(pc[0][pvi].t && g != -TIME_FLAG && pvi < MAXD) {
     put_move(pv_pos.hcode, pc[0][pvi].t);
     pv_pos.exec_move(pc[0][pvi], 0);
     if(pvi > 1 && !tsuite && !analysis_mode && T < 255) {
       gr->learn_positions[T-1] = pv_pos;
       gr->learn_rootpos[T-1] = p;
       gr->learn_root_scores[T-1] = g;
     }  
     pvi++;
    }

    if(post && g != -TIME_FLAG) {
      search_display(g);
      best_depth = max_ply;
    }

	if (!analyze_mode) {  

	// if time is up, or we found a mate... break
    if(inter() || g == -TIME_FLAG) break;

    g_last = g;
	last_depth = max_ply;
	if((g == 0 && max_ply > MAXD-3) ||
        ((g > (MATE/2) || g < -(MATE/2)) && max_ply > 2)) break;
	}

  
  }

  //------------------------------------------------------------------
  //  Clean up after search, record time used and post/log results
  //------------------------------------------------------------------

  elapsed = GetTime() - start_time;  if(!elapsed) elapsed = 1;

  if(ponder) {
   last_ponder = 1; ponder_time = elapsed;
  }

  // prevent divides by zero
  if(fail_high < 1) fail_high = 1;
  if(elapsed < 1) elapsed = 1;

  if(!xboard && !ALLEG && post) { 
   cout << "\nnode_count = " << node_count
        << " quiescent nodes = " << q_count
        << " eval_count = " << eval_count << "\n";
   cout << "hash hits = " << hash_count
        << " hash moves = " << hmove_count
        << " pawn hash hits = " << phash_count << "\n";
   cout << "node_rate = " << int(100.0*(float(node_count)/float(elapsed)))
        << " null cuts = " << null_cutoff
        << " exten = " << extensions
        << " sing_ext = " << singular_extensions
        << " int_iter = " << internal_iter << "\n";
   cout << "egtb_probes = " << egtb_probes
        << " egtb_hits = " << egtb_hits
        << " fail_high(%) = " << int(100.0*(float(first_fail_high)/float(fail_high))) << "\n";
  }

  sprintf(outstring, "node_count = %i, quiescent_nodes = %i, eval_count = %i\n", 
	  node_count, q_count, eval_count);
  write_out(outstring);
  sprintf(outstring, "hash hits = %i, hash moves = %i, pawn hash hits = %i\n", 
	  hash_count, hmove_count, phash_count);
  write_out(outstring);
  sprintf(outstring, "node_rate = %i, null_cuts = %i, exten = %i, sing_ext = %i, int_iter = %i\n",
	  int(100.0*(float(node_count)/float(elapsed))), null_cutoff, extensions, singular_extensions,
	  internal_iter);
  write_out(outstring);
  sprintf(outstring, "egtb_probes = %i, egtb_hits = %i, fail_high(pct) = %i\n",
	  egtb_probes, egtb_hits, int(100.0*(float(first_fail_high)/float(fail_high)))); 
  write_out(outstring);

  print_move(p, pc[0][0], mstring);

  if(ponder) { 
    sprintf(outstring, "***** Pondering ended ***** Time: %i, Time required doublings: %i\n",
	    ponder_time, ponder_time_double);
    write_out(outstring);
  } else {
    sprintf(outstring, "Return move from search: %s\n", mstring);
    write_out(outstring);
  }
  write_out("---------------------------------------------------------------\n");

#if DEBUG_SEARCH
 search_outfile.close();
#endif

  //------------------------------------------------------------------
  //   Do Book or TD leaf learning if score is right
  //------------------------------------------------------------------

  // book learning if applicable
  if(!ponder && gr->learn_bk && BOOK_LEARNING) {
    if(!gr->book && gr->learn_count > 0 && wbest > +LEARN_SCORE)
      { book_learn(1, gr); gr->learned = gr->learn_count; gr->learn_count = -1; }
    else if(!gr->book && gr->learn_count > 0 && wbest < -LEARN_SCORE)
      { book_learn(0, gr); gr->learn_count = -1; }
    else if(gr->learned && wbest < -LEARN_SCORE)
      { gr->learn_count = gr->learned; book_learn(-1, gr);
        gr->learned = 0; gr->learn_count = -1; }
   }

  // TDleaf evaluation learning upon losing
  if(wbest < -(MATE/2) && T < MAX_GAME_PLY-1
      && !tsuite && !analysis_mode && gr->td_learning) {
   gr->learn_scores = 1;
   score_learning(T, p.wtm, gr);
   gr->learn_scores = 0;
   gr->td_learning = 0;
  }


  //------------------------------------------------------------------
  //   Return the best move found by the search
  //------------------------------------------------------------------
  return pc[0][0];

}

/* Function to update principle continuation */
// The principle continuation is stored as a "triangular" array.
// It is updated by doing a mem-copy of the principle continuation
// found at deeper depths to this depth + the move at this depth
// is stuffed in first.
inline void tree_search::pc_update(move pcmove, int ply)
{
 int pci;
 pc[ply][ply].t = pcmove.t;
 for (pci = ply+1; pci < MAXD; pci++)
 {
  if(!(pc[ply+1][pci].t)) break; 
  pc[ply][pci].t = pc[ply+1][pci].t;
 }
 pc[ply][pci].t = NOMOVE;
}

// Special sort to shuffle best move to the top of the list
inline void MSort(move_rec *Lb, move_rec *Ub)
{
  move_rec V, *I, *J;

   V = *Lb; J = Lb;
   for(I = Lb+1; I <= Ub; I++) {
       if (I->score > J->score) { J = I; }
   }
   *Lb = *J;
   *J = V;
}

/*-------------------- Principle variation function --------------------*/
// This function uses the improvement on the
// alpha-beta scheme called "principle variation search".
// After the first node, which is searched with the full alpha-beta window,
// the rest of the nodes are searched with a "null" window: alpha,alpha+1.
int tb_hit = 0;

int search_node::pvs(int alpha, int beta, int depth)
{

 int best = -MATE+ply, talpha = alpha, null_hash = 1;
 int score=0, depth_mod, new_depth, mate_ext = 0;
 int mcount = 0, first = 1, try_lmr = 0, try_prune = 0, total_pieces;
 int hscore, hflag, hdepth, swap_score, premove_score;
 move smove, gmove, bmove; 

 gmove.t = NOMOVE; bmove.t = NOMOVE;

#if DEBUG_SEARCH
// Debug archiving of search to a file
char space_string[50] = "\0";
char last_move_string[10];
for(int si = 0; si < ply; si++) strcat(space_string," ");
if(ply) print_move(prev->pos, pos.last, last_move_string);

outfile << space_string << "->Ply: " << ply << ", max_ply: "
        << ts->max_ply << ", depth: " << depth << ", alpha: " << alpha
        << ", beta: " << beta << ", last: " << last_move_string << "\n";

#endif

 // ----------------------------------------------------------
 //     Check time and keyboard interrupt
 // ----------------------------------------------------------
 if(ply) ts->interrupt_check_count++;
 if(ply && !(ts->interrupt_check_count&4095)) {
  
	 if (!analyze_mode) {
	 if (ts->max_ply > 3 || ts->ponder) {
   if ((GetTime() - ts->start_time >= ts->limit && !ts->ponder) || (inter())) {
    return -TIME_FLAG;
   }
	
   if(FLTK_GUI && ts->ponder && ts->root_wtm == gr->pos.wtm) return -TIME_FLAG;
  }
	 }
 }

 // ----------------------------------------------------------
 //     IF this is not the root ply (ply = 0) of the search
 //       -- test fifty move rule and 3-rep
 //       -- look in the hash table for a cut-off or a move
 //       -- look in the end-game-tablebases (egtb)
 //     ELSE 
 //       -- just get a move from the hash table
 // ----------------------------------------------------------
 if(ply) {
  
  // add hash code for this position to position list
  gr->plist[ts->turn+ply-1] = pos.hcode;

  if(pos.last.t) {	   
    // fifty move rule
    if(pos.fifty >= 100) {
      ts->pc[ply][ply].t = NOMOVE;
      return(0);
    }
    // avoid repeating a position if possible
    int rep_count = 0;
    for(int ri = ts->turn+ply-3; ri >= ts->turn+ply-pos.fifty-1; ri -= 2) {
      if(gr->plist[ri] == gr->plist[ts->turn+ply-1]) rep_count++; 
      if((rep_count && ri >= ts->turn-1) || rep_count > 1) {
	ts->pc[ply][ply].t = NOMOVE;
	return(0);
      }
    }
  }

  // check hash table
  hscore = get_hash(&pos.hcode, &hflag, &hdepth, &mate_ext, &gmove);
  if(hscore != HASH_MISS) {
    // see if we can return a score
    //  -- avoid returning a score when in the main line (alpha != beta-1) and we are learning
    //     this measure is to keep the PV intact so we can trace back to the leaf position that 
    //     gives the score returned by the search
    if(hdepth >= DEPTH(depth)) { // && (!gr->td_learning || alpha==beta-1)) {
      if((hflag == FLAG_A || hflag == FLAG_P) && hscore <= alpha) {
	ts->hash_count++;
	// resurrect a MATE score
	if(hscore <= -32000) return -MATE+ply+hdepth;
	return alpha;
      } 
      if((hflag == FLAG_B || hflag == FLAG_P) && hscore >= beta) {
	ts->hash_count++;
	ts->pc[ply][ply].t = gmove.t;
	ts->pc[ply][ply+1].t = NOMOVE;
	// resurrect a MATE score
	if(hscore >= 32000) return MATE-ply-hdepth;
	return beta;
      }
      if(hflag == FLAG_P && hscore > alpha) {
	ts->hash_count++;
	ts->pc[ply][ply].t = gmove.t;
	ts->pc[ply][ply+1].t = NOMOVE;
	// resurrect a MATE score
	if(hscore >= 32000) return MATE-ply-hdepth;
	return hscore;
      }
    }
    // set null-move switch
    if((hdepth >= MAX(DEPTH(depth)-3,0) && (hflag==FLAG_A || hflag==FLAG_P)
        && hscore < beta) || mate_ext) null_hash = 0;
    // zero the hash move if the depth is not enough
    if(hdepth < DEPTH(depth)-3) gmove.t = NOMOVE;
  } else if(gmove.t) null_hash = 0;   // no hash score hit, but we found a move for this position, stuffed there by put_move() above

  // check egtb
#if TABLEBASES
  if(pos.last.t) {
   total_pieces = pos.pieces[0]+pos.pieces[1]
                 +pos.plist[0][PAWN][0]
                 +pos.plist[1][PAWN][0];
   if(total_pieces == 2) {
     ts->pc[ply][ply].t = NOMOVE;
     return(0);
   }
   if(total_pieces <= EGTB) {
    score = probe_tb(&pos, ply);
    ts->egtb_probes++;
    if(score != -1) {
     if(ply == 1) tb_hit = 1;
     ts->egtb_hits++;
     ts->pc[ply][ply].t = NOMOVE;
     return(score);
    }
   }
  }
#endif  /* TABLEBASES */
 } else gmove.t = get_move(&pos.hcode);

 // ----------------------------------------------------------
 //     Null Move Heuristic
 //       -- only apply null move if... 
 //            R is non-zero, not a root node,
 //            null_hash is non-zero, less than 3 from end of
 //            possible tree size, we have more than one piece,
 //            the last move was not a null, and we have
 //            enough total material on the board
 //       -- simple R = 3 seems best overall (dropping old scheme below)
 //          -- if we are deep enough, increase reduction factor
 //             to -3*UNIT_DEPTH rather than -2 (traditional R=2)
 //          -- testing using depth/2 rather than depth-R-UNIT_DEPTH
 //             when depth/2 is smaller        
 //          -- if null move returns a fail-high, do a
 //             verification search... same depth but from
 //             current position without changing sides..
 //             not sure how helpful this is (needs more testing)
 // ----------------------------------------------------------
 if(NULL_MOVE && ply 
    && !pos.check && null_hash && ply < MAXD-3
    && pos.pieces[pos.wtm] > 1 && pos.last.t 
    && pos.material > beta - NULL_THRESH) {
    //---------------------
    // set reduction level
    //---------------------
    //if(DEPTH(depth) < 6) 
    //  new_depth = depth-2*UNIT_DEPTH-UNIT_DEPTH; 
    //else 
    //  new_depth = MIN((depth/2),(depth-3*UNIT_DEPTH-UNIT_DEPTH)); 
    new_depth = (depth-3*UNIT_DEPTH-UNIT_DEPTH); 
    //----------------------
    // make the null move
    //----------------------
    ts->node_count++;
    next->pos = pos; next->pos.wtm ^= 1;
    Or(next->pos.hcode,hwtm);
    Or(next->pos.hcode,hbtm);
    next->pos.last.t = NOMOVE; next->pos.ep = 0;
    next->pos.material = -next->pos.material;
    next->pos.fifty = 0;
    //----------------------
    // do the search
    //----------------------
    if(new_depth >= 0) {
      score = -next->pvs(-beta, -beta+1, new_depth);
    } else {
      score = -next->qsearch(-beta, -beta+1, 0, 0);
    }
    if(score == TIME_FLAG) return -TIME_FLAG;
    /* verification search */
    //if (score >= beta && new_depth >= 0) {
    //  ts->node_count++;
    //  next->pos = pos;
    //  next->pos.last.t = NOMOVE;
    //  score = next->pvs(beta-1, beta, new_depth+UNIT_DEPTH);
    //  if(score == -TIME_FLAG) return -TIME_FLAG;
    //} 
    if (score >= beta) {
      ts->null_cutoff++;
      //put_hash(&pos.hcode, score, beta-1, beta, DEPTH(depth), bmove, mate_ext);
      return beta;
    }
    // bruce moreland's mate extension idea
    if(score <= -(MATE/2) && beta > -(MATE/2)) mate_ext = 1;
 } 

 // --------------------------------------------------------
 //     Assign Hash Move (or IID move) in the tree structure
 // --------------------------------------------------------
 ts->hmove.t = gmove.t;  // must be assigned even if no hash move to
                         // clear value from the previous search

 // --------------------------------------------------------
 //     Internal Iterative Deepening (IID) if no hash move
 //     -- idea taken from crafty
 //        modified by Ed Schroeder's idea to do this even 
 //        outside the main pv line -> seems to work well
 //        and also helps Singularity test (see below)
 //        NOTE: to facilitate this, we assign several
 //        of the hash variables: hscore,hflag,hdepth
 // --------------------------------------------------------
 if(ts->hmove.t) ts->hmove_count++;
 else if(DEPTH(depth) > 2) {
    ts->internal_iter++; 
    new_depth = depth - 3*UNIT_DEPTH;
    next->pos = pos;  next->pos.last.t = NOMOVE;
#if DEBUG_SEARCH
 outfile << space_string << "Entering an IID loop\n";
#endif
    hscore = next->pvs(alpha, beta, new_depth);
#if DEBUG_SEARCH
 outfile << space_string << "Leaving an IID loop\n";
#endif
    if(hscore == -TIME_FLAG) { return -TIME_FLAG; }
    if(hscore >= beta) { 
      hflag = 2; 
      ts->hmove.t = get_move(&pos.hcode);
    } else if(hscore > alpha) {
      hflag = 3; 
      ts->hmove.t = get_move(&pos.hcode);
    } else { hflag = 1; }
    hdepth = new_depth;
 } 

 // --------------------------------------------------------
 //     Generate Move List
 //     -- the following function call also scores 
 //        moves so that they can be sorted during
 //        the move loop below
 // --------------------------------------------------------
 pos.allmoves(&moves, ts);

 /* 
 // ----------------------------------------------------------
 //     Look for singular extension
 //      -- idea is that the hash move or move from IID 
 //         might be significantly better than the rest
 //         and therefore 'singular' in the language
 //         defined by the Deep Thought team; however,
 //         this simple version only tests the hash/IID 
 //         for singularity
 //      -- wonder if IID move is really a good idea, need
 //         to test... looks good  
 //      -- currently using hash/IID move only if the
 //         score in the table is greater than alpha.  This
 //         is basically as described on the chess programming wiki 
 //         (http://chessprogramming.wikispaces.com/Singular+Extensions) 
 //         as the idea publicized in stockfish 1.6 (lower bound flag) 
 //         which may have also been used earlier in rybka 3
 // ----------------------------------------------------------
 int singular = 0, mc_sing = 0, smargin = MAX(25*(8-moves.count), 25); 
 int singular_depth = 192+UNIT_DEPTH; 
 new_depth = depth-singular_depth;
 if(ply && ts->hmove.t   // hash move or IID move
    //   && gmove.t     // just the hash move    
        && hflag > 1
        && !(hflag == 3 && hscore <= alpha)
        && depth >= singular_depth
    //  && !pos.check
        && pos.last.t
        && (!(pos.last.b.type&CAPTURE))   // avoid recaptures
        && alpha != beta-1 
        && !mate_ext 
        && moves.count >= 2) {

   //---------------------------------------------------
   // assume the first move is singular unless proven
   // otherwise
   //---------------------------------------------------
   singular = ts->hmove.t; 
   
   //---------------------------------------------------
   // Loop over the entire move list
   //  -- make each move
   //  -- take the score of the first move to be hscore
   //  -- search each subsequent move with
   //     a zero-window which is smargin below hscore
   //  -- if any move scores above hscore - smargin
   //     the first move is not singular, so exit
   //---------------------------------------------------
   for(mc_sing = 0; mc_sing < moves.count; mc_sing++) {

     // increase node counts
     ts->node_count++; 
     
     // shuffle highest scored move to top of list
     // and define a shortcut for this move
     MSort(&moves.mv[mc_sing], &moves.mv[moves.count-1]);
     smove = moves.mv[mc_sing].m;
     
     // making move in the next position in the search
     next->pos = pos;
     if(!next->pos.exec_move(smove, ply)) {  
       if(!mc_sing) {
	 singular = 0;   
	 break;  // exit if first move is not legal
       }
       continue;
     }	

     // if we are not at the first move in the list
     // find its score and try to beat hscore-smargin (see desc. above)
     if(mc_sing) {
       score = -next->pvs(-hscore+smargin-1,-hscore+smargin, new_depth);
       if(score == TIME_FLAG) return -TIME_FLAG;
       // if score >= hscore-smargin -- the first move is not singular
       if(score >= hscore-smargin) {
	 // search this move just after best move 
	 if(mc_sing > 1) {
	   moves.mv[moves.count+1] = moves.mv[mc_sing];
	   for(int mi = mc_sing; mi == 2; mi--) {
	     moves.mv[mi] = moves.mv[mi-1];
	   }
	   moves.mv[1] = moves.mv[moves.count+1];
	 }
	 singular = 0;	      
	 break;
       }
     } else if(hflag == 2 && hscore < beta) {
       hscore = -next->pvs(-beta,-alpha, new_depth);
       if(hscore <= alpha) { 
	 singular = 0; 
	 break;
       }
     }  
   
   }  // closing bracket of move loop

 } // closing bracket of singular search code
 */ 

 // --------------------------------------------------------
 //     Pruning and depth reduction setup before move loop
 //     -- first "if" conditions apply to all pruning: 
 //        don't do it if we are in check or we are doing
 //        a research of a fail low of the first ply 
 // --------------------------------------------------------
 if((ply || talpha > -MATE) && !pos.check &&  ts->max_ply > 2) {
   // If DEPTH(depth) >= 1, try to reduce the search
   //  depth of certain moves (see move loop below).
   //  Some of these reductions may lead to pruning.
   if(DEPTH(depth) >= 1) {    
     try_lmr = 1;
   } else {
     // Otherwise just try to prune based on the likely score
     //  change of the move.
     premove_score = pos.score_pos(alpha-101,beta,gr);
     ts->eval_count++;
     try_prune = 1;
   }
 }
 
 // --------------------------------------------------------
 //     Move Loop
 //     Basic plan is as follows...
 //     -- loop over each move from the list
 //     -- make the move to the position in the "next" node
 //     -- setup any extensions
 //     -- do any pruning or depth reductions
 //     -- search the "next" node to depth-UNIT_DEPTH
 //     -- use score from move and alpha/beta cuts
 //        to decide if we are done (fail high) or
 //        need to continue... do associated 
 //        keeping
 // --------------------------------------------------------
 
 while (mcount < moves.count && best < beta)
 {
   // -----------------------------------------------
   // increase node counts
   // -----------------------------------------------
   ts->node_count++; 

   // ----------------------------------------------------------------
   // shuffle highest scored move to top of list
   // and define a shortcut for this move -- skip shuffle if the move
   // has already been sorted when doing the singular extension check
   // ----------------------------------------------------------------
   //if(mcount >= mc_sing) MSort(&moves.mv[mcount], &moves.mv[moves.count-1]);
   MSort(&moves.mv[mcount], &moves.mv[moves.count-1]);
   smove = moves.mv[mcount].m;
 
   // -------------------------------------------------------------
   // Allow possibility for an oversight when knowledge_scale < 75
   // -------------------------------------------------------------
   if(gr->knowledge_scale < 75 && !first) {
     if((((pos.hcode^(smove.b.to+smove.b.from))&63ULL)+12 > gr->knowledge_scale)
	   && ((pos.hcode^smove.b.to^smove.b.from)&3)) {
       mcount++;
       continue;
     }
   }

   // -------------------------------------------------
   // making move in the next position in the search
   //   -- if it is illegal, skip to next move in list
   // -------------------------------------------------
   next->pos = pos;
   if(!next->pos.exec_move(smove, ply)) {
    mcount++;
    continue;
   }

#if DEBUG_SEARCH
 print_move(pos, smove, last_move_string);
 outfile << space_string << "Move: " << last_move_string << "\n";
#endif

   // -----------------------------------------------------------------
   // if we generated a check, find out if it is a safe check... 
   //  (CAPTURES are already tested for this when they are generated)
   // -----------------------------------------------------------------
   swap_score = 0;
   if(next->pos.check && moves.mv[mcount].score < 1999999) {
     if(!(smove.b.type&CAPTURE)) {
       swap_score = swap(smove.b.to, pos, pos.wtm, smove.b.from);
       // check for a revealed check if above gives less than zero
       if(swap_score < 0 && check_table[smove.b.from][pos.plist[pos.wtm^1][KING][1]])  {
	 if(next->pos.simple_check(smove.b.from)) swap_score = 0;
       }
     } else swap_score = -1;
   }

   // -------------------------------------------------------
   // initalize depth modifications for this move to be zero    
   // -------------------------------------------------------
   depth_mod = 0;

   // -----------------------------------
   //   Set the extensions
   // -----------------------------------
   if(DEPTH(depth+depth_mod)+ply < (MAXD-3)) {
     // if move looks to be singular, extend
     //if(smove.t == singular) 
     //  { depth_mod += SINGULAR_EXT; ts->singular_extensions++; }
     //if last move was the only available move from a check
     if(moves.count == 1 && pos.check)
       { depth_mod += ONE_REPLY_TO_CHECK;}
     // if we caused a check, extend
     else if(next->pos.check && pos.material < NO_CHECK_EXT_SCORE && swap_score > -1) 
       { depth_mod += CHECK_EXT; }
     // if last move was a pawn push and endgame, extend
     else if(pos.pieces[pos.wtm^1] < 6 &&  next->pos.last.b.type&PAWN_PUSH && 
        (next->pos.last.b.to > 48 || next->pos.last.b.to < 17))
       { depth_mod += PAWN_EXT; }
     // if mate_extension
     else if(mate_ext) 
       { depth_mod += MATE_EXT; }
     // if last move was a capture (but not a losing capture)
     /*
     else if(ply && next->pos.last.b.type&CAPTURE && moves.mv[mcount].score > 1999999) {
       // if last move was a re-capture, extend
       if(pos.last.b.type&CAPTURE && ply
          && prev->pos.material == next->pos.material      // even exchange
          && pos.sq[next->pos.last.b.to].type > PAWN)
         { depth_mod += RE_CAPT_EXT; }
     }
     */
     // Don't go to qsearch if we this move is a check evasion
     //if (depth+depth_mod < UNIT_DEPTH && pos.check) { depth_mod = UNIT_DEPTH-depth; }           
     // Don't go to qsearch if we this move is a check 
     if (depth+depth_mod < UNIT_DEPTH && next->pos.check) { depth_mod = UNIT_DEPTH-depth; }           
   }

   // ------------------------------------------------
   //   Move Reductions and Pruning
   //    -- only if (1) no depth modifiers were
   //       found above, (2) this isn't the first
   //       move (important!) searched, and 
   //       (3) if the current move hasn't 
   //       caused a check (4) not a pawn push to last rank
   //    -- then apply conditions set prior
   //       to the move loop
   //    -- note that for LMR, the move
   //       score must be less than the lowest
   //       'killer' move score (2000000).
   //       So losing captures can be reduced.
   //       Reduction decisions are based on
   //       history scores and score for the
   //       position.
   //       (see below in code for how
   //        history scores are modified
   //        during search)
   // ------------------------------------------------
   if((try_lmr || try_prune) 
      && !depth_mod && !first && !next->pos.check 
      && (best >= alpha || alpha == beta - 1)
      && (moves.mv[mcount].score < 1999999)
      && alpha > -(MATE/2)) {   // alpha > -(MATE/2) important!
     // -----------------------------------
     // try move reduction first
     // -----------------------------------
     if(try_lmr) {
       //--------------------------------------------------------------
       // Do a search to establish a score for all positions considered
       //  for reductions, moves reduced to DEPTH < 1 are pruned 
       //     Note it makes no sense to send them directly to qsearch
       //     as the qsearch has already proven them to be below alpha    
       //--------------------------------------------------------------     
       if(DEPTH(depth) > 4) score = -next->pvs(-alpha-1,-alpha,depth-(2+DEPTH(depth)/2)*UNIT_DEPTH);
       else 
	 score = -next->qsearch(-alpha-1,-alpha,0,0);
       if(score <= -(MATE/2)) { mcount++; continue; }
       if(score <= alpha) {
	 depth_mod -= UNIT_DEPTH; //*MAX(1,(DEPTH(depth)/4)); 
	 // make another reduction decision based on history or position in move list
	 // --> reduce if this move loses historically (~ 90% fail low history)
	 if(moves.mv[mcount].score < -10*DEPTH(depth)*DEPTH(depth)) depth_mod -= UNIT_DEPTH*2; //*MAX(1,(DEPTH(depth)/4));  
       }
       // prune move if reduction would lead to qsearch (already done above)
       if(DEPTH(depth+depth_mod) < 1) { mcount++; continue; }
     // ---------------------------------------
     //  else try to prune at DEPTH(depth) < 1
     // ---------------------------------------
     } else { 
       if(premove_score < alpha - 100) {  
	 mcount++; continue;
       }
     }
     
   }

   // -----------------------------------
   // initialize tb_hit variable 
   // -----------------------------------
   if(!ply) tb_hit = 0;

   // -----------------------------------
   //   Apply depth modifiers from
   //    extensions and reductions
   //------------------------------------
   new_depth = depth+depth_mod-UNIT_DEPTH;

   // ------------------------------------------
   //   If the net effect = actual extension
   //    record that an extension happened
   // ------------------------------------------
   if(DEPTH(new_depth) > DEPTH(depth)-1) { 
     ts->extensions++; next->pos.extend = 1; 
   } else { 
     next->pos.extend = 0; 
   }

   // -----------------------------------
   //   Search the next node in the tree
   // -----------------------------------
   if(new_depth < 0) {
     score = -next->qsearch(-beta, -alpha, 0, 0); 
#if DEBUG_SEARCH
 outfile << space_string << "Returned value: " << score << " from qsearch\n";
#endif
   } else {
    if(first) {
      score = -next->pvs(-beta, -alpha, new_depth);
      if(!ply && tb_hit && score > (MATE/2) 
         && score <= ts->root_tb_score) score = alpha;
      if (score == TIME_FLAG) return -TIME_FLAG;    
    } else {
      score = -next->pvs(-alpha-1, -alpha, new_depth);
      if(!ply && tb_hit && score > (MATE/2) 
         && score <= ts->root_tb_score) score = alpha;
      if (score == TIME_FLAG) return -TIME_FLAG;
      if (score > alpha && score < (MATE/2)) { // <-- important for fail-soft in qsearch and move-reductions otherwise use score < beta) {
	if(depth_mod < 0) new_depth = depth-UNIT_DEPTH;  // for checking move reductions on re-search
	score = -next->pvs(-beta, -alpha, new_depth);
	if (score == TIME_FLAG) return -TIME_FLAG;
      }
    }
#if DEBUG_SEARCH
 outfile << space_string << "Returned value: " << score << "\n";
#endif
   }
  
   // ------------------------------------ 
   // Panic mode for additional time 
   //  also display if we are failing low
   //-------------------------------------
   if(!ply && first && ts->max_ply > 3) { 
     if(ts->limit < ts->max_limit && score <= ts->g_last-30 
        && !ts->tsuite && GetTime() - ts->start_time >= (ts->limit/4)) {
       if(!ts->ponder) { 
        ts->limit *= 2;
        if(logging) logfile << "Extending search to: " << ts->limit << "\n";
       } else if(ts->ponder_time_double < 2) {
        ts->ponder_time_double++;
        if(logging) logfile << "Doubling required ponder time\n";
       }
     }
     if(score <= alpha) {
      ts->fail = -1;
      if(post) ts->search_display(score);
      ts->log_search(score);
      ts->fail = 0;
      return(score);
     }
   }

   
   // ------------------------------------ 
   //   Update best score
   // ------------------------------------ 
   if(score > best) { 
     best = score;
   }

   // ------------------------------------ 
   //   If score is not a fail-low
   //     -- increase alpha bound
   //     -- store best move
   //     -- update pv
   //     -- if root-node, display line
   //     -- update history/killer moves
   //         if this is a fail high
   //   Else
   //     -- reduce history move score
   // ------------------------------------ 
   if (score > alpha) {
     alpha = score;
     bmove = smove;
     if(score < beta) ts->pc_update(smove, ply);
     else if(!ply) { ts->pc[0][0].t = smove.t; ts->pc[0][1].t = NOMOVE; }
     //
     // display/output search info at root node
     //
     if(!ply) {
      ts->wbest = score; ts->wply = ts->max_ply;  // whisper variables
      if(score >= beta) ts->fail = 1; 
      if(post) ts->search_display(score);
      ts->log_search(score);      
      if(ts->fail) ts->fail = 0;
     }
     //
     // if score >= beta, increase fail high counts and update history/killers
     //
     if(score >= beta) {
       ts->fail_high++;
       if(!mcount) ts->first_fail_high++;	 
       //
       // update history list and killer moves
       //   -- only update history score when
       //      we are more than two ply from leaf
       //
       if(!(smove.b.type&CAPTURE)) {
	 // update history score for this move
	 if(new_depth > UNIT_DEPTH && ts->history[smove.b.from][smove.b.to] < 1000000) 
	   ts->history[smove.b.from][smove.b.to] += 9*DEPTH(new_depth+UNIT_DEPTH)*DEPTH(new_depth+UNIT_DEPTH);
	 if(ts->killer1[pos.wtm] != smove.t) {
	   ts->killer3[pos.wtm] = ts->killer2[pos.wtm];
	   ts->killer2[pos.wtm] = ts->killer1[pos.wtm];
	   ts->killer1[pos.wtm] = smove.t;
	 }
       }
     }

   } else {   /*  following is for when we fail low */

     //
     // adjust score in history table for failing low
     //   -- use a score update which is half the value for
     //      failing high
     //
     if(new_depth > UNIT_DEPTH && !(smove.b.type&CAPTURE) && ts->history[smove.b.from][smove.b.to] > -1000000) 
       ts->history[smove.b.from][smove.b.to] -= DEPTH(new_depth+UNIT_DEPTH)*DEPTH(new_depth+UNIT_DEPTH); 
 
   }  

   // ------------------------------------ 
   // update move loop variables
   // ------------------------------------    
   first = 0;
   mcount++;
 
 }  /* End of move loop */     


 // ----------------------------------------------------------------- 
 // if it is mate or stalemate; no move is in principle continuation
 // ----------------------------------------------------------------- 
 if(first && ply) {
   if(!pos.check) best = 0;        // score is even if stalemate
   ts->pc[ply][ply].t = NOMOVE;
 }

 // ------------------------------------------------------ 
 // storing position in the hash table
 //  -- assign the hash move to be the best move if the
 //     position is a fail-low with no best move
 // ------------------------------------------------------ 
 if(!bmove.t && !first) bmove.t = gmove.t; 
 put_hash(&pos.hcode, best, talpha, beta, DEPTH(depth), bmove, mate_ext);

 return best;

}

/*--------------------- Quiescent search ---------------------*/
// This searches only non-losing captures.  Futility cut-offs
// are made if the capture is not likely to bring us up back
// above alpha.   A straight alpha-beta algorithm is used here.
//   NOTE:  if "check_chain" = 0, we are no longer following checks in
//          qsearch and all checks result in an immediate scoring of 
//          that position at the current value. At the moment, check_chain = 0
//          appears to be best in all circumstances... not sure what that
//          means... perhaps just a bug in coding of MATE returns from
//          qsearch or perhaps simpler is just better.  So all calling
//          functions set check_chain = 0 at the moment.
int search_node::qsearch(int alpha, int beta, int qply, int check_chain)
{
  register int qi, best, score, delta_score;  // best score, score for current move
  register int talpha = alpha;
  move_rec qmove;                             // Move record for current move to search  
 
#if DEBUG_SEARCH
// Debug archiving of search to a file
char space_string[50] = "\0";
char last_move_string[10];
for(int si = 0; si < ply; si++) strcat(space_string," ");
if(ply) print_move(prev->pos, pos.last, last_move_string);

 outfile << space_string << "Qsearch->Ply: (ply, qply) (" << ply << ", " << qply <<"), max_ply: "
        << ts->max_ply << ", alpha: " << alpha
        << ", beta: " << beta << ", last: " << last_move_string << "\n";

#endif

  // must put a blank move in the principle continuation
  // because we may choose to make no move during qsearch
  ts->pc[ply][ply].t = NOMOVE;
  
  // break the search if we are at the end of allowed plys
  if(ply >= MAXD-2) return pos.score_pos(-MATE,+MATE,gr);                      
  
  //---------------------------  
  // On first layer of q-search 
  // - reset qsearch nodes
  // - check hash table 
  //---------------------------  
  if(!qply) {
    ts->nq_count = 0;
    int hflag, hdepth, mate_ext; move gmove;
    int hscore = get_hash(&pos.hcode, &hflag, &hdepth, &mate_ext, &gmove);
    if(hscore != HASH_MISS) {
      // see if we can return a score
      if(hdepth >= -1) { 
      	if((hflag == FLAG_A || hflag == FLAG_P) && hscore <= alpha) {
	  ts->hash_count++;
	  // resurrect a MATE score
	  if(hscore <= -32000) return -MATE+ply+hdepth;
	  return alpha;
      	} 
      	if((hflag == FLAG_B || hflag == FLAG_P) && hscore >= beta) {
	  ts->hash_count++;
	  ts->pc[ply][ply].t = gmove.t;
	  ts->pc[ply][ply+1].t = NOMOVE;
	  // resurrect a MATE score
	  if(hscore >= 32000) return MATE-ply-hdepth;
	  return beta;
      	}
      	if(hflag == FLAG_P && hscore > alpha) {
	  ts->hash_count++;
	  ts->pc[ply][ply].t = gmove.t;
	  ts->pc[ply][ply+1].t = NOMOVE;
	  // resurrect a MATE score
	  if(hscore >= 32000) return MATE-ply-hdepth;
	  return hscore;
      	}
      }
    }
  }
 
  //-------------------------------------
  // Now the rest of the normal qsearch
  //-------------------------------------
  delta_score = -50;   // set default futility cutoff

  // ------------------------------------ 
  //  Generate a score for the position
  // ------------------------------------ 
  if(!pos.check) { 
    best = pos.score_pos(alpha,beta,gr); 
    ts->eval_count++; 
    if(best < alpha && alpha < (MATE/2)) { 
      // set futility cutoff 'delta_score' which is used
      // in the generation of captures -- modified during the
      // capture generation depending on the type of piece
      // captured
      delta_score = alpha - best - 50;     
      //best = alpha;
    }
    else if(best >= beta) {               // return (stand pat) if we already have a high enough score
      if(!qply) {                         // hash result on first layer of qsearch
	qmove.m.t = NOMOVE;
	put_hash(&pos.hcode, best, talpha, beta, -1, qmove.m, 0);
      }
      return best;           
    }
  }
  else { best = -MATE+ply; } 

  if(best > alpha && !pos.check) alpha = best;    // increase alpha if best > alpha

  // --------------------------------------------------------------- 
  // generate captures 
  //  -- have tried many times to generate some combination of captures
  //     and 'safe' checks under various circumstances, but it is always
  //     worse than just plain captures.
  //  -- see check_chain note at start of this function for more info
  // --------------------------------------------------------------- 
  //if(!pos.check && !qply) pos.captchecks(&moves, delta_score); 
  if(!pos.check) pos.captures(&moves, delta_score);
  else { 
    ts->hmove.t = NOMOVE;
    pos.allmoves(&moves,ts);
  }

  // ------------------------------------------------------
  // loop trough possible captures, trying them in turn
  // ------------------------------------------------------
  for (qi = 0; qi < moves.count; qi++)
  {
    // shuffle highest scored move to top of list
    MSort(&moves.mv[qi], &moves.mv[moves.count-1]);
    qmove = moves.mv[qi];

    // increase node counts
    ts->node_count++; ts->q_count++; ts->nq_count++;
    //if(!pos.check && ts->nq_count > 400) break;

    // execute move
    //   -- returns a zero if the move leaves us in check
    next->pos = pos;
    if(!next->pos.qexec_move(qmove.m, ply)) { continue; } 

    // call next iteration to obtain a score
    if(!check_chain && next->pos.check) { 
      score = -next->pos.score_pos(-beta,-alpha,gr);
      ts->eval_count++;
      ts->pc[ply+1][ply+1].t = NOMOVE;
    }
    else score = -next->qsearch(-beta, -alpha, qply+1,(check_chain&(pos.check|next->pos.check)));

    if(score > alpha) {
     ts->pc_update(qmove.m, ply);     
     if (score >= beta) { 
       if(!qply) put_hash(&pos.hcode, score, talpha, beta, -1, qmove.m, 0);  // update hash on first layer
       return(score);  
     }
     alpha = score;
    } 

    if(score > best) best = score;     

  }
  
  // --------------------------------------------- 
  // update hash if this is first layer of qsearch 
  // --------------------------------------------- 
  if(!qply) {
    qmove.m.t = NOMOVE;
    put_hash(&pos.hcode, best, talpha, beta, -1, qmove.m, 0);
  }

  // return the best score
  return best;

}






