// Copyright 1987-1997 by Jon Dart.  All Rights Reserved.

#include "stdafx.h"
#include "bearing.h"
#include "search.h"
#include "scoring.h"
#include "constant.h"
#include "movegen.h"
#include "moveord.h"
#include "util.h"
#include "rmove.h"
#include "pinfo.h"
#include "attacke.h"
#include "log.h"
#ifdef _WINDOWS
#include "clock.h"
#include "display.h"
#include "resource.h"
#include "mainfrm.h"
#endif
#include "options.h"
#include "globals.h"
#include "notation.h"
#include "pool.h"   
#include "debug.h"
#ifdef _WINDOWS
static const UINT SEARCH_TIMER = 2;
#endif
#ifdef _TRACE
#include <iostream.h>
#endif
#include <limits.h>
#include <process.h>
#include <stdio.h>
#include <wincon.h>

const int Illegal = -Constants::BIG - 1000;

#ifdef _WINDOWS
int num_searches = 0;
static Search *searches[MAX_SEARCHES];
#endif

#define HINT_WINDOW 40

#ifdef _WINDOWS
#ifdef _WIN32
void FAR PASCAL TimerProc( HWND hWnd, UINT /*msg*/, UINT wParam, 
DWORD /*lParam*/)
#else
void FAR PASCAL _export TimerProc( HWND hWnd, UINT /*msg*/, UINT wParam, 
DWORD /*lParam*/)
#endif
{
    // timer callback function
    time_t current_time = GetTickCount()/10;
    Search *searcher = searches[wParam-SEARCH_TIMER];
    if (searcher->was_terminated())
        return;
    const Search_Type src_type = searcher->get_search_type();
    if (src_type != Fixed_Ply &&
       current_time - searcher->get_start_time() > searcher->get_time_limit())
       searcher->set_time_up(TRUE);
    the_clock->update( );
    if (!searcher->is_background_search())
    {
       Display::show_search_counts(hWnd,
         searcher->get_ply(),searcher->get_numnodes());
       CMainFrame *frame = (CMainFrame*)AfxGetMainWnd();
       frame->update(searcher->get_numnodes());
    }
}
#endif

Search::Statistics::Statistics()
{
   clear();
}

void Search::Statistics::clear()
{
   state = Normal;
   value = 0;
   for (int i = 0; i < Constants::MaxPly; i++)
       best_line[i].MakeNull();
   elapsed_time = 0;
   *best_line_image = '\0';
   num_moves = num_nodes = num_qnodes = depth = 0;
}

Search::Search()
: hash_table(NULL),ply0moves(NULL),ply0scores(NULL),time_check_counter(0),
  command_function(NULL),post_function(NULL),terminate_function(NULL)
{
#ifdef _WINDOWS
   InitializeCriticalSection(&searchCritSection);
#else
    HANDLE inh = GetStdHandle(STD_INPUT_HANDLE);
    DWORD dw;
    pipe = !GetConsoleMode(inh, &dw);
    if (!pipe)
    {
       SetConsoleMode(inh, dw & ~(ENABLE_LINE_INPUT |
        ENABLE_MOUSE_INPUT | ENABLE_WINDOW_INPUT));
    }
#endif   
    ply0moves = new Move[Move_Generator::MaxMoves];
    ply0scores = new int[Move_Generator::MaxMoves];
    for (int i = 0; i < Constants::MaxPly; i++)
       moves_generated[i] = new Move[Move_Generator::MaxMoves];
}
    
Search::~Search()
{
    cleanup(TRUE);
#ifdef _WINDOWS
    DeleteCriticalSection(&searchCritSection);
#endif
}
    
void Search::terminate_now(BOOL m)
{
    time_up = terminated = TRUE;
#ifdef _WINDOWS
    makeMove = m;
#endif
}

#ifdef _TRACE
static void indent(const int ply)
{
   for (int k = 0; k < ply; k++) cout << ' ';
}
#endif

static BOOL is_move(char *buf)
{
   if (isalpha(*buf) && isdigit(buf[1]) &&
       isalpha(buf[2]) && isdigit(buf[3]))
       return TRUE;
   else if (strcmp(buf,"o-o")==0 || strcmp(buf,"O-O")==0 ||
      strcmp(buf,"o-o-o")==0 || strcmp(buf,"O-O-O") ==0)
       return TRUE;
   else
       return FALSE;
}

#ifndef _WINDOWS
BOOL Search::check_input()
{
     DWORD nchar;
     DWORD dw;
     if (pipe)
     {
     // Use the GnuChess trick of calling PeekNamedPipe to check
     // for user input.  We need to do this because Winboard does
     // not send ^C to interrupt pondering. 
     if (PeekNamedPipe(GetStdHandle(STD_INPUT_HANDLE), NULL, 0, 
         NULL, &nchar, NULL)) 
     {
//        if (nchar) cout << "got console input nchar=" << nchar << endl;
        int nextc;
        BOOL terminate;
        for (unsigned i = 0; i < nchar; i++)
        {
          nextc=getc(stdin);
//          cout << "got: " << (char)nextc << endl;
          if (nextc == '\n') 
          {
             cmd_buf[cmd_buf_count]  = '\0';
             cmd_buf_count = 0;
             // call a function (supplied by the calling code) that
             // sets terminate = TRUE if we should terminate.
             command_function(cmd_buf,terminate);
             if (terminate)
             {
                 return TRUE;
             }
             break;
          }
          else
             cmd_buf[cmd_buf_count++] = nextc;
          //ungetc(nextc,stdin);
       }
       // Hack alert.  Under Windows 95 we sometimes get a move
       // with no trailing carriage return.  Doesn't happen under NT.
       if (cmd_buf_count > 0)
       {
          cmd_buf[cmd_buf_count] = '\0';
          if (is_move(cmd_buf))
          {
//             cout << "got move w/o <CR>: " << cmd_buf << endl;
             cmd_buf_count = 0;
             command_function(cmd_buf,terminate);
             if (terminate)
             {
                 return TRUE;
             }
          }  
       }
    }
    } else {
      // We are reading from the console, not connected to Winboard.
      // Not something we usually do, except for testing.
      int retVal = WaitForSingleObject(GetStdHandle(STD_INPUT_HANDLE), 0);
      if (retVal == WAIT_OBJECT_0)
      {
        INPUT_RECORD recBuf[128];
        ReadConsoleInput(GetStdHandle(STD_INPUT_HANDLE),recBuf,
          128,&dw);
        for (unsigned i = 0; i < dw; i++)
        {
          if (!recBuf[i].Event.KeyEvent.bKeyDown) continue;
          char nextc=recBuf[i].Event.KeyEvent.uChar.AsciiChar;
          if (nextc == (char)13 /* carriage return */) 
          {
             putchar('\n');
             cmd_buf[cmd_buf_count]  = '\0';
             cmd_buf_count = 0;
             BOOL terminate;
             // call a function (supplied by the calling code) that
             // sets terminate = TRUE if we should terminate.
             command_function(cmd_buf,terminate);
             if (terminate)
             {
                 return TRUE;
             }
             break;
          }
          else
          {
             putchar(nextc);
             cmd_buf[cmd_buf_count++] = nextc;
          }
        }
      }
    }
    return FALSE;
}
#endif

BOOL Search::check_time(int ply, int rank)
{
    if (terminated)
        return TRUE;
#ifndef _WINDOWS
    if (command_function && check_input())
    {
        terminate_now();
        return TRUE;
    }
#endif
    if (type_of_search != Fixed_Ply)
    {
       int current_time = (int)(GetTickCount()/10);
       if(current_time - (int)get_start_time() > (int)get_time_limit())
       {
           terminate_now(TRUE);
           return TRUE;
       }
       if (type_of_search == Time_Limit)
       {
           return FALSE;
       }
       // Allow terminating early if this is a recapture, appeared
       // better than everything else at initial sort time, and
       // still looks good.
       if (!time_up && easy && iteration_depth >= 4)
       {
           // require that we have consumed at least 1/3 of the time
           // limit:
           current_time = GetTickCount()/10;
           if (time_target >= 100 &&
               (current_time - get_start_time())*3 > time_target)
           {
              if (pv[0] == easy_move)
              {
                //::MessageBox(NULL,"easy move","",MB_OK);
                time_up = TRUE;
                terminate_now(TRUE);
                return TRUE;
              }
           }
       }
    }
    if( time_up)
    {
        terminate_now(TRUE);
    }
    return time_up;
}

// To reduce the chance of a hash collision, we do some elementary
// testing on moves returned by the hash table, to help weed out
// any that are invalid in the current board position ..
static BOOL hash_move_valid( const Board &board, const Move &move)
{
    if (move.IsNull())
        return TRUE;
    Piece p = board[move.StartSquare()];
    if (!p.IsEmpty() && p.Color() == board.Side())
    {
        p = board[move.DestSquare()];
        if (p.IsEmpty() || p.Color() != board.Side())
        {
           ExtendedMove emove(board,move);
           if (emove.Special() == ExtendedMove::KCastle)
           {
              return (board.CastleStatus(board.Side()) ==
                     Board::CanCastleKSide) ||
                     (board.CastleStatus(board.Side()) ==
                     Board::CanCastleEitherSide);
           }
           else if (emove.Special() == ExtendedMove::QCastle)
           {
              return (board.CastleStatus(board.Side()) ==
                     Board::CanCastleQSide) ||
                     (board.CastleStatus(board.Side()) ==
                     Board::CanCastleEitherSide);
           }
           else
              return TRUE;
        }
        else
           return FALSE;
    }
    else
        return FALSE;
}

void Search::show_status(const Board &board, const char ch,
                        const Search::Statistics &stats, const Move &move)
{
    if (hint || terminated)
       return;
    int ply = stats.depth;
    ExtendedMove emove(board,move);
    static char move_text[20];
    Notation::Image(board, move, move_text);
    char val[20];
    sprintf(val,"%6.2f",stats.value/64.0);
    if (talkLevel == Whisper || talkLevel == Trace)
    {
       if (stats.elapsed_time >= 300 && time_target > 500)
       {
          if (talkLevel == Whisper)
             cout << "whisper ply " << ply;
          else
             cout << "(debug) ply " << ply;
          if (ply < 10) cout << ".  "; else cout << ". ";
          cout << move_text << " score: " << val << " " <<
                  "time: " << stats.elapsed_time/100 << " secs. nodes: " <<
                  stats.num_nodes << endl;
       }
/**
       if ((stats.state == Search::Normal || stats.state == Search::Check) &&
         (stats.value > Constants::BIG-100))
       {
          char text[30];
          if (stats.value != Constants::BIG-1)
             wsprintf(text,"whisper mate in %d!",(Constants::BIG-stats.value-1)/2);
       }
**/
    }
    else if (talkLevel == Debug)
    {
         cout << "ply " << ply;
         if (ply < 10) cout << ".  "; else cout << ". ";
         cout << move_text << '\t' << stats.elapsed_time/100 << 
            " seconds.\tscore: " << val  << "\t" <<
            stats.num_nodes << " nodes." << endl;
    }
    if (!is_background_search())
    {
#ifdef _WINDOWS
       CMainFrame *frame = (CMainFrame*)AfxGetMainWnd();
       frame->update(ply,stats.num_nodes,(float)(stats.value/64.0),
         stats.best_line_image);
#else
       if (post_function) post_function(stats);
#endif
    }
}

void Search::set_background(BOOL b)
{
    bkgrnd_search = b;
    if (!b)
    {
       // changing from background to foreground search,
       // update display
       Statistics stats;
       update_stats(stats);
       show_status(initial_board,0,stats,pv[0]);
       // We are in the foreground now, run at normal priority
       SetThreadPriority(GetCurrentThread(),THREAD_PRIORITY_NORMAL);
    }
}
    
BOOL Search::is_draw( const Board &board, int &rep_count, int ply)
{
    // check for draws due to repetition or insufficient material.

    // First check for draw by repetition
    int entries = board.move_count-2;
    hash_t to_match = board.HashCode();
    rep_count = 0;
    for (hash_t *rep_list=board.rep_list_head-3;
         entries>0;
         rep_list-=2,entries-=2)
    {
       if(*rep_list == to_match) 
       {
            rep_count++;
            if (rep_count >= 3 ||
                (rep_count == 2 && board.rep_list_head-rep_list <= ply))
                return TRUE;
/**
            if (rep_count >= 1) 
            {
               if (ply == 0)
               {  
                  if (rep_count >= 3)
                     return TRUE;
               }
               else
                  return TRUE;
            }
**/
       }
    }
    // check for insufficient material
    const Material &mat1 = board.getMaterial(board.Side());
    const Material &mat2 = board.getMaterial(board.OppositeSide());
    unsigned pcount1 = mat1.count(Piece::Pawn);
    unsigned pcount2 = mat2.count(Piece::Pawn);
    if (pcount1 || pcount2)
       return FALSE;
    const uint16 king_value = Piece::Value(Piece::King);
    const uint16 bishop_value = Piece::Value(Piece::Bishop);
    if ((mat1.value() <= king_value + bishop_value) &&
        (mat2.value() <= king_value + bishop_value))
    {
        if (mat1.king_only() || mat2.king_only())
        // K vs K, or K vs KN, or K vs KB
           return TRUE;
        else if (mat1.count(Piece::Knight) || mat2.count(Piece::Knight))
        {
           // KN vs KN 
           return FALSE;
        }
        else
        {
           int i = 0;
           int d1 = -1;
           int d2 = -1;
           Bitmap bishops = board.bishop_bits[White];
           bishops.or(board.bishop_bits[Black]);
           while (!bishops.is_clear())
           {
              Square sq(bishops.FirstOne());
              bishops.clear(sq);
              if (board[sq].Color() == White)
              {
                  d1 = (sq.Rank(board.Side()) + sq.File()) % 2;
              }
              else
              { 
                  d2 = (sq.Rank(board.Side()) + sq.File()) % 2;
              }
           } 
           // drawn if same-color bishops:
           return (d1 == d2);
        }
    }
    return FALSE;
}

int Search::evalu8(const Board & board)
{
    // evaluate a board position.
    int score = Scoring::material_score(board);
    score += Scoring::positional_score(board) +
             Scoring::king_safety(board);
    return score;
}

int Search::evalu8(const Board & board, int alpha, int beta, int ply)
{
    // Evaluate a board position.  Try to avoid computing
    // the positional score, if we can get a cutoff without
    // computing it.
    const ColorType side = board.Side();
    int score = Scoring::material_score(board);
    if (score + min_pos_score[ply][side] + min_ks_score[ply][side] > beta)
    {
        return beta;
    }
    else if (score + max_pos_score[ply][side] + max_ks_score[ply][side] < alpha)
    {
        return alpha;
    }
    // Can't cut off using material score, so add positional score
    int pos_score = Scoring::positional_score(board);
    if (pos_score > max_pos_score[ply][side])
       max_pos_score[ply][side] = pos_score;
    if (pos_score < min_pos_score[ply][side])
       min_pos_score[ply][side] = pos_score;
    score += pos_score;
    if (!Scoring::in_endgame(board))
    {
    if (score + min_ks_score[ply][side] > beta)
    {
        return beta;
    }
    else if (score + max_ks_score[ply][side] < alpha)
    {
        return alpha;
    }
    int ks_score = Scoring::king_safety(board);
    if (ks_score > max_ks_score[ply][side])
        max_ks_score[ply][side] = ks_score;
    if (ks_score < min_ks_score[ply][side])
        min_ks_score[ply][side] = ks_score;
    score += ks_score;
    }
    if (score < alpha)
        score = alpha;

    return score;
}

int Search::draw_score(const Board &board, int ply)
{
    int score = 0;

    // A draw is worse if there is a lot of material on the board
    if (root_total_mat > 6000)
    {
        score -= 25;
    }
    else if (root_total_mat > 4800)
    {
        score -= 25*(root_total_mat-4800)/1200;
    }
    // Penalize the side to move for allowing a draw if it is ahead in
    // material
    if (Util::Abs(root_material_score) >= 128)
    {
        if (root_material_score > 0)
            score -= (root_material_score-128)/8;
        else
            score -= (root_material_score+128)/8;
    }
    return -score;
}

// calculate a "stand pat" score for the q-search
int Search:: pat_score(const Board &board,int alpha,int beta,int ply)
{
    int score = Scoring::material_score(board);
    const ColorType side = board.Side();
    if (score + min_pos_score[ply][side] + min_ks_score[ply][side] > beta)
    {
        return beta;
    }
    else if (score + max_pos_score[ply][side] + max_ks_score[ply][side] < alpha)
    {
        return alpha;
    }
    int pos_score;
    pos_score = Scoring::positional_score(board);
    if (pos_score > max_pos_score[ply][side])
       max_pos_score[ply][side] = pos_score;
    if (pos_score < min_pos_score[ply][side])
       min_pos_score[ply][side] = pos_score;
    score += pos_score;
    if (!Scoring::in_endgame(board))
    {
    if (score + min_ks_score[ply][side] > beta)
    {
        return beta;
    }
    else if (score + max_ks_score[ply][side] < alpha)
    {
        return alpha;
    }
    int ks_score = Scoring::king_safety(board);
    if (ks_score > max_ks_score[ply][side])
        max_ks_score[ply][side] = ks_score;
    if (ks_score < min_ks_score[ply][side])
        min_ks_score[ply][side] = ks_score;
    score += ks_score;
    }
    return score;
}

unsigned Search::
generate_moves(
               Board & board, Move_Generator & mg,
               const unsigned ply,
               Move * moves)
{
    int i, n;
    if (ply == 0)
    {
        n = ply0move_count;
        // re-order the ply 0 moves in the following order: pv
        // first, then the two killer moves (if non-null), then
        // everything else.
        Move killer1(Move_Ordering::get_killer(0,0));
        Move killer2(Move_Ordering::get_killer(0,1));
        int j = 0;
        if (!pv[0].IsNull())
        {
           moves[j++] = pv[0];
        }
        if (ply0move_count > 0 && !killer1.IsNull() && pv[0] !=
        killer1)
        {
           moves[j++] = killer1;
        }
        if (ply0move_count > 1 && !killer2.IsNull() && pv[0] != killer2
           && killer1 != killer2)
        {
           moves[j++] = killer2;
        }
        for (i = 0; i < ply0move_count; i++)
        {
            if (ply0moves[i] != pv[0] && ply0moves[i] != killer1 &&
                ply0moves[i] != killer2)
            {
                moves[j++] = ply0moves[i];
            }
        }
    }
    else
    {
       n = mg.Generate_Moves(moves);
       num_moves += n;
       Move_Ordering::order_moves(board, moves, n, ply,
          pv[ply]);
    }

    return n;
}

int Search::
move_search(Board & board, int alpha, int beta,
            const int ply, int depth, BOOL in_pv,
            BOOL &terminate)
{
    // recursive function, implements alpha/beta search.  We use
    // the PVS (principal variation search) variant of alpha/beta.

    ASSERT(ply < Constants::MaxPly);
    time_check_counter++;
    num_nodes++;

    flag_struct flags;
    flags.in_check = flags.forced = FALSE;
    BOOL forced = FALSE;
    BOOL deepFlag = FALSE;
    int extend = 0;
    unsigned move_count = 0;
    unsigned move_index = 0;
    int num_try = 0; // # of legal moves tried
    // moves into check are illegal.
    if (ply > 0)
    {
       if (board.any_attacks(board.KingPos(
           board.OppositeSide()),board.Side()))
           return -Illegal;
    }
    int rep_count;

    if (is_draw(board,rep_count,ply))
    {
#ifdef _TRACE
        cout << "draw!" << endl;
#endif
       return draw_score(board,ply);
    }
    else if (ply >= Constants::MaxPly-1)
    {
        return evalu8(board,alpha,beta,ply);
    }
    int initial_alpha = alpha;
    int score = -Constants::BIG;
    Move best_move, hash_move;

    Position_Info *hash_entry = NULL;      
    if (ply > 0 && hash_table)
    {
        // Search the hash table to see if we have hit this
        // position before.

        Position_Info look(board,rep_count);
        hash_entry = (Position_Info*)hash_table->search(look);
        hash_searches++;
        if (hash_entry)
        {
            hash_move = hash_entry->best_move();
           // Found the position in the hash table.
           if (!hash_move_valid(board,hash_move))
           {
#ifdef _TRACE
              indent(ply);
              cout << "Warning: hash move invalid" << endl;
#endif              
              hash_entry = NULL;
              hash_move.MakeNull();
           }
           else
              hash_hits++;
        }
        if (hash_entry)
        {
            forced = hash_entry->forced();
            board.set_check_status(hash_entry->in_check() ?
             Board::InCheck : Board::NotInCheck);
            if (hash_entry->depth() >= depth)
            {
                int value = hash_entry->value();
                //
                // Whether we can use the hash value or not depends on
                // the flags:
                //
                BOOL valid = FALSE;
#ifdef _TRACE                
                char type;
#endif                
                switch(hash_entry->type())
                {
                   case Position_Info::Valid:
                      //
                      // If this is a mate score, adjust it to reflect the
                      // current ply depth.
                      //
                      if (value > Constants::BIG-100)
                         value -= ply;
                      else if (value < -Constants::BIG+100)
                         value += ply;
#ifdef _TRACE                
                      type = 'E';
#endif                

                       valid = TRUE;
                     break;
                   case Position_Info::UpperBound:
#ifdef _TRACE                
                     type = 'U';
#endif                
                     beta = Util::Min(value,beta);
                     break;
                   case Position_Info::LowerBound:
#ifdef _TRACE                
                     type = 'L';
#endif                
                     alpha = Util::Max(value,alpha);
                     break;
                   default:
                     break;
                }
                pv[ply] = hash_move;
                pv[ply+1] = Move::NullMove();
#ifdef _TRACE
                ExtendedMove emove(board,hash_move);
                indent(ply);
                cout << "hash hit, type = " << type <<
                " move = " << emove.Image() <<
                " alpha = " << alpha << " beta = " << beta << 
                " value = " << value << endl;
#endif
                if (valid)
                {
                   ASSERT(value >= -Constants::BIG && value <= Constants::BIG);
                   return value;
                }
                else if (alpha >= beta && hash_entry->type() != Position_Info::Pv)
                {
                   if (hash_entry->type() == Position_Info::LowerBound)
                       return alpha;
                   else
                       return beta;
                }
            }
        }
    }
#ifdef _TRACE
    if (!hash_move.IsNull())
    {
        indent(ply);
        ExtendedMove ehash_move(board,hash_move);
        cout << "hash move = " << ehash_move.Image() << endl;
    }
#endif

    // At this point we need to know if we are in check or not.
    flags.in_check = checks[ply] = board.CheckStatus() == Board::InCheck;
    
    // Try to get a fast cutoff using a "null move".  Skip if the side
    // to move is in check or if material balance is low enough that
    // zugzwang is a possibility.
    if (null_depth && !terminate && ply > 0 && 
        !in_pv && !flags.in_check && !last_move[ply-1].IsNull() &&
        !board.getMaterial(board.Side()).no_pieces() &&
        !board.getMaterial(board.OppositeSide()).no_pieces())
    {      
        last_move[ply].MakeNull();
        ReversibleMove rmove(board,Move::NullMove()); // null move
        board.MakeMove(rmove);
#ifdef _TRACE        
        indent(ply);
        cout << "trying " << ply << ". " << "(null)" << endl;
#endif
        if ((depth-null_depth-1) >= 0)
           score = -move_search(board, -beta, -alpha,
                                 ply+1, depth-null_depth-1, in_pv,
                                 terminate);
        else 
           score = -quiesce(board, -beta, -alpha,
                                 ply+1, depth-null_depth-1,
                                 terminate);
#ifdef _TRACE
        indent(ply);
        cout << ply << ". " << "(null)" << ' ' << score << endl;
#endif
        board.UndoMove(rmove);
        if (score >= beta) // cutoff
        {
#ifdef _TRACE
           indent(ply);
           cout << "**CUTOFF**" << endl;
#endif           
           goto search_end;
        }
    }

    // Use "internal iterative deepening" to get an initial move to try if
    // there is no hash move .. an idea from Crafty.  Note that we do
    // not try this if we have a hash table entry and no hash move, on
    // the theory that we tried it before and didn't get a move.
    int dscore;
    if (ply >0 && !terminate && hash_move.IsNull() && 
        depth >= 2 &&
//       (depth >= 2 || !Scoring::in_endgame(board)) &&
       (!hash_entry || !hash_entry->deep_flag()))
    {
#ifdef _TRACE
        indent(ply); cout << "== deepening, depth = " << depth-2
            << endl;
#endif
        // Clear the pv because the search is not guaranteed to return
        // a move.  E.g. we may be checkmated.  Also sometimes we
        // will get a null move cutoff in the search.
        pv[ply].MakeNull();
        if (depth - 2 >= 0)
           dscore = move_search(board,alpha,beta,ply,depth-2,in_pv,
                  terminate);
        else
           dscore = quiesce(board,alpha,beta,ply,depth-2,
                  terminate);
        if (dscore <= alpha && !pv[ply].IsNull() && !terminate)
        {
           if (depth - 2 >= 0)
             dscore = move_search(board,-Constants::BIG,beta,
                ply,depth-2,in_pv,terminate);
           else
           {
             dscore = quiesce(board,-Constants::BIG,beta,
                ply,depth-2,terminate);
           }
        }
        if (pv[ply].IsNull()) // don't try this again
           deepFlag = TRUE;
#ifdef _TRACE
        indent(ply); cout << "== deepening done.";
#endif
//        if (dscore < beta)
//        {
            hash_move = pv[ply];
#ifdef _TRACE
            ExtendedMove emove(board,hash_move);
            indent(ply); cout << "  hash_move = "
                << emove.Image();
#endif
//        }
#ifdef _TRACE
        cout << endl;
#endif        
    }
    
    {  
    ExtendedMove the_last_move;

    if (ply != 0)
        the_last_move = last_move[ply - 1];

    BOOL generated_moves = ply == 0;
    Move *moves = moves_generated[ply];
    Move_Generator mg(board, ply, the_last_move);
    if (hash_move.IsNull())
    {
       move_count = generate_moves(board, mg, ply,
                             moves);
       generated_moves = TRUE;
       forced = (move_count == 1);
    }
    else
    {
       // Delay generating the moves, use the hash move 1st.
       // If it causes cutoff, we never need to do full move generation.
       move_count = 1;
       moves[0] = hash_move;
    }
    int try_score;

    if (ply >0)
    {
        // Extend the search one ply for "forced" moves.
        if (forced_extensions && forced && flags.in_check)
          ++extend;
        // Also extend one ply for checks (within a limit)
        else if (check_extensions && 
                 flags.in_check && 
                 (ply+depth) < 2*(int)iteration_depth)
          ++extend;
        else if (pawn_push_extensions && (ply > 1) && 
          !last_move[ply-1].IsNull() &&
          (last_move[ply-1].PieceMoved().Type() == Piece::Pawn) &&
          (last_move[ply-1].DestSquare().Rank(board.OppositeSide()) == 7) &&
          Scoring::in_endgame(board))
          ++extend;
    }
    // If you want to do razoring a la Crafty v. 11, this is where.
    // Search one depth less if way behind in material at this node
    // and there is no reason to extend.  Not currently enabled.
    /**
    if (extend == 0 && !flags.in_check && depth == 1 &&
        Scoring::material_score(board)+64*4/3 < alpha)
      --extend; // negative extension!
    **/
    int new_depth = depth+extend;
    // Do the principal variation
    while (move_index < move_count && !terminate)
    {
        ReversibleMove rmove(board,moves[move_index++]);
#ifdef _TRACE
        if (ply == 0)
          cout << "window = [" << alpha << ',' << beta << ']' << endl;
        indent(ply);
        cout << "trying " << ply << ". " << rmove.Image() << endl;
#endif
        last_move[ply] = rmove;
        board.MakeMove(rmove);
        if (new_depth-1 >= 0)
        {
            try_score = -move_search(board, -beta, -alpha,
                                 ply+1, new_depth-1, in_pv,
                                 terminate);
        }
        else
        {
            try_score = -quiesce(board, -beta, -alpha,
                                 ply+1, new_depth-1, 
                                 terminate);
        }
#ifdef _TRACE
        indent(ply);
        cout << ply << ". " << rmove.Image() << ' ';
        cout << try_score;
        cout << " (pv)";
        cout << endl;
#endif
        board.UndoMove(rmove);
        if (ply == 0) 
        {
           ply0scores[move_index-1] = current_score = try_score;
        }
        if (try_score != Illegal)
        {
            best_move = pv[ply] = last_move[ply];
            score = try_score;
            if (try_score > alpha)
            {
               alpha = try_score;
            }
            num_try++;
            break;
        }
    }
    
    if (score >= beta || terminate) goto beta_cutoff;
    
    // Principal variation done.
    // If num_try == 0, there are no legal moves - means checkmate
    // or stalemate.
    // If the p.v. score is outside the alpha-beta window, we
    // have set the window wrong and must re-search.
    // Otherwise, we proceed to try the non-p.v. moves.
    //
    if (num_try > 0 && !(ply == 0 && (score >= beta || 
        score < initial_alpha))) 
    {
       in_pv = FALSE;
       // Generate the moves if we haven't done so already:
       if (!generated_moves)
       {
          move_count = generate_moves(board, mg, ply, moves);
          move_index = 1; // start at 1 cause we already did the p.v.
       }
       int newalpha = alpha, newbeta;
       if (hint)
       {
           newbeta = alpha + HINT_WINDOW/2;
           newalpha = alpha - HINT_WINDOW/2;
       }
       else
       {
           newbeta = alpha + 1; // zero-width window
       }
       while (move_index < move_count)
       {
           ReversibleMove rmove(board,moves[move_index++]);
#ifdef _TRACE
           if (ply == 0)
             cout << "window = [" << alpha << ',' << alpha+1 << ']' << 
             " beta = " << beta << endl;
           indent(ply);
           cout << "trying " << ply << ". " << rmove.Image() << endl;
#endif
           last_move[ply] = rmove;
           board.MakeMove(rmove);
           if (new_depth-1 >= 0)
           {
               try_score = -move_search(board, -newbeta, -newalpha,
                                  ply+1, new_depth-1,in_pv,terminate);
           }
           else
           {
               try_score = -quiesce(board,  -newbeta, -newalpha,
                                 ply+1, new_depth-1, terminate);
           }
#ifdef _TRACE
           if (try_score != Illegal)
           {
              indent(ply);
              cout << ply << ". " << rmove.Image() << ' ';
              cout << try_score;
              cout << endl;
           }
#endif
           if (ply == 0) ply0scores[move_index-1] = try_score;
           if (terminate)
           {
               board.UndoMove(rmove);
               break;
           }
           else if (try_score == Illegal)
           {
               board.UndoMove(rmove);
               continue;
           }
           num_try++;
           if ((try_score > alpha) && (try_score < beta)) 
           {
              // We failed to get a cutoff and must re-search
#ifdef _TRACE
              indent(ply); cout << "window = [" << alpha << "," << beta
              << "]" << endl;
              indent(ply); cout << "score = " << try_score << " - no cutoff, researching .." << endl;
#endif
              if (new_depth-1 >= 0)
                try_score=-move_search(board,
                   -beta,-try_score,ply+1,new_depth-1,in_pv,terminate);
              else 
                try_score=-quiesce(board,
                   -beta,-try_score,ply+1,new_depth-1, terminate);
#ifdef _TRACE
              indent(ply);
              cout << ply << ". " << rmove.Image() << ' ';
              cout << try_score;
              cout << endl;
#endif
           }
           board.UndoMove(rmove);
           if (time_check_counter >= Constants::Time_Check_Interval)
           {
              time_check_counter = 0;
              terminate = check_time(ply,0);
              if (terminate) // don't allow current move to be selected
                break;
           }
           if (try_score != Illegal && try_score > score)
           {
               // new best move
               score = newalpha = alpha = try_score;
               if (hint)
               {
                  newbeta = alpha + HINT_WINDOW/2;
                  newalpha = alpha - HINT_WINDOW/2;
               }
               else
                  newbeta = alpha + 1; // zero-width window
               best_move = pv[ply] = (ExtendedMove)rmove;
               if (ply == 0) 
               {
                   current_score = score;
                   //if (talkLevel != Silent)
                   //{
                       Search::Statistics stats;
                       update_stats(stats);
                       show_status(board,'>',stats,pv[0]);
                   //}
               }
               if (score >= beta) break;
           }
       }
    }
beta_cutoff: ;
#ifdef _TRACE
    if (score >= beta)
    {
       indent(ply);
       cout << "**CUTOFF**" << endl;
    }
#endif
    }
    if (num_try == 0 && move_index == move_count)
    {
        // no moves were tried
        if (flags.in_check)
        {
            if (move_count == 0)        // mate
            {
               score = -(Constants::BIG - ply);
               if (ply == 0)
                   state = Search::Checkmate;
            }
            else
            {
                // We generated some moves, and some were legal,
                // but we skipped them all.
                score = evalu8(board,alpha,beta,ply);
            }
        }
        else    // stalemate
        {
            if (ply == 0)
               state = Search::Stalemate;
#ifdef _TRACE
            indent(ply); cout << "stalemate!" << endl;
#endif
            score = draw_score(board,ply);
        }
    } 
    else if (num_try > 0)
    {
        if (score >= beta)
        {
           // If the last move caused cutoff, and was not a capture,
           // save it as a "killer" move:
           if (ply == 0 || (last_move[ply].Capture().IsEmpty() &&
              last_move[ply].PromoteTo() == Piece::Invalid))
               Move_Ordering::set_killer(board,last_move[ply], ply, depth);
        }
        else
        {
           // If there's only one legal move, don't search any more:           
           if (ply == 0 && num_try == 1 && move_index == move_count)
               terminate = TRUE;
        }
    }
search_end:
    // don't insert into the hash table if we are terminating - we may
    // not have an accurate score.
    if (hash_table && !terminate && ply > 0)
    {
        // store the position in the hash table, if there's room
        int value = score;
        Position_Info::ValueType val_type;
        if (score <= initial_alpha)
        {
            val_type = Position_Info::UpperBound;
#ifdef _TRACE
            cout << 'U';
#endif
            // We don't have a "best" move, because all moves
            // caused alpha cutoff.  But if there was a hash
            // move or an initial move produced by internal 
            // interative deepening, save it in the hash table
            // so it will be tried first next time around.
            best_move = hash_move;
        }
        else if (score >= beta)
        {
            val_type = Position_Info::LowerBound;
#ifdef _TRACE
            cout << 'L';
#endif
        }
        else
        {
            val_type = Position_Info::Valid;
#ifdef _TRACE
            cout << 'E';
#endif
            if (value < -Constants::BIG+100)
            {
               value -= ply;
            }
            else if (value > Constants::BIG-100)
            {
               value += ply;
            }
        }
        Position_Info new_pos(board, depth,
                              age,
                              val_type, forced,
                              flags.in_check,
                              rep_count, value,
                              best_move);
        new_pos.set_deep_flag(deepFlag);
        Position_Info look(board,rep_count);
        Position_Info *hash_entry;
        hash_entry = (Position_Info*)hash_table->search(look);
        if (hash_entry)
        {
           // Position is already in the table, see if we should replace it
           if (depth > hash_entry->depth() || 
               (hash_entry->type() != Position_Info::Valid &&
                val_type == Position_Info::Valid) || 
                age != hash_entry->age())
           {
              *hash_entry = new_pos;
              hash_replaces++;
           }
        }
        else
        {
           // Not in the table, insert it if there is room
           int code = hash_table->replace(new_pos);
           switch(code)
           {
           case 0:
               hash_inserts++;
               break;
           case 1:
               hash_replaces++;
               break;
           case 2:
               hash_inserts_failed++;
                break;
            }

        }
    }
    ASSERT(score >= -Constants::BIG && score <= Constants::BIG);
    return score;
}

int Search::
quiesce(Board & board, int alpha, int beta,
            const int ply, int depth, 
            BOOL &terminate)
{
    // recursive function, implements quiescence search.
    ASSERT(ply < Constants::MaxPly);
    num_nodes++; time_check_counter++; num_qnodes++;
    BOOL in_check;
    int score = -Constants::BIG;
    /**
    int rep_count;
    if (is_draw(board,rep_count,ply))
    {
#ifdef _TRACE
        cout << "draw!" << endl;
#endif
        return draw_score(board,ply);
    }
    else 
    **/
    if (ply >= Constants::MaxPly-1)
    {
        return evalu8(board,alpha,beta,ply);
    }
    int stand_pat_score;

    // At this point we need to know if we are in check or not
    in_check = checks[ply] = (board.CheckStatus() == Board::InCheck);

    // Establish a default score.  This score is returned if no
    // captures are generated, or if no captures generate a better
    // score (since we generally can choose whether or not to capture).
    // Normally we don't allow "standing pat" if in check, but we make
    // an exception if we were not in check somewhere earlier in the
    // quiescence search.
    if (!in_check ||
       (depth <=-2 && !checks[ply-2]) ||
       (depth <=-4 && !checks[ply-4]) ||
       (depth <=-6 && !checks[ply-6]))
    {
        stand_pat_score = score = pat_score(board,alpha,beta,ply);

#ifdef _TRACE
       indent(ply);
       cout << "cap score = " << score << endl;
#endif
       if (score > alpha)
       {
          if (score >= beta)
          {
#ifdef _TRACE
             indent(ply); cout << "** CUTOFF **" << endl;
#endif             
             return score; //beta;
          }
          alpha = score;
       }
    }

    unsigned move_count;
    Move *moves = moves_generated[ply];
    Move_Generator mg(board, ply, last_move[ply-1]);
    move_count = mg.Generate_Captures(moves);
    num_moves += move_count;
    if (move_count > 1)
    {
       move_count = Move_Ordering::order_captures(board, moves, move_count, ply,
         pv[ply]);
    }

    unsigned move_index = 0;
    int num_try = 0; // # of legal moves tried
    int skip = 0;
    int try_score;

    while (move_index < move_count && !terminate)
    {
        ExtendedMove emove(board,moves[move_index++]);
        if (emove.Capture().Type() == Piece::King)
           return -Illegal;
        // forward prune moves that don't gain enough
        if (!in_check)
        {
        if (!emove.Capture().IsEmpty())
        {
           int est = attack_estimate(board,emove);
           if (est+stand_pat_score <= alpha)
           {
              ++skip;
              continue;
           }
        }
        else /*if (emove.Special() == ExtendedMove::Promotion)*/
        {
           if ((int)Piece::Value(emove.PromoteTo())- 64 + stand_pat_score <= alpha)
           {
               ++skip;
               continue;
           }
        }
        }
#ifdef _TRACE
        indent(ply);
        cout << "trying " << ply << ". " << emove.Image() << endl;
#endif
        last_move[ply] = emove;
        ReversibleMove rmove(board,emove);
        board.MakeMove(rmove);
        try_score = -quiesce(board, -beta, -alpha, ply+1, depth-1,
                             terminate);
        board.UndoMove(rmove);
        if (time_check_counter >= Constants::Time_Check_Interval)
        {
            time_check_counter = 0;
            terminate = check_time(ply,move_index);
            if (terminate) // don't allow current move to be selected
                try_score = Illegal;
        }
        if (try_score != Illegal)
        {
#ifdef _TRACE
            indent(ply);
            cout << ply << ". " << emove.Image() << ' ';
            cout << try_score;
            cout << endl;
#endif
            num_try++;
            if (try_score > score)
            {
               score = alpha = try_score;
               pv[ply] = emove;
               if (score >= beta) break;
            }
        }
    }
#ifdef _TRACE
    if (score >= beta)
    {
       indent(ply);
       cout << "**CUTOFF**" << endl;
    }
#endif
    if (num_try == 0 && move_index == move_count
        && in_check)
    {
        // no moves were tried.  Make sure we did not place
        // ourselves in check to get to this position.
        if (board.any_attacks(board.KingPos(
           board.OppositeSide()),board.Side()))
           score = -Illegal;
        else if (move_count == 0)
        {
            // no legal moves, mate
            score = -(Constants::BIG - ply);
        }
        else
        {
            // We are in check, but all check-avoidance
            // moves have been forward pruned.  So we
            // need to calculate a score.
            score = pat_score(board,alpha,beta,ply);
        }
    } 

#ifdef _TTRRACE
    if (terminate) cout << "ply " << ply << " terminated."
    << endl;
#endif    
  return score;
}

Move Search::find_best_move( 
            CWnd* parentWin,
            const Board &board, 
            Search_Type srcType,
            int32 timelimit,
            int plylimit,
            const BOOL background,
            Statistics &stats,
            Talk_Level t)
{
    talkLevel = t;
    time_target = timelimit;
    ply_limit = plylimit;
    type_of_search = srcType;

    bkgrnd_search = background;
#ifdef _WINDOWS
    my_hwnd = parentWin->m_hWnd;
    hint = FALSE;
    EnterCriticalSection(&searchCritSection);
    ASSERT(num_searches < MAX_SEARCHES);
    int search_number = num_searches;
    searches[search_number] = this;
    ++num_searches;

    // set timer every 1000 ms. (1 second). 
    idTimer = parentWin->SetTimer(num_searches+SEARCH_TIMER-1, 
                                  1000, (TIMERPROC)TimerProc);
    if (!idTimer)
    {
        parentWin->MessageBox("Too many clocks or timers!","",
                MB_ICONEXCLAMATION | MB_OK);
    }
    LeaveCriticalSection(&searchCritSection);
#endif    
    Board board_copy(board);
    initial_board = board;

    hint = FALSE;
    init(board_copy);
    // Do the actual search
    iterate(board_copy,stats);

    static const BOOL end_of_game[] = { FALSE, FALSE, FALSE, TRUE, TRUE,
                                           TRUE, TRUE, TRUE, TRUE };
    if (!end_of_game[(int)stats.state] && 
        global_options->can_resign())
    {
        if (stats.depth >= 2)
        {
           if( stats.value <= 8-Constants::BIG)
              stats.state = Resigns;
           else if (stats.value > 100-Constants::BIG &&
              (stats.value <= Constants::Contempt &&
               Scoring::positional_score(board) < 64))
             stats.state = Resigns;
        }
    }

    if (talkLevel == Debug)
    {
        if (stats.elapsed_time > 0)
           cout << 100*stats.num_nodes/stats.elapsed_time << " nodes/second." << endl;
        cout << (num_nodes-num_qnodes) << " regular nodes, " <<
                num_qnodes << " quiesecence nodes." << endl;
        cout << hash_searches << " searches of hash table, " <<
                hash_hits << " successful (" << 
                (int)((100.0*(float)hash_hits)/((float)hash_searches)) <<
                " percent)." << endl;
        cout << hash_inserts << " hash entries inserted, " <<
                hash_replaces << " entries replaced, " <<
                hash_inserts_failed << " inserts failed." << endl;
        fflush(stdout);
    }
#ifdef _WINDOWS
    EnterCriticalSection(&searchCritSection);
    --num_searches;
    LeaveCriticalSection(&searchCritSection);
    KillTimer(my_hwnd,idTimer);
#endif
    return pv[0];
}

void Search::update_stats(Statistics &stats)
{
    time_t end_time = GetTickCount()/10;
    stats.elapsed_time = end_time - start_time;
    stats.num_nodes = num_nodes;
    stats.num_qnodes = num_qnodes;
    stats.num_moves = num_moves;
    // Note: the search routine counts depth internally starting
    // at 0, but we report it starting at 1 (as most other programs do).
    stats.depth = iteration_depth+1;
    stats.value = current_score;
    stats.state = state;
    *(stats.best_line_image) = '\0';
    Move best = pv[0];
    // Try to obtain the best line from the hash table
    int p = 0;
    if (hash_table)
    {
    Board board_copy(initial_board);
    while(p < Constants::MaxPly-1)
    {
        stats.best_line[p++] = best;
        if (stats.best_line[p-1].IsNull())
           break;
        ExtendedMove emove(board_copy,best);
        char move_image[20];
        *move_image = '\0';
        Notation::Image(board_copy,emove,move_image);
        strcat(stats.best_line_image,move_image);
        strcat(stats.best_line_image," ");
        board_copy.MakeMove(emove);
        int rep_count;
        if (is_draw(board_copy,rep_count,p)) break;
        Position_Info look(board_copy,rep_count);
        Position_Info *hash_entry = (Position_Info*)hash_table->search(look);
        if (hash_entry)
        {
            best = hash_entry->best_move();
            if (!hash_move_valid(board_copy,best))
               break;
        }
        else
            break;
    }
    }
    else
    {
        stats.best_line[p++] = best;
    }
    stats.best_line[p].MakeNull();
}

void Search::iterate(const Board &board, Statistics &stats)
{
    int rep_count;
    if (is_draw(board,rep_count,0))
    {
        stats.state = Search::Draw;
        stats.value = draw_score(board,0);
        pv[0].MakeNull();
        iteration_depth = 0;
        return;
    }
    
    BOOL terminate = FALSE;
    if (ply_limit > 0)
      ply_limit = Util::Min(ply_limit-1,Constants::MaxPly-1);
    
    // Generate the ply 0 moves here:
    Move_Generator mg(board,0,Move::NullMove());
    ply0move_count = mg.Generate_Moves(ply0moves, FALSE);
    num_moves += ply0move_count;
    // Searching may alter the board, so operate on a copy:
    Board board_copy(board);
    // Order the moves.  The ordering process removes any illegal moves
    // at ply 0, so fix the move count if necessary.
    ply0move_count = 
      Move_Ordering::order_ply0_moves(board_copy, ply0moves, ply0move_count, 
      Move::NullMove(),
      easy);
    // See if there is an "easy" move (a recapture that appears to
    // gain more material than any other alternative).  If so we
    // may be able to terminate the search early.
    easy &= (ply0move_count > 0 &&
             !board[ply0moves[0].DestSquare()].IsEmpty() &&
             game_moves->num_moves() > 0 &&
             game_moves->move(game_moves->num_moves()-1).DestSquare()
             == ply0moves[0].DestSquare());
    easy_move = ply0moves[0];
    // Positions are stored in the hashtable with an "age" to identify
    // which search they came from.  "Newer" positions can replace 
    // "older" ones.  Update the age here since we are starting a
    // new search.
    age = (age + 1) % 3;

    // Incrementally search the board to greater depths, up to the
    // ply limit
    for (iteration_depth = 0;
         iteration_depth <= ply_limit && !terminate && !time_up; 
         iteration_depth++)
    {
        int value;
        int lo_window, hi_window;
        if (iteration_depth == 0)
            current_score = value = evalu8(board);
        else
            value = stats.value;
        lo_window = Util::Max(-Constants::BIG,value - Constants::Initial_Search_Window / 2);
        hi_window = Util::Min(value + Constants::Initial_Search_Window / 2,
                              Constants::BIG);
        BOOL failhigh = FALSE;
        BOOL faillow = FALSE;
        while (1)
        {
            int root_beta = hi_window;
#ifdef _TRACE
        cout << "root_beta = " << root_beta << endl;
#endif
            stats.value = current_score =
              move_search(board_copy, lo_window, hi_window, 0, 
                      iteration_depth, TRUE, terminate);

            update_stats(stats);
            if (!terminate)
            {
               terminate = check_time(0,0);
               if (terminate_function && terminate_function(stats))
               {
                   terminate = TRUE;
               }

            }
            if (terminate)
            {
//             show_status(board,0,stats,pv[0]);
               break;
            }
            else
            {
               show_status(board,0,stats,pv[0]);
#ifdef _TRACE
               cout << "stats.value = " << stats.value << "  root_beta = "
                    << root_beta << endl;
#endif
               ASSERT(stats.value != Constants::BIG);
               if (stats.value >= root_beta)
               {
#ifdef _TRACE
                  cout << "ply 0 high cutoff, re-searching ..." << endl;
#endif
                  // high cutoff, must re-search
#ifdef _TRACE
                  cout << "last_move[0] = " << last_move[0] << endl;
#endif
                  hi_window = Constants::BIG;
                  lo_window = Util::Min(stats.value,Constants::BIG-Constants::MaxPly);
                  failhigh = TRUE;
                  faillow = FALSE;
               }
               else if (stats.value <= lo_window && !failhigh)
               {
#ifdef _TRACE
                  cout << "ply 0 low cutoff, re-searching ..." << endl;
#endif
                  // keep the hi window intact to minimize chance of a 
                  // fail-low then fail-high.
                  hi_window = lo_window;
                  lo_window = -Constants::BIG;
                  failhigh = FALSE;
                  faillow = TRUE;
               }
               else
               {
                  break; // out of loop
               }
           }
           best_moves[iteration_depth] = pv[0];
           best_scores[iteration_depth] = stats.value;
        }
#ifdef _TRACE
        ExtendedMove emove(board,pv[0]);
        cout << iteration_depth << " ply search result: " << emove.Image() << 
           "   value = " << stats.value << endl;
#endif
        if (stats.value <= 1 + (int)(iteration_depth*2) - Constants::BIG)
        {
            // We're either checkmated or we certainly will be, so
            // quit searching.
            //stats.value = (int)(iteration_depth-1)*2 - Constants::BIG;
#ifdef _TRACE
            cout << "terminating, low score" << endl;
#endif            
            break;
        }
        else if (stats.value >= (Constants::BIG - (int)(iteration_depth*2)
         - 1)) 
        {
#ifdef _TRACE
            cout << "terminating, mate score" << endl;
#endif            
            break;
        }
    }
}

    
unsigned Search::hints( const Board &board,
                    Move *moves,
                    unsigned max_moves)
{
    // fill "moves" with up to "max_moves" hint moves, computed using
    // a minimal search depth.      
    hint = TRUE;
    talkLevel = Silent;    
    time_target = 9999;
    type_of_search = Fixed_Ply;
    ply_limit = 2;
#ifdef _WINDOWS
    bkgrnd_search = TRUE;
    EnterCriticalSection(&searchCritSection);
    ASSERT(num_searches < MAX_SEARCHES);
    int search_number = num_searches;
    searches[search_number] = this;
    ++num_searches;
    LeaveCriticalSection(&searchCritSection);
#endif    
    init(board);

    // Do the actual search
    Statistics stats;
    iterate(board,stats);

#ifdef _WINDOWS
    EnterCriticalSection(&searchCritSection);
    --num_searches;
    LeaveCriticalSection(&searchCritSection);
#endif
    Move_Ordering::sort_moves(ply0moves, ply0scores, ply0move_count);
    int n = Util::Min(ply0move_count,max_moves);
    int hint_count = 0;
    for (int i = 0; i < n; i++)
    {
	if (ply0scores[i] != Illegal)
	{
           if (i>0 && (ply0scores[i] <= ply0scores[0]-HINT_WINDOW/2))
           {
               break;
           }
           moves[hint_count++] = ply0moves[i];
	}
    }

    return hint_count; 
}

int Search::get_ply() const
{
    // return current depth of search.
    return iteration_depth;
}

unsigned long Search::get_numnodes() const
{
    // return # of nodes visited
    return num_nodes;
}    
            
void Search::init(const Board &board)
{
    num_nodes = num_qnodes = num_moves = hash_hits = 
    hash_searches = hash_inserts = hash_replaces = hash_inserts_failed = 0L;
    time_up = FALSE;
    terminated = FALSE;
    time_added = 0;
    iteration_depth = 0;
    current_score = 0;
    age = 0;
    state = Normal;
    side_to_move = board.Side();
    root_material_score = Scoring::material_score(board);
    root_total_mat = board.getMaterial(White).value() + board.getMaterial(Black).value();
    start_time = GetTickCount()/10;
    for (int i = 0; i< Constants::MaxPly;i++)
    {
       max_pos_score[i][Black] = max_pos_score[i][White] = 60;
       min_pos_score[i][Black] = min_pos_score[i][White] = -60;
       max_ks_score[i][Black] = max_ks_score[i][White] = 32;
       min_ks_score[i][Black] = min_ks_score[i][White] = -32;
       pv[i].MakeNull();
    }
    Scoring::init(board);
    Move_Ordering::clear_killer();
    Move_Ordering::clear_history();

    SearchOps src_opts;
    global_options->get_search_ops(src_opts);
    null_depth = src_opts.null_depth;
    check_extensions = src_opts.check_extensions;
    pawn_push_extensions = src_opts.pawn_push_extensions;
    forced_extensions = src_opts.forced_extensions;

    // Allocate the hash table.  Size is in kilobytes.  Guesstimate
    // a conversion to the number of hash table entries. 
    int hash_entries = src_opts.hash_table_size*18;
#ifdef _WINDOWS
    if (!hash_table)
    {
        if (hint)
        {
           // no hash table for "hint" search
        }
        else if (src_opts.auto_size_hash_table)
        {
           long size = calc_hash_size();
           hash_table = new Hash (size/32L,size);
        }
        else if (hash_entries >0)
        {
            hash_table = new Hash(Util::Max(hash_entries,32)/32,
                                  hash_entries);
        }
    }
    makeMove = TRUE;
#else
    // no auto size option for console program
    if (!hash_table && src_opts.hash_table_size >0)
    {
        hash_table = new Hash(Util::Max(hash_entries,32)/32,
                          hash_entries);
    }
#endif    
}

void Search::reinit()
{
    // After the search options change, we may need to reallocate
    // the hash table.  Free it here so that next time through init()
    // the reallocation will be done.
    if (hash_table != NULL)
    {
       hash_table->clear(TRUE);
       Position_Info::freeAll(FALSE);
       delete hash_table;
       hash_table = NULL;
    }
}

long Search::calc_hash_size()
{
       // Size the hash table according to how much memory we have.
       static int sizes[12]={ 997, 1997, 3001, 4003, 4999, 6007, 6997, 8003,
           10007, 12007, 15013, 18103 };

       DWORD memSize = GlobalCompact(0);
       int i;
       for (i = 0; i < 11; i++)
           if (sizeof(Position_Info)*((long)sizes[i]) > memSize/16)
               break;
       return 32L*sizes[i];
}

void Search::cleanup(BOOL clearHash)
{
    if (hash_table != NULL && clearHash)
    {
       hash_table->clear(TRUE);
       Position_Info::freeAll(FALSE);
       delete hash_table;
       hash_table = NULL;
    }
    delete [] ply0moves;
    delete [] ply0scores;
    for (int i = 0; i< Constants::MaxPly;i++)
    {
       if (moves_generated[i] != NULL)
           delete [] moves_generated[i];
    }
}

struct SearchParams
{
     SearchParams(Search *searcher,
       CWnd *, const Board &,
       Search_Type srcType,
       int32 time_limit, int ply_limit,
       const BOOL background,
       Search::Statistics &,
       Search::Talk_Level t);
     Search *searcher;
     CWnd* parentWin;
     const Board &ABoard; 
     Search_Type type_of_search;
     int32 time_limit;
     int ply_limit;
     Search::Statistics &stats;
     BOOL background;
     Search::Talk_Level talkLevel;
};

SearchParams::SearchParams(
            Search *srch,
            CWnd* pWin,
            const Board &b,
            Search_Type src_type,
            int32 timelimit,
            int plylimit,
            const BOOL bkgrnd,
            Search::Statistics &s,
            Search::Talk_Level tl)
: searcher(srch),parentWin(pWin),ABoard(b),type_of_search(src_type),
  time_limit(timelimit),ply_limit(plylimit),background(bkgrnd),
  stats(s), talkLevel(tl)
{
}

// Thread procedure
static unsigned int _stdcall threadProc(LPVOID pParam)
{
    SearchParams *params = (SearchParams*)pParam;
    params->searcher->find_best_move(params->parentWin,
      params->ABoard,
      params->type_of_search,
      params->time_limit,
      params->ply_limit,
      params->background,
      params->stats,
      Search::Silent);
    // signal the parent that our search is done
#ifdef _WINDOWS
    ((CArasanView*)params->parentWin)->OnSearchComplete(
      params->searcher->make_the_move());
#endif      
    delete params;
    return 0;
}
 
HANDLE Search::start_search(
            CWnd* parentWin,
            const Board &board, 
            Search_Type srcType,
            int32 time_limit,
            int ply_limit,
            const BOOL background,
            Statistics &stats,
            Search::Talk_Level t)
{
    // pack the parameters into a single structure

    SearchParams *pParam = new SearchParams(
      this,
      parentWin,board,srcType,time_limit,ply_limit,
      background,stats, t);
    // start the thread.  If this is a background search, use
    // IDLE priority to keep the GUI responsive.
    unsigned int threadId;
    HANDLE hThread = (HANDLE)_beginthreadex(NULL,0 /*stack*/,
        &threadProc,(void*)pParam, (DWORD)0,
        &threadId);
#ifdef _WINDOWS
    if (hThread)
      SetThreadPriority(hThread,background ? THREAD_PRIORITY_BELOW_NORMAL : THREAD_PRIORITY_NORMAL);
#endif
    return hThread;
}

  

