// Copyright 1987-1996 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 "attacks.h"
#include "util.h"
#include "rmove.h"
#include "pinfo.h"
#include "attacke.h"
#ifdef _WINDOWS
#include "clock.h"
#include "display.h"
#include "resource.h"
#endif
#include "options.h"
#include "globals.h"
#include "notation.h"
#include "pool.h"   
#ifdef _WINDOWS
static const UINT SEARCH_TIMER = 2;
#endif
#ifdef _TRACE
#include <iostream.h>
#endif
#include <limits.h>
#include <stdio.h>

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

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

#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 = time(NULL);
    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());
    }
}
#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;
   num_moves = num_nodes = num_qnodes = plies_completed = 0;
}

Search::Search()
{
#ifdef _WINDOWS
   InitializeCriticalSection(&searchCritSection);
#endif
}
    
Search::~Search()
{
#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

BOOL Search::check_time(int ply, int rank)
{
    if (terminated)
        return TRUE;
#ifndef _WINDOWS
    // Provide a simple polling method of terminating after a set time
    time_t current_time;
    if (get_search_type() != Fixed_Ply &&
        (current_time = time(NULL)) - get_start_time() > time_target)
       set_time_up(TRUE);
#endif       
    const Search_Type type_of_search = get_search_type();    
    if (type_of_search != Fixed_Ply && 
        type_of_search != Time_Limit)
    {
       // Allow terminating early if the best move has not changed for
       // the past several plies and the score is stable.
       if (!time_up && ply == 0 && rank > 1 && iteration_depth >= 4)
       {
#ifdef _WINDOWS
           // require that we have consumed at least 1/3 of the time
           // limit:
           time_t current_time = time(NULL);
           if ((current_time - get_start_time())*3 > time_target)
           {
#endif
               BOOL canTerminate = TRUE;
               int top_score = best_scores[iteration_depth-3];
               for (int i = iteration_depth; i >= iteration_depth-3; --i)
               {
                  if (ply0moves[0] != best_moves[i])
                  {
                     canTerminate = FALSE;
                     break;
                  }
                  // check that the score is not dropping
                  if (ply0best_score <= top_score - 32  ||
                      best_scores[i] <= top_score - 32)
                  {
                     canTerminate = FALSE;
                     break;
                  }
               }
               if (canTerminate)
               {
                  time_up = TRUE;
               }
#ifdef _WINDOWS
           }
#endif
           if (ply == 0 && rank > 0 && best_scores[iteration_depth] - ply0best_score > 48)
           {
               // If the score has dropped significantly in the last
               // iteration, add a little more search time.
               if (!terminated && !time_added && iteration_depth >= 4)
               {
                  time_t current_time = time(NULL);
                  if ((current_time - get_start_time())*3 > 2*time_target)
                  {
                      time_added = time_target/4;
                      time_up = FALSE;
                  }
               }
           }
       }
    }
    if( time_up)
    {
        terminate_now(TRUE);
    }
    return time_up;
}

#ifdef USE_HASH
// 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;
}
#endif

static void show_status(const Board &board, const int ply, const char ch,
                        const Search::Statistics &stats, const Move &move)
{
    ExtendedMove emove(board,move);
    static char move_text[20];
    Notation::Image(board, emove, move_text);
    cout << "Ply " << ply;
    if (ch != '\0') cout << ch;
    
    char val[20];
    sprintf(val,"%6.2f",stats.value/64.0);
    cout << '.';
    cout << '\t' << move_text << "\t" << stats.elapsed_time <<
     " seconds.\tscore: " << val << "\t" << stats.num_moves << " moves.\t" <<
     stats.num_nodes << " nodes.  ";
     static char pred[100];
     *pred = '\0';
     if (!stats.best_line[0].IsNull())
     {
           Board tmp_board = board;
           tmp_board.MakeMove(emove);
           for (int i=1; i<=10; i++)
           {
              Move m = stats.best_line[i];
              if (m.IsNull())
                 break;
              static char pred_move_image[20];
              *pred_move_image = '\0';
              Notation::Image(tmp_board,m,pred_move_image);
              strcat(pred,pred_move_image);
              strcat(pred," ");
              tmp_board.MakeMove(ExtendedMove(tmp_board,m));
           }
     }
     cout << pred << endl;
}

BOOL Search::is_draw( const Board &board, int &rep_count, int ply)
{
    // check for draws due to repetition or insufficient material.

    // We follow the same rule as Crafty: twice in the search or
    // three times in the game + search counts as a draw by repetition
    rep_count = game_moves->rep_count(board,0);
    if (rep_count >= 3)
      return TRUE;
    int n = game_moves->num_moves()-ply;
    if (n >= 0)
    {
       int rep_count2 = game_moves->rep_count(board,n);
       if (rep_count2 >= 2)
          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;
           do
           {
              Square sq(board.PiecePos(board.Side(),i));
              if (!sq.IsInvalid())
              {
                 Piece::PieceType piece = board[sq].Type();
                 if (piece == Piece::Bishop)
                 {
                    d1 = (sq.Rank(board.Side()) + sq.File()) % 2;
                 }
                 sq = board.PiecePos(board.OppositeSide(),i);
                 if (!sq.IsInvalid())
                 {
                    piece = board[sq].Type();
                    if (piece == Piece::Bishop)
                    { 
                        d2 = (sq.Rank(board.Side()) + sq.File()) % 2;
                    }
                 }
              }
              i++;
           } while (i < 16);
           // 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);
    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 - max_pos_score[side] > beta)
    {
        return beta;
    }
    else if (score + max_pos_score[side] < alpha)
    {
        return alpha;
    }
    // Can't cut off using material score, so add positional score
    int pos_score = Scoring::positional_score(board);
    score += pos_score;

    if (Util::Abs(pos_score) > max_pos_score[side])
        max_pos_score[side] = Util::Abs(pos_score);
    if (score < alpha)
        score = alpha;

    return score;
}

int Search::draw_score(const Board &board, int alpha, int beta, 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 score = Scoring::material_score(board);
    const ColorType side = board.Side();
    if (score - max_pos_score[side] > beta)
    {
        score = beta;
    }
    else if (score + max_pos_score[side] < alpha)
    {
        score = alpha;
    }
    else
    {
        // Can't cut off using material score, so add positional score
        int pos_score = Scoring::positional_score(board);
        score += pos_score;
        if (Util::Abs(pos_score) > max_pos_score[side])
           max_pos_score[side] = Util::Abs(pos_score);
    }
    return score;
}


unsigned Search::
generate_moves(
               Board & board, Move_Generator & mg,
               const unsigned ply,
               Move * moves,
               const BOOL captures_only)
{
    int i, n;
    if (ply == 0)
    {
        n = ply0move_count;
        Move_Ordering::order_moves(board, ply0moves, n, ply,
             pv[0]);

        for (i = 0; i < ply0move_count; i++)
            moves[i] = ply0moves[i];
    }
    else if (captures_only)
    {
       n = mg.Generate_Captures(moves);
       num_moves += n;
    }
    else
    {
       n = mg.Generate_Moves(moves);
       Move_Ordering::order_moves(board, moves, n, ply,
       pv[ply]);
       num_moves += n;
    }

    return n;
}

int Search::
move_search(Board & board, int alpha, int beta,
            const int ply, int depth, flag_struct flags,
            BOOL &terminate)
{
    // recursive function, implements alpha/beta search.  We use
    // the PVS (principal variation search) variant of alpha/beta.
    ASSERT(ply < Constants::MaxPly);
    num_nodes++;
    BOOL forced = FALSE;
    int extend = 0;
    
    flags.in_check = checks[ply] = board.CheckStatus() == Board::InCheck;
    int rep_count;

    if (is_draw(board,rep_count,ply))
    {
#ifdef _TRACE
        cout << "draw!" << endl;
#endif
       if (ply == 0)
       {
          terminate = TRUE;
          state = Search::Draw;
       }
       return draw_score(board,alpha,beta,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;

#ifdef USE_HASH
    if (ply > 0 && hash_table)
    {
        // Search the hash table to see if we have hit this
        // position before.

        Position_Info *hash_entry;      
        Position_Info look(board,rep_count);
        hash_entry = (Position_Info*)hash_table->search(look);
        hash_searches++;
        if (hash_entry)
        {
           // Found the position in the hash table.

           hash_move = hash_entry->best_move();
           forced = hash_entry->forced();
           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();
            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;
                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 = (Constants::BIG - ply);
                      else if (value < -Constants::BIG+100)
                         value = -(Constants::BIG-ply);

                       valid = TRUE;
                     break;
                   case Position_Info::UpperBound:
                     beta = Util::Min(value,beta);
                     break;
                   case Position_Info::LowerBound:
                     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, move = " << emove.Image() <<
                " alpha = " << alpha << " beta = " << beta << endl;
#endif
                if (valid)
                {
                   return hash_entry->value();
                }
                else if (alpha >= beta)
                {
                   if (hash_entry->type() == Position_Info::LowerBound)
                       return alpha;
                   else
                       return beta;
                }
            }
        }
    }
#endif
#ifdef _TRACE
    if (!hash_move.IsNull())
    {
        indent(ply);
        ExtendedMove ehash_move(board,hash_move);
        cout << "hash move = " << ehash_move.Image() << endl;
    }
#endif

    // 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 && ply > 0 &&
        alpha > -Constants::BIG+100 &&
        alpha < Constants::BIG-100 &&
        !flags.pv && !flags.in_check && !last_move[ply-1].IsNull() &&
        board.getMaterial(board.Side()).value() > 2800 &&
        board.getMaterial(board.OppositeSide()).value() > 2800)
    {      
        last_move[ply].MakeNull();
        ExtendedMove emove(board,Move::NullMove());
        ReversibleMove rmove(board,emove); // 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, 
                                 flags,terminate);
        else 
           score = -quiesce(board, -beta, -alpha,
                                 ply+1, depth-null_depth-1, 
                                 flags,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
            return score;
        }
    }

    // Use "internal iterative deepening" to get an initial move to try if
    // there is no hash move .. an idea from Crafty.
    int dscore;
    if (ply >0 && score < beta && hash_move.IsNull() && depth > 2)
    {
#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.
        pv[ply].MakeNull();
        dscore = move_search(board,alpha,beta,ply,depth-2,
                  flags,terminate);
        if (dscore <= alpha)
        {
           dscore = move_search(board,-Constants::BIG,beta,
             ply,depth-2,flags,terminate);
        }
#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 = FALSE;
    unsigned move_count;
    Move *moves = moves_generated[ply];
    Move_Generator mg(board, ply, the_last_move);
    if (score < beta)
    {
        if (!moves)
           moves = moves_generated[ply] = new Move[Move_Generator::MaxMoves];
        if (hash_move.IsNull())
        {
           move_count = generate_moves(board, mg, ply,
                                 moves, 
                                 FALSE);
           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;
        }
    }

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

    // Extend the search one ply for "forced" moves.
    int total_mat = board.getMaterial(Black).value() +
        board.getMaterial(White).value();
    if (forced_extensions && forced)
      ++extend;
    // Also extend one ply for checks (within a limit)
    else if (check_extensions && 
             flags.in_check && 
             (ply+depth) < 2*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))
      ++extend;

    int new_depth = depth+extend;
    Board board_copy(board);
    // Do the principal variation
    while (move_index < move_count && score < beta && !flags.mate &&
           !terminate)
    {
        ExtendedMove emove(board,moves[move_index++]);
        ReversibleMove rmove(board,emove);
#ifdef _TRACE
        if (ply == 0)
          cout << "window = [" << alpha << ',' << beta << ']' << endl;
        indent(ply);
        cout << "trying " << ply << ". " << emove.Image() << endl;
#endif
        last_move[ply] = emove;
        board.MakeMove(rmove);
        game_moves->add_move(board,emove);
        if (board.num_attacks(board.KingPos(board.OppositeSide()),
                           board.Side()) > 0)
        {
#ifdef _TRACE
            indent(ply);
            cout << "(illegal)" << endl;
#endif
            try_score = Illegal;
        }
        else if (new_depth-1 > 0)
        {
            try_score = -move_search(board, -beta, -alpha,
                                 ply+1, new_depth-1, 
                                 flags,terminate);
        }
        else
        {
            try_score = -quiesce(board, -beta, -alpha,
                                 ply+1, new_depth-1, 
                                 flags,terminate);
        }
#ifdef _TRACE
        indent(ply);
        cout << ply << ". " << emove.Image() << ' ';
        cout << try_score;
        cout << " (pv)";
        cout << endl;
#endif
        game_moves->remove_move();
        board = board_copy; // undo move
        if (ply == 0) ply0scores[move_index-1] = try_score;
        if (try_score != Illegal)
        {
            best_move = pv[ply] = last_move[ply];
            if (ply == 0) 
            {
               ply0best_score = score;
            }
            score = try_score;
            if (try_score > alpha)
            {
               alpha = try_score;
            }
            num_try++;
            break;
        }
    }
    
    if (ply == 0)
    {
        flags.mate = score >= Constants::BIG - (int)ply - 1;
    }

    // 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 && !flags.failhigh)))) 
    {
       flags.pv = FALSE;
       // Generate the moves if we haven't done so already:
       if (!generated_moves && score < beta && !flags.mate)
       {
          move_count = generate_moves(board, mg, ply, moves, FALSE);
          move_index = 1; // start at 1 cause we already did the p.v.
       }
       int newalpha = alpha, newbeta;
       if (hint)
       {
           newbeta = alpha + 20;
           newalpha = alpha - 20;
       }
       else
       {
           newbeta = alpha + 1; // zero-width window
       }
       while (move_index < move_count && score < beta && !flags.mate &&
           !terminate)
       {
           ExtendedMove emove(board,moves[move_index++]);
           ReversibleMove rmove(board,emove);
#ifdef _TRACE
           if (ply == 0)
             cout << "window = [" << alpha << ',' << alpha+1 << ']' << 
             " beta = " << beta << endl;
           indent(ply);
           cout << "trying " << ply << ". " << emove.Image() << endl;
#endif
           last_move[ply] = emove;
           board.MakeMove(rmove);
           game_moves->add_move(board,emove);
           if (board.num_attacks(board.KingPos(board.OppositeSide()),
                           board.Side()) > 0)
           {
               try_score = Illegal;
#ifdef _TRACE
               indent(ply);
               cout << "(illegal)" << endl;
#endif
           }
           else if (new_depth-1 > 0)
           {
               try_score = -move_search(board, -newbeta, -newalpha,
                                  ply+1, new_depth-1,flags,terminate);
           }
           else
           {
               try_score = -quiesce(board,  -newbeta, -newalpha,
                                 ply+1, new_depth-1,flags,terminate);
           }
#ifdef _TRACE
           if (try_score != Illegal)
           {
              indent(ply);
              cout << ply << ". " << emove.Image() << ' ';
              cout << try_score;
              cout << endl;
           }
#endif
           if (ply == 0) ply0scores[move_index-1] = try_score;
           if (terminate || try_score == Illegal)
           {
               game_moves->remove_move();
               board = board_copy; // undo move
               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,flags,terminate);
              else 
                try_score=-quiesce(board,
                   -beta,-try_score,ply+1,new_depth-1,flags,terminate);
#ifdef _TRACE
              indent(ply);
              cout << ply << ". " << emove.Image() << ' ';
              cout << try_score;
              cout << endl;
#endif
           }
           game_moves->remove_move();
           board = board_copy; // undo move
           if (num_nodes % Constants::Time_Check_Interval == 0)
           {
              terminate = check_time(ply,move_index);
              if (time_up) // 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 + 20;
                  newalpha = alpha - 20;
               }
               else
                  newbeta = alpha + 1; // zero-width window
               best_move = pv[ply] = emove;
               flags.mate = score >= Constants::BIG - (int)ply - 1;
               if (ply == 0) 
               {
                   ply0best_score = score;
                   if (verbose)
                   {
                       Statistics stats;
                       stats.value = score;
                       stats.num_nodes = num_nodes;
                       stats.num_moves = num_moves;
                       time_t now = time(NULL);
                       stats.elapsed_time =now -start_time;
                       show_status(board,iteration_depth,'>',stats,pv[0]);
                   }
               }
           }
       }
    }
    BOOL Cutoff = (score >= beta);
#ifdef _TRACE
    if (Cutoff)
    {
       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,alpha,beta,ply);
        }
    } 
    else if (num_try > 0)
    {
        if (Cutoff)
        {
           // 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())
               Move_Ordering::set_killer(board,last_move[ply], ply);
        }
        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;
        }
    }
#ifdef USE_HASH
    if (hash_table)
    {
        // store the position in the hash table, if there's room
        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
        }
        Position_Info *my_pi = new Position_Info(board, new_depth,
                                                 ply,
                                                 val_type, forced,
                                                 rep_count, score,
                                                 best_move);
        Position_Info look(board,rep_count);
        Position_Info *hash_entry = (Position_Info*)hash_table->search(look);
        if (hash_entry)
        {
           // Position is already in table, see if we should replace it
           if (new_depth > hash_entry->depth() || 
               (hash_entry->type() != Position_Info::Valid &&
                val_type == Position_Info::Valid))
           {
              *hash_entry = *my_pi;
              hash_replaces++;
           }
           else
           {
              delete my_pi;
           }
        }
        else
        {
           if (!hash_table->insert(my_pi,FALSE))
           {
              delete my_pi; // not inserted
              hash_inserts_failed++;
           }
           else
              hash_inserts++;
        }
    }
#endif
    ASSERT(score >= -Constants::BIG && score <= Constants::BIG);
    return score;
}

int Search::
quiesce(Board & board, int alpha, int beta,
            const int ply, int depth, flag_struct flags,
            BOOL &terminate)
{
    // recursive function, implements quiescence search.
    ASSERT(ply < Constants::MaxPly);
    num_nodes++; num_qnodes++;

    flags.in_check = checks[ply] = (board.CheckStatus() == Board::InCheck);

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

    // Establish a default score by calling evalu8. This score is
    // returned if no captures are generated, or if no captures
    // generate a better score (since we assume we can always 
    // choose not to capture).
    if (!flags.in_check)
    {
        score = pat_score(board,alpha,beta);

#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;
       }
    }

    the_last_move = last_move[ply - 1];
    
    BOOL generated_moves = FALSE;
    unsigned move_count;
    Move *moves = moves_generated[ply];
    Move_Generator mg(board, ply, the_last_move);
    if (score < beta)
    {
        if (!moves)
           moves = moves_generated[ply] = new Move[Move_Generator::MaxMoves];
        if (hash_move.IsNull())
        {
           move_count = generate_moves(board, mg, ply,
                                 moves, 
                                 !flags.in_check);
           generated_moves = TRUE;
        }
        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;
        }
    }

    unsigned move_index = 0;
    int num_try = 0; // # of legal moves tried
    int skip = 0;
    int try_score;
    Board board_copy(board);
    while (move_index < move_count && score < beta && !flags.mate &&
           !terminate)
    {
        ExtendedMove emove(board,moves[move_index++]);
        ReversibleMove rmove(board,emove);
        // forward prune moves that don't gain enough
        if (!emove.Capture().IsEmpty() && emove.Special() == ExtendedMove::Normal
            && !(flags.in_check && depth > -2))
        {
           int est =
              attack_estimate(board,emove);
           if (est+max_pos_score[board.Side()] <= alpha)
           {
               ++skip;
               continue;
           }
        }
#ifdef _TRACE
        indent(ply);
        cout << "trying " << ply << ". " << emove.Image() << endl;
#endif
        last_move[ply] = emove;
        board.MakeMove(rmove);
        game_moves->add_move(board,emove);
        if (board.num_attacks(board.KingPos(board.OppositeSide()),
                           board.Side()) > 0)
        {
            try_score = Illegal;
#ifdef _TRACE
            indent(ply);
            cout << " (illegal)" << endl;
#endif            
        }
        else
        {
            try_score = -quiesce(board, -beta, -alpha, ply+1, depth-1,
                                 flags,terminate);
        }
        game_moves->remove_move();
        board = board_copy; // undo move
        if (num_nodes % Constants::Time_Check_Interval == 0)
        {
            terminate = check_time(ply,move_index);
            if (time_up) // 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;
               best_move = pv[ply] = emove;
               flags.mate = score >= Constants::BIG - (int)ply - 1;
            }
        }
    }
    BOOL Cutoff = (score >= beta);
#ifdef _TRACE
    if (Cutoff)
    {
       indent(ply);
       cout << "**CUTOFF**" << endl;
    }
#endif

    if (num_try == 0 && move_index == move_count
        && flags.in_check)
    {
        // no moves were tried
        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);
        }
    } 
    // Don't save killers or history, because only non-captures
    // qualify.
    
    return score;
}

Move Search::find_best_move( 
#ifdef _WINDOWS
            CWnd* parentWin,
#endif
            const Board &board, 
            const Time_Info &ti,
#ifdef _WINDOWS             
            const BOOL background,
#endif              
            Statistics &stats,
            Move &prev_move,
            BOOL use_previous_search,
            BOOL be_verbose)
{
    timeCtrl = ti;
    verbose = be_verbose;
    moves_in_game = game_moves->num_moves()/2; // full moves, not half-moves
    pred_moves = 60;
    if (moves_in_game > 40)
       pred_moves += (moves_in_game-40)/2;

#ifdef _WINDOWS
    bkgrnd_search = background;
    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);

    hint = FALSE;
    const Search_Limit limits = timeCtrl.get_search_limit();
    switch (timeCtrl.get_search_type())
    {
       case Fixed_Ply:
         break;
       case Time_Limit:
       case Time_Target:
         time_target = limits.seconds; 
         break;
       case Tournament:
#ifdef _WINDOWS
         {
         unsigned long game_elapsed = 
            the_clock->elapsed_time(board.Side());
         int moves_to_time_control = 
           limits.limit.moves - (moves_in_game % limits.limit.moves) + 1;
         time_target = 9L*(limits.limit.minutes*60L - game_elapsed)/
                        (moves_to_time_control*10L);
         }
#else
         time_target = 
           (limits.limit.minutes*60L*9L)/(limits.limit.moves*10L);
#endif           
          break;
#ifdef _WINDOWS
       case Game:
         unsigned long game_elapsed = 
            the_clock->elapsed_time(board.Side());
         time_target = (limits.limit.minutes*60L - game_elapsed)/
                        (pred_moves - moves_in_game);
#else
       // Game time control not supported in console mode
       default:
         break;
#endif

    }
    init(board_copy);

    // We can use the results of a previous search only if it
    // was deep enough and if we predicted the last move.
    use_previous_search &= (stats.plies_completed >= 2) &&
       (stats.best_line[0] == prev_move);
    int start_ply;
    if (use_previous_search)
       start_ply = stats.plies_completed - 1;
    else
       start_ply = 0;
    if (use_previous_search)
    {
       for (int ply = 0; ply < Constants::MaxPly &&
            !stats.best_line[ply].IsNull(); ply++)
         pv[ply] = stats.best_line[ply+1];
    }

    // Do the actual search
    iterate(board_copy,start_ply,limits,stats,verbose);

    // Update the "Statistics" data structure with the results
    time_t end_time = time(NULL);
    stats.elapsed_time = end_time - start_time;
    stats.num_nodes = num_nodes;
    stats.num_qnodes = num_qnodes;
    stats.num_moves = num_moves;
    stats.plies_completed = iteration_depth ? iteration_depth-1 : 0;
    stats.state = state;

    Move_Array tmpArray;
    Move best = pv[0];
    // Try to obtain the best line from the hash table
    int p = 0;
#ifdef USE_HASH
    if (hash_table)
    {
    while(p < Constants::MaxPly-1)
    {
        stats.best_line[p++] = best;
        ExtendedMove emove(board_copy,best);
        board_copy.MakeMove(emove);
        tmpArray.add_move(board_copy,emove);
        Position_Info look(board_copy,tmpArray.rep_count(board_copy));
        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;
    }
    }
#endif
    stats.best_line[p].MakeNull();
    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() && 
        stats.value <= Constants::Contempt)
    {
        // We resign only if about to be mated, or if behind in
        // material and if our positional score is low.
        if ((stats.value <= -Constants::BIG +100) ||
            Scoring::positional_score(board) < 40)
           stats.state = Resigns;
    }
    cleanup(TRUE);

    if (verbose)
    {
        if (stats.elapsed_time > 0)
           cout << 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);
#endif
    return pv[0];
}

void Search::iterate(const Board &board, int start_ply,
  const Search_Limit &limits, Statistics
  &stats, BOOL verbose)
{
    BOOL terminate = FALSE;
    unsigned ply_limit = (get_search_type() == Fixed_Ply) ? limits.max_ply :
                          Constants::MaxPly-1;
    ply_limit = Util::Min(ply_limit,Constants::MaxPly-1);
    
    for (int i = 0; i < Constants::MaxPly; i++)
    {
        pv[i].MakeNull();
    }
    
    // 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, either permanently (e.g. PiecePos)
    // or temporarily (during a search), so operate on a copy:
    Board board_copy(board);
    Move_Ordering::order_moves(board_copy, ply0moves, ply0move_count, 0,
      Move::NullMove());

    for (iteration_depth = start_ply;
         iteration_depth <= ply_limit && !terminate && !time_up; 
         iteration_depth++)
    {
        int value;
        int lo_window, hi_window;
        if (iteration_depth == 0)
            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);
        flag_struct flags;                              
        flags.failhigh = flags.faillow = 0;
        flags.mate = 0;
        flags.pv = 1;
        while (1)
        {
            int root_beta = hi_window;
#ifdef _TRACE
        cout << "root_beta = " << root_beta << endl;
#endif
            stats.value =
              move_search(board_copy, lo_window, hi_window, 0, 
                      iteration_depth, flags,
                      terminate);

            if (verbose)
            {
               time_t end_time = time(NULL);
               stats.elapsed_time = end_time - start_time;
               stats.num_nodes = num_nodes;
               stats.num_qnodes = num_nodes;
               stats.num_moves = num_moves;
               char ch = '\0';
               if (flags.failhigh)
                  ch = '+';
               else if (flags.faillow)
                  ch = '-';
               show_status(board,iteration_depth,0,stats,pv[0]);
            }
            if (terminate)
               break;
            else
            {
#ifdef _TRACE
               cout << "stats.value = " << stats.value << "  root_beta = "
                    << root_beta << endl;
#endif
               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 = stats.value;
                  flags.failhigh = 1;
                  flags.faillow = 0;
               }
               else if (stats.value <= lo_window && !flags.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;
                  flags.failhigh = 0;
                  flags.faillow = 1;
               }
               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 <= (int)(iteration_depth-1)*2 - Constants::BIG)
        {
            // We're either checkmated or we certainly will be, so
            // quit searching.
            stats.value = (int)(iteration_depth-1)*2 - Constants::BIG;
            break;
        }
        else if (stats.value > Constants::BIG - 100) // mate
            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;
    
    Search_Limit limit;
    limit.max_ply = 2;
    timeCtrl = Time_Control(Fixed_Ply,limit);
#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,0,limit,stats,FALSE);

#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]-32))
           {
               break;
           }
           moves[hint_count++] = ply0moves[i];
		}
    }

    // Don't clear the hash table.  Storage for the nodes and lists in the
    // table may be shared with another search in progress.  When that
    // search terminates, our memory will be cleaned up, too.
    cleanup(FALSE);
   
    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;
    max_pos_score[Black] = max_pos_score[White] = 80;
    time_up = FALSE;
    terminated = FALSE;
    time_added = 0;
    iteration_depth = 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();
    pv[0].MakeNull();
    ply0moves = new Move[Move_Generator::MaxMoves];
    ply0scores = new int[Move_Generator::MaxMoves];
    start_time = time(NULL);
    for (int i = 0; i< Constants::MaxPly;i++)
    {
       moves_generated[i] = NULL;
    }
    Move_Ordering::clear_killer();

    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;
    hash_table = NULL;
#ifdef _WINDOWS
    if (src_opts.auto_size_hash_table)
    {
       long size = calc_hash_size();
       hash_table = new Hash (size/32L,size);
    }
    else if (src_opts.hash_table_size >0)
    {
        hash_table = new Hash(Util::Max(src_opts.hash_table_size,32)/32,
                             src_opts.hash_table_size);
    }
    makeMove = TRUE;
#else
    if (src_opts.hash_table_size >0)
    {
        // no auto size option for console program
        hash_table = new Hash(Util::Max(src_opts.hash_table_size,32)/32,
                          src_opts.hash_table_size);
    }
#endif    

#ifdef _DEBUG
    cout << "check_extensions = " << check_extensions << endl;
    cout << "forced_extensions = " << forced_extensions << endl;
    cout << "pawn_push_extensions = " << pawn_push_extensions << endl;
    cout << "null_depth = " << null_depth << endl;
#endif

}

long Search::calc_hash_size()
{
       // Size the hash table according to how much memory we have.
       // Bucket sizes should be prime.
       static int sizes[8]={ 997, 1997, 3001, 4003, 4999, 6007, 6997, 8003 };
       DWORD memSize = GlobalCompact(0);
       int i;
       for (i = 0; i < 7; i++)
           if (16*sizeof(Position_Info)*((long)sizes[i]) > memSize/8)
               break;
       return 32*sizes[i];
}

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

#ifdef _WINDOWS
struct SearchParams
{
     SearchParams(Search *searcher,
       CWnd *, const Board &,
       const Time_Info &, const BOOL background,
       Search::Statistics &,Move &, BOOL use_previous_search,
       BOOL verbose = FALSE);
     Search *searcher;
     CWnd* parentWin;
     const Board &ABoard; 
     const Time_Info &ti;
     Search::Statistics &stats;
     Move &prev_move;
     BOOL use_previous_search;
     BOOL background;
     BOOL verbose;
};

SearchParams::SearchParams(
            Search *srch,
            CWnd* pWin,
            const Board &b,
            const Time_Info &t,
            const BOOL bkgrnd,
            Search::Statistics &s,
            Move &pmove,
            BOOL prev_search,
            BOOL verb)
: searcher(srch),parentWin(pWin),ABoard(b),ti(t),background(bkgrnd),
  stats(s),prev_move(pmove),use_previous_search(prev_search),
  verbose(verb)
{
}

// Thread procedure
static UINT threadProc(LPVOID pParam)
{
    SearchParams *params = (SearchParams*)pParam;
    params->searcher->find_best_move(params->parentWin,
      params->ABoard,
      params->ti,
      params->background,
      params->stats,
      params->prev_move,
      params->use_previous_search,
      params->verbose);
    // signal the parent that our search is done
    ((CArasanView*)params->parentWin)->OnSearchComplete(
      params->searcher->make_the_move());
    delete params;
    return 0;
}
 
CWinThread * Search::start_search(
            CWnd* parentWin,
            const Board &ABoard, 
            const Time_Info &ti,
            const BOOL background,
            Statistics &stats,
            Move &prev_move,
            BOOL use_previous_search,
            BOOL verbose)
{
    // pack the parameters into a single structure
    SearchParams *pParam = new SearchParams(
      this,
      parentWin,ABoard,ti,background,stats,prev_move,use_previous_search,
      verbose);
    // start the thread.  If this is a background search, use
    // IDLE priority to keep the GUI responsive.
    return AfxBeginThread(threadProc,(void*)pParam,
        background ? THREAD_PRIORITY_IDLE : THREAD_PRIORITY_NORMAL);
}

  
#endif
