Fixed sideeffects of enabling the gui to visualize the search tree.

[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 "search_gui.h"
#include "search.h"
#include <string.h>
#include <stdlib.h>



#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 nega-scout pv-search */
#define NEGA_SCOUT            1

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

/* il null move > beta-margin, reduce (not a dangerous position). Set to 1 to disable */
#define NULL_SOLIDITY_MARGIN  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   0

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

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

#define IGNORE_ALLBAD_NODES   0


void Engine::print_stat()
{
    if(thinking && current_root)
    {
        output("stat01: %d %llu %d %d %d %s\n",
            current_time() - start_think_time,
            (unsigned long long)processed_nodes,
            current_root->base_depth/PLY,
            current_root->stack[0].num_moves - 1 - current_root->stack[0].curr_move,
            current_root->stack[0].num_moves,
            board.move_to_alg(TmpStr().data(),
                    current_root->stack[0].moves[current_root->stack[0].curr_move])
        );
    }
    else
        output("stat01: 0 0 0 0 0\n");
}

bool SearchRoot::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
SearchRoot::moves_heuristic(Move *mv, int num_mv, bool pv, int ply, int orig_depth,
                            Move best_mv_hash, bool quiesce, Move* prev, int* overall_extensions,
                            int p1, int p2)
{
#if PAWN_STRIKE
    int escapes[2];
    int num_escapes = 0;
#endif //PAWN_STRIKE
    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 PAWN_STRIKE
        if(num_escapes<=2 && PIECE_OF(board.data[mv[i].from]) != PAWN &&
            (mv[i].from == stack[ply-1].escape_from[1] || stack[ply-1].escape_from[2]) )
        {
            int x = board.move_see_val(mv[i]);

            if(x >= 0)
            {
                if(num_escapes < 2)
                    escapes[num_escapes] = i;
                num_escapes++;
            }
        }
#endif //PAWN_STRIKE

        /* process strong pawn moves */
        if(PIECE_OF(board.data[mv[i].from])==PAWN)  /* pawn strike */
        {
            uint8_t x = X(mv[i].to);
            uint8_t y = IS_WHITE(board.color_to_move) ? Y(mv[i].to) : 7-Y(mv[i].to);

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

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

            if(y >= 4)
            {
                int other = IS_WHITE(board.other_color);
                uint8_t pos = 7-y;
                if((!board.line_pawns[other][x].count || board.line_pawns[other][x].pos[0] > pos)
                    && (x==0 || !board.line_pawns[other][x-1].count || board.line_pawns[other][x-1].pos[0] >= pos)
                    && (x==7 || !board.line_pawns[other][x+1].count || board.line_pawns[other][x+1].pos[0] >= pos))
                {
                    int x = board.move_see_val(mv[i]);

                    if(x>=0)
                    {
                        mv[i].val += y >= 5 ? 29550 : 29500; /* passed pawn advancing! */
                        if(y >= 5)
                            mv[i].extend = PLY;   /* extend search */
                        continue;
                    }
                }
            }

            /* pawn attack */
            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! */
                        continue;
                    }
                }
            }
        }

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

            /* recapture? */
            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 = PLY;
                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(board.move_is_check(mv[i]) )
        {
            if(board.move_see_val(mv[i])>=0)
                mv[i].val = 28799;
            else
                mv[i].val = 28700;
            continue;
        }

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

#if 1
        mv[i].val += (history_hit[HISTORY_INDEX(mv[i])] + 32) * 1024 / (3 * (history_tot[HISTORY_INDEX(mv[i])] + 64));

        int mx = CAPT_INDEX(mv[i]);
        if(p1 != -1)
        {
            int ix = FAST_PLUTO(p1, mx);
            mv[i].val += (pluto_hit[ix] + 24) * 1024 / (3 * (pluto_tot[ix] + 48));
        }
        else
            mv[i].val += 512/3;
        if(p2 != -1)
        {
            int ix = FAST_PLUTO(p2, mx);
            mv[i].val += (pluto2_hit[ix] + 16) * 1024 / (3 * (pluto2_tot[ix] + 32));
        }
        else
            mv[i].val += 512/3;
#else
        mv[i].val += (history_hit[HISTORY_INDEX(mv[i])] + 32) * 256*4 / (history_tot[HISTORY_INDEX(mv[i])] + 64);
#endif
    }

#if PAWN_STRIKE
    if((stack[ply-1].escape_from[1] != INVALID || stack[ply-1].escape_from[2] != INVALID) && num_escapes <= 2)
    {
        for(int i=0;i<num_escapes;i++)
            mv[escapes[i]].extend = PLY;
    }
#endif //PAWN_STRIKE

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


void
SearchRoot::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)
{
    int hash_move = -1;
    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)
            hash_move = i;

        /* process strong pawn moves */
        if(PIECE_OF(board.data[mv[i].from])==PAWN)
        {
            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 += 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 += 29500; /* promote! */
                    mv[i].extend = PLY;   /* extend search */
                    continue;
                }
            }
        }

        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 + x;
                if( (x == Board::simple_values[PIECE_OF(prev->capture)]) )
                    mv[i].extend = PLY;
                continue;
            }

            if( x>0 && ((orig_depth>-2*PLY || static_eval==-INF) ? true : x*100+static_eval+200>alpha) )
            {
                mv[i].val = 10000+x;
                continue;
            }
            else if((x>=0 && orig_depth>-4*PLY) && board.move_is_check(mv[i]) )
            {
                /* = capture but check */
                mv[i].val = 8000;
                continue;
            }
        }
        else /* add a bonus for checks (but not too deep, or quiescence will get mad) */
        if(orig_depth>-2*PLY && board.move_is_check(mv[i]) && board.move_see_val(mv[i])>=0)
        {
            mv[i].val = 5000;
            continue;
        }
    }

    if(hash_move >= 0 && mv[hash_move].val > 9000)
        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 SearchRoot::search(int ply, int base_depth, bool pv, int16_t orig_alpha, int16_t beta, bool expect_allbad)
{
    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;
    bool    no_good_moves = false;
    int16_t lower_bound = -INF;
#if FUTILITY
    int16_t position_val;
#endif
    int     depth = base_depth;
    int16_t alpha = orig_alpha;
    int pluto1, pluto2;

#if IGNORE_ALLBAD_NODES
    expect_allbad = false;
#endif

#if 0
    if(ply >= 75)
    {
        for(int i=ply-1;i>=0;i--)
        {
            if(stack[i].curr_move == -1)
                board.undo_null_move(stack[i].save_buf);
            else if(stack[i].curr_move >= 0)
                board.undo_move(stack[i].moves[stack[i].curr_move], stack[i].save_buf);
        }
        printf("[FEN \"%s\"]\n", board.to_fen(BigStr().data()) );
        for(int i=0;i<ply;i++)
        {
            printf(" %s", stack[i].curr_move <= -1 ? "NULL" :
                        board.move_to_alg(TmpStr().data(), stack[i].moves[stack[i].curr_move]));
            if(stack[i].curr_move == -1)
                board.do_null_move(stack[i].save_buf);
            else if(stack[i].curr_move >= 0)
                board.do_move(stack[i].moves[stack[i].curr_move], stack[i].save_buf);
        }
        printf(" *\n");
        exit(0);
    }
#endif

//     if(depth <= 0)
//         STAT(quiesce_nodes)

    s->num_moves = 0;
    s->curr_move = -3;
    s->best_move = -1;
    s->null_threat = Move::FromInt(0);
    s->null_threat_dangerous = false;
#if PAWN_STRIKE
    stack[ply].escape_from[1] = stack[ply].escape_from[2] = INVALID;
#endif //PAWN_STRIKE

    engine->prefetch_hash( board.hash );

    /* check if time is running out */
    engine->check_time();

    /* check for a draw for repetition or 50mvs. Of course the draw for
        repetition must be checked BEFORE probing the hash :)*/
    if(check_draw(ply))
        return (board.color_to_move == engine->st_computer_color) ? engine->v_eval_draw :
               ((board.other_color == engine->st_computer_color) ? -engine->v_eval_draw : 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 :)
*******************************************************************************/

    HashEntry *h = engine->probe_hash( board.hash );

    if(h){
        GUI(notify_hash(ply, h->lo, h->up, h->depth, alpha, beta,
            h->best_mv ? board.uncompress_move(h->best_mv) : Move::None(), false,
            (((h->depth >= base_depth) && (h->lo>=beta || h->up==h->lo || h->up<=alpha))
                 ? SearchGui::Bold : 0) | SearchGui::Magenta) );
    }

    if(h && (h->depth >= 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);
        best = 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)) || (ply > 70);
    if(quiesce)
        STAT(quiesce_nodes);

#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 && (best == -INF || ply>70) )
    {
        best = board.evaluate(engine->st_computer_color, alpha, beta);
        lower_bound = best; //we have at the very least "best" as lower bound now.
        GUI(notify_eval(ply, best, alpha, beta, best>=beta ? SearchGui::Blue|SearchGui::Bold : SearchGui::Blue ));

        alpha = MAX(alpha, best);
        if(best >= beta)
            goto search_done;

        if(ply>70)
            goto search_done;
    }

    if(quiesce && h && h->no_good_moves)
        goto search_done;

#if NULL_MOVE
/*******************************************************************************
    Try the null move.
*******************************************************************************/
    if(!expect_allbad && !pv && !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;

        s->curr_move = -1;
        board.do_null_move(s->save_buf);
        GUI1(notify(&board, Move::None(), ply, sdepth, -INF, beta-NULL_SOLIDITY_MARGIN, beta, SearchGui::Green ));
        val = -search( ply+1, sdepth, false, -beta, -beta+NULL_SOLIDITY_MARGIN, false);
        GUI2(notify_value(ply, val, DIFF_NODES, SearchGui::Bold ));
        board.undo_null_move(s->save_buf);

        /* null move cut! */
        if(val >= beta)
            return val;

#if NULL_SOLIDITY_MARGIN > 1
        if(depth <= 3*PLY && val > beta - NULL_SOLIDITY_MARGIN)
            depth -= PLY;
#endif

        if(val < -WORST_MATE)
            s->null_threat_dangerous = 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;

    pluto1 = stack[ply-1].best_move >=0 ? PLUTO1(stack[ply-1].moves[stack[ply-1].best_move]) : -1;
    pluto2 = (ply>=2 && stack[ply-1].best_move >=0 && stack[ply-2].best_move >=0) ?
        PLUTO2(stack[ply-2].moves[stack[ply-2].best_move], stack[ply-1].moves[stack[ply-1].best_move]) : -1;

    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 :) */
            int mt = IS_WHITE(board.other_color) ? 5 : -1;
            int16_t matval = Board::simple_values[PAWN]*board.mat_tracking[mt+PAWN].count +
                             Board::simple_values[KNIGHT]*board.mat_tracking[mt+KNIGHT].count +
                             Board::simple_values[BISHOP]*board.mat_tracking[mt+BISHOP].count +
                             Board::simple_values[QUEEN]*board.mat_tracking[mt+QUEEN].count;
            best = alpha = beta = -INF + ply*100 + matval;
        }
        else
            best = alpha = beta = 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(base_depth>3*PLY && pv) /* don't do it only on the pv, or it will be useless :) */
    {
        int val;
        s->curr_move = -2;
        GUI1(notify(&board, Move::None(), ply, base_depth-2*PLY, -INF, alpha, beta, SearchGui::Blue ));
        val = search(ply+1, base_depth-2*PLY, true, alpha, beta, expect_allbad);
        GUI2(notify_value(ply, val, DIFF_NODES, 0));

        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 */
#if DEBUG && TRACK_ATTACKS
    board.check_attacks();
#endif
    {
        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, base_depth, prev);
        else
        {
            int overall_ext = 0;
            moves_heuristic( s->moves, s->num_moves, pv, ply, base_depth,
                                            best_mv_hash, quiesce, prev, &overall_ext, pluto1, pluto2 );
            depth += overall_ext;
        }
    }
#if DEBUG && TRACK_ATTACKS
    board.check_attacks();
#endif

    /* 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;
        if(!n)
            no_good_moves = true;
    }

    /* 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++)
        {
            engine->prefetch_hash(hk);
            HashKey newhk = board.move_hash(s->moves[i]);
            HashEntry *h2 = engine->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 = engine->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

/*******************************************************************************
    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.dummy_evaluate(); //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 */
        engine->incremental_sort_moves(s->moves+i, s->num_moves-i);

        /* extensions calculated during the heuristic sort */
        sdepth += s->moves[i].extend;

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

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

        if(!expect_allbad)
        {
            int mx = CAPT_INDEX(s->moves[i]);

            /* collect history statistics  */
            if(!s->moves[i].capture &&
                !(s->moves[i].flags>=PROMOTE_FIRST) )
            {
                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] += quiesce ? 8 : 16;
            }

            if(pluto1!=-1 && !s->moves[i].capture &&
                !(s->moves[i].flags>=PROMOTE_FIRST))
            {
                int ix = FAST_PLUTO(pluto1, mx);
                if(pluto_tot[ix] > 256)
                {
                    pluto_tot[ix] = pluto_tot[ix]*7/8;
                    pluto_hit[ix] = pluto_hit[ix]*7/8;
                }
                pluto_tot[ix] += quiesce ? 8 : 16;
            }

            if(pluto2!=-1 && !s->moves[i].capture &&
                !(s->moves[i].flags>=PROMOTE_FIRST))
            {
                int ix = FAST_PLUTO(pluto2, mx);
                if(pluto2_tot[ix] > 128)
                {
                    pluto2_tot[ix] = pluto2_tot[ix]*7/8;
                    pluto2_hit[ix] = pluto2_hit[ix]*7/8;
                }
                pluto2_tot[ix] += quiesce ? 8 : 16;
            }
        }

        //Set data for pawn-strike
#if PAWN_STRIKE
        if(!quiesce && PIECE_OF(board.data[s->moves[i].from]) == PAWN && s->moves[i].val == 27000) //FIXME, UGLY
        {
            stack[ply].escape_from[1] = s->moves[i].to + Board::up_dir[IS_WHITE(board.color_to_move)] + RIGHT;
            if(OUT_OF_BOARD(stack[ply].escape_from[1]) || !IS_OF_COLOR(board.data[stack[ply].escape_from[1]], board.other_color)
                    || PIECE_OF(board.data[stack[ply].escape_from[1]])==PAWN)
                stack[ply].escape_from[1] = INVALID;
            stack[ply].escape_from[2] = s->moves[i].to + Board::up_dir[IS_WHITE(board.color_to_move)] + LEFT;
            if(OUT_OF_BOARD(stack[ply].escape_from[2]) || !IS_OF_COLOR(board.data[stack[ply].escape_from[2]], board.other_color)
                    || PIECE_OF(board.data[stack[ply].escape_from[2]])==PAWN)
                stack[ply].escape_from[2] = INVALID;
        }
        else
        {
            stack[ply].escape_from[1] = stack[ply].escape_from[2] = INVALID;
        }
#endif //PAWN_STRIKE
        s->curr_move = i;
        board.do_move(s->moves[i], s->save_buf);

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

#if NEGA_SCOUT        /* use negascout, (null window search for nodes that are not in the pv) */
            if(i == 0 && !expect_allbad)
            {
                if(depth>=0 && pv && mv_pv_top>=ply)
                {
                    mv_pv[ply] = s->moves[i];
                    mv_pv_top = ply + 1;
                }
#endif
                GUI1(notify(&board, s->moves[i], ply, sdepth, s->moves[i].val, alpha, beta, SearchGui::Bold ));
                val = -search( ply+1, sdepth, pv, -beta, -alpha, !pv);
                GUI2(notify_value(ply, val, DIFF_NODES, 0));
#if NEGA_SCOUT
            }
            else
            {
                bool red_fuck = false;
#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->null_threat_dangerous
                        && s->moves[i].val<28000 && (s->moves[i].val<(sdepth<=PLY ? 650 : 450)) )
                {
                    int rdepth = depth - 2*PLY;
                        //sdepth - PLY; //(s->moves[i].val<250 ? 2*PLY : PLY) - s->moves[i].extend;
                    GUI1(notify(&board, s->moves[i], ply, rdepth, s->moves[i].val, alpha, alpha+1, SearchGui::Italic|SearchGui::Gray ));
                    val = -search( ply+1, rdepth, false, -alpha-1, -alpha, false );
                    GUI2(notify_value(ply, val, DIFF_NODES, val>alpha ? SearchGui::Red : 0));
                    if(val <= alpha)
                        goto skip_search; /* reduced search was effective */
                    red_fuck = true;
                }
#endif
                GUI1(notify(&board, s->moves[i], ply, sdepth, s->moves[i].val, alpha, alpha+1, 0 ));
                val = -search( ply+1, sdepth, false, -alpha-1, -alpha, red_fuck);
                GUI2(notify_value(ply, val, DIFF_NODES, val>alpha ? SearchGui::Red : 0));

                if((val>alpha) && pv)
                {
                    if(depth>=0 && mv_pv_top>=ply)
                    {
                        mv_pv[ply] = s->moves[i];
                        mv_pv_top = ply + 1;
                    }

                    GUI1(notify(&board, s->moves[i], ply, sdepth, -INF, alpha, beta, SearchGui::Bold ));
                    val = -search( ply+1, sdepth, true, -beta, -alpha, false );
                    GUI2(notify_value(ply, val, DIFF_NODES, val>beta ? SearchGui::Red : 0));
                }
            }
#endif

#if 0
            if(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;
                }
            }
#endif
        }
#if NEGA_SCOUT && LATE_MOVE_REDUCTION
skip_search:
#endif
        board.undo_move(s->moves[i], s->save_buf);

        /* update the current best value and check for and alpha cut */
        if(val > best)
        {
            best = val;

            best_mv_found = i;
            s->best_move = i;
        }

        if(best > alpha)
        {
            /* alpha improvement! */
            alpha = best;
        }

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

    if(!expect_allbad || best >= beta)
    {
        /* collect statistics for the history */
        if(/*best >= beta &&*/ (best_mv_found!=-1) &&
                !s->moves[best_mv_found].capture &&
                !(s->moves[best_mv_found].flags>=PROMOTE_FIRST) )
            history_hit[HISTORY_INDEX(s->moves[best_mv_found])] += quiesce ? 8 : 16;

        int mx = CAPT_INDEX(s->moves[best_mv_found]);
        if(pluto1!=-1 && !s->moves[best_mv_found].capture &&
            !(s->moves[best_mv_found].flags>=PROMOTE_FIRST))
        {
            int ix = FAST_PLUTO(pluto1, mx);
            pluto_hit[ix] += quiesce ? 8 : 16;
        }

        if(pluto2!=-1 && !s->moves[best_mv_found].capture &&
            !(s->moves[best_mv_found].flags>=PROMOTE_FIRST))
        {
            int ix = FAST_PLUTO(pluto2, mx);
            pluto2_hit[ix] += quiesce ? 8 : 16;
        }
    }

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)
        stack[ply-1].null_threat = 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 */
    engine->write_hash( board.hash,
                best > orig_alpha ? MIN(best, beta) : lower_bound,
                best < beta ? best : +INF,
                MAX(base_depth,-500), bestmv, no_good_moves);
    GUI(notify_hash(ply, best > orig_alpha ? MIN(best, beta) : lower_bound, best < beta ? best : +INF,
                MAX(base_depth,-500), alpha, beta, bestmv ? board.uncompress_move(bestmv) : Move::None(), true,
                SearchGui::Bold | SearchGui::Magenta) );

    return best;
}

uint16_t SearchRoot::pluto_tot[PLUTO_SIZE];
uint16_t SearchRoot::pluto_hit[PLUTO_SIZE];
uint16_t SearchRoot::pluto2_tot[PLUTO_SIZE];
uint16_t SearchRoot::pluto2_hit[PLUTO_SIZE];
uint16_t SearchRoot::history_tot[HISTORY_SIZE];
uint16_t SearchRoot::history_hit[HISTORY_SIZE];

SearchRoot::SearchRoot(Engine* e, const Board& b)
    : mv_stack_top(0)
    , mv_pv_top(0)
    , search_gui(e->search_gui)
    , engine(e)
    , board(b)
{
    engine->current_root = this;
}

SearchRoot::~SearchRoot()
{
    engine->current_root = NULL;
}

Move Engine::find_best_move()
{
    ASSERT(!thinking);
    IFGUI(Engine *engine = this);
    int num_mate_hits = 0;
    SearchRoot root(this, board);
    SearchRoot::SearchStack *s = &root.stack[0];

    /* initialize the root node */
    root.base_depth = PLY;
    s->curr_move = -1;
    s->best_move = 0;
    s->null_threat = Move::FromInt(0);
    s->null_threat_dangerous = false;
    s->moves     = root.mv_stack;
    s->num_moves = root.mv_stack_top = root.board.find_moves(s->moves);
#if PAWN_STRIKE
    s->escape_from[1] = s->escape_from[2] = INVALID;
#endif //PAWN_STRIKE

    ASSERT(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)
    {
        if(post)
            output("\t0\t0\t0\t0\t%s (only move)\n", board.move_to_alg(MoveStr().data(), s->moves[0]));
        return s->moves[0];
    }

    /* probe the play lines */
    if(eng_status == PLAYING && st_computer_color == board.color_to_move)
    {
        Move retv = probe_lines(&root.board);

        if(retv.valid())
        {
            retv.val = 0;
            output("\t0\t0\t0\t0\t%s (selected line)\n", board.move_to_alg(MoveStr().data(), retv));
            return retv;
        }
    }

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

    reset_stats();
    reset_hash(); //Try to be deterministic
    processed_nodes = 0;
    thinking = true;
    make_old_hash();

    memset( root.history_tot, 0, HISTORY_SIZE*sizeof(uint16_t));
    memset( root.history_hit, 0, HISTORY_SIZE*sizeof(uint16_t));
    memset( root.pluto_tot, 0, PLUTO_SIZE*sizeof(uint16_t));
    memset( root.pluto_hit, 0, PLUTO_SIZE*sizeof(uint16_t));
    memset( root.pluto2_tot, 0, PLUTO_SIZE*sizeof(uint16_t));
    memset( root.pluto2_hit, 0, PLUTO_SIZE*sizeof(uint16_t));

    GUI(init_root());


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


    /* do the iterative deepening thing. */
    while(1)
    {
        int16_t alpha = num_mate_hits ? -INF : -WORST_MATE;
        int16_t beta = num_mate_hits ? INF : WORST_MATE;

        GUI(new_root_level(root.base_depth));

        /* for each move call the alpha-beta search function */
        for(int i=0;i<s->num_moves;i++)
        {
            s->curr_move = i;
            root.board.do_move(s->moves[i], s->save_buf);
#if NEGA_SCOUT
            if(i == 0)
            {
                root.mv_pv[0] = s->moves[i];
                root.mv_pv_top = 1;
#endif
                GUI1(notify(&root.board, s->moves[i], 0, root.base_depth-PLY, s->moves[i].val, alpha, beta, SearchGui::Bold));
                s->moves[i].val = -root.search( 1, root.base_depth-PLY, true, -beta, -alpha, false );
                GUI2(notify_value(0, s->moves[i].val, DIFF_NODES, 0));
#if NEGA_SCOUT
            }
            else
            {
                GUI1(notify(&root.board, s->moves[i], 0, root.base_depth-PLY, s->moves[i].val, alpha, alpha+1, 0 ));
                s->moves[i].val = -root.search( 1, root.base_depth-PLY, false, -alpha-1, -alpha, false );
                GUI2(notify_value(0, s->moves[i].val, DIFF_NODES, s->moves[i].val>alpha ? SearchGui::Red : 0));

                if(s->moves[i].val > alpha)
                {
                    root.mv_pv[0] = s->moves[i];
                    root.mv_pv_top = 1;

                    GUI1(notify(&root.board, s->moves[i], 0, root.base_depth-PLY, -INF, alpha, beta, SearchGui::Bold));
                    s->moves[i].val = -root.search( 1, root.base_depth-PLY, true, -beta, -alpha, false );
                    GUI2(notify_value(0, s->moves[i].val, DIFF_NODES, 0));
                }
            }
#endif
            root.board.undo_move(s->moves[i], s->save_buf);

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

                Move tmp = s->moves[i];
                for(int q=i-1;q>=0;q--)
                    s->moves[q+1] = s->moves[q];
                s->moves[0] = tmp;

                /* 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",
                                root.base_depth/PLY,
                                s->moves[0].val,
                                current_time() - start_think_time,
                                (unsigned long long)processed_nodes);
                    print_moves(root.mv_pv, 1/*root.mv_pv_top*/, true, true);
                }
            }
        }

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

        /* max depth */
        if( root.base_depth >= 50*PLY )
                break;

        /* return in case of fixed depth search */
        if( eng_status == PLAYING && st_computer_color == board.color_to_move &&
                analysis_limit == DEPTH_LIMIT && root.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;
        }

        root.base_depth += PLY;
    }

exit_thinking:

    if(post)
    {
        print_stats();
        output("#max quiesce board: %s [%d %d]\n", max_quiesce_board.to_fen(BigStr().data()),
                                                   max_quiesce_alpha, max_quiesce_beta);
    }

    thinking = false;
    return s->moves[0];
}