/* SPDX-License-Identifier: GPL-3.0-or-later */
/*
 *  Copyright (C) 2015-2021, Rasmus Althoff <info@ct800.net>
 *  Copyright (C) 2010-2014, George Georgopoulos
 *
 *  This file is part of CT800/NGPlay (search engine).
 *
 *  CT800/NGPlay 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 3 of the License, or
 *  (at your option) any later version.
 *
 *  CT800/NGPlay is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with CT800/NGPlay. If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include <stdint.h>
#include <stddef.h>
#include "ctdefs.h"
#include "confdefs.h"
#include "timekeeping.h"
#include "hmi.h"
#include "move_gen.h"
#include "hashtables.h"
#include "eval.h"
#include "book.h"
#include "util.h"
#include "hardware.h"
#include "search.h"

#ifdef PC_PRINTF
#include <stdio.h>
extern char *Play_Translate_Moves(MOVE m);
#endif

/*---------- external variables ----------*/
/*-- READ-ONLY  --*/
extern int game_started_from_0;
extern PIECE empty_p;
extern int fifty_moves;
extern int dynamic_resign_threshold;
extern enum E_COLOUR computer_side;
extern PIECE Wpieces[16];
extern PIECE Bpieces[16];
extern int32_t eval_noise;
extern MOVE mv_move_mask;

/*-- READ-WRITE --*/
extern PIECE *board[120];
extern int mv_stack_p;
extern MVST move_stack[MAX_STACK+1];
extern int cst_p;
extern uint16_t cstack[MAX_STACK+1];
extern int Starting_Mv;
extern int wking, bking;
extern int en_passant_sq;
extern unsigned int gflags;
extern GAME_INFO game_info;
extern LINE GlobalPV;
extern volatile enum E_TIMEOUT time_is_up;
extern TT_ST     T_T[MAX_TT+CLUSTER_SIZE];
extern TT_ST Opp_T_T[MAX_TT+CLUSTER_SIZE];
extern unsigned int hash_clear_counter;
extern uint64_t hw_config;

#ifdef DEBUG_STACK
extern size_t top_of_stack;
extern size_t max_of_stack;
#endif


/*---------- module global variables ----------*/

/*for every root move, the opponent's reply (cut-off move for non-PV root
  moves) is cached in this array during the iterative deepening to help with
  the move sorting. since the hash tables are so small, the entries quickly
  get overwritten during the middlegame, but move sorting is most important
  close to the root. so this arrays helps out.*/
static CMOVE root_refutation_table[MAXMV];

/*for the alternate search info display mode*/
static MOVE curr_root_move;

/*use the Ciura sequence for the shell sort. more than 57 is not needed because
  the rare maximum of pseudo-legal moves in real game positions is about 80 to 90.*/
DATA_SECTION static int shell_sort_gaps[] = {1, 4, 10, 23, 57 /*, 132, 301, 701*/};

DATA_SECTION static int PieceValFromType[PIECEMAX]= {0, 0, PAWN_V, KNIGHT_V, BISHOP_V, ROOK_V, QUEEN_V, INFINITY_, 0, 0,
                                                     0, 0, PAWN_V, KNIGHT_V, BISHOP_V, ROOK_V, QUEEN_V, INFINITY_
                                                    };

/*this is needed for deepening the PV against delay exchanges, which can cause
  a horizon effect. only equal exchanges can do so because unequal ones either
  would be a clear win or loss anyway.
  note that for this purpose, minor pieces are assumed to be equal.*/
DATA_SECTION static int ExchangeValue[PIECEMAX]=    {0, 0, PAWN_V, KNIGHT_V, KNIGHT_V, ROOK_V, QUEEN_V, INFINITY_, 0, 0,
                                                     0, 0, PAWN_V, KNIGHT_V, KNIGHT_V, ROOK_V, QUEEN_V, INFINITY_
                                                    };
/*for mapping board squares to file masks*/
DATA_SECTION static uint8_t board_file_mask[120] = {
     0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU,
     0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0x01U, 0x02U, 0x04U, 0x08U, 0x10U, 0x20U, 0x40U, 0x80U, 0xFFU,
     0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU,
     0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU, 0xFFU
};

/* --------- FUTILITY PRUNING DEFINITIONS ---------- */
#define FUTIL_DEPTH  4
DATA_SECTION static int FutilityMargins[FUTIL_DEPTH]  = {0, 240, 450, 600};

/*same margins in both directions*/
#define RVRS_FUTIL_D    FUTIL_DEPTH
#define RVRS_FutilMargs FutilityMargins

/* ------------- GLOBAL KILLERS/HISTORY TABLES ----------------*/

uint16_t W_history[6][ENDSQ], B_history[6][ENDSQ];
CMOVE W_Killers[2][MAX_DEPTH], B_Killers[2][MAX_DEPTH];

/* ------------- CHECK LIST BUFFER ----------------*/

/*the check list is only used as intermediate buffer back to back with
  finding evasions as move generation if being in check. works because
  of single thread and reduces stack usage.*/
static MOVE search_check_attacks_buf[CHECKLISTLEN];

#ifdef G_NODES
uint64_t g_nodes;
#endif

/*---------- local functions ----------*/

/*that's a shell sort which
  a) doesn't need recursion, unlike quicksort, and
  b) is faster than quicksort on lists with less than 100 entries.*/
static void FUNC_HOT Search_Do_Sort(MOVE *restrict movelist, int N)
{
    int sizeIndex = sizeof(shell_sort_gaps)/sizeof(shell_sort_gaps[0]) - 1;

    do {
        int gap = shell_sort_gaps[sizeIndex];

        for (int i = gap; i < N; i++)
        {
            int value = movelist[i].m.mvv_lva;
            uint32_t tmp_move = movelist[i].u;
            int j;

            for (j = i - gap; j >= 0; j -= gap)
            {
                MOVE current_move;

                current_move.u = movelist[j].u;
                if (current_move.m.mvv_lva >= value)
                    break;
                movelist[j + gap].u = current_move.u;
            }
            movelist[j + gap].u = tmp_move;
        }
    } while (--sizeIndex >= 0);
}

/*shell sort for smaller capture lists*/
inline static void ALWAYS_INLINE Search_Do_Sort_QS(MOVE *restrict movelist, int N)
{
#define GAP_1 4
#define GAP_0 1
    for (int i = GAP_1; i < N; i++)
    {
        int value = movelist[i].m.mvv_lva;
        uint32_t tmp_move = movelist[i].u;
        int j;

        for (j = i - GAP_1; j >= 0; j -= GAP_1)
        {
            MOVE current_move;

            current_move.u = movelist[j].u;
            if (current_move.m.mvv_lva >= value)
                break;
            movelist[j + GAP_1].u = current_move.u;
        }
        movelist[j + GAP_1].u = tmp_move;
    }

    for (int i = GAP_0; i < N; i++)
    {
        int value = movelist[i].m.mvv_lva;
        uint32_t tmp_move = movelist[i].u;
        int j;

        for (j = i - GAP_0; j >= 0; j -= GAP_0)
        {
            MOVE current_move;

            current_move.u = movelist[j].u;
            if (current_move.m.mvv_lva >= value)
                break;
            movelist[j + GAP_0].u = current_move.u;
        }
        movelist[j + GAP_0].u = tmp_move;
    }
#undef GAP_1
#undef GAP_0
}

/*that's a shell sort for the Search_Play_And_Sort_Moves() routine. Sorts by the position value in sortV[].*/
static void Search_Do_Sort_Value(MOVE *restrict movelist, int *restrict sortV, int N)
{
    int sizeIndex = sizeof(shell_sort_gaps)/sizeof(shell_sort_gaps[0]) - 1;

    do {
        int gap = shell_sort_gaps[sizeIndex];

        for (int i = gap; i < N; i++)
        {
            uint32_t tmp_move = movelist[i].u;
            int tmp_sortV = sortV[i];
            int j;

            for (j = i - gap; ((j >= 0) && (sortV[j] < tmp_sortV)); j -= gap)
            {
                movelist[j + gap].u = movelist[j].u;
                sortV[j + gap] = sortV[j];
            }
            movelist[j + gap].u = tmp_move;
            sortV[j + gap] = tmp_sortV;
        }
    } while (--sizeIndex >= 0);
}

#ifdef PC_PRINTF
void Search_Print_PV_Line(const LINE *aPVp, int Goodmove)
{
    int i;

    for (i = 0; i < aPVp->line_len; i++)
    {
        MOVE decomp_move = Mvgen_Decompress_Move(aPVp->line_cmoves[i]);

        if (i==0 && Goodmove)
            printf("%s! ", Play_Translate_Moves(decomp_move));
        else
            printf("%s ", Play_Translate_Moves(decomp_move));
    }
    printf("\n");
}
#endif

/*find the move "key_move" in the list and put it to the top,
  moving the following moves down the list.
  used for getting PV moves to the top of the list.*/
static void Search_Find_Put_To_Top(MOVE *restrict movelist, int len, MOVE key_move)
{
    uint32_t mv_mask = mv_move_mask.u;

    for (int i = 0; i < len; i++)
    {
        if (((movelist[i].u ^ key_move.u) & mv_mask) == 0)
        {
            uint32_t listed_key;

            if (i == 0) /*already at the top*/
                return;

            listed_key = movelist[i].u;

            for ( ; i > 0; i--)
                movelist[i].u = movelist[i-1].u;

            movelist[0].u = listed_key;
            return;
        }
    }
}

/*find the move "key_move" in the list and put it to the top,
  moving the following moves down the list, and handle the associated
  answer compressed move list, too.
  used for getting PV moves to the top of the list.*/
static void Search_Find_Put_To_Top_Root(MOVE *restrict movelist, CMOVE *restrict comp_answerlist, int len, MOVE key_move)
{
    uint32_t mv_mask = mv_move_mask.u;

    for (int i = 0; i < len; i++)
    {
        if (((movelist[i].u ^ key_move.u) & mv_mask) == 0)
        {
            uint32_t listed_key = movelist[i].u;
            CMOVE listed_answer = comp_answerlist[i];

            for ( ; i > 0; i--)
            {
                movelist[i].u      = movelist[i - 1].u;
                comp_answerlist[i] = comp_answerlist[i - 1];
            }

            movelist[0].u      = listed_key;
            comp_answerlist[0] = listed_answer;

            return;
        }
    }
}

/*find the move best mvv/lva move in the list and swap it to the top.
  note that list length 0 theoretically would yield a buffer overflow,
  but all places where this function is called from actually have a
  sufficient buffer - it could just be that there is no valid move
  inside.*/
static void FUNC_HOT Search_Swap_Best_To_Top(MOVE *movelist, int len)
{
    int best_val;
    MOVE tmp_move;
    MOVE *list_ptr, *end_ptr, *best_ptr;

    tmp_move.u = movelist->u;
    best_val = tmp_move.m.mvv_lva;
    best_ptr = movelist;
    list_ptr = movelist + 1;
    end_ptr = movelist + len;

    while (list_ptr < end_ptr)
    {
        int cur_val = list_ptr->m.mvv_lva;
        if (cur_val > best_val)
        {
            best_val = cur_val;
            best_ptr = list_ptr;
        }
        list_ptr++;
    }
    movelist->u = best_ptr->u;
    best_ptr->u = tmp_move.u;
}

/*for the alternate search info display mode in the HMI*/
MOVE Search_Get_Current_Root_Move(void)
{
    return(curr_root_move);
}

/*returns whether a mate has been seen despite the noise setting.
  for each move of depth, the engine shall overlook the mate with a probability
  of "eval_noise".*/
static int NEVER_INLINE Search_Mate_Noise(int depth)
{
    unsigned int prob, eval_real;

    prob = 100U;
    eval_real = 100U - ((unsigned) eval_noise); /*non-noise part*/
    depth /= 2; /*plies depth to moves depth*/

    for (int i = 0; i < depth; i++)
    {
        prob *= eval_real;
        prob += 50U;         /*rounding*/
        prob /= 100U;        /*scale back to 0..100%*/
    }

    /*the probability of mate detection decreases with depth.*/
    if (Hw_Rand(101U) > prob)
        return(0); /*mate overlooked*/

    return(1);
}

/*20 moves without capture or pawn move, that might tend drawish.
  so start to ramp down the difference from 100% at move 20 to 10% target at move 50.
  From some moves before move 50, the looming draw will also appear,
  but if it has already been flattened before, that will not come as surprisingly.

  flatten steadily as to encourage staying draw in worse positions, but don't
  introduce a sudden drop which might cause panic in better situations.

  note that this routine is ONLY called if fifty_moves >= NO_ACTION_PLIES already.*/
static int32_t NEVER_INLINE Search_Flatten_Difference(int32_t eval)
{
    int i, fifty_moves_search;

    /*basic endgames*/
    if ((Wpieces[0].next == NULL) || (Wpieces[0].next->next == NULL) ||
        (Bpieces[0].next == NULL) || (Bpieces[0].next->next == NULL))
    {
        return(eval);
    }

    for (i = Starting_Mv + 1, fifty_moves_search = fifty_moves; i <= mv_stack_p; i++, fifty_moves_search++)
    {
        MVST* p = &move_stack[i];
        if ((p->captured->type) /* capture */ || (p->move.m.flag > 1) /* pawn move */)
            return (eval); /*such moves will reset the drawish tendency*/

        /*50 moves draw detected*/
        if (fifty_moves_search >= 100)
            return(0);
    }

    /*90% discount during 60 plies (30 moves).*/
    eval *= (107 - fifty_moves_search); /*fifty_moves_search is >= NO_ACTION_PLIES*/
    eval /= (107 - NO_ACTION_PLIES);
    return(eval);
}

/*mini SEE for pruning in QS*/
inline static int ALWAYS_INLINE Search_SEE_Prune(MOVE move, enum E_COLOUR colour)
{
    int to_sq, mov_type;

    /*good or equal capture (ignoring e.p.)*/
    mov_type = board[move.m.from]->type;
    to_sq = move.m.to;
    if (ExchangeValue[mov_type] <= ExchangeValue[board[to_sq]->type])
        return(0);

    if (colour == BLACK)
    {
        /*BPAWN: catch e.p.*/
        if (mov_type == BPAWN)
            return(0);
        /*HxL defended by P, or moving a piece to such a square*/
        if ((board[to_sq - 11]->type == WPAWN) || (board[to_sq - 9]->type == WPAWN))
            return(1);
    } else {
        /*WPAWN: catch e.p.*/
        if (mov_type == WPAWN)
            return(0);
        /*HxL defended by P, or moving a piece to such a square*/
        if ((board[to_sq + 11]->type == BPAWN) || (board[to_sq + 9]->type == BPAWN))
            return(1);
    }
    /*default: no pruning*/
    return(0);
}

static int NEVER_INLINE Search_Quiescence(int alpha, int beta, enum E_COLOUR colour, int do_checks, int qs_depth)
{
    MOVE movelist[MAXCAPTMV];
    enum E_COLOUR next_colour;
    int e, i, move_cnt, recapt;
    int is_material_enough, n_checks, n_checks_valid, n_check_pieces;
    unsigned has_move;
#ifdef DEBUG_STACK
    if ((top_of_stack - ((size_t) &has_move)) > max_of_stack)
    {
        max_of_stack = (top_of_stack - ((size_t) &has_move));
    }
#endif
#ifdef G_NODES
    g_nodes++;
#endif
    if (colour==BLACK) {
        /*using has_move as dummy*/
        e = -Eval_Static_Evaluation(&is_material_enough, BLACK, &has_move, &has_move, &has_move);
        if (UNLIKELY(!is_material_enough))
            return 0;
        if (UNLIKELY(fifty_moves >= NO_ACTION_PLIES))
            e = Search_Flatten_Difference(e);
        /*try to delay bad positions and go for good positions faster,
          but don't change the eval sign*/
        if (e > 0)
        {
            e -= (mv_stack_p - Starting_Mv);
            if (e <= 0) e = 1;
        } else if (e < 0)
        {
            e += (mv_stack_p - Starting_Mv);
            if (e >= 0) e = -1;
        }
        /*prevent stack overflow*/
        if (UNLIKELY((mv_stack_p - Starting_Mv >= MAX_DEPTH+MAX_QIESC_DEPTH-1) ||
                     (time_is_up == TM_USER_CANCEL)))
        {
            return e;
        }

        /*in pre-search or after 4 plies QS, don't do check extensions.
          depth 0 cannot have checks because Negascout does not enter QS
          when in check, and the pre-search does not request QS check extension.*/
        if ((qs_depth < QS_CHECK_DEPTH) && (qs_depth > 0) && (do_checks != QS_NO_CHECKS))
        {
            n_checks = Mvgen_Black_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
            n_checks_valid = 1;
        } else
            n_checks = n_checks_valid = 0;

        if (n_checks == 0)
        {
            if (e >= beta)
                return e;

            /*check for stalemate against lone king.
              needed in some endgames like these:
              8/8/1b5p/8/6P1/8/5k1K/8 w - - 0 1
              6K1/5P2/8/5q2/2k5/8/8/8 b - - 0 1*/
            if (Bpieces[0].next == NULL)
            {
                move_cnt = has_move = 0;
                Mvgen_Add_Black_King_Moves(&Bpieces[0], movelist, &move_cnt, NO_LEVEL);
                for (i = 0; i < move_cnt; i++)
                {
                    Search_Push_Status();
                    Search_Make_Move(movelist[i]);
                    if (!Mvgen_Black_King_In_Check())
                    {
                        /*no stalemate*/
                        Search_Retract_Last_Move();
                        Search_Pop_Status();
                        has_move = 1U;
                        break;
                    }
                    Search_Retract_Last_Move();
                    Search_Pop_Status();
                }
                if (!has_move)
                    return 0;
            }
            /*ignore underpromotion in quiescence - not worth the effort.*/
            move_cnt = Mvgen_Find_All_Black_Captures_And_Promotions(movelist, QUEENING);

            if (move_cnt == 0)
                return e;
            if (alpha < e)
                alpha = e;
        } else
        {
            /*in QS, drop underpromotion.*/
            move_cnt = Mvgen_Find_All_Black_Evasions(movelist, search_check_attacks_buf, n_checks, n_check_pieces, QUEENING);
            if (alpha < -MATE_CUTOFF)
            {
                int mate_score = -INFINITY_ + (mv_stack_p - Starting_Mv);

                if (alpha < mate_score)
                    alpha = mate_score;
            }
        }
        next_colour = WHITE;
    } else {
        /*using has_move as dummy*/
        e = Eval_Static_Evaluation(&is_material_enough, WHITE, &has_move, &has_move, &has_move);
        if (UNLIKELY(!is_material_enough))
            return 0;
        if (UNLIKELY(fifty_moves >= NO_ACTION_PLIES))
            e = Search_Flatten_Difference(e);
        /*try to delay bad positions and go for good positions faster,
          but don't change the eval sign*/
        if (e > 0)
        {
            e -= (mv_stack_p - Starting_Mv);
            if (e <= 0) e = 1;
        } else if (e < 0)
        {
            e += (mv_stack_p - Starting_Mv);
            if (e >= 0) e = -1;
        }

        /*prevent stack overflow*/
        if (UNLIKELY((mv_stack_p - Starting_Mv >= MAX_DEPTH+MAX_QIESC_DEPTH-1) ||
                     (time_is_up == TM_USER_CANCEL)))
        {
            return e;
        }

        /*in pre-search or after 4 plies QS, don't do check extensions.
          depth 0 cannot have checks because Negascout does not enter QS
          when in check, and the pre-search does not request QS check extension.*/
        if ((qs_depth < QS_CHECK_DEPTH) && (qs_depth > 0) && (do_checks != QS_NO_CHECKS))
        {
            n_checks = Mvgen_White_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
            n_checks_valid = 1;
        } else
            n_checks = n_checks_valid = 0;

        if (n_checks == 0)
        {
            if (e >= beta)
                return e;

            /*check for stalemate against lone king.
              needed in some endgames like these:
              8/8/1b5p/8/6P1/8/5k1K/8 w - - 0 1
              6K1/5P2/8/5q2/2k5/8/8/8 b - - 0 1*/
            if (Wpieces[0].next == NULL)
            {
                move_cnt = has_move = 0;
                Mvgen_Add_White_King_Moves(&Wpieces[0], movelist, &move_cnt, NO_LEVEL);
                for (i = 0; i < move_cnt; i++)
                {
                    Search_Push_Status();
                    Search_Make_Move(movelist[i]);
                    if (!Mvgen_White_King_In_Check())
                    {
                        /*no stalemate*/
                        Search_Retract_Last_Move();
                        Search_Pop_Status();
                        has_move = 1U;
                        break;
                    }
                    Search_Retract_Last_Move();
                    Search_Pop_Status();
                }
                if (!has_move)
                    return 0;
            }
            /*ignore underpromotion in quiescence - not worth the effort.*/
            move_cnt = Mvgen_Find_All_White_Captures_And_Promotions(movelist, QUEENING);

            if (move_cnt == 0)
                return e;
            if (alpha < e)
                alpha = e;
        } else
        {
            /*in QS, drop underpromotion.*/
            move_cnt = Mvgen_Find_All_White_Evasions(movelist, search_check_attacks_buf, n_checks, n_check_pieces, QUEENING);
            if (alpha < -MATE_CUTOFF)
            {
                int mate_score = -INFINITY_ + (mv_stack_p - Starting_Mv);

                if (alpha < mate_score)
                    alpha = mate_score;
            }
        }
        next_colour = BLACK;
    }

    if (!n_checks_valid)
        n_checks = Mvgen_King_In_Check(colour);

    Search_Swap_Best_To_Top(movelist, move_cnt);
    recapt = (qs_depth < QS_RECAPT_DEPTH) ? 0 : move_stack[mv_stack_p].move.m.to;
    qs_depth++;

    /*continue QS despite timeout because otherwise, the pre-search
      would return nonsense instead of a fail-safe move. besides, apart from
      some pathological QS explosion positions, QS is quick anyway. Still
      check the time to trigger the watchdog and update the display.*/
    if (UNLIKELY(Time_Check(computer_side)))
        if (time_is_up == TM_NO_TIMEOUT)
            time_is_up = TM_TIMEOUT;

    for (i = 0; i < move_cnt; i++)
    {
        int score, to, from, delta;
        enum E_MOVESTATE move_state;
        MOVE currmove;

        /*after first move (usually cuts), sort if there are more moves*/
        if ((i == 1) && (move_cnt >= 3))
            Search_Do_Sort_QS(movelist + 1, move_cnt - 1);

        /*delta pruning*/
        currmove.u = movelist[i].u;
        to = currmove.m.to;
        from = currmove.m.from;
        delta = PieceValFromType[board[to]->type];
        if (colour == BLACK)
        {
            if ((board[from]->type == BPAWN) && (to <= H1))
                delta += QUEEN_V - PAWN_V;
        } else
        {
            if ((board[from]->type == WPAWN) && (to >= A8))
                delta += QUEEN_V - PAWN_V;
        }
        if (e + delta + QS_DELTA_MARGIN < alpha)
        {
            /*if this move has no chance of improving alpha, the others are
              even less likely to do so because of MVV/LVA sorting.*/
            return alpha;
        }

        /*recapture-only after 5 plies QS, and SEE pruning*/
        if (((recapt != 0) && (recapt != to)) ||
            (((n_checks == 0) || (!n_checks_valid)) && (Search_SEE_Prune(currmove, colour))))
        {
            /*in-check, we did the delta pruning above because it does not
              matter whether it is mate or material fail-low. However, giving
              back some material in an advantageous position may be the best
              way to defend against the check, hence no SEE pruning.*/
            continue;
        }

        move_state = (n_checks == 0) ? Mvgen_Is_Move_Safe(currmove, colour) : MOVE_UNKNOWN;
        if (move_state == MOVE_UNSAFE)
            continue;

        Search_Push_Status();
        Search_Make_Move(movelist[i]);

        if ((move_state == MOVE_UNKNOWN) && (Mvgen_King_In_Check(colour)))
        {
            Search_Retract_Last_Move();
            Search_Pop_Status();
            continue;
        }

        score = -Search_Quiescence(-beta, -alpha, next_colour, do_checks, qs_depth);
        Search_Retract_Last_Move();
        Search_Pop_Status();

        if (score >= beta)
            return score;
        if (score > alpha)
            alpha = score;
    }

    return alpha;
}

static void Search_Update_Killers_History(enum E_COLOUR colour, int depth, int level,
                                          const MOVE *restrict movelist, int last_mv_idx)
{
    MOVE last_move = movelist[last_mv_idx];
    int last_mv_from = last_move.m.from,
        last_mv_to   = last_move.m.to;
    int last_mv_piece_type = board[last_mv_from]->type;

    if (colour == BLACK)
    {
        /*don't use promotions and e.p. (protect the killer slots)*/
        if ((last_mv_piece_type != BPAWN) ||
            ((last_mv_to >= A2) &&
             (((last_mv_from - last_mv_to) & 1) == 0)))
        {
            uint32_t depth_sq = ((uint32_t) depth) * ((uint32_t) depth);
            CMOVE cmove = Mvgen_Compress_Move(last_move);

            /*black depth killers*/
            if (B_Killers[0][level] != cmove)
            {
                B_Killers[1][level] = B_Killers[0][level];
                B_Killers[0][level] = cmove;
            }

            /*black history update (reward this move). not for king moves
              against lone king because that ruins e.g. KNB-K.*/
            if ((last_mv_piece_type != BKING) || (Wpieces[0].next != NULL))
            {
                uint16_t *hist_ptr = &B_history[last_mv_piece_type - BPAWN][last_mv_to];
                uint32_t hist_val = *hist_ptr + depth_sq;

                if (hist_val >= HIST_MAX) /*dynamic history ageing / overflow*/
                {
                    uint16_t *h_ptr = (uint16_t *) B_history;
                    uint16_t *h_end_ptr = h_ptr + 6 * ENDSQ;

                    do {
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                    } while (h_ptr < h_end_ptr);

                    depth_sq >>= 1;
                    hist_val >>= 1;
                }
                *hist_ptr = hist_val;
            }

            /*black history update (punish previous quiet moves)*/
            depth_sq >>= 1;
            depth_sq++;
            for (int mcnt = 0; mcnt < last_mv_idx; mcnt++)
            {
                MOVE move = movelist[mcnt];

                /*find quiet and legal moves that have been tried.
                  e.p. and promotions can be ignored here:
                  e.p. not cutting and then moving another pawn on
                  the e.p. field causing a cut-off (searched earlier with
                  better history) is extremely rare.
                  promotions don't derive their mvv/lva from history.*/
                if ((move.m.flag != 0) && (board[move.m.to]->type == NO_PIECE))
                {
                    uint16_t *hist_ptr = &B_history[board[move.m.from]->type - BPAWN][move.m.to];
                    uint32_t hist_val = *hist_ptr;

                    /*subtract 1+(depth^2)/2 and prevent underflow*/
                    hist_val = (hist_val > depth_sq) ? hist_val - depth_sq : 0;
                    *hist_ptr = hist_val;
                }
            }
        }
    } else /*white*/
    {
        /*don't use promotions and e.p. (protect the killer slots)*/
        if ((last_mv_piece_type != WPAWN) ||
            ((last_mv_to <= H7) &&
             (((last_mv_to - last_mv_from) & 1) == 0)))
        {
            uint32_t depth_sq = ((uint32_t) depth) * ((uint32_t) depth);
            CMOVE cmove = Mvgen_Compress_Move(last_move);

            /*white depth killers*/
            if (W_Killers[0][level] != cmove)
            {
                W_Killers[1][level] = W_Killers[0][level];
                W_Killers[0][level] = cmove;
            }

            /*white history update (reward this move). not for king moves
              against lone king because that ruins e.g. KNB-K.*/
            if ((last_mv_piece_type != WKING) || (Bpieces[0].next != NULL))
            {
                uint16_t *hist_ptr = &W_history[last_mv_piece_type - WPAWN][last_mv_to];
                uint32_t hist_val = *hist_ptr + depth_sq;

                if (hist_val >= HIST_MAX) /*dynamic history ageing / overflow*/
                {
                    uint16_t *h_ptr = (uint16_t *) W_history;
                    uint16_t *h_end_ptr = h_ptr + 6 * ENDSQ;

                    do {
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                        *h_ptr >>= 1; h_ptr++;
                    } while (h_ptr < h_end_ptr);

                    depth_sq >>= 1;
                    hist_val >>= 1;
                }
                *hist_ptr = hist_val;
            }

            /*white history update (punish previous quiet moves)*/
            depth_sq >>= 1;
            depth_sq++;
            for (int mcnt = 0; mcnt < last_mv_idx; mcnt++)
            {
                MOVE move = movelist[mcnt];

                /*find quiet and legal moves that have been tried.
                  e.p. and promotions can be ignored here:
                  e.p. not cutting and then moving another pawn on
                  the e.p. field causing a cut-off (searched earlier with
                  better history) is extremely rare.
                  promotions don't derive their mvv/lva from history.*/
                if ((move.m.flag != 0) && (board[move.m.to]->type == NO_PIECE))
                {
                    uint16_t *hist_ptr = &W_history[board[move.m.from]->type - WPAWN][move.m.to];
                    uint32_t hist_val = *hist_ptr;

                    /*subtract 1+(depth^2)/2 and prevent underflow*/
                    hist_val = (hist_val > depth_sq) ? hist_val - depth_sq : 0;
                    *hist_ptr = hist_val;
                }
            }
        }
    }
}

/*only adjust stuff if there is something to adjust. moving the checks
  outside the for loop increases the NPS rate by about 1%.
  len is assumed to be > 0, which is always the case because there are
  always pseudo-legal moves.*/
static void NEVER_INLINE Search_Adjust_Priorities(MOVE * restrict movelist, int len,
                                                  uint8_t * restrict should_iid,
                                                  MOVE pv_move, MOVE hash_move)
{
    #define NONE_ADJ 0U
    #define PV_ADJ   1U
    #define HS_ADJ   2U
    int i;
    unsigned int search_mode = NONE_ADJ, search_done;
    uint32_t mv_mask = mv_move_mask.u;

    /*what we are looking for to adjust. only consider the hash move
      if it is different from the PV move, similarly for the threat move.*/
    if (pv_move.u != MV_NO_MOVE_MASK)
        search_mode = PV_ADJ;
    if ((hash_move.u != MV_NO_MOVE_MASK) && (((hash_move.u ^ pv_move.u) & mv_mask) != 0))
        search_mode |= HS_ADJ;

    switch (search_mode)
    {
    case NONE_ADJ: /*0*/
        return;
    case PV_ADJ: /*1*/
        i = 0;
        do {
            if (((movelist[i].u ^ pv_move.u) & mv_mask) == 0)
            {
                movelist[i].m.mvv_lva = MVV_LVA_PV; /* Move follows PV*/
                *should_iid = 0;
                return;
            }
            i++;
        } while (i < len);
        return;
    case HS_ADJ: /*2*/
        i = 0;
        do {
            if (((movelist[i].u ^ hash_move.u) & mv_mask) == 0)
            {
                movelist[i].m.mvv_lva = MVV_LVA_HASH; /* Move from Hash table */
                *should_iid = 0;
                return;
            }
            i++;
        } while (i < len);
        return;
    case PV_ADJ | HS_ADJ: /*3*/
        search_done = 0;
        i = 0;
        do {
            if (((movelist[i].u ^ pv_move.u) & mv_mask) == 0)
            {
                movelist[i].m.mvv_lva = MVV_LVA_PV; /* Move follows PV*/
                *should_iid = 0;
                if (search_done == HS_ADJ) /*both found*/
                    return;
                search_done = PV_ADJ;
            } else if (((movelist[i].u ^ hash_move.u) & mv_mask) == 0)
            {
                movelist[i].m.mvv_lva = MVV_LVA_HASH; /* Move from Hash table */
                *should_iid = 0;
                if (search_done == PV_ADJ) /*both found*/
                    return;
                search_done = HS_ADJ;
            }
            i++;
        } while (i < len);
        return;
    }
    #undef NONE_ADJ
    #undef PV_ADJ
    #undef HS_ADJ
}

static int Search_Endgame_Reduct(void)
{
    /*basic endgames*/
    if ((Wpieces[0].next == NULL) || (Wpieces[0].next->next == NULL) ||
        (Bpieces[0].next == NULL) || (Bpieces[0].next->next == NULL))
    {
        return(0);
    }

    /*promotion threat*/
    for (int i = A2; i <= H2; i += FILE_DIFF)
    {
        if ((board[i]->type == BPAWN) ||
            (board[i + 5*RANK_DIFF]->type == WPAWN))
        {
            return(0);
        }
    }
    return(1);
}

/* -------------------------------- NEGA SCOUT ALGORITHM -------------------------------- */

static int NEVER_INLINE FUNC_NOGCSE
Search_Negascout(int CanNull, int level, LINE *restrict pline, MOVE *restrict mlst,
                 int n, int depth, int alpha, int beta, enum E_COLOUR colour,
                 int *restrict best_move_index, int is_pv_node, int being_in_check,
                 int following_pv, int lmp_active)
{
    const int mate_score = INFINITY_ - (mv_stack_p - Starting_Mv);

    pline->line_len = 0;
    *best_move_index = TERMINAL_NODE;

    /*mate distance pruning*/
    if (alpha >= mate_score) return alpha;
    if (beta <= -mate_score) return beta;

    if ((depth <= 0) || /*node is a terminal node*/
        (UNLIKELY(mv_stack_p - Starting_Mv >= MAX_DEPTH-1))) /*we are too deep*/
    {
        if (eval_noise < HIGH_EVAL_NOISE)
            return Search_Quiescence(alpha, beta, colour, QS_CHECKS, 0);
        else
            return Search_Quiescence(alpha, beta, colour, QS_NO_CHECKS, 0);
    } else
    {
        static int root_move_index;
        MOVE x2movelst[MAXMV];
        MOVE threat_best, hash_best;
        enum E_COLOUR next_colour;
        int i, e, t, a, x2movelen, next_depth, node_moves;
        int iret, is_material_enough, n_check_pieces;
        unsigned is_endgame, w_passed_mask, b_passed_mask;
        LINE line;
        uint8_t should_iid=1, hash_move_mode, level_gt_1, node_pruned_moves;

        level_gt_1 = (level > 1);
#ifdef DEBUG_STACK
        if ((top_of_stack - ((size_t) &node_pruned_moves)) > max_of_stack)
        {
            max_of_stack = (top_of_stack - ((size_t) &node_pruned_moves));
        }
#endif
        hash_best.u = MV_NO_MOVE_MASK;
#ifdef G_NODES
        g_nodes++;
#endif
        /* Check Transposition Table for a match */
        if (!is_pv_node) {
            if (level & 1) { /* Our side to move */
                if (Hash_Check_TT(    T_T, colour, alpha, beta, depth, move_stack[mv_stack_p].mv_pos_hash, &t, &hash_best)) {
                    if (hash_best.u != MV_NO_MOVE_MASK)
                    {
                        pline->line_cmoves[0] = Mvgen_Compress_Move(hash_best);
                        pline->line_len = 1;
                    }
                    return t;
                }
            } else { /* Opponent time to move */
                if (Hash_Check_TT(Opp_T_T, colour, alpha, beta, depth, move_stack[mv_stack_p].mv_pos_hash, &t, &hash_best)) {
                    if (hash_best.u != MV_NO_MOVE_MASK)
                    {
                        pline->line_cmoves[0] = Mvgen_Compress_Move(hash_best);
                        pline->line_len = 1;
                    }
                    return t;
                }
            }
        } else if (level_gt_1)
        /*for PV nodes, don't return because that causes PV truncation. Only use the
          hash best move for move ordering.*/
        {
            if (level & 1) /* Our side to move */
                Hash_Check_TT_PV(    T_T, colour, depth, move_stack[mv_stack_p].mv_pos_hash, &t, &hash_best);
            else           /* Opponent time to move */
                Hash_Check_TT_PV(Opp_T_T, colour, depth, move_stack[mv_stack_p].mv_pos_hash, &t, &hash_best);
        }

        /*level 2 has a dedicated move cache.*/
        if ((level == 2) && (hash_best.u == MV_NO_MOVE_MASK))
            hash_best = Mvgen_Decompress_Move(root_refutation_table[root_move_index]);

        /*note that the contents of the passed pawn masks are only defined for is_endgame != 0.*/
        if (colour == BLACK) {
            e = -Eval_Static_Evaluation(&is_material_enough, BLACK, &is_endgame, &w_passed_mask, &b_passed_mask);
            next_colour = WHITE;
        } else {
            e = Eval_Static_Evaluation(&is_material_enough, WHITE, &is_endgame, &w_passed_mask, &b_passed_mask);
            next_colour = BLACK;
        }
        if (!is_material_enough)
        /*if this node has insufficient material, that cannot change further
          down towards the leaves of the search tree.*/
        {
            MOVE smove;
            smove.u = MV_NO_MOVE_MASK;
            if (level & 1)
                Hash_Update_TT(    T_T, depth, 0, EXACT, move_stack[mv_stack_p].mv_pos_hash, smove);
            else
                Hash_Update_TT(Opp_T_T, depth, 0, EXACT, move_stack[mv_stack_p].mv_pos_hash, smove);
            return 0;
        }
        if (UNLIKELY(fifty_moves >= NO_ACTION_PLIES))
            e = Search_Flatten_Difference(e);

        if ((!is_pv_node) && (!being_in_check))
        {
            /*Reverse Futility Pruning*/
            if ((depth < RVRS_FUTIL_D) && (e - RVRS_FutilMargs[depth] >= beta) &&
                ((is_material_enough >= EG_PIECES) || Search_Endgame_Reduct()))
            {
                return e;
            }
            /*Null search. Allow null move pruning if the side to move has enough pieces.*/
            if (CanNull && (e >= beta) && (depth >= NULL_START_DEPTH) && (!(is_endgame & (1U << colour))))
            {
                int null_depth = depth - (3 + depth / 4) - (e >= beta + PAWN_V),
                    store_ep_sq = en_passant_sq;

                /*this can fall right into QS which does not do check evasions at
                  QS level 0. But this is OK because the other side cannot be in check
                  given that it is actually our turn here, i.e. without null move.*/
                en_passant_sq = 0;
                t = -Search_Negascout(0, level + 1, &line, x2movelst, 0, null_depth, -beta, -beta + 1, next_colour, &iret, 0, 0,  0, lmp_active);
                en_passant_sq = store_ep_sq;
                if (t >= beta)
                    return t;
            }
        }

        /*late move generation*/
        hash_move_mode = 0;
        if (n == 0)
        {
            /*defer that if we have a hash move - a beta cutoff is likely.*/
            if ((hash_best.u == MV_NO_MOVE_MASK) || (following_pv))
            {
                MOVE GPVmove;

                n = Mvgen_Find_All_Moves(mlst, level-1, colour, UNDERPROM);

                /* Adjust move priorities */
                if ((following_pv) && (GlobalPV.line_len > level-1))
                    GPVmove = Mvgen_Decompress_Move(GlobalPV.line_cmoves[level-1]);
                else
                    GPVmove.u = MV_NO_MOVE_MASK;

                Search_Adjust_Priorities(mlst, n, &should_iid, GPVmove, hash_best);
            } else
            {
                /*if we are not in a PV node and there is a hash best move, then this
                  move is 90% likely to cause a cutoff here. The move list has not
                  yet been generated, so n is 0, and the hash move is the only move
                  for now. It has been validated for pseudo legality upon retrieval
                  from the hash table. The in-check verification remains to do.*/
                hash_move_mode = 1;
                mlst[0].u = hash_best.u;
                mlst[1].u = MV_NO_MOVE_MASK; /*swap to top keeps the order with both MVV/LVA as 0*/
                n = 2;
                should_iid = 0;
            }
        } else if (level_gt_1) /*early move generation - check evasions*/
        {
            MOVE GPVmove;

            /* Adjust move priorities */
            if ((following_pv) && (GlobalPV.line_len > level-1))
                GPVmove = Mvgen_Decompress_Move(GlobalPV.line_cmoves[level-1]);
            else
                GPVmove.u = MV_NO_MOVE_MASK;

            Search_Adjust_Priorities(mlst, n, &should_iid, GPVmove, hash_best);
        }

        /*root move list is already sorted in the main ID loop.*/
        if (level_gt_1)
        {
            if (should_iid && (depth > IID_DEPTH))
            {
                /*Internal Iterative Deepening
                  level > 1: no IID in the root node because the pre-sorting in
                  Search_Play_And_Sort_Moves() has already done that.
                  should_iid would have been set to false if we had had a hash or PV move available.*/
                Search_Negascout(CanNull, level, &line, mlst, n, depth/3, alpha, beta, colour,
                                 &iret, is_pv_node, being_in_check, following_pv, lmp_active);
                if (iret >= 0)
                    mlst[iret].m.mvv_lva = MVV_LVA_HASH;
            }
            Search_Swap_Best_To_Top(mlst, n);
        }

        a = alpha;
        node_moves = node_pruned_moves = 0;

        if (UNLIKELY(Time_Check(computer_side)))
            if (time_is_up == TM_NO_TIMEOUT)
                time_is_up = TM_TIMEOUT;

        for (i = 0; i < n; i++)
        {
            /*foreach child of node*/
            int capture_1, capture_2, curr_move_follows_pv, can_reduct, n_checks;
            enum E_MOVESTATE move_state;

            if (level_gt_1) /*initial move list is already sorted*/
            {
                if (i == 1)
                {
                    /*even later move generation*/
                    if (hash_move_mode)
                    {
                        MOVE GPVmove;
                        GPVmove.u = MV_NO_MOVE_MASK;

                        n = Mvgen_Find_All_Moves(mlst, level-1, colour, UNDERPROM);
                        /*if there is only one pseudo legal move, that must have been
                          the hash move which has already been tried.*/
                        if (n <= 1)
                            break;

                        /* Adjust move priorities */
                        Search_Adjust_Priorities(mlst, n, &should_iid, GPVmove, hash_best);
                        Search_Do_Sort(mlst, n); /*hash move will be at the top*/
                    } else
                        Search_Do_Sort(mlst + 1, n - 1);
                }
            } else /*level 1 is root moves.*/
            {
                root_move_index = i;
                /*save the current root move for the live search mode in the HMI*/
                curr_root_move.u = mlst[i].u;
            }
            move_state = (!being_in_check) ? Mvgen_Is_Move_Safe(mlst[i], colour) : MOVE_UNKNOWN;
            if (move_state == MOVE_UNSAFE)
            {
                mlst[i].m.flag = 0; /*for history: mark as illegal*/
                continue;
            }
            Search_Push_Status();
            Search_Make_Move(mlst[i]);
            if ((move_state == MOVE_UNKNOWN) && (Mvgen_King_In_Check(colour)))
            {
                Search_Retract_Last_Move();
                Search_Pop_Status();
                mlst[i].m.flag = 0; /*for history: mark as illegal*/
                continue;
            }
            threat_best.u = MV_NO_MOVE_MASK;
            if (Hash_Check_For_Draw())
            {
                if ((mv_stack_p < CONTEMPT_END) && (game_started_from_0))
                {
                    if (colour == computer_side)
                        t = CONTEMPT_VAL;
                    else
                        t = -CONTEMPT_VAL;
                } else
                    t = 0;
            } else
            {
                if (colour == BLACK)
                {
                    /* if our move just played gives check, generate evasions and do not reduce depth so we can search deeper */
                    n_checks = Mvgen_White_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
                    if (n_checks) { /* early move generation */
                        can_reduct = 0;
                        if ((depth <= CHECK_DEPTH) && (eval_noise < HIGH_EVAL_NOISE))
                            /*track checks if the search tree were to end, but don't replicate high-level trees.*/
                            next_depth = depth;
                        else
                            next_depth = depth - 1;
                        x2movelen = Mvgen_Find_All_White_Evasions(x2movelst, search_check_attacks_buf, n_checks, n_check_pieces, UNDERPROM);
                    } else {
                        can_reduct = (!being_in_check) && (mlst[i].m.mvv_lva < MVV_LVA_TACTICAL) &&
                                      ((is_material_enough >= EG_PIECES) || Search_Endgame_Reduct());
                        /*futility pruning*/
                        if ( can_reduct && (!is_pv_node) && (depth < FUTIL_DEPTH) && (e+FutilityMargins[depth] < a) ) {
                            Search_Retract_Last_Move();
                            Search_Pop_Status();
                            node_pruned_moves = 1U; /*a pruned legal move still is a legal move - for the stalemate recognition at the end of this routine.*/
                            continue;
                        }
                        x2movelen = 0;
                        next_depth = depth - 1;
                        if (time_is_up == TM_NO_TIMEOUT)
                        {
                            /*special attention to mutual passed pawn races*/
                            if ((is_endgame) && (depth <= 2) && (mlst[i].m.flag == BPAWN) &&
                                (b_passed_mask & board_file_mask[mlst[i].m.to]) && (eval_noise < HIGH_EVAL_NOISE))
                            {
                                next_depth = depth;
                            } else if ((is_pv_node) && (depth <= PV_ADD_DEPTH) && (eval_noise < HIGH_EVAL_NOISE))
                            {
                                /*make sure that capture chains don't push things just out of the horizon.
                                  checks are deepened anyway.*/
                                capture_1 = move_stack[mv_stack_p].captured->type;
                                if (capture_1)
                                {
                                    capture_2 = move_stack[mv_stack_p-1].captured->type;
                                    /*there cannot be a buffer underun because the current search move
                                      has been made so that mv_stack_p is minimum 1 at this point.*/
                                    if (capture_2)
                                    {
                                        if (ExchangeValue[capture_1] == ExchangeValue[capture_2])
                                        /*unequal captures would either be a bad idea, then the quiescence show
                                          a loss anyway, or a win, which the quiescence also shows. Only equal
                                          captures could cause a horizon effect delay.*/
                                           next_depth = depth;
                                    }
                                }
                            }
                        }
                    }
                } else { /* colour == WHITE */
                    /* if our move just played gives check do not reduce depth so we can search deeper */
                    n_checks = Mvgen_Black_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
                    if (n_checks) { /* early move generation */
                        can_reduct = 0;
                        if ((depth <= CHECK_DEPTH) && (eval_noise < HIGH_EVAL_NOISE))
                            /*track checks if the search tree were to end, but don't replicate high-level trees.*/
                            next_depth = depth;
                        else
                            next_depth = depth - 1;
                        x2movelen=Mvgen_Find_All_Black_Evasions(x2movelst, search_check_attacks_buf, n_checks, n_check_pieces, UNDERPROM);
                    } else {
                        can_reduct = (!being_in_check) && (mlst[i].m.mvv_lva < MVV_LVA_TACTICAL) &&
                                      ((is_material_enough >= EG_PIECES) || Search_Endgame_Reduct());
                        /*futility pruning*/
                        if ( can_reduct && (!is_pv_node) && (depth < FUTIL_DEPTH) && (e+FutilityMargins[depth] < a) ) {
                            Search_Retract_Last_Move();
                            Search_Pop_Status();
                            node_pruned_moves = 1U; /*a pruned legal move still is a legal move - for the stalemate recognition at the end of this routine.*/
                            continue;
                        }
                        x2movelen = 0;
                        next_depth = depth - 1;
                        if (time_is_up == TM_NO_TIMEOUT)
                        {
                            /*special attention to mutual passed pawn races*/
                            if ((is_endgame) && (depth <= 2) && (mlst[i].m.flag == WPAWN) &&
                                (w_passed_mask & board_file_mask[mlst[i].m.to]) && (eval_noise < HIGH_EVAL_NOISE))
                            {
                                next_depth = depth;
                            } else if ((is_pv_node) && (depth <= PV_ADD_DEPTH) && (eval_noise < HIGH_EVAL_NOISE))
                            {
                                /*make sure that capture chains don't push things just out of the horizon.
                                  checks are deepened anyway.*/
                                capture_1 = move_stack[mv_stack_p].captured->type;
                                if (capture_1)
                                {
                                    capture_2 = move_stack[mv_stack_p-1].captured->type;
                                    /*there cannot be a buffer underun because the current search move
                                      has been made so that mv_stack_p is minimum 1 at this point.*/
                                    if (capture_2)
                                    {
                                        if (ExchangeValue[capture_1] == ExchangeValue[capture_2])
                                        /*unequal captures would either be a bad idea, then the quiescence show
                                          a loss anyway, or a win, which the quiescence also shows. Only equal
                                          captures could cause a horizon effect delay.*/
                                           next_depth = depth;
                                    }
                                }
                            }
                        }
                    }
                }
                curr_move_follows_pv = 0;
                if ((following_pv) && (GlobalPV.line_len > level-1) &&
                    (Mvgen_Compress_Move(mlst[i]) == GlobalPV.line_cmoves[level-1]))
                {
                    curr_move_follows_pv = 1;
                }
                if (node_moves == 0) { /* First move to search- full window [-beta,-alpha] used */
                    t = (beta > a + 1) ? PV_NODE : CUT_NODE;
                    t = -Search_Negascout(1, level+1, &line, x2movelst, x2movelen, next_depth, -beta, -a, next_colour, &iret, t, n_checks, curr_move_follows_pv, lmp_active);
                } else {
                    if (can_reduct)
                    {
                        if ((i > n/3) && (depth <= LMP_DEPTH_LIMIT) && (a > -MATE_CUTOFF) && lmp_active)
                        {
                            /*late move pruning*/
                            t = a;
                            iret = TERMINAL_NODE;
                        } else if ((node_moves >= LMR_MOVES) && (depth >= LMR_DEPTH_LIMIT))
                        {
                            /* LMR - Search with reduced depth and scout window [-alpha-1,-alpha].*/
                            if (node_moves < 2*LMR_MOVES)
                                t = depth - 2;
                            else if (node_moves < 3*LMR_MOVES)
                                t = depth - 3;
                            else
                                t = depth - 4;
                            /*Don't fall straight into quiescence.*/
                            if (t <= 0)
                                t = 1;
                            t = -Search_Negascout(1, level+1, &line, x2movelst, x2movelen, t, -a-1, -a, next_colour, &iret, CUT_NODE, n_checks, curr_move_follows_pv, lmp_active);
                        } else t = a + 1;
                    } else t = a + 1;  /* Ensure that re-search is done. */

                    if (t > a) {
                        /* Search normal depth and scout window [-alpha-1,-alpha] */
                        t = -Search_Negascout(1, level+1, &line, x2movelst, x2movelen, next_depth, -a-1, -a, next_colour, &iret, CUT_NODE, n_checks, curr_move_follows_pv, lmp_active);
                        if ((t > a) && (t < beta)) {
                            /* re-search using full window for PV nodes */
                            t = -Search_Negascout(1, level+1, &line, x2movelst, x2movelen, next_depth, -beta, -a, next_colour, &iret, PV_NODE, n_checks, curr_move_follows_pv, lmp_active);
                        }
                    }
                }
                if (iret >= 0) /* Update Best defense for later use in PV line update */
                    threat_best.u = x2movelst[iret].u;
            }
            Search_Retract_Last_Move();
            Search_Pop_Status();

            if (time_is_up != TM_NO_TIMEOUT)
                return a;

            /*if we are in level 1, then store the best answer from level 2
              for the next main depth iteration.*/
            if ((!level_gt_1) && (threat_best.u != MV_NO_MOVE_MASK))
                root_refutation_table[i] = Mvgen_Compress_Move(threat_best);

            /*the following constitutes alpha-beta pruning*/
            if (t > a) {
                a = t;
                *best_move_index = i;
                /* Update Principal Variation */
                if (threat_best.u != MV_NO_MOVE_MASK) {
                    pline->line_cmoves[0] = Mvgen_Compress_Move(threat_best);
                    Util_Movelinecpy(pline->line_cmoves + 1, line.line_cmoves, line.line_len);
                    pline->line_len = line.line_len + 1;
                } else
                    pline->line_len = 0;
                if (a >= beta) { /*-- cut-off --*/
#ifdef DBGCUTOFF
                    if (node_moves == 0) /* First move of search */
                        cutoffs_on_1st_move++;
                    total_cutoffs++;
#endif
                    /*for non-captures/promotions, update depth killers and history*/
                    if (board[mlst[i].m.to]->type == NO_PIECE)
                        Search_Update_Killers_History(colour, depth, level-1, mlst, i);

                    /* Update Transposition table */
                    if (level & 1)
                        Hash_Update_TT(    T_T, depth, a, CHECK_BETA, move_stack[mv_stack_p].mv_pos_hash, mlst[i]);
                    else
                        Hash_Update_TT(Opp_T_T, depth, a, CHECK_BETA, move_stack[mv_stack_p].mv_pos_hash, mlst[i]);

                    return a;
                }
            }
            node_moves++;
        }/* for each node */

        if (node_moves == 0) /*no useful and legal moves*/
        {
            if (!node_pruned_moves) /*there are no legal moves.*/
            {
                if (being_in_check) /*mate */
                {
                    if ((eval_noise <= 0) || (Search_Mate_Noise(mv_stack_p - Starting_Mv)))
                        a = -mate_score;
                    else
                        a = e; /*mate overlooked*/
                } else /*stalemate */
                    a = 0;
            } else
            /*there are legal moves, but they were all cut away in the
              futility pruning.*/
            {
                /*'a' just stays alpha because no move has improved alpha.*/
            }
            *best_move_index = TERMINAL_NODE;
        }
        /* Update Transposition table */
        if (a > alpha)
        {
            if ( *best_move_index != TERMINAL_NODE )
                hash_best = mlst[*best_move_index];
            else
                hash_best.u = MV_NO_MOVE_MASK;

            if (level & 1)
                Hash_Update_TT(    T_T, depth, a, EXACT, move_stack[mv_stack_p].mv_pos_hash, hash_best);
            else
                Hash_Update_TT(Opp_T_T, depth, a, EXACT, move_stack[mv_stack_p].mv_pos_hash, hash_best);
        } else
        {
            hash_best.u = MV_NO_MOVE_MASK;
            if (level & 1)
                Hash_Update_TT(    T_T, depth, a, CHECK_ALPHA, move_stack[mv_stack_p].mv_pos_hash, hash_best);
            else
                Hash_Update_TT(Opp_T_T, depth, a, CHECK_ALPHA, move_stack[mv_stack_p].mv_pos_hash, hash_best);
        }
        return a;
    }
}

static int NEVER_INLINE Search_Negamate(int depth, int alpha, int beta, enum E_COLOUR colour, int check_depth,
                                 LINE *restrict pline, MOVE *restrict blocked_movelist, int blocked_moves,
                                 int root_node, int in_check, enum E_MATE_CHECK check_type)
{
    MOVE movelist[MAXMV];
    MOVE dummy;
    LINE line;
    enum E_COLOUR next_colour;
    int i, a, move_cnt, actual_move_cnt, checking, tt_value;
#ifdef DEBUG_STACK
    if ((top_of_stack - ((size_t) &tt_value)) > max_of_stack)
    {
        max_of_stack = (top_of_stack - ((size_t) &tt_value));
    }
#endif

    pline->line_len = 0;

    /*prevent stack overflow.
      should never hit because the maximum mate search depth is 8 moves,
      which is mate in 15 plies plus 1 ply for scanning the final position.

      So, 16 plies in total, and 20 plies are allowed. But just in case
     something changes.*/
    if (UNLIKELY(mv_stack_p - Starting_Mv >= MAX_DEPTH-1 ))
    /* We are too deep */
        return(0);

    if (Hash_Check_For_Draw())
        return(0);
    if (colour == WHITE) /*slightly different way to use the hash tables*/
    {
        if (Hash_Check_TT(    T_T, colour, alpha, beta, depth, move_stack[mv_stack_p].mv_pos_hash, &tt_value, &dummy))
            return(tt_value);
    } else /*black*/
    {
        if (Hash_Check_TT(Opp_T_T, colour, alpha, beta, depth, move_stack[mv_stack_p].mv_pos_hash, &tt_value, &dummy))
            return(tt_value);
    }

    /*first phase: get the moves, filter out the legal ones,
      prioritise check delivering moves, and if it is checkmate, return.*/

    /*the history is used differently here because the depth serves as level.
      This is possible because Negamate does not have selective deepening.*/
    if (in_check == 0)
        move_cnt = Mvgen_Find_All_Moves(movelist, depth, colour, UNDERPROM);
    else
    {
        int n_checks, n_check_pieces;
        /*in mate problems, always consider underpromotion even with evasions as
          this might be part of the puzzle.*/
        if (colour == WHITE)
        {
            n_checks = Mvgen_White_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
            move_cnt = Mvgen_Find_All_White_Evasions(movelist, search_check_attacks_buf, n_checks, n_check_pieces, UNDERPROM);
        } else
        {
            n_checks = Mvgen_Black_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
            move_cnt = Mvgen_Find_All_Black_Evasions(movelist, search_check_attacks_buf, n_checks, n_check_pieces, UNDERPROM);
        }
    }

    next_colour = Mvgen_Opp_Colour(colour);

    for (i = 0, actual_move_cnt = 0, checking = 0; i < move_cnt; i++)
    {
        enum E_MOVESTATE move_state;

        /*if we are searching for double solutions, we may have
          to filter out the blocked moves.*/
        if (blocked_moves)
        {
            int j, move_is_blocked;
            for (j = 0, move_is_blocked = 0; j < blocked_moves; j++)
            {
                if (((movelist[i].u ^ blocked_movelist[j].u) & mv_move_mask.u) == 0)
                {
                    move_is_blocked = 1;
                    break;
                }
            }
            if (move_is_blocked)
            {
                movelist[i].m.mvv_lva = MVV_LVA_ILLEGAL;
                movelist[i].m.flag = 0;
                continue;
            }
        }

        move_state = (!in_check) ? Mvgen_Is_Move_Safe(movelist[i], colour) : MOVE_UNKNOWN;
        if (move_state == MOVE_UNSAFE)
        {
            movelist[i].m.mvv_lva = MVV_LVA_ILLEGAL;
            movelist[i].m.flag = 0; /*for history: mark as illegal*/
            continue;
        }
        Search_Push_Status();
        Search_Make_Move(movelist[i]);
        if ((move_state == MOVE_UNKNOWN) && (Mvgen_King_In_Check(colour)))
        {
            movelist[i].m.mvv_lva = MVV_LVA_ILLEGAL;
            movelist[i].m.flag = 0; /*for history: mark as illegal*/
        } else
        {
            /*if there is a legal move at depth == 0, then it isn't checkmate.*/
            if (depth == 0)
            {
                Search_Retract_Last_Move();
                Search_Pop_Status();
                return(0);
            }
            actual_move_cnt++;
            if (Mvgen_King_In_Check(next_colour))
            /*prioritise check giving moves*/
            {
                checking++;
                movelist[i].m.mvv_lva = MVV_LVA_CHECK;
            }
        }
        Search_Retract_Last_Move();
        Search_Pop_Status();
    }

    /*at depth==1, only check giving moves are tried. so at this point, there
      are no legal moves, otherwise we would have returned, and we are in check.
      Must be checkmate.*/
    if (depth == 0)
        return(-INFINITY_ + (mv_stack_p - Starting_Mv));

    if (actual_move_cnt == 0)
    {
        if (in_check)
            return(-INFINITY_ + (mv_stack_p - Starting_Mv));
        else
            return(0);
    }

    /*if no move delivers check, then it won't be checkmate.*/
    if (depth & 1)
    {
        if (((check_type != EXACT_CHECK_DEPTH) && (depth <= check_depth)) ||
            ((check_type == EXACT_CHECK_DEPTH) && (depth != check_depth)))
        {
            if (checking == 0)
                return(0);
            else
            {
                /*if the depth is below the "from here on only checking moves" threshold,
                  only consider the checking moves. only for odd depths because the side that
                  is supposed to be mated always must have all possibilities evaluated.*/
                actual_move_cnt = checking;
            }
        }
    }

    Search_Swap_Best_To_Top(movelist, move_cnt);

    if (UNLIKELY(Time_Check(computer_side)))
        if (time_is_up == TM_NO_TIMEOUT)
            time_is_up = TM_TIMEOUT;
    /*remember time_is_up is volatile and might also get set from the interrupt
      if the user cancels the computation.*/
    if (time_is_up != TM_NO_TIMEOUT)
        return(0);

    line.line_len = 0;
    a = alpha;
    /*second phase: iterate deeper.*/
    for (i = 0; i < actual_move_cnt; i++)
    {
        int score;

        if (i == 1)
            Search_Do_Sort(movelist+1, move_cnt-1);

        Search_Push_Status();
        Search_Make_Move(movelist[i]);

        /*there are no blocked moves from within this search, only from the root level.*/
        score = -Search_Negamate(depth-1, -beta, -a, next_colour, check_depth, &line,
                                 NULL /*no block list*/, 0 /*no blocked moves*/, 0 /*not root node*/,
                                 (movelist[i].m.mvv_lva == MVV_LVA_CHECK), check_type);

        if (score == 0) /*don't risk messing up the PV with the hash tables.*/
        {
            MOVE no_move;
            no_move.u = MV_NO_MOVE_MASK; /*don't store moves, doesn't matter anyway.*/
            /*since we already have made the move and are before retracting it, the depth is
              one less. And it must be the opponent's hash table because he is to move with the
              board position before retracting the move.*/
            if (colour == WHITE)
                Hash_Update_TT(Opp_T_T, depth-1, 0, EXACT, move_stack[mv_stack_p].mv_pos_hash, no_move);
            else
                Hash_Update_TT(T_T, depth-1, 0, EXACT, move_stack[mv_stack_p].mv_pos_hash, no_move);
        }

        Search_Retract_Last_Move();
        Search_Pop_Status();

        if (score > a)
        {
            a = score;
            /*update the PV*/
            pline->line_cmoves[0] = Mvgen_Compress_Move(movelist[i]);
            Util_Movelinecpy(pline->line_cmoves + 1, line.line_cmoves, line.line_len);
            pline->line_len = line.line_len + 1;

            if ((root_node) && (score > MATE_CUTOFF)) /*all we are looking for*/
                return(score);

            if (score >= beta)
            {
                /*for non-captures/promotions, update depth killers and history*/
                if (board[movelist[i].m.to]->type == NO_PIECE)
                    Search_Update_Killers_History(colour, depth, depth, movelist, i);

                return(score);
            }
        }
    } /*for each node*/

    return(a);
}

/*perform a shallow search of 1 ply + QS at root to sort the root move list.*/
static int NEVER_INLINE Search_Play_And_Sort_Moves(MOVE *restrict movelist, int len,
                                                   enum E_COLOUR next_colour, int *restrict score_drop)
{
    int sortV[MAXMV], i;

#ifdef DEBUG_STACK
    if ((top_of_stack - ((size_t) &i)) > max_of_stack)
    {
        max_of_stack = (top_of_stack - ((size_t) &i));
    }
#endif

    /*this is just in case that during future works, this routine gets called
      with an empty move list (len == 0), i.e. mate or stalemate. usually,
      this should have been handled before calling this routine. but this way,
      the program would resign immediately, making it obvious that something
      is wrong. otherwise, if len==0, we would return an uninitialised value.*/
    sortV[0] = -INFINITY_;

    for (i = 0; i < len; i++)
    {
        int current_score;

        if (movelist[i].m.flag == 0) /*illegal move - should not happen*/
            current_score = -INFINITY_;
        else
        {
            Search_Push_Status();
            Search_Make_Move(movelist[i]);

            if (Hash_Check_For_Draw())
            {
                if ((mv_stack_p < CONTEMPT_END) && (game_started_from_0))
                    current_score = CONTEMPT_VAL;
                else
                    current_score = 0;
            } else
                current_score = -Search_Quiescence(-INFINITY_, INFINITY_, next_colour, QS_NO_CHECKS, 0);

            Search_Retract_Last_Move();
            Search_Pop_Status();
        }
        sortV[i] = current_score;
    }

    /*sort movelist using sortV.*/
    if (len > 1)
    {
        Search_Do_Sort_Value(movelist, sortV, len);
        *score_drop = sortV[0] - sortV[1];
    } else
        *score_drop = SORT_THRESHOLD;

    return(sortV[0]);
}

#ifdef PC_PRINTF
static void Search_Print_Move_Output(int depth, int score, int goodmove)
{
#ifdef MOVE_ANALYSIS
    printf("\n");
#endif
    printf("%3d%7.2lf%7.2lf   ",depth, 0.01*score, SECONDS_PASSED);
    Search_Print_PV_Line(&GlobalPV,goodmove);
}
#endif

/*tests whether the position is checkmate for the relevant colour.*/
static int NEVER_INLINE Search_Is_Checkmate(enum E_COLOUR colour)
{
    MOVE check_attacks[CHECKLISTLEN];
    MOVE movelist[MAXMV];
    int i, move_cnt;
    int n_checks, n_check_pieces;
    if (colour == WHITE)
    {
        if (Mvgen_White_King_In_Check())
        {
            int non_checking_move = 0;
            n_checks = Mvgen_White_King_In_Check_Info(check_attacks, &n_check_pieces);
            move_cnt = Mvgen_Find_All_White_Evasions(movelist, check_attacks, n_checks, n_check_pieces, UNDERPROM);
            /*is there a legal move?*/
            for (i = 0; i < move_cnt; i++)
            {
#ifdef G_NODES
                g_nodes++;
#endif
                Search_Push_Status();
                Search_Make_Move(movelist[i]);
                if (!Mvgen_White_King_In_Check()) non_checking_move = 1;
                Search_Retract_Last_Move();
                Search_Pop_Status();
                if (non_checking_move) return(0); /*that move gets out of check: no checkmate.*/
            }
            return(1); /*no move gets the white king out of check: checkmate.*/
        }
    } else
    {
        if (Mvgen_Black_King_In_Check())
        {
            int non_checking_move = 0;
            n_checks = Mvgen_Black_King_In_Check_Info(check_attacks, &n_check_pieces);
            move_cnt = Mvgen_Find_All_Black_Evasions(movelist, check_attacks, n_checks, n_check_pieces, UNDERPROM);
            /*is there a legal move?*/
            for (i = 0; i < move_cnt; i++)
            {
#ifdef G_NODES
                g_nodes++;
#endif
                Search_Push_Status();
                Search_Make_Move(movelist[i]);
                if (!Mvgen_Black_King_In_Check()) non_checking_move = 1;
                Search_Retract_Last_Move();
                Search_Pop_Status();
                if (non_checking_move) return(0); /*that move gets out of check: no checkmate.*/
            }
            return(1); /*no move gets the black king out of check: checkmate.*/
        }
    }
    return(0); /*no king is in check, so it can't be checkmate.*/
}

void Search_Reset_History(void)
{
    Util_Memzero(W_history, sizeof(W_history));
    Util_Memzero(B_history, sizeof(B_history));
    Util_Memzero(W_Killers, sizeof(W_Killers));
    Util_Memzero(B_Killers, sizeof(B_Killers));
}


/* ---------- global functions ----------*/


void Search_Make_Move(MOVE amove)
{
    int xy1, xy2, flag, ptype1, xyc, xydif;
    MVST* p;

    xy1  = amove.m.from;
    xy2  = amove.m.to;
    flag = amove.m.flag;
    ptype1 = board[xy1]->type;
    mv_stack_p++;
    p = &move_stack[mv_stack_p];
    p->move.u = amove.u;
    en_passant_sq = 0;
    p->special = NORMAL;

    /*en passant captures: with a null move, the e.p. square is cleared
      beforehand and restored afterwards.*/

    if (ptype1 == WPAWN) {
        xydif = xy2-xy1;
        if (((xydif == 11) || (xydif == 9)) && (board[xy2]->type == 0)) { /*En Passant*/
            xyc = xy2-10;
            p->captured = board[xyc];
            p->capt = xyc;
        } else {
            if ((flag >= WKNIGHT) && (flag < WKING)) { /* white pawn promotion. Piece in flag */
                board[xy1]->type = flag;
                p->special = PROMOT;
            }
            xyc = xy2;
            p->captured = board[xyc];
            p->capt = xyc;
            if (xydif == 20) {
                if ((board[xy2+1]->type == BPAWN) || (board[xy2-1]->type == BPAWN)) {
                    en_passant_sq = xy1+10;
                }
            }
        }
    } else if (ptype1 == BPAWN) {
        xydif = xy2-xy1;
        if (((xydif == -11) || (xydif == -9)) && (board[xy2]->type == 0)) { /*En Passant*/
            xyc = xy2+10;
            p->captured = board[xyc];
            p->capt = xyc;
        } else {
            if ((flag >= BKNIGHT) && (flag < BKING)) { /* black pawn promotes to flag */
                board[xy1]->type = flag;
                p->special = PROMOT;
            }
            xyc = xy2;
            p->captured = board[xyc];
            p->capt = xyc;
            if (xydif == -20) {
                if ((board[xy2+1]->type == WPAWN) || (board[xy2-1]->type == WPAWN)) {
                    en_passant_sq = xy1-10;
                }
            }
        }
    } else {
        xyc = xy2;
        p->captured = board[xyc];
        p->capt = xyc;
    }
    /* Captured piece struct modified */
    if (board[xyc]->type) {
        PIECE *piece_p = board[xyc];
        piece_p->xy = 0;
        piece_p->prev->next = piece_p->next;
        if (piece_p->next) {
            piece_p->next->prev = piece_p->prev;
        }
        board[xyc] = &empty_p;
    }
    board[xy1]->xy = xy2;    /* Moving piece struct modified */
    board[xy2] = board[xy1];
    board[xy1] = &empty_p;
    /* Update Flags */
    if (board[xy2]->type > BLACK) {
        gflags |= BLACK_MOVED; /*black move*/
        if (ptype1 == BROOK) {
            if (xy1 == A8) {
                gflags |= BRA8MOVED; /*  bra8moved=1;*/
                if (gflags & BRH8MOVED) /*if both rooks have moved, set the king also moved*/
                    gflags |= BKMOVED;
            } else if (xy1 == H8) {
                gflags |= BRH8MOVED; /*  brh8moved=1;*/
                if (gflags & BRA8MOVED) /*if both rooks have moved, set the king also moved*/
                    gflags |= BKMOVED;
            }
        } else if (ptype1 == BKING) {
            gflags |= (BKMOVED | BRA8MOVED | BRH8MOVED);
            bking = xy2;
            if (xy1 == E8) {
                if (xy2 == G8) { /* black short castle */
                    board[F8] = board[H8];
                    board[F8]->xy = F8;
                    board[H8] = &empty_p;
                    p->special = CASTL;
                    gflags |= BCASTLED;
                } else if (xy2 == C8) { /* black long castle */
                    board[D8] = board[A8];
                    board[D8]->xy = D8;
                    board[A8] = &empty_p;
                    p->special = CASTL;
                    gflags |= BCASTLED;
                }
            }
            if (xy2 == G8) {
                if ((board[F8]->type == BROOK) && (board[H8]->xy == 0)) {
                    gflags |= BCASTLED; /*  artificial BHasCastled=1 */
                }
            }
        }
    } else {
        gflags &= ~BLACK_MOVED; /*white move*/
        if (ptype1 == WROOK) {
            if (xy1 == A1) {
                gflags |= WRA1MOVED;
                if (gflags & WRH1MOVED) /*if both rooks have moved, set the king also moved*/
                    gflags |= WKMOVED;
            } else if (xy1 == H1) {
                gflags |= WRH1MOVED;
                if (gflags & WRA1MOVED) /*if both rooks have moved, set the king also moved*/
                    gflags |= WKMOVED;
            }
        } else if (ptype1 == WKING) {
            wking = xy2;
            if (xy1 == E1) {
                gflags |= (WKMOVED | WRA1MOVED | WRH1MOVED);
                if (xy2 == G1) { /* white short castle */
                    board[F1] = board[H1];
                    board[F1]->xy = F1;
                    board[H1] = &empty_p;
                    p->special = CASTL;
                    gflags |= WCASTLED;
                } else if (xy2 == C1) { /* white long castle */
                    board[D1] = board[A1];
                    board[D1]->xy = D1;
                    board[A1] = &empty_p;
                    p->special = CASTL;
                    gflags |= WCASTLED;
                }
            }
            if (xy2 == G1) {
                if ((board[F1]->type == WROOK) && (board[H1]->xy == 0)) {
                    gflags |= WCASTLED; /*  artificial WHasCastled=1 */
                }
            }
        }
    }
    p->mv_pos_hash = Hash_Get_Position_Value(&(p->mv_pawn_hash));
}

void Search_Retract_Last_Move(void)
{
    int xy1=move_stack[mv_stack_p].move.m.from;
    int xy2=move_stack[mv_stack_p].move.m.to;
    int cpt=move_stack[mv_stack_p].capt;
    board[xy1] = board[xy2];
    board[xy1]->xy = xy1;
    board[xy2] = &empty_p;
    board[cpt] = move_stack[mv_stack_p].captured;
    if (board[cpt] != &empty_p) {
        board[cpt]->xy = cpt;
        board[cpt]->prev->next = board[cpt];
        if (board[cpt]->next)
            board[cpt]->next->prev = board[cpt];
    }

    if (move_stack[mv_stack_p].special==PROMOT) {
        if (xy1>=A7) { /* white pawn promotion */
            board[xy1]->type  = WPAWN;
        } else { /* black pawn promotion */
            board[xy1]->type  = BPAWN;
        }
    } else {
        if (board[xy1]->type==WKING) {
            wking=xy1;
        } else if (board[xy1]->type==BKING) {
            bking=xy1;
        }
        if (move_stack[mv_stack_p].special==CASTL) {
            if (xy1==E1) { /* white castle */
                if (xy2==G1) {
                    board[H1] = board[F1];
                    board[H1]->xy = H1;
                    board[F1] = &empty_p;
                } else if (xy2==C1) {
                    board[A1] = board[D1];
                    board[A1]->xy = A1;
                    board[D1] = &empty_p;
                } else Hmi_Reboot_Dialogue("err: castle moves,", "must reboot.");
            } else if (xy1==E8) { /* black castle */
                if (xy2==G8) {
                    board[H8] = board[F8];
                    board[H8]->xy = H8;
                    board[F8] = &empty_p;
                } else if (xy2==C8) {
                    board[A8] = board[D8];
                    board[A8]->xy = A8;
                    board[D8] = &empty_p;
                } else Hmi_Reboot_Dialogue("err: castle moves,", "must reboot.");
            } else Hmi_Reboot_Dialogue("err: castle moves,", "must reboot.");
        }
    }
    mv_stack_p--;
}

void Search_Try_Move(MOVE amove) /* No ep/castle flags checked */
{
    int xyc, xydif;
    int xy1 =amove.m.from;
    int xy2 =amove.m.to;
    int flag=amove.m.flag;
    mv_stack_p++;

    move_stack[mv_stack_p].move.u = amove.u;
    move_stack[mv_stack_p].special = NORMAL;
    if (board[xy1]->type==WPAWN) {
        xydif = xy2-xy1;
        if ((xydif==11 || xydif==9) && (board[xy2]->type==0)) { /*En Passant*/
            xyc = xy2-10;
            move_stack[mv_stack_p].captured = board[xyc];
            move_stack[mv_stack_p].capt = xyc;
        } else {
            if (flag>=WKNIGHT && flag<WKING) { /* white pawn promotion. Piece in flag */
                board[xy1]->type = flag;
                move_stack[mv_stack_p].special=PROMOT;
            }
            xyc=xy2;
            move_stack[mv_stack_p].captured = board[xyc];
            move_stack[mv_stack_p].capt = xyc;
        }
    } else if (board[xy1]->type==BPAWN) {
        xydif = xy2-xy1;
        if ((xydif==-11 || xydif==-9) && (board[xy2]->type==0)) { /*En Passant*/
            xyc = xy2+10;
            move_stack[mv_stack_p].captured = board[xyc];
            move_stack[mv_stack_p].capt = xyc;
        } else {
            if (flag>=BKNIGHT && flag<BKING) { /* black pawn promotes to flag */
                board[xy1]->type = flag;
                move_stack[mv_stack_p].special=PROMOT;
            }
            xyc=xy2;
            move_stack[mv_stack_p].captured = board[xyc];
            move_stack[mv_stack_p].capt = xyc;
        }
    } else {
        xyc=xy2;
        move_stack[mv_stack_p].captured = board[xyc];
        move_stack[mv_stack_p].capt = xyc;
    }
    board[xyc]->xy = 0;      /* Captured piece struct modified */
    board[xy1]->xy = xy2;    /* Moving piece struct modified */
    board[xyc] = &empty_p;
    board[xy2] = board[xy1];
    board[xy1] = &empty_p;
    if (board[xy2]->type==WKING) {
        wking = xy2;
        if (xy1==E1) {
            if (xy2==G1) { /* white short castle */
                board[F1] = board[H1];
                board[F1]->xy = F1;
                board[H1] = &empty_p;
                move_stack[mv_stack_p].special = CASTL;
            } else if (xy2==C1) { /* white long castle */
                board[D1] = board[A1];
                board[D1]->xy = D1;
                board[A1] = &empty_p;
                move_stack[mv_stack_p].special = CASTL;
            }
        }
    } else if (board[xy2]->type==BKING) {
        bking = xy2;
        if (xy1==E8) {
            if (xy2==G8) { /* black short castle */
                board[F8] = board[H8];
                board[F8]->xy = F8;
                board[H8] = &empty_p;
                move_stack[mv_stack_p].special = CASTL;
            } else if (xy2==C8) { /* black long castle */
                board[D8] = board[A8];
                board[D8]->xy = D8;
                board[A8] = &empty_p;
                move_stack[mv_stack_p].special = CASTL;
            }
        }
    }
}

/*50 moves rule: every move will draw except captures and pawn moves,
  and if these had been useful, they would have been chosen before.
  just don't make a move that allows the opponent to capture. that
  would still be a draw, but some GUIs might have issues in noticing
  that. besides, it would look silly.
  however, if the opponent has hung a piece and now it isn't draw, then
  we'll catch that because it's only about pre-sorting the list. on the
  other hand, if everything draws, then the list order will not be changed
  in search.*/
static void NEVER_INLINE Search_Sort_50_Moves(MOVE *restrict player_move, MOVE *restrict movelist, int move_cnt, enum E_COLOUR colour)
{
    if (fifty_moves >= 99)
    {
        MOVE opp_movelist[MAXMV];
        enum E_COLOUR next_colour = Mvgen_Opp_Colour(colour);
        int i;

        for (i = 0; i < move_cnt; i++)
        {
            int moving_piece, moving_to;

            if (movelist[i].m.mvv_lva == MVV_LVA_MATE_1) /*mate already found*/
                continue;
            moving_piece = board[movelist[i].m.from]->type;
            moving_to = movelist[i].m.to;

            if ((moving_piece != WPAWN) && (moving_piece != BPAWN) &&
                (board[movelist[i].m.to]->type == NO_PIECE))
            {
                int opp_capture_moves, is_checking, take_moving_piece = 0;

                Search_Push_Status();
                Search_Make_Move(movelist[i]);

                /*prefer check giving moves. if those lead to legal
                  captures, they will be de-prioritised anyway.*/
                if (Mvgen_King_In_Check(next_colour))
                    is_checking = 1;
                else
                    is_checking = 0;

                /*find the opponent's capture moves.*/
                opp_capture_moves = Mvgen_Find_All_Captures_And_Promotions(opp_movelist, next_colour, QUEENING);

                /*if there are any, don't count those that would put the
                  opponent in check. that increases the chance to find
                  suitable own moves.*/
                if (opp_capture_moves > 0)
                {
                    int k, legal_opp_moves = 0;
                    for (k = 0; k < opp_capture_moves; k++)
                    {
                        Search_Push_Status();
                        Search_Make_Move(opp_movelist[k]);
                        if (!Mvgen_King_In_Check(next_colour))
                        {
                            legal_opp_moves = 1;
                            /*can take the piece that we have moved?*/
                            if (opp_movelist[k].m.to == moving_to)
                                take_moving_piece = 1;
                        }
                        Search_Retract_Last_Move();
                        Search_Pop_Status();
                    }
                    if (legal_opp_moves == 0) /*no legal captures.*/
                        opp_capture_moves = 0;
                }
                if (opp_capture_moves == 0)
                {
                    /*a checking move that can't be answered by a capture is
                      bullet-proof - it might even be checkmate if the opponent
                      does not know that checkmate has priority over the 50 moves
                      draw. otherwise, at least a move where there are no captures.*/
                    movelist[i].m.mvv_lva = MVV_LVA_50_OK + is_checking;
                } else
                {
                    /*a check giving move that can be answered by a capture
                      will capture the check-giving piece!*/
                    movelist[i].m.mvv_lva = MVV_LVA_50_NOK - is_checking - take_moving_piece;
                }

                Search_Retract_Last_Move();
                Search_Pop_Status();
            } else
                movelist[i].m.mvv_lva = MVV_LVA_50_NOK;
        }
        Search_Do_Sort(movelist, move_cnt);
        player_move->u = MV_NO_MOVE_MASK; /*trash PV*/
    }
}

int NEVER_INLINE Search_Get_Root_Move_List(MOVE *restrict movelist, int *restrict move_cnt, enum E_COLOUR colour, int mate_check)
{
    enum E_COLOUR next_colour;
    int i, mv_len, actual_move_cnt, n_checks, n_check_pieces;

    if (colour == WHITE)
    {
        next_colour = BLACK;
        n_checks = Mvgen_White_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
        if (n_checks != 0)
            mv_len = Mvgen_Find_All_White_Evasions(movelist, search_check_attacks_buf, n_checks, n_check_pieces, UNDERPROM);
        else
            mv_len = Mvgen_Find_All_White_Moves(movelist, NO_LEVEL, UNDERPROM);
    } else
    {
        next_colour = WHITE;
        n_checks = Mvgen_Black_King_In_Check_Info(search_check_attacks_buf, &n_check_pieces);
        if (n_checks != 0)
            mv_len = Mvgen_Find_All_Black_Evasions(movelist, search_check_attacks_buf, n_checks, n_check_pieces, UNDERPROM);
        else
            mv_len = Mvgen_Find_All_Black_Moves(movelist, NO_LEVEL, UNDERPROM);
    }

    for (i = 0, actual_move_cnt = 0; i < mv_len; i++)
    {
        /*filter out all moves that would put or let our king in check*/
        Search_Push_Status();
        Search_Make_Move(movelist[i]);
        if (Mvgen_King_In_Check(colour))
        {
            movelist[i].m.mvv_lva = MVV_LVA_ILLEGAL;
            movelist[i].m.flag = 0;
            Search_Retract_Last_Move();
            Search_Pop_Status();
            continue;
        }
        /*rank mate in 1 high: useful for pathological test positions like this:
          1QqQqQq1/r6Q/Q6q/q6Q/B2q4/q6Q/k6K/1qQ1QqRb w - -
          1Qq1qQrB/K6k/Q6q/b2Q4/Q6q/q6Q/R6q/1qQqQqQ1 b - -
          1qQ1QqRb/k6K/q6Q/B2q4/q6Q/Q6q/r6Q/1QqQqQq1 w - -
          1qQqQqQ1/R6q/q6Q/Q6q/b2Q4/Q6q/K6k/1Qq1qQrB b - -
          doesn't cost significant time in normal play, and the CT800 shall
          always be able to deliver mate no matter what.*/
        if (mate_check)
            if (Search_Is_Checkmate(next_colour))
                movelist[i].m.mvv_lva = MVV_LVA_MATE_1;
        Search_Retract_Last_Move();
        Search_Pop_Status();
        actual_move_cnt++;
    }

    /*the illegal moves get sorted to the end of the list.*/
    Search_Do_Sort(movelist, mv_len);
    *move_cnt = actual_move_cnt;
    return(n_checks);
}

/*set up the eval/search noise for the following search.*/
static void NEVER_INLINE Search_Setup_Noise(void)
{
    uint64_t noise_option = CFG_GET_OPT(CFG_NOISE_MODE);

    /*option is in 10% steps*/
    eval_noise = (int)(noise_option >> CFG_NOISE_OFFSET);
    eval_noise *= 10;
    if (eval_noise > 100) /*should not happen*/
        eval_noise = 100;
}

/*never inline this one since this isn't called in hot loops anway.*/
enum E_COMP_RESULT NEVER_INLINE
Search_Get_Best_Move(MOVE *restrict answer_move, MOVE player_move, int32_t full_move_time, enum E_COLOUR colour)
{
    int ret_mv_idx=0, move_cnt, is_material_enough, in_check, mate_in_1, is_analysis;
    MOVE movelist[MAXMV];
    LINE line;

    time_is_up = TM_NO_TIMEOUT;
    COMPILER_BARRIER;

#ifdef G_NODES
    g_nodes = 0;
#endif

#ifdef DBGCUTOFF
    cutoffs_on_1st_move = total_cutoffs = 0;
#endif

    answer_move->u = MV_NO_MOVE_MASK;
    mate_in_1 = 0;

    is_analysis = CFG_HAS_OPT(CFG_GAME_MODE, CFG_GAME_MODE_ANA);

    /*static history ageing*/
    {
        uint16_t *hw_ptr = (uint16_t *) W_history,
                 *hb_ptr = (uint16_t *) B_history;
        uint16_t *hw_end_ptr = hw_ptr + 6 * ENDSQ;

        do {
            *hw_ptr >>= 3; hw_ptr++;
            *hb_ptr >>= 3; hb_ptr++;
            *hw_ptr >>= 3; hw_ptr++;
            *hb_ptr >>= 3; hb_ptr++;
            *hw_ptr >>= 3; hw_ptr++;
            *hb_ptr >>= 3; hb_ptr++;
        } while (hw_ptr < hw_end_ptr);
    }

    Search_Setup_Noise();

    is_material_enough = Eval_Setup_Initial_Material();
    if (!is_material_enough) /*draw due to insufficient material*/
        return(COMP_MAT_DRAW);

    Starting_Mv = mv_stack_p;
    in_check = Search_Get_Root_Move_List(movelist, &move_cnt, colour, MATE_CHECK);

    if (move_cnt == 0)
    {
        if (in_check)
            return (COMP_MATE);
        else
            return(COMP_STALE);
    }

    if (Book_Is_Line(&ret_mv_idx, movelist, move_cnt))
    {
        game_info.valid = EVAL_BOOK;
        answer_move->u = movelist[ret_mv_idx].u;
        return(COMP_MOVE_FOUND);
    } else
    {
        int32_t reduced_move_time;
        MOVE decomp_move;
        int i, d, sort_max, pv_hit = 0, score_drop, pos_score, nscore;
        CMOVE failsafe_cmove;
        uint8_t mate_conf;

        curr_root_move.u = MV_NO_MOVE_MASK;

        /*if 50 moves draw is close, re-sort the list*/
        Search_Sort_50_Moves(&player_move, movelist, move_cnt, colour);

        if (hash_clear_counter < MAX_AGE_CNT) hash_clear_counter++;
        else hash_clear_counter = 0;

        if (full_move_time >= 500L) /*drop age clearing under extreme time pressure*/
            Hash_Cut_Tables(hash_clear_counter);

        /*if too much time has been used, don't start another iteration as it will not finish anyway.*/
        if (!is_analysis)
        {
            if (in_check) /*there are not many moves anyway*/
            {
                full_move_time /= 2;
                Time_Override_Stop_Time(full_move_time);
            }
            reduced_move_time = (full_move_time * 55L) / 100L;
        } else
            reduced_move_time = full_move_time;

        /*immediate mate found?*/
        if (movelist[0].m.mvv_lva == MVV_LVA_MATE_1)
        {
            mate_in_1 = 1;
            GlobalPV.line_cmoves[0] = Mvgen_Compress_Move(movelist[0]);
            GlobalPV.line_len = 1;
            if (fifty_moves < 100)
                game_info.eval = sort_max = pos_score = INF_MATE_1;
            else
                game_info.eval = sort_max = pos_score = 0;
            game_info.valid = EVAL_MOVE;
            game_info.depth = 1;
            player_move.u = MV_NO_MOVE_MASK; /*trash PV*/
            score_drop = 2 * EASY_THRESHOLD;
            /*save the best move from the pre-scan*/
            failsafe_cmove = GlobalPV.line_cmoves[0];
            if (!is_analysis)
            {
                answer_move->u = movelist[0].u;
                return(COMP_MOVE_FOUND);
            }
        } else
        {
            MOVE hash_best;
            int dummy;

            hash_best.u = MV_NO_MOVE_MASK;
            /*check with alpha=+INF and beta=-INF so that only the depth check
              is actually performed.*/
            if (!Hash_Check_TT(T_T, colour, INFINITY_, -INFINITY_, PRE_DEPTH, move_stack[mv_stack_p].mv_pos_hash, &dummy, &hash_best))
                 hash_best.u = MV_NO_MOVE_MASK;

             if ((player_move.u != MV_NO_MOVE_MASK) && (GlobalPV.line_len >= 3) &&
                 (GlobalPV.line_cmoves[1] == Mvgen_Compress_Move(player_move)))
            {
                /*shift down the global PV*/
                for (i = 0; i < GlobalPV.line_len - 2; i++)
                    GlobalPV.line_cmoves[i] = GlobalPV.line_cmoves[i+2];
                GlobalPV.line_len -= 2;
                if (GlobalPV.line_len > PRE_DEPTH) /*else the pre-search is better*/
                    pv_hit = 1;
                decomp_move = Mvgen_Decompress_Move(GlobalPV.line_cmoves[0]);
                Search_Find_Put_To_Top(movelist, move_cnt, decomp_move);
            } else
            {
                /*the opponent didn't follow the PV, so trash it.*/
                GlobalPV.line_len = 0;
                GlobalPV.line_cmoves[0] = MV_NO_MOVE_CMASK;
            }

            /*do the move presorting at depth=1.*/
            sort_max = Search_Play_And_Sort_Moves(movelist, move_cnt, Mvgen_Opp_Colour(colour), &score_drop);
#ifdef PC_PRINTF
            printf("\nInitial Eval:%d\n",sort_max);
#endif
            game_info.valid = EVAL_MOVE;

            /*prepare the game info structure. if the move time is about 0, then the iterative
              deepening loop will not be finished even for depth 2.*/
            if (!pv_hit)
            {
                GlobalPV.line_cmoves[0] = Mvgen_Compress_Move(movelist[0]);
                GlobalPV.line_len = 1;
                pos_score = game_info.eval = sort_max;
                game_info.depth = PRE_DEPTH;
            } else /*PV hit*/
            {
                if (game_info.last_valid_eval != NO_RESIGN)
                {
                    /*adjust possible mate distance*/
                    if (game_info.last_valid_eval > MATE_CUTOFF)
                        game_info.eval = game_info.last_valid_eval + 2;
                    else if (game_info.last_valid_eval < -MATE_CUTOFF)
                        game_info.eval = game_info.last_valid_eval - 2;
                    else
                        game_info.eval = game_info.last_valid_eval;
                } else
                    game_info.eval = sort_max;
                pos_score = game_info.eval;
                game_info.depth = GlobalPV.line_len;

                /*if this is a forced move and we have a PV anyway, just play the move.*/
                if ((move_cnt < 2) && (!is_analysis))
                {
#ifdef PC_PRINTF
                    printf("Anticipated forced move.\r\n");
#endif
                    *answer_move = Mvgen_Decompress_Move(GlobalPV.line_cmoves[0]);
                    return(COMP_MOVE_FOUND);
                }
            }
            /*save the best move from the pre-scan*/
            failsafe_cmove = Mvgen_Compress_Move(movelist[0]);

            /*put the hash move (if available) to the top before doing so with the
              PV move - if both are equal, nothing happens, and otherwise, the hash move
              will come at place 2.*/
            if (hash_best.u != MV_NO_MOVE_MASK)
                Search_Find_Put_To_Top(movelist, move_cnt, hash_best);
        }

#ifdef PC_PRINTF
        printf("\nDepth Eval  Seconds Principal Variation  \n ---  ----  ------- -------------------\n");
#endif

        /* If opponent answered following previous PV, add the computer reply choice first in the moves list*/
        if (pv_hit)
        {
            decomp_move = Mvgen_Decompress_Move(GlobalPV.line_cmoves[0]);
            Search_Find_Put_To_Top(movelist, move_cnt, decomp_move);
#ifdef PC_PRINTF
            printf("Anticipated move.\r\n");
#endif
        }

        /*look whether the easy move detection is
          a) a PV hit
          OR
          b) mate in 1
          OR
          c) bad enough to be realistic: yes, the opponent might just hang a piece. But it could also be a trap.
          AND
          d) good enough: maybe in the deep search, we know we have a mate, then don't be content with a piece.*/
        if (!(
            ((pv_hit) && (failsafe_cmove == GlobalPV.line_cmoves[0])) ||
            (mate_in_1) ||
            ((game_info.last_valid_eval != NO_RESIGN) &&
                ((sort_max - game_info.last_valid_eval) < EASY_MARGIN_UP) &&
                ((sort_max - game_info.last_valid_eval) > EASY_MARGIN_DOWN))
           ))
        {
            score_drop = 0;
        }

        /*clear the level 2 move cache.*/
        Util_Memzero(root_refutation_table, sizeof(root_refutation_table));

        /*reduce CPU speed after the presort (if applicable).*/
        Hw_Throttle_Speed();

        nscore = pos_score;
        mate_conf = 0;

        if (!is_analysis)
        {
            int32_t disp_time = Hw_Get_System_Time();

            curr_root_move = Mvgen_Decompress_Move(GlobalPV.line_cmoves[0]);
            Hmi_Update_Alternate_Screen(pos_score, PRE_DEPTH, &GlobalPV);
            /*a full display update takes about 6 ms, so maybe add this*/
            disp_time = Hw_Get_System_Time() - disp_time;
            if (disp_time > 1L) /*probably just timer interrupt*/
                Time_Add_Conf_Delay(disp_time + 1L);
        }

        for (d = START_DEPTH; d < MAX_DEPTH; d++)
        { /* Iterative deepening method*/
            const int alpha_full = -INFINITY_;
            const int beta_full  =  INFINITY_;
            int alpha, beta, lmp_active;

            /*set aspiration window.*/
            if (d >= ID_WINDOW_DEPTH)
            {
                /*note: a step-wise opening between +/- ID_WINDOW_DEPTH and
                  half-open window was tried, but lost around 10 Elo.*/
                alpha = nscore - ID_WINDOW_SIZE;
                if (alpha < alpha_full) alpha = alpha_full;
                beta  = nscore + ID_WINDOW_SIZE;
                if (beta > beta_full) beta = beta_full;
                lmp_active = 1;
            } else
            {
                /*use full window and no late move pruning at low depth.*/
                alpha = alpha_full;
                beta  = beta_full;
                lmp_active = 0;
            }

            /*widen window until neither fail high nor low.*/
            for (;;)
            {
                nscore = Search_Negascout(0, 1, &line, movelist, move_cnt, d, alpha, beta, colour,
                                          &ret_mv_idx, PV_NODE, in_check, 1, lmp_active);

                /*search with full window should not fail, but
                  just for robustness.*/
                if (((alpha == alpha_full) && (beta == beta_full)) ||
                    ((alpha == alpha_full) && (nscore <= alpha_full)) ||
                    ((beta == beta_full) && (nscore >= beta_full)))
                {
                    break;
                }

                COMPILER_BARRIER;
                if (time_is_up != TM_NO_TIMEOUT)
                    break;
                COMPILER_BARRIER;

                if (nscore <= alpha) /*fail low*/
                {
                    /*note that a fail low implies ret_mv_idx == -1 because
                      the Negascout initialises the return index to that value
                      and only sets it up when a move raises alpha, which no
                      move does in case of a fail low.*/
                    alpha = alpha_full;
                } else if (nscore >= beta) /*fail high*/
                {
                    beta = beta_full;

                    if (ret_mv_idx > 0) /*not already the main PV?*/
                    {
                        MOVE ret_move = movelist[ret_mv_idx];

                        /*found new best move. update ranking and PV immediately to get this
                          move searched before the old PV root move. We may not have time
                          to search both, and this move failed high while the old PV root
                          move didn't.*/
                        Search_Find_Put_To_Top_Root(movelist, root_refutation_table, move_cnt, ret_move);
                        /*update global PV*/
                        GlobalPV.line_cmoves[0] = Mvgen_Compress_Move(ret_move);
                        if (line.line_len > 0)
                        {
                            /*we have a (maybe truncated) PV despite fail high*/
                            Util_Movelinecpy(GlobalPV.line_cmoves + 1, line.line_cmoves, line.line_len);
                            GlobalPV.line_len = line.line_len + 1;
                        } else if (root_refutation_table[0] != MV_NO_MOVE_CMASK)
                        {
                            /*otherwise, the reply move from the opponent move cache
                              failed low for the opponent, like all reply moves, but
                              it is at least somewhat reasonable*/
                            GlobalPV.line_cmoves[1] = root_refutation_table[0];
                            GlobalPV.line_len = 2;
                        } else
                            GlobalPV.line_len = 1; /*not even opponent cache move is available*/
                    }
                } else
                    break;
            }

            if (ret_mv_idx >= 0)
            {
#ifdef PC_PRINTF
                int exclamation = 0;
#endif
                /*retain the PV if possible. this helps the move ordering and is
                  especially useful with PV hits.*/
                int copy_line_pv = 0;
                /*first move of PV changed, or new PV is at least as long?*/
                if ((GlobalPV.line_cmoves[0] != Mvgen_Compress_Move(movelist[ret_mv_idx])) ||
                    (GlobalPV.line_len <= line.line_len + 1))
                {
                    copy_line_pv = 1;
                } else
                {
                    /*something in the new, but shorter PV changed?*/
                    for (i = 0; i < line.line_len; i++)
                    {
                        if (GlobalPV.line_cmoves[i+1] != line.line_cmoves[i])
                        {
                            copy_line_pv = 1;
                            break;
                        }
                    }
                }

                if (copy_line_pv)
                {
                    game_info.valid = EVAL_MOVE;
                    game_info.eval = pos_score = nscore;
                    game_info.depth = d;

                    decomp_move = movelist[ret_mv_idx];
                    GlobalPV.line_cmoves[0] = Mvgen_Compress_Move(decomp_move);
                    Util_Movelinecpy(GlobalPV.line_cmoves + 1, line.line_cmoves, line.line_len);
                    GlobalPV.line_len = line.line_len + 1;
                    Search_Find_Put_To_Top_Root(movelist, root_refutation_table, move_cnt, decomp_move);
                }
#ifdef PC_PRINTF
                exclamation = (d > START_DEPTH) && ((pos_score - sort_max) > PV_CHANGE_THRESH);
                Search_Print_Move_Output(d, pos_score, exclamation);
#ifdef G_NODES
                printf(" Nodes: %llu\r\n", (long long unsigned) g_nodes);
#endif
#endif
                if (is_analysis)
                {
                    int32_t time_passed = Time_Passed();
                    Hmi_Update_Analysis_Screen(time_passed, pos_score, d, &GlobalPV);
                    if (time_passed > 5L*MILLISECONDS)
                        /*don't annoy the user with a constant BEEP during the first few plies depth*/
                        Hmi_Signal(HMI_MSG_ATT);
                    Hw_Sig_Send_Msg(HW_MSG_LED_BACK_ON, BACKLIGHT_ANA, HW_MSG_PARAM_BACK_CONF);
                } else
                {
                    int32_t disp_time = Hw_Get_System_Time();

                    Hmi_Update_Alternate_Screen(pos_score, d, &GlobalPV);
                    /*a full display update takes about 6 ms, so maybe add this*/
                    disp_time = Hw_Get_System_Time() - disp_time;
                    if (disp_time > 1L) /*probably just timer interrupt*/
                        Time_Add_Conf_Delay(disp_time + 1L);
                }

                /*with mate score, allow one more iteration for confirmation.*/
                if ((pos_score > MATE_CUTOFF) || (pos_score < -MATE_CUTOFF))
                    mate_conf++;
                else
                    mate_conf = 0;

                if (((((mate_conf >= 2U)) || (move_cnt < 2)) && (!is_analysis))
                    || (time_is_up != TM_NO_TIMEOUT))
                    break;
            }
            /*if the pre-sorting has shown an outstanding move, and this move
              is still at the head of the PV, then just do it. Saves time and
              prevents the opponent from having a certain ponder hit in case he
              is using pondering.
              if we have an easy move that also is a PV hit, then the PV is
              retained if it is longer than the "easy depth", which is the
              desired effect.*/
            if ((score_drop >= EASY_THRESHOLD) && (d >= EASY_DEPTH) &&
                (failsafe_cmove == GlobalPV.line_cmoves[0]) &&
                (!is_analysis))
            {
                break;
            }
            if (Time_Passed() > reduced_move_time) /*more than 55% already used*/
            {
                time_is_up = TM_TIMEOUT;
                break;
            }
        } /*for (d=...) end of Iterative Deepening loop*/
#ifdef DBGCUTOFF
        printf("\n Cutoff on 1st move is %4.2lf%% \n", 100.0*((double)cutoffs_on_1st_move)/((double)total_cutoffs) );
#endif

        COMPILER_BARRIER;
        if (is_analysis)
        {
            /*the question now is: why are we here?
              big question indeed, but fortunately, the chess program has only three possible answers
              at this point. yes, being a chess program makes life pretty easy sometimes.
              a) analysis mode hit the maximum searching depth, OR
              b) the 9 hours thinking time are over, OR
              c) the user pressed the GO button.
            if case c), we don't want to idle around, but in case a) and b), we want.*/
            if ((time_is_up == TM_NO_TIMEOUT) ||  /*case a)*/
                (Time_Check(computer_side))) /*case b)*/
            {
                /*redundant in case a), but in case b), we want to reset that flag
                  and wait for the user to hit GO, which will drive it to 1.*/
                time_is_up = TM_NO_TIMEOUT;

                /*we're idling along, so get the system speed down - that saves energy.*/
                Hw_Set_Speed(SYSTEM_SPEED_LOW, SYSTEM_MODE_COMP, CLK_FORCE_AUTO);
                COMPILER_BARRIER;
                while ((!Time_Check(computer_side)) && (time_is_up == TM_NO_TIMEOUT))
                {
                    /*do nothing. the current time will be updated on the display once per second.*/
                    Time_Delay(10U, SLEEP_ALLOWED);
                }
                COMPILER_BARRIER;
                while (time_is_up == TM_NO_TIMEOUT)
                {
                    /*wait for the user to hit GO*/
                    Time_Delay(10U, SLEEP_ALLOWED);
                    Hw_Trigger_Watchdog();
                }
            }
        }

        if ((pos_score < -dynamic_resign_threshold) && (!is_analysis))
        {
            /*computer resigns, but still return the move found in case the player wants to play it out*/
            *answer_move = Mvgen_Decompress_Move(GlobalPV.line_cmoves[0]);
            return(COMP_RESIGN);
        }
    }
    *answer_move = Mvgen_Decompress_Move(GlobalPV.line_cmoves[0]);
    return(COMP_MOVE_FOUND);
}

/*the mate solver.*/
static enum E_COMP_RESULT NEVER_INLINE
Search_Get_Mate_Solution(int max_d, MOVE *blocked_movelist, int blocked_moves, LINE *pline, enum E_COLOUR colour)
{
    int res = 0, move_cnt, actual_move_cnt, i, in_check;
    int Alpha = 0;
    int Beta  = INFINITY_;
    MOVE movelist[MAXMV];

    pline->line_len = 0;
    in_check = Mvgen_King_In_Check(colour);

    Starting_Mv = mv_stack_p;
    move_cnt = Mvgen_Find_All_Moves(movelist, NO_LEVEL, colour, UNDERPROM);
    actual_move_cnt = 0;

    for (i = 0; i < move_cnt; i++)
    {
        int j, move_deleted = 0;
        /*filter out blocked moves. used for finding double solutions.*/
        for (j = 0; j < blocked_moves; j++)
        {
            if (((movelist[i].u ^ blocked_movelist[j].u) & mv_move_mask.u) == 0)
            {
                move_deleted = 1;
                break;
            }
        }
        if (move_deleted)
            continue;
        /*filter out all moves that would put or let our king in check*/
        Search_Push_Status();
        Search_Make_Move(movelist[i]);
        if (Mvgen_King_In_Check(colour)) {
            Search_Retract_Last_Move();
            Search_Pop_Status();
            continue;
        }
        Search_Retract_Last_Move();
        Search_Pop_Status();
        actual_move_cnt++;
    }
    if (actual_move_cnt == 0)
        return(COMP_NO_MOVE);

    /*first try to look for a mate when only considering check-delivering
      moves in the last "check_depth" moves. the idea is that the last
      few plies in a mate problem usually is a series of checks, so limit
      the moves for the attacking side to checks. the defending side, of
      course, always has the full tange of answer moves.
      if the approach of "all attacking moves deliver check" does not work
      out, then try to allow non-checking moves in the first ply and then only
      checks. if that doesn't work, allow all moves for the first two attack
      plies, and then only checks. and so on. it is amazing how much time this
      little scheme can save.
      since the last ply must deliver check (or else it cannot be mate),
      check_depth has to stay greater than zero.*/

    /*checks only*/
    Search_Reset_History();
    Hash_Clear_Tables();
    res = Search_Negamate(max_d, Alpha, Beta, colour, max_d, pline,
                          blocked_movelist, blocked_moves, 1 /*root node*/, in_check,
                          MIN_CHECK_DEPTH);

    /*non-checks at exactly one depth*/
    if ((res <= MATE_CUTOFF) && (time_is_up == TM_NO_TIMEOUT))
    {
        res = 0;
        for (int non_check_depth = max_d;
             ((non_check_depth > 1) && (res <= MATE_CUTOFF) && (time_is_up == TM_NO_TIMEOUT)); non_check_depth -= 2)
        {
            Search_Reset_History();
            Hash_Clear_Tables();
            res = Search_Negamate(max_d, Alpha, Beta, colour, non_check_depth, pline,
                                 blocked_movelist, blocked_moves, 1 /*root node*/, in_check,
                                 EXACT_CHECK_DEPTH);
        }
    }

    /*non-checks at increasing depth - root level has already been searched*/
    if ((res <= MATE_CUTOFF) && (time_is_up == TM_NO_TIMEOUT))
    {
        res = 0;
        for (int check_depth = max_d - 4;
             ((check_depth > 0) && (res <= MATE_CUTOFF) && (time_is_up == TM_NO_TIMEOUT)); check_depth -= 2)
        {
            Search_Reset_History();
            Hash_Clear_Tables();
            res = Search_Negamate(max_d, Alpha, Beta, colour, check_depth, pline,
                                 blocked_movelist, blocked_moves, 1 /*root node*/, in_check,
                                 MIN_CHECK_DEPTH);
        }
    }

    Search_Reset_History();
    Hash_Clear_Tables();

    if (res > MATE_CUTOFF)
        return(COMP_MOVE_FOUND);
    else
        return(COMP_NO_MOVE);
}

/*play out all PV moves*/
int Search_Play_PV(const LINE *pv, enum E_PV_STARTED pv_started, int *black_started_pv)
{
    int pos_start_mv = mv_stack_p + 1, black_pv = 0,
        pv_start_mv = (pv_started == PV_NOT_STARTED) ? 0 : 1;

    /*put the move sequence to the notation display, including "pretty print".*/
    for (int mv_cnt = pv_start_mv; mv_cnt < pv->line_len; mv_cnt++)
    {
        MOVE decomp_move = Mvgen_Decompress_Move(pv->line_cmoves[mv_cnt]);

        if ((mv_cnt == pv_start_mv) && (board[decomp_move.m.from]->type > BLACK))
            black_pv = 1;
        Search_Push_Status();
        Search_Make_Move(decomp_move);
        Hmi_Prepare_Pretty_Print();
    }
    *black_started_pv = black_pv;
    return(pos_start_mv);
}

/*take back all PV moves*/
void Search_Revert_PV(const LINE *pv, enum E_PV_STARTED pv_started)
{
    int take_back_len = (pv_started == PV_NOT_STARTED) ? pv->line_len : pv->line_len - 1;

    for (int mv_cnt = 0; mv_cnt < take_back_len; mv_cnt++)
    {
        Search_Retract_Last_Move();
        Search_Pop_Status();
    }
}

void NEVER_INLINE Search_Mate_Solver(enum E_COLOUR colour)
{
    MOVE blockmovelst[MAXMV];
    int mate_depth, mate_plies, is_material_enough,
    mate_found = 1, blocked_moves = 0, solve_cnt = 0;
    int32_t dummy_conf_time;
    LINE pline;
    char mate_found_number[18], mate_found_str[12];

#ifdef G_NODES
    g_nodes = 0;
#endif

    time_is_up = TM_NO_TIMEOUT;

    Util_Memzero(blockmovelst, sizeof(blockmovelst));

    /*should actually already have been caught via play.c / Play_Handling()*/
    is_material_enough = Eval_Setup_Initial_Material();
    if (!is_material_enough) /*draw due to insufficient material*/
    {
        (void) Hmi_Conf_Dialogue("no mate found:", "material draw.", &dummy_conf_time,
                                 HMI_NO_TIMEOUT, HMI_INFO, HMI_RESTORE);
        return;
    }

    Util_Strcpy(mate_found_number, "mate #");
    Util_Strcpy(mate_found_str, "mate in X.");

    mate_depth = (int) ((CFG_GET_OPT(CFG_MTI_MODE)) >> CFG_MTI_OFFSET);
    mate_depth++; /*config 0 is mate-in-1*/
    mate_plies = mate_depth * 2;
    mate_plies--; /*now we got the allowed mate distance in plies*/

    if ((mate_plies > MAX_DEPTH-2) || (mate_plies > 17))
    /*should not happen, maximum is 8 moves, but for future changes*/
    {
        (void) Hmi_Conf_Dialogue("solver error:", "mate too deep.", &dummy_conf_time,
                                 HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
        return;
    }

    do /*look for mate solutions*/
    {
        enum E_COMP_RESULT mate_result;
        enum E_TIMEOUT time_status;

        /*ramp up the speed*/
        Hw_Set_Speed(SYSTEM_SPEED_HIGH, SYSTEM_MODE_COMP, CLK_ALLOW_LOW);
        if (CFG_GET_OPT(CFG_CLOCK_MODE) > CFG_CLOCK_100)
        {
            /*we are overclocked - check the firmware image. The point here is not
              the image, but the calculation. the system speed is already high here.*/
            unsigned int sys_test_result;
            sys_test_result = Hw_Check_FW_Image(); /*do some lengthy calculation stuff*/
            if (sys_test_result != HW_SYSTEM_OK)   /*ooops - overclocked operation is instable!*/
            {
                Hw_Set_Speed(SYSTEM_SPEED_LOW, SYSTEM_MODE_USER, CLK_FORCE_AUTO);  /*save energy and get the keyboard going*/
                (void) Hmi_Conf_Dialogue("O/C failed,", "normal speed.", &dummy_conf_time,
                                         HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
                CFG_SET_OPT(CFG_CLOCK_MODE, CFG_CLOCK_100);        /*disable overclocking*/
                Hw_Set_Speed(SYSTEM_SPEED_HIGH, SYSTEM_MODE_COMP, CLK_ALLOW_LOW); /*ramp up for the computer move*/
            }
        }

        Util_Memzero(&pline, sizeof(LINE));

        Time_Set_Current(); /*for the display*/
        (void) Time_Init(mv_stack_p);

        Hmi_Build_Mating_Screen(mate_depth);

        mate_result = Search_Get_Mate_Solution(mate_plies, blockmovelst, blocked_moves, &pline, colour);
        time_status = time_is_up;

        Time_Set_Stop();
        /*ramp down the speed*/
        Hw_Set_Speed(SYSTEM_SPEED_LOW, SYSTEM_MODE_USER, CLK_FORCE_AUTO);

#if defined(G_NODES) && defined(PC_PRINTF)
        printf("Nodes: %llu\r\n", (long long unsigned) g_nodes);
#endif

        /*double-beep only if we have actually found a solving move.
          means also: don't double-beep if there is a forced mate
          for the opponent instead.*/
        if (mate_result == COMP_MOVE_FOUND)
            Hmi_Signal(HMI_MSG_MOVE);
        else if (time_status != TM_USER_CANCEL) /*user triggered abort does not need attention*/
            Hmi_Signal(HMI_MSG_ATT);

        Hw_Sig_Send_Msg(HW_MSG_LED_BACK_ON, BACKLIGHT_MOVE, HW_MSG_PARAM_BACK_CONF);

        if (mate_result == COMP_MOVE_FOUND)
        {
            enum E_HMI_USER user_answer;
            int pos_start_mv, display_depth, black_started_pv;
            char *mate_found_ptr;

            /*prepare mate solution number, but announce it only if there
              are any double solutions, not for the first finding.*/
            if (++solve_cnt == 1)
                mate_found_ptr = "mate found:";
            else /*more solutions*/
            {
                char solve_cnt_buf[4];
                char *solve_cnt_ptr = solve_cnt_buf;

                /*solve_cnt cannot be greater than 999 because there are not
                  that many moves in a chess position*/
                Util_Itoa(solve_cnt_buf, solve_cnt);
                solve_cnt_buf[3] = '\0';      /*add 0-termination*/
                while (*solve_cnt_ptr == ' ') /*jump over leading spaces*/
                    solve_cnt_ptr++;

                /*append mate solution number after "mate #"*/
                Util_Strcpy(mate_found_number + 6, solve_cnt_ptr);
                Util_Strcat(mate_found_number + 6, " found:");
                mate_found_ptr = mate_found_number;
            }

            /*at which depth this mate was found*/
            display_depth = (pline.line_len + 1) / 2;
            mate_found_str[8] = ((char) display_depth) + '0';

            (void) Hmi_Conf_Dialogue(mate_found_ptr, mate_found_str, &dummy_conf_time,
                                     HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);

            /*play PV moves on the board and prepare "pretty print"*/
            pos_start_mv = Search_Play_PV(&pline, PV_NOT_STARTED, &black_started_pv);
            /*open the notation screen.*/
            Hmi_Disp_Movelist(black_started_pv, pos_start_mv, HMI_IS_PV, HMI_MENU_MODE_POS);
            /*undo the PV moves*/
            Search_Revert_PV(&pline, PV_NOT_STARTED);

            user_answer = Hmi_Conf_Dialogue("search for", "other solutions?", &dummy_conf_time,
                                            HMI_NO_TIMEOUT, HMI_QUESTION, HMI_NO_RESTORE);
            if (user_answer == HMI_USER_CANCEL)
                return;
            /*add the current solution move to the blocklist*/
            blockmovelst[blocked_moves] = Mvgen_Decompress_Move(pline.line_cmoves[0]);
            blocked_moves++;
        } else
        {
            switch (time_status)
            {
            case TM_TIMEOUT:
                (void) Hmi_Conf_Dialogue("no mate found:", "time over.", &dummy_conf_time,
                                         HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
                break;
            case TM_USER_CANCEL:
                (void) Hmi_Conf_Dialogue("no mate found:", "cancelled.", &dummy_conf_time,
                                         HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
                break;
            case TM_NO_TIMEOUT:
            default:
                    if ((mate_result == COMP_MATE) && (blocked_moves == 0))
                    /*the entered position is already checkmate. that should be caught
                      after entering the position, but keep it here just in case
                      that the interface should change later on.*/
                    {
                        if (colour == WHITE)
                            (void) Hmi_Conf_Dialogue("white is mated:", "search finished.", &dummy_conf_time,
                                                     HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
                        else
                            (void) Hmi_Conf_Dialogue("black is mated:", "search finished.", &dummy_conf_time,
                                                     HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
                    } else
                        (void) Hmi_Conf_Dialogue("no mate found:", "search finished.", &dummy_conf_time,
                                                 HMI_NO_TIMEOUT, HMI_INFO, HMI_NO_RESTORE);
                break;
            }

            /*no (or no further) mate found, so we are done.*/
            mate_found = 0;
        }
    } while (mate_found);
}
