Tuned late move reduction.

[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

Move null_threat[MAX_PV];
bool null_threat_dangerous[MAX_PV];
uint8_t escape_from_1[MAX_PV];
uint8_t escape_from_2[MAX_PV];

#define HISTORY_SIZE (64*64)
uint16_t history_tot[HISTORY_SIZE];
uint16_t history_hit[HISTORY_SIZE];

#define HISTORY_INDEX(m) (SQUARE_TO_64(m.from)*64 + SQUARE_TO_64(m.to))

#define WORST_MATE (INF-2500)

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;


#if 0
#define STAT(x)
#else

#define S_ALL                      \
    S(max_quiesce_nodes);          \
    S(quiesce_nodes);              \
    S(quiesce_hash);               \
    S(quiesce_called);             \
    S(quiesce_best_can_be_first);  \
    S(quiesce_best_was_first);     \
    S(quiesce_cutoff);             \
    S(quiesce_cutoff_first);       \
    S(search_nodes);               \
    S(search_hash);                \
    S(search_best_can_be_first);   \
    S(search_best_was_first);      \
    S(search_cutoff);              \
    S(search_cutoff_first);        \
    S(null_tried);                 \
    S(null_successful);

#define STAT(x) stat_##x++;

#define S(x) uint64_t stat_##x;
    S_ALL
    Board max_quiesce_board;
    int16_t max_quiesce_alpha;
    int16_t max_quiesce_beta;
#undef S

void reset_stats()
{
#define S(x) stat_##x = 0;
    S_ALL
#undef S
}

void print_stats()
{
#define S(x) printf("# " #x " = %llu\n", (unsigned long long)stat_##x);
    S_ALL
#undef S
}

#endif

/* 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

/* 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:
   Extend when there is only one decent move */
#define SINGULAR_EXTENSION    0

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

/* futility pruning: */
#define FUTILITY              0

/* 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

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

/* improve the sorting heuristic for moves to the center */
#define CENTER_HEURISTIC     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)
    {
        printf("Thinking: ");
        for(int i=0; i<current_ply; i++)
        {
            if(stack[i].curr_move == -2)
                continue; //Internal iterative deepening
            else if(stack[i].curr_move == -1)
            {
                printf("<NULL>");
                board.do_null_move();
            }
            else
            {
                char buf[32];
                printf("%s", move_to_alg(buf, &(stack[i].moves[stack[i].curr_move]) ) );
                board.do_move(stack[i].moves[stack[i].curr_move]);
            }
            printf((i != current_ply-1) ? " " : "\n");
        }
        rewind_thinking();
        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 == -2)
        {}
        else if(stack[i].curr_move == -1)
            board.undo_null_move();
        else
            board.undo_move(stack[i].moves[stack[i].curr_move]);
    }
}

bool Engine::null_move_ok()
{
    int c = IS_WHITE(board.color_to_move) ? 5 : -1;
    int numpawns = board.mat_tracking[c+PAWN].count;
    int numpieces = board.mat_tracking[c+KNIGHT].count + board.mat_tracking[c+BISHOP].count
                    + board.mat_tracking[c+ROOK].count + board.mat_tracking[c+QUEEN].count;
    if(numpieces >= 2)
        return true;
    if(numpieces >= 1 && numpawns >= 2)
        return true;
    return false;
}

void Engine::restore_thinking()
{
    for(int i=0; i<current_ply; i++)
    {
        if(stack[i].curr_move == -2)
        {}
        else 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, Move* prev)
{
    int hash_move = -1;

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

        /* 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;

#if 1
#if 0
        if(PIECE_OF(board.data[mv[i].from]) != PAWN &&
            (mv[i].from == escape_from_1[ply-1] || mv[i].from == escape_from_2[ply-1]) )
        {
            int x = board.move_see_val(mv[i]);

            if(x >= 0)
            {
                mv[i].val += 29000 + x; /* escape */
                mv[i].extend = PLY;
                continue;
            }
        }
#endif

        /* 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 += 29599; /* 7th push */
                    mv[i].extend = PLY;   /* extend search */
                    continue;
                }
            }

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

                if(x>=0)
                {
                    mv[i].val += 29600; /* promote! */
                    mv[i].extend = PLY;   /* extend search */
                    continue;
                }
            }

            #if 1
            if(orig_depth >= 2*PLY)
            {
                /* pawn strike */
                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;
                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 = 27000; /* pawn strike! */
                        //mv[i].extend = PLY;   /* extend search */
                        continue;
                    }
                }
            }
            #endif
        }
#endif
        if(mv[i].capture)
        {
            int x = board.move_see_val(mv[i]);

            if(prev && prev->capture &&
                 (mv[i].to == prev->to) && (x >= Board::simple_values[PIECE_OF(prev->capture)]) )
            {
                mv[i].val = 29900;
                if( (x == Board::simple_values[PIECE_OF(prev->capture)]) )
                    mv[i].extend = /*(x==1) ? (PLY/2) :*/ PLY;
//                      else if(prev->capture && ABS(x - Board::simple_values[PIECE_OF(prev->capture)]) == 1)
//                          mv[i].extend = PLY/2;
                continue;
            }

            if(x>0)
            {
                if(orig_depth>-7*PLY && board.move_is_check(mv[i]) )
                    mv[i].val = 29800+x;
                else
                    mv[i].val = 29000+x;
                continue;
            }
            else if(x>=0 && 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;
            }
        }

        /* null-move threat */
        if(null_threat[ply-1] == mv[i])
        {
            mv[i].val = 28500;
            continue;
        }

        mv[i].val += history_hit[HISTORY_INDEX(mv[i])] * 1024 / (history_tot[HISTORY_INDEX(mv[i])] + 4);

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


void
Engine::moves_quiescence_heuristic(Move *mv, int num_mv, const Move& best_mv_hash,
                           int static_eval, int alpha, int beta, int orig_depth, Move* prev)
{
    for(int i=0;i<num_mv;i++)
    {
        mv[i].val = -10000;
        mv[i].extend = 0;

        /* 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)
        {
            mv[i].val = 30000;
            continue;
        }

#if 0
        /* 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 = PLY;   /* 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 = PLY;   /* 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 = PLY;   /* extend search */
                continue;
            }
            #endif
        }
#endif
        if(mv[i].capture)
        {
            int x = board.move_see_val(mv[i]);

            if(prev && prev->capture &&
                (mv[i].to == prev->to) && (x >= Board::simple_values[PIECE_OF(prev->capture)]) )
            {
                mv[i].val = 29900;
                if( (x == Board::simple_values[PIECE_OF(prev->capture)]) )
                    mv[i].extend = /*(x==1) ? (PLY/2) :*/ PLY;
//                      else if(prev->capture && ABS(x - Board::simple_values[PIECE_OF(prev->capture)]) == 1)
//                          mv[i].extend = PLY/2;
                continue;
            }

            if(x>0)
            {
                if(orig_depth>-5*PLY && board.move_is_check(mv[i]) )
                    mv[i].val = 18000+x;
                else
                    mv[i].val = 10000+x;
                continue;
            }
            else if(x>=0 && orig_depth>-5*PLY && board.move_is_check(mv[i]) )
            {
                /* = capture but check */
                mv[i].val = 18000;
                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 = 7990;
                continue;
            }
        }
    }
}


/*******************************************************************************
    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(depth <= 0)
        STAT(quiesce_nodes)

    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;
    null_threat[ply] = Move::FromInt(0);
    null_threat_dangerous[ply] = false;
    //escape_from_1[ply] = escape_from_2[ply] = INVALID;

    /* 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! */

/*******************************************************************************
    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(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(h)
        cbest_mv_hash = h->best_mv;

/*******************************************************************************
    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 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 //PAPOPEPO
    if(quiesce && depth>=-PLY)
    {
        int num_mv;
        Move *mv = mv_stack + mv_stack_top;
        board.do_null_move();
        num_mv = board.find_moves(mv);
        uint8_t pup = INVALID;

        for(int i=0;i<num_mv;i++)
        {
            if(!mv[i].capture || PIECE_OF(mv[i].capture)==PAWN)
                continue;
            if(mv[i].to != pup && board.move_see_val(mv[i])>0)
            if(pup == INVALID)
                pup = mv[i].to;
            else
            {
                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;
        }

        if(ply>60)
            goto search_done;
    }

#if NULL_MOVE
/*******************************************************************************
    Try the null move.
*******************************************************************************/
    if(!s->under_check && (stack[ply-1].curr_move != -1) && depth >= 2*PLY && beta<WORST_MATE && null_move_ok())
    {
        int16_t val;
        int sdepth = (depth >= 5*PLY) ? (depth-4*PLY) : 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 < -WORST_MATE)
            null_threat_dangerous[ply] = true;
#if 0
        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
    }
#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 += 2*PLY;
        extended = true;
    }
    else if(s->under_check) /* simple check */
    {
        depth += PLY;
        if(stack[ply-1].curr_move>=0 &&
           !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 += PLY/2;
        }
        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 += PLY;
        extended = true;
    }
    else if(s->num_moves <= 3 && !extended)
    {
        depth += PLY/2;
        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.
*******************************************************************************/

    /* 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>3*PLY && pv) /* don't do it only on the pv, or it will be useless :) */
    {
        s->curr_move = -2;
        current_ply++;
        int val = search(ply+1, s->base_depth-2*PLY, true, alpha, beta);
        current_ply--;

        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

    /* for each move calculate the heuristic goodness value */
    {
        Move *prev = (stack[ply-1].curr_move>=0) ? &stack[ply-1].moves[stack[ply-1].curr_move] : NULL;
        if(quiesce)
            moves_quiescence_heuristic( s->moves, s->num_moves, best_mv_hash,
                                            best, alpha, beta, s->base_depth, prev);
        else
            moves_heuristic( s->moves, s->num_moves, ply, s->base_depth,
                                            best_mv_hash, quiesce, prev );
    }

    /* 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>0)
            s->moves[n++] = s->moves[i];
        mv_stack_top -= s->num_moves-n;
        s->num_moves = n;
    }

    /* Don't do it now, do it incrementally */
    //sort_moves( s->moves, s->num_moves );


#if EARLY_TRANSP_CUTOFF
/*******************************************************************************
    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 >= 3*PLY)
    {
        HashKey hk = board.move_hash(s->moves[0]);
        for(int i=1;i<s->num_moves;i++)
        {
            prefetch_hash(hk);
            HashKey newhk = board.move_hash(s->moves[i]);
            HashEntry *h2 = probe_hash( hk );
            hk = newhk;

            if(h2 && h2->depth >= depth-PLY)
            {
                if(-h2->up >= beta)
                {
                    best = -h2->up;
                    goto search_done;
                }
                alpha = MAX(alpha, (int16_t)-h2->up);
            }
        }

        HashEntry *h2 = probe_hash( hk );
        if(h2 && h2->depth >= depth-PLY)
        {
            if(-h2->up >= beta)
            {
                best = -h2->up;
                goto search_done;
            }
            alpha = MAX(alpha, (int16_t)-h2->up);
        }
    }
#endif //EARLY_TRANSP_CUTOFF

    /* 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.
*******************************************************************************/

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

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

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

        if(depth < s->base_depth+100)
            sdepth += s->moves[i].extend; /* extensions calculated during the heuristic sort */

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

            int16_t fmargin = (depth <= PLY ? 420 : 950);
            int16_t fval = position_val + mavala[PIECE_OF(s->moves[i].capture)];
            if(fval < alpha-fmargin)
                continue;
        }
#endif

        /* collect history statistics  */
        if(s->moves[i].val<28000)
        {
            int ix = HISTORY_INDEX(s->moves[i]);
            if(history_tot[ix] > 1024)
            {
                history_tot[ix] = history_tot[ix]*7/8;
                history_hit[ix] = history_hit[ix]*7/8;
            }
            history_tot[ix]++;
        }

#if 0
        if(!quiesce && PIECE_OF(board.data[s->moves[i].from]) == PAWN && s->moves[i].val == 27000) //FIXME, UGLY
        {
            escape_from_1[ply] = s->moves[i].to + Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
            escape_from_2[ply] = s->moves[i].to + Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;
        }
        else
        {
            escape_from_1[ply] = escape_from_2[ply] = 0;
        }
#endif

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

        {
            uint64_t q;
            if(s->base_depth > 0 && sdepth <= 0)
            {
                STAT(quiesce_called);
                q = stat_quiesce_nodes;
            }

#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 LATE_MOVE_REDUCTION
                /* 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((sdepth>0) && !s->under_check && depth<=3*PLY && s->moves[i].val<28000 &&
//                     (history_hit[HISTORY_INDEX(s->moves[i])]+1)*3
//                         < (history_tot[HISTORY_INDEX(s->moves[i])]+1))
                if((sdepth>0) && !s->under_check && s->moves[i].val<28000 && (i>=7 || (i>=5 && s->moves[i].val<350) ) )
                {
                    val = -search( ply+1, sdepth - PLY, 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

            if(s->base_depth > 0 && sdepth <= 0)
            {
                q = stat_quiesce_nodes-q;
                if(q > stat_max_quiesce_nodes)
                {
                    stat_max_quiesce_nodes = q;
                    max_quiesce_board = board;
                }
            }
        }
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++;
        }
    }

    /* collect statistics for the history */
    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])]++;
    }

search_done:
    mv_stack_top -= s->num_moves; /* free the moves we allocated */

    /* this is a null move, save what the threat is */
    if(stack[ply-1].curr_move == -1 && best_mv_found >= 0)
        null_threat[ply-1] = s->moves[best_mv_found];

    /* 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 ? MAX(best, s->alpha) : +INF,
                MAX(s->base_depth,-500), bestmv);

    return best;
}


Move Engine::find_best_move()
{
    int num_mate_hits = 0;
    SearchStack *s = &stack[0];
    Move retv;
    Move result[80];

    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);

    /* 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;
    }

    /* 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_stats();
    //reset_hash();

    //analysis_color = board.color_to_move;
    processed_nodes = 0;
    int16_t best_guess = 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;

        memset( history_tot, 0, HISTORY_SIZE*sizeof(uint16_t));
        memset( history_hit, 0, HISTORY_SIZE*sizeof(uint16_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-PLY, true, -INF, -alpha );
            }
            else
            {
                s->moves[i].val = -search( 1, s->base_depth-PLY, false, -alpha-1, -alpha );
                if(s->moves[i].val > alpha)
                    s->moves[i].val = -search( 1, s->base_depth-PLY, 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);
                }
            }
        }

        best_guess = alpha;

        /* 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) > WORST_MATE)
        {
            num_mate_hits++;
            if(num_mate_hits >= 5)
                break;
        }

        s->base_depth += PLY;
    }

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);

        print_stats();
        char buf[256];
        max_quiesce_board.write_board(buf);
        output("#max quiesce board: %s [%d %d]\n", buf, max_quiesce_alpha, max_quiesce_beta);
    }

    thinking = false;
    return retv;
}