Deleted log file from repository

[rattatechess.git] / search.cpp

/***************************************************************************
                          search.cpp  -  description
                             -------------------
    begin                : Wed Mar 13 2002
    copyright            : (C) 2002-2005 by Monge Maurizio
    email                : monge@linuz.sns.it
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include "engine.h"
#include "utils.h"
#include <string.h>
#include <stdlib.h>

#define MAX_PV 80
#define PLY    100

uint64_t history_tot[64*64];
uint64_t history_hit[64*64];
uint16_t killers[MAX_PV][64*64];

#define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 +  \
                            SQUARE_TO_64(m.to))
#define PROF(f,n) {uint64_t tmp = rdtsc(); f; prof_##n += rdtsc()-tmp; }

/*uint64_t prof_eval;
uint64_t prof_find_moves;
uint64_t prof_find_captures;
uint64_t prof_heuristic;
uint64_t prof_sort_moves;
uint64_t prof_do_move;
uint64_t prof_move_is_check;
uint64_t prof_move_see_val;
uint64_t prof_tot;*/

int stat_early_transp;
int stat_hash_write;
int stat_hash_tot;
int stat_hash_ex;
int stat_hash_low;
int stat_hash_upp;
int stat_best_cut;
int stat_best_first;
int stat_search_moves;
int stat_best_cut0;
int stat_best_first0;
int stat_search_moves0;
int stat_evaluate;
int stat_evaluate_cutoff;
int stat_null_move;
int stat_null_cut;

//int stat_
/* enable the quiescence search */
#define QUIESCENCE           1

/* enable the nega-scout pv-search */
#define NEGA_SCOUT           1

/* enable the null move */
#define NULL_MOVE            1

/* enable hashing the positions */
#define HASH_TABLE           1

/* use the hastable to detect tranpositions */
#define TRANSP_TABLE         1

/* SEEMS TO BE QUITE BAD:
   trust the values from a search at lower depth stored in the hashtable
   to produce a cutoff, taking the value with a margin of uncertainity */
#define APPROX_TRANSP_CUTOFF  0

/* before doing the alpha beta search check if any of the following positions
   can give use an early cutoff thanks to the hashtable */
#define EARLY_TRANSP_CUTOFF   1

/* SEEMS TO BE A BIT BAD:
   when the we find that the values stored in the hash (the result of a
   lighter search) were wrong by a big factor, this means that the node is
   unstable, so re-search it */
#define CONSISTENCY_EXTENSION 0

/* SEEMS TO BE A BIT BAD:
   Extend when there is only one decent move */
#define SINGULAR_EXTENSION    0

/* DANGEROUS:
   reduce nodes for moves that are not check/captures that are considered
   bad from the heuristic */
#define HISTORY_PRUNING      1

/* futility pruning: */
#define FUTILITY             1

/* sort the moves to improve alpha-beta cutoff */
#define SORT_MOVES           1

/* use the candidate move stored in the hashtable */
#define HASH_HEURISTIC       1

/* when the hashtable provides no "best" move, do a depth-2 search */
#define INTERNAL_ITERATIVE_DEEPENING  0

/* use the history sorting heuristic */
#define HISTORY_HEURISTIC    1

/* use the Max Value Victim/Least Value Attacker sorting heuristic */
#define MVV_LVA_HEURISTIC    1

/* improve the sorting heuristic for pawn strikes */
#define PAWNSTRIKE_HEURISTIC 1

/* improve the sorting heuristic for moves to the center */
#define CENTER_HEURISTIC     0

/* search 2 times per ply, to compare our move sorting to the perfect move sorting */
#define RE_SEARCH            0


class SearchStack
{
public:
    int   base_depth;     /* depth of the search at this ply */
    int   extensions;     /* global extensions at this node */
    Move *moves;       /* all generated moves */
    int   num_moves;   /* num of moves */
    int   curr_move;   /* the move being currently analyzed */
    int16_t  alpha;    /* alpha ans beta when the search started (not improved) */
    int16_t  beta;
    bool  under_check;
    Move  threat;
    int   best_move;
};

Move mv_stack[200*MAX_PV];
int mv_stack_top = 0;
SearchStack stack[MAX_PV];
int current_ply = 0;

void Engine::print_stat()
{
    if(eng_status != ANALYZING)
    {
        output("You cannot use this command now!\n");
        return;
    }

    if(thinking)
    {
        char buf[32];
        output("stat01: %d %llu %d %d %d %s\n",
            current_time() - start_think_time,
            (unsigned long long)processed_nodes,
            stack[0].base_depth/100,
            stack[0].num_moves-1-stack[0].curr_move,
            stack[0].num_moves,
            move_to_alg(buf, &(stack[0].moves[stack[0].curr_move]) ) );
    }
    else
        output("stat01: 0 0 0 0 0\n");
}

void Engine::rewind_thinking()
{
    for(int i=current_ply-1; i>=0; i--)
    {
        if(stack[i].curr_move == -1)
            board.undo_null_move();
        else
            board.undo_move(stack[i].moves[stack[i].curr_move]);
    }
}

void Engine::restore_thinking()
{
    for(int i=0; i<current_ply; i++)
    {
        if(stack[i].curr_move == -1)
            board.do_null_move();
        else
            board.do_move(stack[i].moves[stack[i].curr_move]);
    }

    /* regenerate pinning info and under_check var, just to be sure :) */
    Move mvs[250];
    board.find_moves(mvs);
}

void
Engine::moves_heuristic(Move *mv, int num_mv, int ply, int orig_depth,
                                    Move best_mv_hash, bool quiesce)
{
    /*uint8_t up_right = Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
    uint8_t up_left = Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;*/
    int hash_move = -1;

    for(int i=0;i<num_mv;i++)
    {
        mv[i].val = 0;
        mv[i].extend = 0;

#if HASH_TABLE && HASH_HEURISTIC
        /* give a high bonus to the move stored in the hash, if any.
           mark only which is, don't continue, because some extensions
           may be triggered ad added later (ie pawn strike, etc) */
        if(mv[i].as_int == best_mv_hash.as_int)
            hash_move = i;
#endif //HASH_HEURISTIC

        /* process strong pawn moves */
        if(PIECE_OF(board.data[mv[i].from])==PAWN)  /* pawn strike */
        {
            if( ROW_OF(mv[i].to) == board.seventh_rank[IS_WHITE(board.color_to_move)] )
            {
                int x = board.move_see_val(mv[i]);

                if(x<0)
                {
                    mv[i].val += -15000;
                    continue;
                }

                mv[i].val += 29499; /* 7th push */
                mv[i].extend = 1;   /* extend search */
                continue;
            }

            if( mv[i].flags == PROMOTEQUEEN )
            {
                int x = board.move_see_val(mv[i]);

                if(x<0)
                {
                    mv[i].val += -15000;
                    continue;
                }

                mv[i].val += 29500; /* promote! */
                mv[i].extend = 1;   /* extend search */
                continue;
            }

            #if 0
            /* pawn strike */
            uint8_t p1 = mv[i].to + up_right;
            uint8_t p2 = mv[i].to + up_left;
            uint8_t a = OUT_OF_BOARD(p1) ? 0 : board.data[p1];
            uint8_t b = OUT_OF_BOARD(p2) ? 0 : board.data[p2];
            if( (COLOR_OF(a)==board.other_color && PIECE_OF(a)!=PAWN)
                || (COLOR_OF(b)==board.other_color && PIECE_OF(b)!=PAWN) )
            {
                int x = board.move_see_val(mv[i]);
                if(x<0)
                {
                    mv[i].val += -15000;
                    continue;
                }

                mv[i].val += 27000; /* pawn strike! */
                mv[i].extend = 1;   /* extend search */
                continue;
            }
            #endif
        }

        if(mv[i].capture)
        {
            int x = board.move_see_val(mv[i]);

            if(x>0)
            {
                if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
                {
                    mv[i].val += 29800+x;
                    //mv[i].extend = 1;
                }
                else
                    mv[i].val += 29000+x;
                continue;
            }
            else if(x<0)
            {
                mv[i].val += -15000+x;
                continue;
            }
            else if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
            {
                /* = capture but check */
                mv[i].val += 29800;
                continue;
            }
        }
        else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
        if(orig_depth>-3*PLY && board.move_is_check(mv[i]) )
        {
            if(board.move_see_val(mv[i])>=0)
            {
                mv[i].val += 28799;
                continue;
            }
        }

        if(quiesce)
            continue;

#if HISTORY_HEURISTIC
        /* add the value depending on the heuristic */
        mv[i].val += killers[ply][HISTORY_INDEX(mv[i])];
        if(ply>=2)
            mv[i].val += killers[ply-2][HISTORY_INDEX(mv[i])];
#endif //HISTORY_HEURISTIC

#if CENTER_HEURISTIC
        static int bof[128] = {
            0,0,1,2,2,1,0,0,ENDL,
            0,1,2,3,3,2,1,0,ENDL,
            0,2,4,5,5,4,2,0,ENDL,
            1,2,5,6,6,5,2,1,ENDL,
            1,2,5,6,6,5,2,1,ENDL,
            0,2,4,5,5,4,2,0,ENDL,
            0,1,2,3,3,2,1,0,ENDL,
            0,0,1,2,2,1,0,0,ENDL
        };

        /* add a bonus for moves towards the center */
        mv[i].val += (bof[mv[i].to] - bof[mv[i].from]);
#endif //CENTER_HEURISTIC
    }

    if(hash_move!=-1)
        mv[hash_move].val = 30000;
}


/*******************************************************************************
    The main alpha-beta recursive search function.
    It handles both normal search (with or without null move)
    and quiescence search, because i have having 2 almost identical
    function around.
*******************************************************************************/
int16_t Engine::search(int ply, int depth, bool pv, int16_t alpha, int16_t beta)
{
    SearchStack *s = &stack[ply];
    int16_t best = -INF;
    uint16_t cbest_mv_hash = 0;    /* the compressed move from the hash */
    Move best_mv_hash = Move::FromInt(0);   /* the move from the hash */
    int best_mv_found = -1;  /* the index of the best move AFTER searching */
    bool    quiesce;
    bool    extended = false;
    int16_t position_val;
#if CONSISTENCY_EXTENSION
    int old_hash_lower = -INF;
    int old_hash_upper = INF;
    int old_hash_depth = 0;
#endif //CONSISTENCY_EXTENSION

    s->base_depth = depth;
    s->extensions = 0;
    s->num_moves = 0;
    s->curr_move = -1;
    s->alpha = alpha;
    s->beta = beta;
    s->threat = Move::FromInt(0);
    s->best_move = -1;

    /* check if time is running out */
    if(check_time())
        return 0;

    /* check for a draw for repetition or 50mvs. Of course the draw for
        repetition must be checked BEFORE probing the hash :)*/
    if(check_draw())
        return (board.color_to_move == st_computer_color) ? -35 :
               ((board.other_color == st_computer_color) ? 35 : 0); /* be aggressive! */

#if HASH_TABLE
/*******************************************************************************
    Probe the hashtable.
    If the probe is succesful the hashtable will return us value
    that can be exact, a lower bound or an upper bound, and if the
    depth of the hashed search is >= the current depth this value
    will be used to improve alpha and beta and possibly return immediatly.
    The hastable will also give us a "best" move that will be searched
    first.
    This is the move that caused the "final" cutoff when this position
    was searched previously. This best move is actually the index of the best
    move in the array of generated moves (it is supposed to be deterministic :)
*******************************************************************************/
    stat_hash_tot++;
    HashEntry *h = probe_hash( board.hash );

#if TRANSP_TABLE
    if(h && (h->depth >= s->base_depth))// || ABS(h->value)>INF-1000) )
    {
        int16_t l = h->lower();
        int16_t u = h->upper();
        if(l>=beta || u==l)
            return l;
        if(u<=alpha)
            return u;

        beta = MIN(beta, u);
        alpha = MAX(alpha, l);
    }

    #if APPROX_TRANSP_CUTOFF
    /* risky, we are assuming that the result of a search at lower
       depth will not be very different from the true result */
    if(h && depth<=300 && (h->depth >= depth-100))
    {
        if(h->upper()+350<=alpha)
            return alpha;
        if(h->lower()-350>=beta)
            return beta;
    }
    #endif //APPROX_TRANSP_CUTOFF
#endif //TRANSP_TABLE

#if HASH_HEURISTIC
    if(h)
        cbest_mv_hash = h->best_mv;
#endif //HASH_HEURISTIC

    #if CONSISTENCY_EXTENSION
    /* save the bounds stored in the hash, so we can re-search unstable nodes */
    if(h)
    {
        old_hash_lower = h->lo;
        old_hash_upper = h->up;
        old_hash_depth = h->depth;
    }
    #endif //CONSISTENCY_EXTENSION

#endif //HASH_TABLE


/*******************************************************************************
    Test if we are under check, and if so extend search
*******************************************************************************/

    s->under_check = board.under_attack(board.king_pos[IS_WHITE(board.color_to_move)],
                                                    board.other_color);
#if 0
    if(s->under_check)
    {
        depth += PLY;
        extended = true;
    }
#endif

/*******************************************************************************
    If it is time to quiesce, evaluate and test if we can exit
    immediately with a beta cut-off (try first a rough eval - delta)
*******************************************************************************/
    quiesce = ((!s->under_check) && (depth<=0)) || (depth<-60*PLY);
#if 0
    if(quiesce && depth>=-100)
    {
        int num_mv;
        Move *mv = mv_stack + mv_stack_top;
        board.do_null_move();
        num_mv = board.find_moves(mv);

        for(int i=0;i<num_mv;i++)
        {
            if(!mv[i].capture)
                continue;
            if(board.move_see_val(mv[i])>0)
            {
                quiesce = false;
                break;
            }
        }

        board.undo_null_move();
    }
#endif

    if(quiesce)
    {
        stat_evaluate++;
        best = board.evaluate(st_computer_color, alpha, beta);

        alpha = MAX(alpha, best);
        if(best >= beta)
        {
            stat_evaluate_cutoff++;
            goto search_done;
        }

        //best =0;
#if QUIESCENCE
        if(ply>60)
#endif //QUIESCENCE
            goto search_done;
    }


#if NULL_MOVE
/*******************************************************************************
    Try the null move.
*******************************************************************************/
    if(!s->under_check && (stack[ply-1].curr_move!=-1) && depth >= 2*PLY && beta<INF-1000)
    {
        int16_t val;
        int sdepth = depth-3*PLY;

        stat_null_move++;
        s->curr_move = -1;
        current_ply++;
        board.do_null_move();
        val = -search( ply+1, sdepth, true, -beta, -beta+1);
        board.undo_null_move();
        current_ply--;

        /* null move cut! */
        if(val >= beta)
        {
            stat_null_cut++;
            return val;
        }

        if(val<alpha-100 &&  /* we are facing a threat*/
           stack[ply+1].best_move != -1) /* be sure we aren't reading random memory */
        {
            /* ok, officially the array stack[ply+1].moves has already
                been deallocated, but who cares :) */
            s->threat = stack[ply+1].moves[stack[ply+1].best_move];

            #if 0
            /* Botvinnik-Markoff extension!!! */
            if(!extended && ply>=3 && (s->threat == stack[ply-2].threat) )
            {
                depth += 80;
                extended = true;
            }
            #endif
        }
    }
#endif



/*******************************************************************************
    Now generate the legal moves and look for a check/stalemate
*******************************************************************************/

    /* generate all the legal moves */
    s->moves = &mv_stack[mv_stack_top];
    s->num_moves = board.find_moves(s->moves);
    mv_stack_top += s->num_moves;
    s->under_check = board.under_check;

    if(s->under_check==2) /* double check */
    {
        depth += 200;
        extended = true;
    }
    else if(s->under_check) /* simple check */
    {
        depth += 100;
        if(stack[ply-1].curr_move!=-1 &&
           !board.pins[stack[ply-1].moves[  /* last moved piece is not attacking the king */
             stack[ply-1].curr_move].to])   /* so this is a discover check */
        {
            depth += 50;
        }
        extended = true;
    }

    /* return now if the positon is terminal */
    if(!s->num_moves)
    {
        if(s->under_check)
        {
            /* while mating, sacrify as much as possible :) */
            best = -INF + ply;//*50 + board.material[IS_WHITE(eng_color)]/50;
        }
        else
            best = 0;
        goto search_done;
    }

    /* single-reply extension */
    if(s->num_moves == 1 && !extended)
    {
        depth += 100;
        extended = true;
    }
    else if(s->num_moves <= 3 && !extended)
    {
        depth += 50;
        extended = true;
    }

/*******************************************************************************
    Sort the moves.
    First comes the move from the hashtable, if avalable.
    The remaining moves are sorted with a heuristic that keeps in account
    the history heuristic (ie the moves that previously caused an alpha
    cutoff), a MVV/LVA bonus value and a small bonus for moves that go
    toward the center.
*******************************************************************************/
#if SORT_MOVES

#if HASH_HEURISTIC

        /* convert the move we got from the hash to the move structure */
        if(cbest_mv_hash)
        {
            best_mv_hash = board.uncompress_move(cbest_mv_hash);
            /* if it happened that the move we got from the hashtable
               is not valid, simply no move will get the high
               heuristic bonus value */
        }
        #if INTERNAL_ITERATIVE_DEEPENING
        else if(s->base_depth>300) /* don't do it only on the pv, or it will be useless :) */
        {
            int val = search( ply+1, s->base_depth-200, true, alpha, beta);
            /*if (val >= beta)
                val = search( ply+1, s->base_depth-200, true, alpha, INF, last_capture);*/
            //if (val <= alpha)
              //  val = search( ply+1, s->base_depth-200, true, -INF, beta, last_capture);

            /*HashEntry *h2 = probe_hash( board.hash );
            if(h2 && h2->best_mv)
            {
                cbest_mv_hash = h2->best_mv;
                best_mv_hash = board.uncompress_move(cbest_mv_hash);
            }*/
        }
        #endif //INTERNAL_ITERATIVE_DEEPENING
    #endif //HASH_HEURISTIC

    /* for each move calculate the heuristic goodness value */
    moves_heuristic( s->moves, s->num_moves, ply, s->base_depth,
                                  best_mv_hash, quiesce );

    /* if quiesce rip-off the "non-critical" moves */
    if(quiesce)
    {
        int n = 0;
        for(int i=0;i<s->num_moves;i++)
        if(s->moves[i].val>=28000)
            s->moves[n++] = s->moves[i];
        mv_stack_top -= s->num_moves-n;
        s->num_moves = n;
    }


    /* sort the moves using the heuristic values */
#if 0
    sort_moves( s->moves, s->num_moves );
#endif

#if HISTORY_HEURISTIC
    /* reset killer values for the 3-next search */
    if(depth>=200)
    {
        memset( &killers[ply+3], 0, 64*64*sizeof(uint16_t));
        /*memset( &history_hit[ply+3], 0, 64*64*sizeof(uint64_t));
        memset( &history_tot[ply+3], 0, 64*64*sizeof(uint64_t));*/
    }
#endif //HISTORY_HEURISTIC
#endif //SORT_MOVES



#if EARLY_TRANSP_CUTOFF && HASH_TABLE
/*******************************************************************************
    Try to get an early beta cutoff using the hash table values
    of the following moves, and improve alpha too.
    Try on the first 6 value of the ordered moves (argh, looking into the
    hashtable is very expensive because of the cache!!!!!!!!)
*******************************************************************************/
    if(depth>=2*PLY)
    for(int i=MIN(s->num_moves-1,10);i>0;i--)
    {
        HashKey hk = board.move_hash(s->moves[i]);
        HashEntry *h2 = probe_hash( hk );
        stat_hash_tot++;

        if(h2 && h2->depth >= depth-100)
        {
            int16_t u = h2->upper();
            if(-u >= beta)
            {
                /* increase the node count to simulate calling
                the search function for this move */
                stat_early_transp++;
                processed_nodes++;

                best = -u;
                goto search_done;
            }
        }
    }
#endif //EARLY_TRANSP_CUTOFF && HASH_TABLE


    /* set the current best move index (as will be saved in the hash) */
    best_mv_found = 0;

/*******************************************************************************
    It is now time to loop all the successor moves and search recursively.
*******************************************************************************/

    /* calcluate the evaluation (required by fitility pruning) */
    position_val = quiesce ? best : board.evaluate( st_computer_color, -INF, INF);

    /*for DEBUG*/
#ifdef DEBUG
    {int w = IS_WHITE(board.color_to_move);
    for(int i=0;i<s->num_moves;i++)
    {
        if(s->moves[i].from == board.king_pos[w] && DISTANCE(s->moves[i].to, board.king_pos[!w]) < 2)
            ASSERT(!"Error!!!!");
    }}
#endif

    for(int i=0;i<s->num_moves;i++)
    {
        int16_t val;
        int sdepth = depth-100;

    #if SORT_MOVES
        /* sort moves incrementally, in the hope of a beta cut */
        incremental_sort_moves(s->moves+i, s->num_moves-i);
    #endif

    /* calculate local search extensions */
    #if 0
        if(!extended)
        {
            //if(s->moves[i].extend) /* extensions calculated during the heuristic sort */
              //  sdepth += 100;
            else if(s->moves[i].to == last_capture && board.move_see_val(s->moves[i])>=0)
                sdepth += 100;     /* recapture extension */
        }
    #endif

        /* recapture extension */
        static const int vallapiglia[] = { 0, 5, 3, 9, 3, 1, 0 };
        if(stack[ply-1].curr_move!=-1)
        {
            Move& prev = stack[ply-1].moves[stack[ply-1].curr_move];

            if(s->moves[i].to == prev.to)
            {
                if(vallapiglia[PIECE_OF(board.data[s->moves[i].to])]
                        == vallapiglia[PIECE_OF(prev.capture)])
                    depth += 50;
            }
        }

#if FUTILITY
        /* futility pruning, it is done only if we are no under check
           and the move is not a "critical" move */
        if(depth<300 && !s->under_check && s->moves[i].val <28000)
        {
            static const int mavala[] = { 0, 490, 315, 980, 315, 100, 0 };

            int16_t fmargin = quiesce ? 150 : (depth < 200 ? 320 : 850);
            int16_t fval = position_val + mavala[PIECE_OF(s->moves[i].capture)];
            if(fval < alpha-fmargin)
                continue;
        }
#endif

        if(!s->moves[i].capture && !(s->moves[i].flags>=PROMOTE_FIRST))
            history_tot[HISTORY_INDEX(s->moves[i])]++;

        s->curr_move = i;
        current_ply++;
        board.do_move(s->moves[i]);

#if NEGA_SCOUT        /* use negascout, (null window search for nodes that are not in the pv) */
        if(i == 0) // || depth<200)
            val = -search( ply+1, sdepth, pv, -beta, -alpha);
        else
        {
#if HISTORY_PRUNING
            /* history pruning, if this is not a "critical" move and the failhigh
               stats are too low, try a reduced depth search (if it returns >alpha,
               re-do the full depth search) */
            if( s->moves[i].val<28000 &&
                (history_hit[HISTORY_INDEX(s->moves[i])]+1)
                < (history_tot[HISTORY_INDEX(s->moves[i])]+1)/4)
            {
                val = -search( ply+1, sdepth - 100, false, -alpha-1, -alpha );
                if(val <= alpha)
                    goto skip_search; /* reduced search was effective */
            }
#endif
            val = -search( ply+1, sdepth, false, -alpha-1, -alpha );
            if((val>alpha) && pv)
                val = -search( ply+1, sdepth, true, -beta, -alpha );
        }
#else
        /* normal full width alpha-beta */
        val = -search( ply+1, sdepth, pv, -beta, -alpha );
#endif
skip_search:
        board.undo_move(s->moves[i]);
        current_ply--;

        /* update the current best value and check for and alpha cut */
        best = MAX(best, val);
        if(best > alpha)
        {
            best_mv_found = i;
            s->best_move = i;

            /* alpha cut! */
            alpha = best;
        }
        /* beta cut! */
        if(best >= beta)
            break;
    }

    /* update a few stats */
    if(!quiesce)
    {
        if(best_mv_found==0)
        {
            if(best >= beta)
                stat_best_cut++;
            else
                stat_best_first++;
        }
        stat_search_moves++;
        if(ply==0 && depth>100)
        {
            if(best_mv_found==0)
            {
                if(best >= beta)
                    stat_best_cut0++;
                else
                    stat_best_first0++;
            }
            stat_search_moves0++;
        }
    }

    /* improve the heuristic value of the best move */
#if SORT_MOVES && HISTORY_HEURISTIC
    for(int i=0;i<best_mv_found;i++)
    {
        uint16_t& val = killers[ply][HISTORY_INDEX(s->moves[i])];
        val = MAX(val-2, 0);
        //history_tot[HISTORY_INDEX(s->moves[i])]++;
    }
    killers[ply][HISTORY_INDEX(s->moves[best_mv_found])] += 3;

    if(best >= beta &&
            !s->moves[best_mv_found].capture &&
            !(s->moves[best_mv_found].flags>=PROMOTE_FIRST))
        history_hit[HISTORY_INDEX(s->moves[best_mv_found])]++;
    //history_tot[HISTORY_INDEX(s->moves[best_mv_found])]++;
#endif //SORT_MOVES && HISTORY_HEURISTIC

search_done:
    mv_stack_top -= s->num_moves; /* free the moves we allocated */
    /*if(best_mv_found>=0 && skip_null)
        strong_reply[ply] = mv[best_mv_found];
    else
        strong_reply[ply] = Move::FromInt(0);*/

#if HASH_TABLE
    /* if we found a best move searching, that move will be saved.
       if we did no search (ie quiescence), save the old hash value,
       or -1 if no hash entry had been found */
    int bestmv = cbest_mv_hash;
    if(best_mv_found >= 0)
        bestmv = board.compress_move(s->moves[best_mv_found]);

    /* write the value in the hash, with the index of the best move */
    write_hash( best > s->alpha ? best : -INF,
                best < beta ? best : +INF,
                MAX(s->base_depth,-500), bestmv);
#endif //HASH_TABLE

#if CONSISTENCY_EXTENSION
    /* instability re-search, ie search deeper the nodes whose value
       change a lot since last evaluation */
    //if(!skip_inst)
    if(s->base_depth < stack[ply-1].base_depth)
    {
        if( ((best < old_hash_lower-150) ||
             (best > old_hash_upper+150) )
                && old_hash_depth>=s->base_depth-100
                && s->base_depth<=400 && s->base_depth>0)// && !skip_null )
            return search(ply, s->base_depth+100, pv, alpha, beta );
    }
#endif //CONSISTENCY_EXTENSION

    return best;
}


Move Engine::find_best_move()
{
    SearchStack *s = &stack[0];
    Move retv;
    Move result[80];
#if RE_SEARCH
    bool research = true;
#endif //RE_SEARCH

    ASSERT(!thinking);

    /* initialize the root node */
    current_ply = 0;
    s->base_depth = 100;
    s->extensions = 0;
    s->curr_move = -1;
    s->alpha = -INF;
    s->beta = INF;
    s->threat = Move::FromInt(0);
    s->best_move = -1;

    s->moves = mv_stack;
    s->num_moves = mv_stack_top = board.find_moves(s->moves);

    /* to print the analysis */
    if(post)
        output("\tply\tscore\ttime\tnodes\tpv\n");

    /* return immediatly if the move is forced. */
    if(s->num_moves==1)
        return s->moves[0];

    /* probe the play lines */
    if( eng_status == PLAYING
        && st_computer_color == board.color_to_move
         && probe_lines( board.hash, &retv))
    {
        retv.val = 0;
        return retv;
    }

    /* probe the book */
    if(probe_book( board.hash, &retv)) {
        for(int i=0;i<s->num_moves++;i++)
        if(retv.as_int == s->moves[i].as_int)
        {
            retv.val = 0;
            return retv;
        }
        output("Error!!! invalid move in the book!!!\n");
    }

    #if 0
    prof_eval = 0;
    prof_find_moves = 0;
    prof_find_captures = 0;
    prof_heuristic = 0;
    prof_sort_moves = 0;
    prof_move_is_check = 0;
    prof_move_see_val = 0;
    prof_tot = rdtsc();
    #endif

    stat_early_transp = 0;
    stat_hash_tot = 0;
    stat_hash_ex = 0;
    stat_hash_low = 0;
    stat_hash_upp = 0;
    stat_best_first = 0;
    stat_best_cut = 0;
    stat_search_moves = 0;
    stat_best_first0 = 0;
    stat_best_cut0 = 0;
    stat_search_moves0 = 0;
    stat_evaluate = 0;
    stat_evaluate_cutoff = 0;
    stat_null_move = 0;
    stat_null_cut = 0;
    stat_hash_write = 0;
    //reset_hash();

    /* calculate how much time we will think*/
    start_think_time = current_time();
    if( analysis_limit == TIME_LIMIT )
    {
        if(board.color_to_move == st_computer_color)
            calc_best_time();
        else /* pondering? analysing? */
            time_best_csec = 99999999;
        max_think_time = start_think_time + time_best_csec - 2;
    }

    //analysis_color = board.color_to_move;
    processed_nodes = 0;
    thinking = true;
    make_old_hash();

    /* set the back jump for the quick thinking exit */
    if(setjmp(back))
        goto exit_thinking;

    /* start with a guess of 0 */
    s->moves[0].val = 0;
    retv = s->moves[0];

    /* do the iterative deepening thing. */
    while(1)
    {
        int16_t alpha = -INF;
        int i=0;

#if SORT_MOVES && HISTORY_HEURISTIC
        /* reset killer values for the next search */
        for(int i=0;i<40;i++)
            memset( &killers[i], 0, 64*64*sizeof(uint16_t));
#endif
        memset( history_tot, 0, 64*64*sizeof(uint64_t));
        memset( history_hit, 0, 64*64*sizeof(uint64_t));

        /* save the result of the previous search */
        result[s->base_depth/PLY-1] = s->moves[0];

        /* for each move call the alpha-beta search function */
        int best_mv = 0;
        for(i=0;i<s->num_moves;i++)
        {
            s->curr_move = i;
            current_ply++;
            board.do_move(s->moves[i]);
#if NEGA_SCOUT
            if(i == 0)
            {
                s->moves[i].val = -search( 1, s->base_depth-100, true,
                                                    -INF, -alpha );
            }
            else
            {
                s->moves[i].val = -search( 1, s->base_depth-100, false,
                                                    -alpha-1, -alpha );
                if(s->moves[i].val > alpha)
                    s->moves[i].val = -search( 1, s->base_depth-100, true,
                                                    -INF, -alpha );
            }
#else
            s->moves[i].val = -search( 1, s->base_depth-100, true,
                                                    -INF, -alpha );
#endif
            board.undo_move(s->moves[i]);
            current_ply--;


            /* cut alpha */
            if(s->moves[i].val > alpha)
            {
                alpha = s->moves[i].val;
                retv = s->moves[i];
                best_mv = i;
                s->best_move = i;

                /* this move caused an alpha cut, so print the new line */
                if( post /*&& processed_nodes>100000*/)
                {
                    output("\t%d\t%d\t%d\t%llu\t", s->base_depth/100,
                                s->moves[i].val, current_time() - start_think_time, processed_nodes);
                    print_moves(&s->moves[i], 1, true);
                }
            }
        }

        /* the search is done, sort the moves so that best is searched first */
        if(i>1)
        {
            s->moves[best_mv].val++;
            sort_moves(s->moves, i);   /* sort i moves (those that we where able to search) */
            s->moves[0].val--;
        }

        /* print the result of the analysis at this depth */
        if( post /*&& processed_nodes>100000*/)
        {
            output("\t%d\t%d\t%d\t%llu\t", s->base_depth/100,
                        s->moves[0].val, current_time() - start_think_time, processed_nodes);
            print_moves(&s->moves[0], 1, true);
        }

        /* max depth */
        if( s->base_depth >= 40*PLY )
                break;

        /* return in case of fixed depth search */
        if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
                analysis_limit == DEPTH_LIMIT && s->base_depth == st_depth*PLY)
            break;

        /* return if 3/5 of time is gone (we can't search another ply anyway) */
        if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
                analysis_limit == TIME_LIMIT &&
                (current_time()-start_think_time) >= (time_best_csec*3/5) )
            break;

        /* if a checkmate was detected return immediately */
        if( ABS(alpha) > INF-1000)
            break;

#if RE_SEARCH
        if(!research)
            s->base_depth += PLY;
        else
        {
            for(int i=0;i<(1<<21);i++)
            {
                HashEntry* h = &hash_table[i];
                h->depth -= PLY;
            }
            output(" -> (Hash purged)\n");
        }
        research = !research;
#else
        s->base_depth += PLY;
#endif
    }

exit_thinking:

    if(post)
    {
        #if 0
        prof_tot = rdtsc() - prof_tot;
        #define SHOW_PROF(a) output("@"#a": %llu (%llu%%)\n", \
                                prof_##a, prof_##a*100/prof_tot);
        SHOW_PROF(tot);
        SHOW_PROF(eval);
        SHOW_PROF(do_move);
        SHOW_PROF(find_moves);
        SHOW_PROF(find_captures);
        SHOW_PROF(heuristic);
        SHOW_PROF(move_is_check);
        SHOW_PROF(move_see_val);
        SHOW_PROF(sort_moves);
        #endif
        output("#nodes: %llu (~%llu nps)\n", processed_nodes, (processed_nodes*100)/
                                                MAX(current_time()-start_think_time,1) );
        output("#       %d times all the moves were seached (non-leaf non-quiesce node)\n",
                                                                        stat_search_moves);
        output("#        of which %d times first move caused a cutoff\n", stat_best_cut);
        output("#        of the remaining %d times first move was really best (%02d%%)\n",
           stat_best_first, (stat_best_first*100)/MAX(stat_search_moves-stat_best_cut, 1));
        output("#       evaluate was called %d times (quiescence node)\n", stat_evaluate);
        output("#        of which %d times caused an early cutoff (leaf node)\n",
                                                                    stat_evaluate_cutoff);
        output("#hash:  %d writes, %d probes (%d succesful, =%d, >%d, <%d)\n",
            stat_hash_write, stat_hash_tot, stat_hash_ex+stat_hash_low+stat_hash_upp,
                stat_hash_ex, stat_hash_low, stat_hash_upp );
        output("#etc: %d\n", stat_early_transp);
        output("#null move: %d (%d succesful)\n", stat_null_move, stat_null_cut);
    }

    thinking = false;
    return retv;
}