
// search.cpp

// includes

#include <csetjmp>

#include "attack.h"
#include "board.h"
#include "book.h"
#include "colour.h"
#include "list.h"
#include "material.h"
#include "move.h"
#include "move_do.h"
#include "move_gen.h"
#include "option.h"
#include "pawn.h"
#include "protocol.h"
#include "pv.h"
#include "search.h"
#include "search_full.h"

// kh 10.04.07 Thomas Gaksch
//#include "sort.h" 

#include "trans.h"
#include "util.h"
#include "value.h"

#include "YBWCManager.h"
extern YBWCManager* g_pYBWCManagerInstance;

// constants

static const bool UseCpuTime = false; // false

// kh 14.02.08 
//static const bool UseEvent = true; // true

static const bool UseShortSearch = true;

// kh 02.06.08 Thomas Gaksch 14b5c
static const int ShortSearchDepth = 1;

static const bool DispBest = true; // true
static const bool DispDepthStart = true; // true
static const bool DispDepthEnd = true; // true
static const bool DispRoot = true; // true
static const bool DispStat = true; // true

static const bool UseEasy = true; // singular move
static const int EasyThreshold = 150;
static const double EasyRatio = 0.20;

static const bool UseEarly = true; // early iteration end
static const double EarlyRatio = 0.60;

static const bool UseBad = true;
static const int BadThreshold = 50; // 50
static const bool UseExtension = true;

// variables

// kh 10.04.07 start Thomas Gaksch
static search_multipv_t save_multipv[MultiPVMax];

// kh 02.06.08 Thomas Gaksch 14b5c
//bool trans_endgame;

// kh 10.04.07 end Thomas Gaksch

search_input_t    SearchInput   [1];
search_info_t     SearchInfo    [1];
search_root_t     SearchRoot    [1];
search_current_t  SearchCurrent [1];
search_best_t     SearchBest    [MultiPVMax]; // kh 10.04.07 start Thomas Gaksch
search_best_t     SearchBestLast[MultiPVMax]; // kh 18.06.08 

/*static */ uint16 Killer[HeightMax][KillerNb];

// prototypes

static void search_send_stat ();

// functions

// depth_is_ok()

bool depth_is_ok(int depth) {

   return depth > -128 && depth < DepthMax;
}

// height_is_ok()

bool height_is_ok(int height) {

   return height >= 0 && height < HeightMax;
}

// search_clear()

void search_clear() 
{
   // SearchInput

   SearchInput->infinite          = false;
   SearchInput->depth_is_limited  = false;
   SearchInput->depth_limit       = 0;
   SearchInput->time_is_limited   = false;
   SearchInput->time_limit_1      = 0.0;
   SearchInput->time_limit_2      = 0.0;

   // SearchInfo

   SearchInfo->can_stop           = false;
   SearchInfo->stop               = false;

   SearchInfo->check_nb   = g_pYBWCManagerInstance->pFruitConfiguration->nCheckNb;
   SearchInfo->check_inc  = g_pYBWCManagerInstance->pFruitConfiguration->nCheckInc;
   
// kh 01.08.06 the poll frequency while searching (measured in nodes searched) is adjusted here
// the bRootMaster property may be used as a future expansion
// SearchInfo->check_nb_mpi_poll_min = 1; // kh 04.08.06 any value > 0 is sufficient
   if(g_pYBWCManagerInstance->bRootMaster)
   {
     SearchInfo->check_nb_mpi_poll  = g_pYBWCManagerInstance->pFruitConfiguration->nCheckNbMPIPoll;
     SearchInfo->check_inc_mpi_poll = g_pYBWCManagerInstance->pFruitConfiguration->nCheckIncMPIPoll;
   }
   else
   {
     SearchInfo->check_nb_mpi_poll  = g_pYBWCManagerInstance->pFruitConfiguration->nCheckNbMPIPoll;
     SearchInfo->check_inc_mpi_poll = g_pYBWCManagerInstance->pFruitConfiguration->nCheckIncMPIPoll;
   }

   SearchInfo->nHeightOffset  = 0;

   SearchInfo->last_time      = 0.0;

   // SearchBest

// kh 10.04.07 start Thomas Gaksch
   SearchBest[SearchCurrent->multipv].move = MoveNone;
   SearchBest[SearchCurrent->multipv].value = 0;
   SearchBest[SearchCurrent->multipv].flags = SearchUnknown;
   PV_CLEAR(SearchBest[SearchCurrent->multipv].pv);


/*
   SearchBest->move           = MoveNone;
   SearchBest->value          = 0;
   SearchBest->flags          = SearchUnknown;
   PV_CLEAR(SearchBest->pv);
*/
// kh 10.04.07 end Thomas Gaksch

   // SearchRoot

   SearchRoot->depth          = 0;
   SearchRoot->move           = MoveNone;
   SearchRoot->move_pos       = 0;
   SearchRoot->move_nb        = 0;
   SearchRoot->last_value     = 0;
   SearchRoot->bad_1          = false;
   SearchRoot->bad_2          = false;
   SearchRoot->change         = false;
   SearchRoot->easy           = false;
   SearchRoot->flag           = false;

   // SearchCurrent

// kh 14.02.07
   if(g_pYBWCManagerInstance->bSearchingSubproblem && (g_pYBWCManagerInstance->nRerunSearchCounter > 0))
   {
   }
   else
   {
     SearchCurrent->node_local_nb    = 0;

     SearchCurrent->max_depth        = 0;
     SearchCurrent->max_local_depth  = 0;

// kh 04.04.08 clear node counts etc. for subjobs initially when the root master requests a search support (YBWCManager_HookGo(... ) 
// and deferred after transmitting the search result to favor "gross" node counting.
// recursive subnodes of a slave stopped by a cutoff and sendig a "late" result asynchronously are also counted this way
     if(g_pYBWCManagerInstance->bRootMaster)
     {
       SearchCurrent->node_nb          = 0;
       SearchCurrent->time             = 0.0;
       SearchCurrent->speed            = 0.0;
       SearchCurrent->cpu              = 0.0;
     }
   }
}

// search()

void search() 
{
  int  move;
  int  depth;

  int  nResult;

  int  nDepthStart;

  bool  bPotentialDepthLimitChangeOk;

// kh 10.04.07 Thomas Gaksch
  int   i;
  bool  search_ready;
     
// kh 10.04.07 start Thomas Gaksch
  for(i = 0; i < MultiPVMax; i++)
  {
	  save_multipv[SearchCurrent->multipv].mate       = 0;
	  save_multipv[SearchCurrent->multipv].depth      = 0;
	  save_multipv[SearchCurrent->multipv].max_depth  = 0;
	  save_multipv[SearchCurrent->multipv].value      = 0;
	  save_multipv[SearchCurrent->multipv].time       = 0;
	  save_multipv[SearchCurrent->multipv].node_nb    = 0;
	  strcpy(save_multipv[SearchCurrent->multipv].pv_string, ""); 
  }
  
  SearchInput->multipv = option_get_int("MultiPV") - 1;

  SearchCurrent->multipv = 0;
// kh 10.04.07 end Thomas Gaksch
      
  ASSERT(board_is_ok(SearchInput->board));

   // opening book

  if(    option_get_bool("OwnBook") 
      && !SearchInput->infinite
      && !g_pYBWCManagerInstance->bSearchingSubproblem) 
  {
    move = book_move(SearchInput->board);

    if(move != MoveNone)
    {
         // play book move

      SearchBest[SearchCurrent->multipv].move   = move;
      SearchBest[SearchCurrent->multipv].value  = 1;
      SearchBest[SearchCurrent->multipv].flags  = SearchExact;
      SearchBest[SearchCurrent->multipv].depth  = 1;
      SearchBest[SearchCurrent->multipv].pv[0]  = move;
      SearchBest[SearchCurrent->multipv].pv[1]  = MoveNone;

      search_update_best();

      return;
    }
  }

   // SearchInput

  gen_legal_moves(SearchInput->list, SearchInput->board);

// kh 10.04.07 Thomas Gaksch
  if(LIST_SIZE(SearchInput->list) < SearchInput->multipv + 1)
  { 
	  SearchInput->multipv = LIST_SIZE(SearchInput->list) - 1;
  }

  if(LIST_SIZE(SearchInput->list) <= 1) 
  {
    SearchInput->depth_is_limited = true;
    SearchInput->depth_limit      = 4; // was 1
  }

   // SearchInfo

  g_pYBWCManagerInstance->bRestoreBestFromBestLast = FALSE;
  if(setjmp(SearchInfo->buf) != 0) 
  {
    ASSERT(SearchInfo->can_stop);

    if(g_pYBWCManagerInstance->bRestoreBestFromBestLast)
    {
      SearchBest[0].depth = SearchBestLast[0].depth;
      SearchBest[0].flags = SearchBestLast[0].flags;
      SearchBest[0].move  = SearchBestLast[0].move;
      SearchBest[0].value = SearchBestLast[0].value;
      pv_copy(SearchBest[0].pv, SearchBestLast[0].pv); 
    }

// kh 13.10.06 best move is eventually 0 when search is early stopped and a subproblem is searched 
    ASSERT((SearchBest[0].move != MoveNone) || g_pYBWCManagerInstance->bSearchingSubproblem);
    search_update_current();

// kh 20.09.06 stop searching on all processors for actual stack content
// stop may be broadcasted here as a "forced stop" as 
// a future expansion to all non root master for a better performance
    nResult = Stack_Stop(/* g_pYBWCManagerInstance->pStack */);
    if(nResult == MPI_SUCCESS)
    {
    }
    else
    {
      if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_ERROR_PRIO_1)
      {
        YBWCManager_Printf(g_pYBWCManagerInstance, "ERROR search(... failed at Stack_Stop(..., errorcode = %d\n", nResult);
      }
    }

    Stack_Clear(/* g_pYBWCManagerInstance->pStack */);
    ASSERT(g_pYBWCManagerInstance->pStack->nCount == 0);

    return;
  } // if(setjmp(SearchInfo->buf) != 0) 

   // SearchRoot

  list_copy(SearchRoot->list, SearchInput->list);

   // SearchCurrent

  board_copy(SearchCurrent->board, SearchInput->board);

  if(g_pYBWCManagerInstance->bSearchingSubproblem && (g_pYBWCManagerInstance->nRerunSearchCounter > 0))
  {
  }
  else
  {
    my_timer_reset(SearchCurrent->timer);
    my_timer_start(SearchCurrent->timer);
  }

   // init

  if(g_pYBWCManagerInstance->bRootMaster)
  {
    trans_inc_date(Trans);

    if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_INFO_PRIO_2)
    {
      YBWCManager_Printf(g_pYBWCManagerInstance, "root date after inc = %d\n", Trans->date);
    }
  }
  else
  {
    trans_update_date(Trans, g_pYBWCManagerInstance->pWorkAvailableResult->nTransDate);

    if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_INFO_PRIO_2)
    {
      YBWCManager_Printf(g_pYBWCManagerInstance, "update date for subjob = %d\n", 
                         g_pYBWCManagerInstance->pWorkAvailableResult->nTransDate);
    }
  }

// kh 10.04.07 Thomas Gaksch
//sort_init(); 

  search_full_init(SearchRoot->list, SearchCurrent->board);

// kh 02.06.08 Thomas Gaksch 14b5c
/*   
// kh 10.04.07 start Thomas Gaksch
   // analyze game for evaluation
  if(    SearchCurrent->board->piece_size[White] < 3 
      && SearchCurrent->board->piece_size[Black] < 3
      && (SearchCurrent->board->pawn_size[White]+SearchCurrent->board->pawn_size[Black]) > 0)
  {
	  trans_endgame = true;
  }
  else
  {
	  trans_endgame = false;
  }
// kh 10.04.07 end Thomas Gaksch
*/

   // iterative deepening

	search_ready = false; // kh 10.04.07 Thomas Gaksch

  if(g_pYBWCManagerInstance->bSearchingSubproblem)
  {

// kh 11.10.06 the last move leading to the position (subproblem) to search will be handled 
// or filtered respectively as it would be the only root move 
// that seems to be an acceptable way to reuse all the fruit standard 
// search logic/behavior (e.g. setting up and managing all the internal data structures, 
// saving all necessary the information associated with the best move (score, pv etc.)
// but nDepthStart is immediately set to the remaing depth of the sub problem (as received 
// from the master of this sub problem), to avoid some kind of an additional internal iterative deepening
// behavior (hint from Ulf Lorenz)

    if(g_pYBWCManagerInstance->pFruitConfiguration->nSlaveStartIIDDepth == 0)
    {
      nDepthStart = g_pYBWCManagerInstance->pWorkAvailableResult->nDepth; // kh 01.02.07 default, no IID for sub problems
    }
    else if(g_pYBWCManagerInstance->pFruitConfiguration->nSlaveStartIIDDepth > 0) // kh 01.02.07 use fix IID start depth for sub problems
    {
      nDepthStart = g_pYBWCManagerInstance->pFruitConfiguration->nSlaveStartIIDDepth;
      if(nDepthStart > g_pYBWCManagerInstance->pWorkAvailableResult->nDepth)
      {
        nDepthStart = g_pYBWCManagerInstance->pWorkAvailableResult->nDepth;
      }
    }
    else if(g_pYBWCManagerInstance->pFruitConfiguration->nSlaveStartIIDDepth < 0) // kh 01.02.07 use relative IID start depth for sub problems
    {
      nDepthStart = g_pYBWCManagerInstance->pWorkAvailableResult->nDepth - 
                    (-g_pYBWCManagerInstance->pFruitConfiguration->nSlaveStartIIDDepth);
      if(nDepthStart < 1) 
      {
        nDepthStart = 1;
      }
    }
    else
    {
      ASSERT(false);
      nDepthStart = g_pYBWCManagerInstance->pWorkAvailableResult->nDepth;
    }

// kh 13.10.06 SearchInfo->can_stop is originally otherwise not set before at least depth 1 has been completed 
// but the search result will be ignored anyway by the master if he sends a stop request
// (hopefully the internal data structures are initialized "good enough" in that case, 
// so the standard fruit assertions hold)
    SearchInfo->can_stop = true; 

// kh 13.10.06 was used for test purposes only
//   nDepthStart = 1;
  } // if(g_pYBWCManagerInstance->bSearchingSubproblem)
  else
  {

// kh 11.10.06 fruit original assignment
    nDepthStart = 1;

// kh 26.03.07 for a test only
//  nDepthStart = SearchInput->depth_limit;

  } // !if(g_pYBWCManagerInstance->bSearchingSubproblem)

  bPotentialDepthLimitChangeOk = false;

  for(depth = nDepthStart; depth < DepthMax; depth++) 
  {

// kh 22.12.06 tuning 
    if(g_pYBWCManagerInstance->bSearchingSubproblem)
    {
      if(    (g_pYBWCManagerInstance->pWorkAvailableResult->nDepth != SearchInput->depth_limit)
          && !bPotentialDepthLimitChangeOk) // kh 17.03.07 limit may change if there exist just one legal move
      {
        if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_ERROR_PRIO_1)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, 
                             "ERROR search(... failed: depth limit has changed actual = %d but expected = %d\n", 
                             SearchInput->depth_limit,
                             g_pYBWCManagerInstance->pWorkAvailableResult->nDepth);
        }
      }

      if(depth > g_pYBWCManagerInstance->pWorkAvailableResult->nDepth)
      {
        if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_ERROR_PRIO_1)
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, 
                             "ERROR search(... failed: depth (%d) > pWorkAvailableResult->nDepth (%d)\n", 
                             depth,
                             g_pYBWCManagerInstance->pWorkAvailableResult->nDepth);
        }
      }
    } // if(g_pYBWCManagerInstance->bSearchingSubproblem)

// kh 13.02.07 skip to the final search depth if the skip level is reached (i.e. break the IID 
// at that level and skip)
    if(    (g_pYBWCManagerInstance->pFruitConfiguration->nSlaveIIDDepthSkipToMax > 0)
        && (depth >= g_pYBWCManagerInstance->pFruitConfiguration->nSlaveIIDDepthSkipToMax) 
        && g_pYBWCManagerInstance->bSearchingSubproblem)
    {
      ASSERT(depth <= g_pYBWCManagerInstance->pWorkAvailableResult->nDepth);
      depth = g_pYBWCManagerInstance->pWorkAvailableResult->nDepth;
    }

	  for(SearchCurrent->multipv = 0; SearchCurrent->multipv <= SearchInput->multipv; SearchCurrent->multipv++) // kh 10.04.07 Thomas Gaksch
    {


// kh 10.04.07 Thomas Gaksch
		  if(DispDepthStart && SearchCurrent->multipv == 0) 
//    if(DispDepthStart) 
      {
        send("info depth %d", depth);
      }
		  SearchCurrent->max_extensions = depth;

// kh 04.06.08 Thomas Gaksch 14b5c
  	  SearchCurrent->act_iteration  = depth;

      SearchRoot->bad_1             = false;
      SearchRoot->change            = false;

      board_copy(SearchCurrent->board, SearchInput->board);

      if(    UseShortSearch 
          && (depth <= ShortSearchDepth)
          && !g_pYBWCManagerInstance->bSearchingSubproblem) 
      {
        search_full_root(SearchRoot->list, SearchCurrent->board, depth, SearchShort);
      } 
      else 
      {
        search_full_root(SearchRoot->list, SearchCurrent->board, depth, SearchNormal);
      }

      search_update_current();

		  if(DispDepthEnd && SearchCurrent->multipv == SearchInput->multipv) // kh 10.04.07 Thomas Gaksch 
//    if(DispDepthEnd) 
      {
        send("info depth %d seldepth %d time %.0f nodes " S64_FORMAT " nps %.0f",
             depth,
             SearchCurrent->max_depth,
             SearchCurrent->time * 1000.0,
             SearchCurrent->node_nb,
             SearchCurrent->speed);
      }

  // kh 15.03.07
      if(g_pYBWCManagerInstance->bSearchingSubproblem)
      {
  //    if(depth >= 14)
        if(false && /* tuning */ SearchCurrent->time >= 10.0) // kh 17.03.07 use seconds here
        {
          YBWCManager_Printf(g_pYBWCManagerInstance, 
                             "slaveinfo depth %d seldepth %d time %.0f nodes " S64_FORMAT " local " S64_FORMAT " nps %.0f height/depth %d/%d a=%d b=%d\n",
                             depth,
                             SearchCurrent->max_depth,
                             SearchCurrent->time * 1000.0,
                             SearchCurrent->node_nb,
                             SearchCurrent->node_local_nb,
                             SearchCurrent->speed,
                             g_pYBWCManagerInstance->pWorkAvailableResult->nHeight,
                             g_pYBWCManagerInstance->pWorkAvailableResult->nDepth,
                             g_pYBWCManagerInstance->pWorkAvailableResult->nAlpha,
                             g_pYBWCManagerInstance->pWorkAvailableResult->nBeta);
        }
      }

      // update search info

      if(depth >= 1) 
      {
        SearchInfo->can_stop = true;
      }

  // kh 17.03.07 depth limit is limited to 4 if there exist just one legal move
  // flag is used only for debug purposes (see above)
      if(LIST_SIZE(SearchInput->list) <= 1) 
      {
        bPotentialDepthLimitChangeOk; 
      }

      if(    (depth == 1)
          && (LIST_SIZE(SearchRoot->list) >= 2)
          && (LIST_VALUE(SearchRoot->list, 0) >= LIST_VALUE(SearchRoot->list, 1) + EasyThreshold))
      {
        SearchRoot->easy = true;
      }

      if(UseBad && depth > 1) 
      {
        SearchRoot->bad_2 = SearchRoot->bad_1;
        SearchRoot->bad_1 = false;

// kh 16.04.07 assertion does not hold any longer for toga in multipv mode
//	    ASSERT(SearchRoot->bad_2 == (SearchBest->value <= SearchRoot->last_value - BadThreshold));
  	    ASSERT(    (SearchRoot->bad_2 == (SearchBest[0].value <= SearchRoot->last_value - BadThreshold))
                || (SearchInput->multipv > 0));
      }

// kh 10.04.07 Thomas Gaksch
		  SearchRoot->last_value = SearchBest[0].value;

      // stop search?

// kh 10.04.07 Thomas Gaksch
		  if(    SearchInput->depth_is_limited && SearchCurrent->multipv >= SearchInput->multipv
//    if(    SearchInput->depth_is_limited
          && depth >= SearchInput->depth_limit) 
      {
        SearchRoot->flag = true;
      }

      if(    SearchInput->time_is_limited
          && SearchCurrent->time >= SearchInput->time_limit_1
          && !SearchRoot->bad_2) 
      {
        SearchRoot->flag = true;
      }

      if(    UseEasy
          && SearchInput->time_is_limited
          && SearchCurrent->time >= SearchInput->time_limit_1 * EasyRatio
          && SearchRoot->easy) 
      {
        ASSERT(!SearchRoot->bad_2);
        ASSERT(!SearchRoot->change);
        SearchRoot->flag = true;
      }

      if(    UseEarly
          && SearchInput->time_is_limited
          && SearchCurrent->time >= SearchInput->time_limit_1 * EarlyRatio
          && !SearchRoot->bad_2
          && !SearchRoot->change) 
      {
        SearchRoot->flag = true;
      }

      if(    SearchInfo->can_stop
          && (SearchInfo->stop || (SearchRoot->flag && !SearchInput->infinite))) 
      {
			  search_ready = true;
        break;
      }

      if(SearchInfo->stop)
      {
        if(g_pYBWCManagerInstance->bRootMaster)
        {
        }
        else
        {
          if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_ERROR_PRIO_1)
          {
            YBWCManager_Printf(g_pYBWCManagerInstance, "ERROR search(... failed at missing break for SearchInfo->stop\n");
          }
        } 
      } // if(SearchInfo->stop)
    } // for(SearchCurrent->multipv = 0; SearchCurrent->multipv <= SearchInput->multipv; SearchCurrent->multipv++) // kh 10.04.07 Thomas Gaksch

// kh 10.04.07 Thomas Gaksch
    if(search_ready)
    {
		  break;
    }

  } // for(depth = nDepthStart; depth < DepthMax; depth++) 
}

// search_update_best()

void search_update_best() 
{
  int         move;
  int         value; 
  int         flags; 
  int         depth; 
  int         max_depth;

  const mv_t* pv;
  double      time;
  sint64      node_nb;
  int         mate;

// kh 10.04.07 Thomas Gaksch
  int         i;
  int         z;
  bool        found;

  char        move_string [256];
  char        pv_string   [512];

  search_update_current();

  if(DispBest) 
  {

// kh 10.04.07 start Thomas Gaksch
    move  = SearchBest[SearchCurrent->multipv].move;
    value = SearchBest[SearchCurrent->multipv].value;
    flags = SearchBest[SearchCurrent->multipv].flags;
    depth = SearchBest[SearchCurrent->multipv].depth;
    pv    = SearchBest[SearchCurrent->multipv].pv;

/*
    move  = SearchBest->move;
    value = SearchBest->value;
    flags = SearchBest->flags;
    depth = SearchBest->depth;
    pv    = SearchBest->pv;
*/
// kh 10.04.07 end Thomas Gaksch

    max_depth = SearchCurrent->max_depth;
    time      = SearchCurrent->time;
    node_nb   = SearchCurrent->node_nb;

    move_to_string(move, move_string, 256);
    pv_to_string(pv, pv_string, 512);

    mate = value_to_mate(value);

// kh 10.04.07 start Thomas Gaksch
	  if(SearchCurrent->multipv == 0)
    {
		  save_multipv[SearchCurrent->multipv].mate       = mate;
		  save_multipv[SearchCurrent->multipv].depth      = depth;
		  save_multipv[SearchCurrent->multipv].max_depth  = max_depth;
		  save_multipv[SearchCurrent->multipv].value      = value;
		  save_multipv[SearchCurrent->multipv].time       = time * 1000.0;
		  save_multipv[SearchCurrent->multipv].node_nb    = node_nb;
		  strcpy(save_multipv[SearchCurrent->multipv].pv_string, pv_string); 
	  }
	  else
    {
		  found = false;
		  for(i = 0; i < SearchCurrent->multipv; i++)
      {
			  if(save_multipv[i].value < value)
        {
				  found = true;
				  break;
			  }
		  }
		  if(found)
      {
			  for(z = SearchCurrent->multipv; z > i; z--)
        {
				  save_multipv[z].mate      = save_multipv[z-1].mate;
				  save_multipv[z].depth     = save_multipv[z-1].depth;
				  save_multipv[z].max_depth = save_multipv[z-1].max_depth;
				  save_multipv[z].value     = save_multipv[z-1].value;
				  save_multipv[z].time      = save_multipv[z-1].time;
				  save_multipv[z].node_nb   = save_multipv[z-1].node_nb;
				  strcpy(save_multipv[z].pv_string, save_multipv[z-1].pv_string); 
			  }
			  
			  save_multipv[i].mate      = mate;
		    save_multipv[i].depth     = depth;
		    save_multipv[i].max_depth = max_depth;
		    save_multipv[i].value     = value;
		    save_multipv[i].time      = time * 1000.0;
		    save_multipv[i].node_nb   = node_nb;
		    strcpy(save_multipv[i].pv_string, pv_string); 
		  }
		  else
      {
			  save_multipv[SearchCurrent->multipv].mate       = mate;
			  save_multipv[SearchCurrent->multipv].depth      = depth;
			  save_multipv[SearchCurrent->multipv].max_depth  = max_depth;
			  save_multipv[SearchCurrent->multipv].value      = value;
			  save_multipv[SearchCurrent->multipv].time       = time * 1000.0;
			  save_multipv[SearchCurrent->multipv].node_nb    = node_nb;
			  strcpy(save_multipv[SearchCurrent->multipv].pv_string, pv_string); 
		  }
	  }
	  
    if (depth > 1 || (depth == 1 && SearchCurrent->multipv == SearchInput->multipv))
    {
		  for(i = 0; i <= SearchInput->multipv; i++)
      {
			  if(save_multipv[i].mate == 0) 
        {
// kh 10.04.07 end Thomas Gaksch

       // normal evaluation

          if(false) 
          {
          } 
          else if(flags == SearchExact) 
          {

// kh 10.04.07 Thomas Gaksch
  					send("info multipv %d depth %d seldepth %d score cp %d time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].value,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
//          send("info depth %d seldepth %d score cp %d time %.0f nodes " S64_FORMAT " pv %s",depth,max_depth,value,time*1000.0,node_nb,pv_string);

          } 
          else if(flags == SearchLower) 
          {

// kh 10.04.07 Thomas Gaksch
					  send("info multipv %d depth %d seldepth %d score cp %d lowerbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].value,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
//          send("info depth %d seldepth %d score cp %d lowerbound time %.0f nodes " S64_FORMAT " pv %s",depth,max_depth,value,time*1000.0,node_nb,pv_string);

          } 
          else if(flags == SearchUpper) 
          {

// kh 10.04.07 Thomas Gaksch
					  send("info multipv %d depth %d seldepth %d score cp %d upperbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].value,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
//          send("info depth %d seldepth %d score cp %d upperbound time %.0f nodes " S64_FORMAT " pv %s",depth,max_depth,value,time*1000.0,node_nb,pv_string);

          }
        } 
        else 
        {
          // mate announcement

          if(false) 
          {
          } 
          else if(flags == SearchExact) 
          {

// kh 10.04.07 Thomas Gaksch
  					send("info multipv %d depth %d seldepth %d score mate %d time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].mate,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
//          send("info depth %d seldepth %d score mate %d time %.0f nodes " S64_FORMAT " pv %s",depth,max_depth,mate,time*1000.0,node_nb,pv_string);

          } 
          else if(flags == SearchLower) 
          {

// kh 10.04.07 Thomas Gaksch
  					send("info multipv %d depth %d seldepth %d score mate %d lowerbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].mate,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
//          send("info depth %d seldepth %d score mate %d lowerbound time %.0f nodes " S64_FORMAT " pv %s",depth,max_depth,mate,time*1000.0,node_nb,pv_string);

          } 
          else if(flags == SearchUpper) 
          {

// kh 10.04.07 Thomas Gaksch
  					send("info multipv %d depth %d seldepth %d score mate %d upperbound time %.0f nodes " S64_FORMAT " pv %s",i+1,save_multipv[i].depth,save_multipv[i].max_depth,save_multipv[i].mate,save_multipv[i].time,save_multipv[i].node_nb,save_multipv[i].pv_string);
//          send("info depth %d seldepth %d score mate %d upperbound time %.0f nodes " S64_FORMAT " pv %s",depth,max_depth,mate,time*1000.0,node_nb,pv_string);

          }
        }
      }
    }
  }

  // update time-management info

  if(UseBad && SearchBest[SearchCurrent->multipv].depth > 1) // kh 10.04.07 Thomas Gaksch
//if(UseBad && SearchBest->depth > 1) 
  {
    if(SearchBest[SearchCurrent->multipv].value <= SearchRoot->last_value - BadThreshold) // kh 10.04.07 Thomas Gaksch
//  if(SearchBest->value <= SearchRoot->last_value - BadThreshold) 
    {
      SearchRoot->bad_1 = true;
      SearchRoot->easy  = false;
      SearchRoot->flag  = false;
    } 
    else 
    {
      SearchRoot->bad_1 = false;
    }
  }
}

// search_update_root()

void search_update_root() 
{
  int     move;
  int     move_pos;
  int     move_nb;
  double  time;
  sint64  node_nb;
  char    move_string[256];

  int     nId;

  if(DispRoot) 
  {
    search_update_current();

    if(SearchCurrent->time >= 1.0) 
    {
      move      = SearchRoot->move;
      move_pos  = SearchRoot->move_pos;
      move_nb   = SearchRoot->move_nb;

      time      = SearchCurrent->time;
      node_nb   = SearchCurrent->node_nb;

      move_to_string(move, move_string, 256);

      if(g_pYBWCManagerInstance->pFruitConfiguration->bSendAdditionalUCIInfo)
      {
        nId = g_pYBWCManagerInstance->pStack->stackEntry[0].SlaveList[move_pos];
        ASSERT((nId == -1) || (nId > 0));

        if(nId == -1) // kh 24.01.07 locally searched by the root master itself
        {
          nId = 0;
        }

        send("info currmove %s currmovenumber %d currprocessorid %d",
             move_string,
             move_pos + 1,
             nId);

/*
        send("info currmove %s currmovenumber %d currprocessorid %d currtimestamp %s",
             move_string,
             move_pos + 1,
             nId,
             YBWCManager_TimeStampAsString(g_pYBWCManagerInstance));
*/

      }
      else
      {

// kh 25.01.07 standard info 
        send("info currmove %s currmovenumber %d",
              move_string,
              move_pos + 1);
      }
    }
  }
}

// kh 02.02.07
// post_search_update_current()

void post_search_update_root(int nMoveListIndex) 
{
  int         move;
  int         move_pos;
//int         move_nb;
  double      time;
  sint64      node_nb;
  char        move_string[256];

  int         nId;

  double      dTime;
  double      dSpeed;
  sint64      nNodes;

  StackEntry* pStackEntryRoot;

  if(DispRoot) 
  {
//  search_update_current();

//  if(SearchCurrent->time >= 1.0) 
    {
//    move      = SearchRoot->move;
      move      = g_pYBWCManagerInstance->pStack->stackEntry[0].MoveList[nMoveListIndex];
//    move_pos  = SearchRoot->move_pos;
      move_pos  = nMoveListIndex;

//    move_nb   = SearchRoot->move_nb;

      time      = SearchCurrent->time;
      node_nb   = SearchCurrent->node_nb;

      move_to_string(move, move_string, 256);

      if(g_pYBWCManagerInstance->pFruitConfiguration->bSendAdditionalUCIInfo)
      {
        pStackEntryRoot = &g_pYBWCManagerInstance->pStack->stackEntry[0];

        nId = pStackEntryRoot->SlaveList[move_pos];

        ASSERT((nId == -1) || (nId > 0));

        if(nId == -1) // kh 24.01.07 locally searched by the root master itself
        {
          nId = 0;
        }

        search_update_current();

        pStackEntryRoot->TimeList[move_pos] = 
          SearchCurrent->time - pStackEntryRoot->TimeList[move_pos];

        ASSERT(pStackEntryRoot->TimeList[move_pos] >= 0.0);

        dTime   = pStackEntryRoot->TimeList[move_pos];
        nNodes  = pStackEntryRoot->NodesList[move_pos];

        dSpeed = 0.0;
        if(dTime >= 1.0)
        {
          dSpeed = double(nNodes) / dTime;
        }

        send("info postmove %s postmovenumber %d postprocessorid %d posttime %.0f postnodes " S64_FORMAT " postnps %.0f postworkalpha %d postworkbeta %d posteval % d posttimestamp %s - %s",
             move_string,
             move_pos + 1,
             nId,
             dTime * 1000.0,
             nNodes,
             dSpeed,
             pStackEntryRoot->AlphaList[move_pos],
             pStackEntryRoot->BetaList[move_pos],
             pStackEntryRoot->EvalList[move_pos],
             pStackEntryRoot->TimeStampList[move_pos],
             YBWCManager_TimeStampShortAsString(g_pYBWCManagerInstance));
      }
      else
      {

// there is nothing to send if additional uci info is not wanted
/*
// kh 25.01.07 standard info 
        send("info currmove %s currmovenumber %d",
              move_string,
              move_pos + 1);
*/

      }
    }
  }
}

// search_update_current()

void search_update_current() 
{
  my_timer_t* timer;
  sint64      node_nb;
  double      time;
  double      speed;
  double      cpu;

  if(g_pYBWCManagerInstance->nState == YBWC_MANAGER_STATE_SEARCHING_REMOTE)
  {
    // kh 26.09.06 do not update here, use the values received from remote processor directly
  }
  else
  {
    timer = SearchCurrent->timer;

    node_nb = SearchCurrent->node_nb;
    time = (UseCpuTime) ? my_timer_elapsed_cpu(timer) : my_timer_elapsed_real(timer);
    speed = (time >= 1.0) ? double(node_nb) / time : 0.0;
    cpu = my_timer_cpu_usage(timer);

    g_pYBWCManagerInstance->dTimeUsedLast = time;

    SearchCurrent->time   = time;
    SearchCurrent->speed  = speed;
    SearchCurrent->cpu    = cpu;
  }
}

// search_check()

void search_check()
{
  search_send_stat();

  if(g_pYBWCManagerInstance->pFruitConfiguration->bUseEvent) 
  {
    event();
  }

  if(    SearchInput->depth_is_limited
      && SearchRoot->depth > SearchInput->depth_limit) 
  {
    SearchRoot->flag = true;
  }

  if(    SearchInput->time_is_limited
      && SearchCurrent->time >= SearchInput->time_limit_2) 
  {
    SearchRoot->flag = true;
  }

  if    (SearchInput->time_is_limited
     && SearchCurrent->time >= SearchInput->time_limit_1
     && !SearchRoot->bad_1
     && !SearchRoot->bad_2
     && (!UseExtension || SearchRoot->move_pos == 0)) 
  {
    SearchRoot->flag = true;
  }

  if(    SearchInfo->can_stop
      && (    SearchInfo->stop 
           || (SearchRoot->flag && !SearchInput->infinite)))
  {
    longjmp(SearchInfo->buf, 1);
  }

  if(SearchInfo->stop)
  {
    if(g_pYBWCManagerInstance->bRootMaster)
    {
    }
    else
    {
      if(g_pYBWCManagerInstance->pFruitConfiguration->nFruitDebugLevel >= FRUIT_DEBUG_LEVEL_ERROR_PRIO_1)
      {
        YBWCManager_Printf(g_pYBWCManagerInstance, "ERROR search_check(... failed at missing longjmp(... for SearchInfo->stop\n");
      }
    } 
  } // if(SearchInfo->stop)
}

// search_send_stat()

static void search_send_stat() {

   double time, speed, cpu;
   sint64 node_nb;

   search_update_current();

   if (DispStat && SearchCurrent->time >= SearchInfo->last_time + 1.0) { // at least one-second gap

      SearchInfo->last_time = SearchCurrent->time;

      time = SearchCurrent->time;
      speed = SearchCurrent->speed;
      cpu = SearchCurrent->cpu;
      node_nb = SearchCurrent->node_nb;

      send("info time %.0f nodes " S64_FORMAT " nps %.0f cpuload %.0f",time*1000.0,node_nb,speed,cpu*1000.0);

      trans_stats(Trans);
   }
}

// end of search.cpp
