/*
    Copyright 2015 Harm Jetten

    This file is part of Moby Dam.

    Moby Dam 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.

    Moby Dam 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 Moby Dam.  If not, see <http://www.gnu.org/licenses/>.
*/

/* search.c: the principal variation search */

#include "main.h"

typedef struct {               /* set of board positions */
    int count;
    bitboard pos[128];
} poslist;

typedef struct {               /* killer store per ply */
    int k1;
    int k2;
} kilst;

typedef struct {               /* info per concurrent thread */
    int tid;                   /* the thread id */
#ifdef _WIN32
    HANDLE hthread;
#else
    pthread_t thread;
    int created;
#endif
    int maxdepth;              /* depth limit */
    int depth;                 /* current working depth of thread */
    int completed;             /* most recent fully completed depth of thread */

    /* statistics */
    u64 movegen;               /* move generation calls */
    u64 eval;                  /* evaluations */
    u64 dtw;                   /* distance-to-win db hits */
    u64 wdl;                   /* win/draw/loss db hits */
    u64 node;                  /* nodes visited */
    u64 nonleaf;               /* non-leaf nodes visited */
    u64 ttprobe;               /* tt probes */
    u64 tthit;                 /* tt hits */
    u64 ttbest;                /* tt bestmoves */
    u64 ttstore;               /* tt stores */
#ifdef CUT
    u64 cuttst;                /* cut tests */
    u64 cuthit;                /* cut hits */
    u64 cutprobe;              /* cut tt probes */
#endif
#ifdef ETC
    u64 etctst;                /* etc tests */
    u64 etchit;                /* etc hits */
    u64 etccut;                /* etc cutoffs */
#endif

    movelist list;             /* the thread's root move list */
    s32 scores[128];           /* scores corresponding to the move list */
    kilst killers[MAXPLY];     /* killer store */
} perthread;

perthread thread_info[MAXTHR]; /* various data for the threads */

/* kept separate from thread_info to preserve contents over the moves: */
u32 good_hist[MAXTHR][51*51];  /* history of good moves per thread */

s32 iter0_score;               /* static root value before iterations start */
int max_ply;                   /* maximum ply to search */
int db_maxpc;                  /* maximum piece count for wdl lookup */
s32 db_threshold;              /* egdb win/loss score cutoff threshold */

u32 start_tick;                /* time tick at start of search */
u32 last_tick;                 /* most recent time tick */
u32 think_time;                /* time budget in milliseconds */

/* clear history array */
void clear_hist(void)
{
    memset(good_hist, 0, num_threads*sizeof good_hist[0]);
}

/* fade history array */
/* let info from past moves gradually fade away */
static void fade_hist(void)
{
    int i, j, tid;

    for (tid = 0; tid < num_threads; tid++)
    {
        for (i = 1; i <= 50; i++)
        {
            for (j = 1; j <= 50; j++)
            {
                good_hist[tid][51*i + j] >>= 3;
            }
        }
    }
}

/* sort moves best-first */
/* currently using info from transposition table, */
/* killer moves, and history of earlier good moves */
/* listptr -> move list to be sorted */
/* d = tree depth (distance from leaves) */
/* bestmove = the best move from the tt */
/* kilptr -> the current ply's killer store */
__inline__
static void sort_moves(movelist *listptr, int d, int bestmove, kilst *kilptr, int tid)
{
    bitboard move;
    int fromto;
    int m, mtt = -1;
#ifdef KIL
    int mk1 = -1, mk2 = -1;
#endif

    /* do tt best move and killers */
    if (bestmove != 0 || d > 2)
    {
        /* find the indexes of the interesting moves */
        for (m = 0; m < listptr->count; m++)
        {
            fromto = move_square(&listptr->move[m], FROMTO);
            if (fromto == bestmove)
            {
                mtt = m;
            }
#ifdef KIL
            else if (fromto == kilptr->k1)
            {
                mk1 = m;
            }
            else if (fromto == kilptr->k2)
            {
                mk2 = m;
            }
#endif
        }
        /* swap the found moves around to the front of the list */
        m = 0;
        if (mtt == 0)
        {
            m = 1; /* tt best move already at intended place */
        }
        if (mtt > 0)
        {
            /* swap tt best move to head of list */
            move = listptr->move[mtt];
            listptr->move[mtt] = listptr->move[0];
            listptr->move[0] = move;
#ifdef KIL
            if (mk1 == 0)
            {
                mk1 = mtt; /* got a new position */
            }
            if (mk2 == 0)
            {
                mk2 = mtt; /* got a new position */
            }
#endif
            m = 1;
        }
#ifdef KIL
        if (mk1 == m)
        {
            m++; /* killer 1 already at intended place */
        }
        if (mk1 > m)
        {
            /* swap killer 1 to next place */
            move = listptr->move[mk1];
            listptr->move[mk1] = listptr->move[m];
            listptr->move[m] = move;
            if (mk2 == m)
            {
                mk2 = mk1; /* got a new position */
            }
            m++;
        }
        if (mk2 == m)
        {
            m++; /* killer 2 already at intended place */
        }
        if (mk2 > m)
        {
            /* swap killer 2 to next place */
            move = listptr->move[mk2];
            listptr->move[mk2] = listptr->move[m];
            listptr->move[m] = move;
            m++;
        }
#endif

        /* sort on good history for remaining moves m..end */
        if (d > 2 && m < listptr->count - 1)
        {
            u32 g, gh[elements(listptr->move)];
            int i, j;

            /* first make the good_hist scores fast to access */
            for (i = m; i < listptr->count; i++)
            {
                fromto = move_square(&listptr->move[i], FROMTO);
                gh[i] = good_hist[tid][fromto];
            }
            /* do insertion sort, is fast for small number of moves */
            for (i = m + 1; i < listptr->count; i++)
            {
                move = listptr->move[i];
                g = gh[i];
                j = i;
                while (j > m && g > gh[j - 1])
                {
                    listptr->move[j] = listptr->move[j - 1];
                    gh[j] = gh[j - 1];
                    j--;
                }
                listptr->move[j] = move;
                gh[j] = g;
            }
        }
    }
}

/* do the recursive principal variation search */
/* bb -> current board */
/* ply = ply level */
/* depth = depth of tree to build */
/* alpha = minimum value to consider */
/* beta = maximum value to consider */
/* cut = whether this branch is pruned */
/* tid = thread id */
/* returns: backed-up score of move tree, or abort */
static s32 pv_search(bitboard *bb, int ply, int depth, s32 alpha, s32 beta, bool cut, int tid)
{
    movelist list;
    u32 tick;
    int bestmove;
    s32 origalpha, best, merit;
    int d, m, bestm, pcnt;

    debugf("pv_search enter ply=%d depth=%d side=%d\n",
           ply, depth, bb->side);

    thread_info[tid].node++;
    if (thread_info[tid].node%4096 == 0) /* don't peek too often */
    {
        if (tid == 0) /* only the main thread checks time and external events */
        {
            tick = get_tick();
            if (tick != last_tick)
            {
                last_tick = tick;
                if (side_moving == our_side) /* not pondering */
                {
                    /* time check */
                    if (tick - start_tick >= think_time ||
                        (test_time != 0 && tick - start_tick >= test_time))
                    {
                        debugf("pv_search time limit reached ply=%d depth=%d\n",
                               ply, depth);
                        main_event.movenow = TRUE;
                        return ABORT;
                    }
                }
                /* event check every ms */
                poll_event(0);
                if (main_event.any)
                {
                    debugf("pv_search event occurred ply=%d depth=%d\n",
                           ply, depth);
                    return ABORT;
                }
            }
        }
        else /* extra threads check for reasons to abort */
        {
            if (main_event.any)
            {
                debugf("pv_search thread event occurred ply=%d depth=%d\n",
                       ply, depth);
                return ABORT;
            }
        }
    }

    if (bb->white == 0 || bb->black == 0)
    {
        /* side to move has no pieces left */
        debugf("pv_search return ply=%d depth=%d side=%d nopcleft\n",
               ply, depth, bb->side);
        return -INFIN + ply;
    }

    /* check for regulation draw */
    if (is_draw(bb, ply, NULL)) /* in search, avoid any repetitions */
    {
        debugf("pv_search return ply=%d depth=%d side=%d draw\n",
               ply, depth, bb->side);
        /* an aimless king move, even if it's a draw by the book, */
        /* should not stumble into a lost db position */
        if (endgame_value(bb, ply, &best) && best > INFIN - MAXPLY)
        {
            return best;
        }
        return 0;
    }

    best = origalpha = alpha;
    bestmove = 0;
    if (depth > 0) /* no tt probing in quiescence search / leaf nodes, */
    {              /* the memory read stalls are too expensive */
        thread_info[tid].ttprobe++;
        if (probe_tt(bb, ply, depth, alpha, beta, &best, &bestmove))
        {
            debugf("probe_tt hit ply=%d depth=%d side=%d score=%d\n",
                   ply, depth, bb->side, best);
            thread_info[tid].tthit++;
            return best;
        }
        if (bestmove != 0) /* probe_tt found move from lower depth entry */
        {
            thread_info[tid].ttbest++;
        }
        alpha = best;      /* alpha may have been improved by probe_tt */
    }

    /* check DTW endgame database */
    pcnt = popcount(bb->white | bb->black);
    if (pcnt <= DTWENDPC && endgame_dtw(bb, ply, &best))
    {
        thread_info[tid].dtw++;
        debugf("pv_search dtw hit ply=%d depth=%d side=%d score=%d\n",
               ply, depth, bb->side, best);
        return best;
    }

    /* when depth <= 0, generate capture moves only for quiescence search */
    thread_info[tid].movegen++;
    gen_moves(bb, &list, NULL, depth > 0);

    if (list.count == 0 && depth > 0)
    {
        /* side to move can't move */
        debugf("pv_search return ply=%d depth=%d side=%d nomove\n",
               ply, depth, bb->side);
        return -INFIN + ply;
    }

    /* check WDL endgame database, except when we must capture */
    if (pcnt > DTWENDPC && pcnt <= MAXENDPC &&
        (list.count == 0 ||                      /* quiescent leaf node */
         (list.npcapt == 0 && pcnt <= db_maxpc)))/* non-capture interior node */
    {
        if (endgame_wdl(bb, &best))
        {
            thread_info[tid].wdl++;
            debugf("pv_search wdl hit ply=%d depth=%d side=%d score=%d\n",
                   ply, depth, bb->side, best);
            if (depth <= 0 ||             /* quiescent leaf node */
                abs(best) > db_threshold) /* win/loss score found */
            {
                debugf("pv_search wdl cutoff\n");
                return best;
            }
        }
    }

    if (list.count == 0 || ply >= max_ply)
    {
        /* quiescence search complete, arrived at leaf depth */
        thread_info[tid].eval++;
        return eval_board(bb);
    }

    d = depth;
    if (list.count > 1)
    {
        d--;

#ifdef CUT
        /* bad move pruning; poor man's ProbCut in the style of Scan 2.0 */
        m = VAL_MAN*9/10; /* margin */

        /* not too close to leaf depth, non-pv node, no db win */
        if (!cut && depth > 2 && alpha + 1 == beta && beta < INFIN - MAXPLY - m)
        {
            thread_info[tid].cuttst++;
            best = pv_search(bb, ply, depth*2/5, beta + m - 1, beta + m, TRUE, tid);

            /* check for engine event received at greater depth */
            if (best == ABORT)
            {
                debugf("pv_search abort while pruning ply=%d depth=%d\n",
                       ply, depth);
                return ABORT;
            }

            if (best >= beta + m)
            {
                thread_info[tid].cuthit++;
                return beta; /* fail-hard seems to work best here */
            }

            if (bestmove == 0)
            {
                /* tt may have a bestmove now */
                thread_info[tid].cutprobe++;
                probe_tt(bb, ply, depth, alpha, beta, &best, &bestmove);
            }
        }
#endif

        /* order moves best-first */
#ifdef KIL
        sort_moves(&list, d, bestmove, &thread_info[tid].killers[ply], tid);
#else
        sort_moves(&list, d, bestmove, NULL, tid);
#endif

#ifdef ETC
        /* enhanced transposition cutoffs */
        /* not too close to leaf depth, and not in pv nodes */
        if (d > 4 && alpha + 1 == beta)
        {
            thread_info[tid].etctst++;
            for (m = 0; m < list.count; m++)
            {
                /* see if move leads to a position in the tt */
                if (probe_tt(&list.move[m], ply + 1, d, -beta, -alpha, &best, NULL))
                {
                    thread_info[tid].etchit++;
                    best = -best;
                    /* check for beta cutoff */
                    if (best >= beta)
                    {
                        thread_info[tid].etccut++;
                        debugf("pv_search ETC cut ply=%d depth=%d side=%d "
                               "score=%d\n", ply, depth, bb->side, best);
                        return best;
                    }
                }
            }
        }
#endif
    }

    /* build next tree level */
    thread_info[tid].nonleaf++;

    debugf("pv_search first move\n");
    best = -pv_search(&list.move[0], ply + 1, d, -beta, -alpha, cut, tid);
    bestm = 0;

    /* check for engine event received at greater depth */
    if (best == -ABORT)
    {
        debugf("pv_search abort after first move ply=%d depth=%d\n",
               ply, depth);
        return ABORT;
    }

    for (m = 1; m < list.count; m++)
    {
        /* beta cutoff */
        if (best >= beta)
        {
            break; /* out of for loop */
        }
        /* raise lower bound */
        if (best > alpha)
        {
            alpha = best;
        }

#ifdef LMR
        /* late move reductions */
        merit = alpha + 1; /* to do the full search if not reduced */
        if (m >= 3 && alpha + 1 == beta && d > 2 && pcnt >= 8)
        {
            /* reduced depth zero width window search */
            merit = -pv_search(&list.move[m], ply + 1, d - 1 - (m >= 6),
                               -alpha - 1, -alpha, cut, tid);

            /* check for engine event received at greater depth */
            if (merit == -ABORT)
            {
                debugf("pv_search abort after lmr search ply=%d depth=%d\n",
                       ply, depth);
                return ABORT;
            }
        }
        if (merit > alpha)
#endif
        {
            /* full depth zero width window search */
            merit = -pv_search(&list.move[m], ply + 1, d, -alpha - 1, -alpha, cut, tid);

            /* check for engine event received at greater depth */
            if (merit == -ABORT)
            {
                debugf("pv_search abort after 0-width search ply=%d depth=%d\n",
                       ply, depth);
                return ABORT;
            }
        }

        if (merit > best)
        {
            /* found a new best move */
            best = merit;
            bestm = m;
            debugf("pv_search merit > best\n");
            if (best > alpha && best < beta) /* in PV (open window) */
            {
                /* new PV, re-search with full window */
                debugf("pv_search re-search\n");
                merit = -pv_search(&list.move[m], ply + 1, d, -beta, -best, cut, tid);

                /* check for engine event received at greater depth */
                if (merit == -ABORT)
                {
                    debugf("pv_search abort after re-search ply=%d depth=%d\n",
                           ply, depth);
                    return ABORT;
                }

                if (merit > best)
                {
                    best = merit;
                }
            }
        }
    }

    bestmove = move_square(&list.move[bestm], FROMTO);

#ifdef KIL
    if (best >= beta && list.count > 1)
    {

        /* save as a killer */
        if (thread_info[tid].killers[ply].k1 != bestmove)
        {
            thread_info[tid].killers[ply].k2 = thread_info[tid].killers[ply].k1;
            thread_info[tid].killers[ply].k1 = bestmove;
        }
    }
#endif

    if (depth > 1 && best > origalpha)
    {
        /* save in history of good moves */
        good_hist[tid][bestmove] += (depth - 1)*(depth - 1);
    }

    if (depth > 0)
    {
        /* save score and bestmove in transposition table */
        store_tt(bb, ply, depth, origalpha, beta, best, bestmove);
        thread_info[tid].ttstore++;
    }

    debugf("pv_search return ply=%d depth=%d side=%d score=%d\n",
           ply, depth, bb->side, best);
    return best;
}

/* set time budget */
/* depending on worsening or improving score */
/* bb -> current board */
/* m = index number of the move in the move list, use -m for re-search */
/* score = current score */
/* start = score at start of search */
static void set_budget(bitboard *bb, int m, s32 score, s32 start)
{
    if (score < start - VAL_MAN/10)
    {
        /* try to think our way out of trouble */
        think_time = 3*move_time;
        return;
    }

    think_time = move_time;

    switch (m)
    {
    case 0:        /* try to finish the PV and the runner-up */
    case 1:
        think_time = 2*think_time;
        break;
    case -1:       /* re-search of runner-up */
    case 2:        /* search of second runner-up */
        think_time = 3*think_time/2;
        break;
    default:
        /* no extra time for the rest, including other re-searches */
        break;
    }

    if (score > start + 7*VAL_MAN/5)
    {
        /* things are going well */
        think_time = 2*think_time/3;
    }
}

/* do the root-level principal variation search */
/* moves have already been generated by the caller */
/* depth = depth of tree to build */
/* listptr -> move list; the best move will be put in front */
/* tid = thread id */
/* out: scores -> values of individual moves in the move list, same order */
/* returns: index of last examined move in list */
static int pv_search0(int depth, movelist *listptr, s32 *scores, int tid)
{
    bitboard move;
    lnentry moveln;
    s32 alpha, beta, best, merit;
    int d, m;
    char str[356];

    thread_info[tid].depth = depth;
    if (verbose_info)
    {
        printf("%u t%d starting depth %d\n",
               last_tick - start_tick, tid, depth);
    }

    thread_info[tid].node++;

#ifdef _DEBUG
    if (debug_info)
    {
        printf("pv_search0 ");
        for (m = 0; m < listptr->count; m++)
        {
            print_move(&listptr->move[m]);
        }
        printf("\n");
    }
    if (listptr->count == 0)
    {
        debugf("pv_search0 can't move\n");
        scores[0] = -INFIN;
        return 0;
    }
#endif

    if (tid == 0 && depth == 1) /* first iterative deepening pass */
    {
        /* get a first approximation of the score at */
        /* start of search, save for set_budget() */
        if (!endgame_value(listptr->bb, 0, &iter0_score))
        {
            thread_info[tid].eval++;
            iter0_score = eval_board(listptr->bb);
        }
        scores[0] = iter0_score;
    }

    d = depth;
    if (listptr->count > 1)
    {
        d--;
    }

    /* adjust time budget */
    if (tid == 0)
    {
        set_budget(&listptr->move[0], 0, scores[0], iter0_score);
    }

    /* build first tree level */
    thread_info[tid].nonleaf++;
    alpha = -INFIN;
    beta = INFIN;
    best = -pv_search(&listptr->move[0], 1, d, -beta, -alpha, FALSE, tid);

    /* check for engine event received at greater depth */
    if (best == -ABORT)
    {
        debugf("pv_search0 abort first move\n");
        return 0;
    }

    if (verbose_info)
    {
        sprint_pv(str, &listptr->move[0]);
        printf("%u t%d %d.%d score=%d pv=%s",
               last_tick - start_tick, tid, depth, 0, best, str);
    }

    scores[0] = best;

    for (m = 1; m < listptr->count; m++)
    {
        if (tid != 0 && thread_info[0].depth > depth)
        {
            /* main thread has started deeper iterative search, */
            /* this extra thread should abandon current depth */
            if (verbose_info)
            {
                printf("%u t%d abandoning depth %d\n",
                       last_tick - start_tick, tid, depth);
            }
            return m;
        }

        fflush(stdout);

        /* raise lower bound */
        if (best > alpha)
        {
            alpha = best;
        }

        /* adjust time budget */
        if (tid == 0)
        {
            set_budget(&listptr->move[m], m, best, iter0_score);
        }

        /* zero width window search */
        merit = -pv_search(&listptr->move[m], 1, d, -alpha - 1, -alpha, FALSE, tid);

        /* check for engine event received at greater depth */
        if (merit == -ABORT)
        {
            debugf("pv_search0 abort 0-width search\n");
            return m;
        }

        scores[m] = merit;
        if (merit > best)
        {
            if (tid != 0 && thread_info[0].depth > depth)
            {
                /* main thread has started deeper iterative search, */
                /* this extra thread should abandon current depth */
                if (verbose_info)
                {
                    printf("%u t%d abandoning depth %d\n",
                           last_tick - start_tick, tid, depth);
                }
                return m;
            }

            /* found a new best move */
            best = merit;
            if (verbose_info)
            {
                sprint_pv(str, &listptr->move[m]);
                printf("%u t%d %d.%d merit=%d pv=%s",
                       last_tick - start_tick, tid, depth, m, merit, str);
            }
            /* pull the move to the head of the list, shifting the rest */
            /* so previous best moves stay near the front */
            move = listptr->move[m];
            memmove(&listptr->move[1], &listptr->move[0],
                    m*sizeof listptr->move[0]);
            listptr->move[0] = move;
            if (listptr->lnptr != NULL) /* long notation too, if present */
            {
                moveln = listptr->lnptr[m];
                memmove(&listptr->lnptr[1], &listptr->lnptr[0],
                        m*sizeof listptr->lnptr[0]);
                listptr->lnptr[0] = moveln;
            }
            memmove(&scores[1], &scores[0], m*sizeof scores[0]);
            scores[0] = best;

            /* re-search is only needed if not the last in the list */
            if (m < listptr->count - 1)
            {
                /* adjust time budget */
                if (tid == 0)
                {
                    set_budget(&listptr->move[0], -m, best, iter0_score);
                }

                if (verbose_info)
                {
                    printf("%u t%d %d.%d re-search\n",
                           last_tick - start_tick, tid, depth, m);
                }

                fflush(stdout);

                merit = -pv_search(&listptr->move[0], 1, d, -beta, -best, FALSE, tid);

                /* check for engine event received at greater depth */
                if (merit == -ABORT)
                {
                    debugf("pv_search0 abort re-search\n");
                    return m;
                }

                if (merit > best)
                {
                    best = merit;
                }
                scores[0] = best;
            }
            if (verbose_info)
            {
                sprint_pv(str, &listptr->move[0]);
                printf("%u t%d %d.%d new best=%d pv=%s",
                       last_tick - start_tick, tid, depth, m, best, str);
            }
        }
        else
        {
            if (verbose_info)
            {
                sprint_move(str, &listptr->move[m]);
                printf("%u t%d %d.%d score=%d move=%s\n",
                       last_tick - start_tick, tid, depth, m, merit, str);
            }
        }
    }

    thread_info[tid].completed = depth;
    if (verbose_info)
    {
        sprint_move(str, &listptr->move[0]);
        printf("%u t%d %d.complete, score=%d move=%s\n",
               last_tick - start_tick, tid, depth, scores[0], str);
    }
    return listptr->count;
}

/* additional thread(s) started by main search; */
/* this performs the Lazy SMP parallel search, */
/* filling the transposition table and hopefully */
/* improving the quality of the main search */
/* arg -> current thread's info structure */
#ifdef _WIN32
static unsigned __stdcall
#else
static void *
#endif
thread_think(void *arg)
{
    perthread *tinfo = arg;
    int d, i;

    if (popcount(tinfo->list.bb->white | tinfo->list.bb->black) <= DTWENDPC)
    {
        /* no need for extra threads, main thread can handle dtw endgame */
        return 0;
    }

    /* iterative deepening; start thread with varying depths */
    for (d = tinfo->tid + 1; ; d++)
    {
        int n = 0;
        if (d <= thread_info[0].depth)
        {
            d = thread_info[0].depth + 1; /* leapfrog the main thread's depth */
        }
        for (i = 1; i < num_threads; i++)
        {
            if (i != tinfo->tid)
            {
                if (d < thread_info[i].depth)
                {          /* catch up to thread with highest depth */
                    d = thread_info[i].depth;
                    n = 0;
                }
                if (d == thread_info[i].depth)
                {
                    n++;   /* count threads working at this depth */
                }
                if (n > d - thread_info[0].depth)
                {
                    d++;   /* already enough threads working at this depth, */
                    n = 0; /* take the next higher */
                }
            }
        }
        if (d > tinfo->maxdepth)
        {
            break; /* out of iteration */
        }

        pv_search0(d, &tinfo->list, tinfo->scores, tinfo->tid);

        fflush(stdout);

        if (main_event.any)
        {
            /* search was interrupted */
            break; /* out of iteration */
        }
    }
    return 0;
}

/* start the extra threads to fill the transposition table */
/* listptr -> move list */
/* maxdepth = ultimate iterative search depth */
void start_threads(movelist *listptr, int maxdepth)
{
    int i;

    for (i = 1; i < num_threads; i++)
    {
        /* make local copy of move list */
        thread_info[i].list.count = listptr->count;
        thread_info[i].list.npcapt = listptr->npcapt;
        thread_info[i].list.bb = listptr->bb;
        thread_info[i].list.lnptr = NULL;
        memcpy(thread_info[i].list.move, listptr->move,
               listptr->count*sizeof listptr->move[0]);

        thread_info[i].maxdepth = maxdepth;
        thread_info[i].tid = i;
#ifdef _WIN32
        thread_info[i].hthread = (HANDLE)_beginthreadex(NULL, 0, thread_think,
                                 &thread_info[i], 0, NULL);
#else
        thread_info[i].created =
            pthread_create(&thread_info[i].thread, NULL, thread_think,
                           &thread_info[i]);
#endif
    }
}

/* stop the extra threads */
void stop_threads(void)
{
    int i;

    /* signal the extra threads to stop now */
    main_event.movenow = TRUE;

    for (i = 1; i < num_threads; i++)
    {
#ifdef _WIN32
        if (thread_info[i].hthread > 0) /* was successful */
        {
            WaitForSingleObject(thread_info[i].hthread, INFINITE);
            CloseHandle(thread_info[i].hthread);
            thread_info[i].hthread = 0;
        }
#else
        if (thread_info[i].created == 0) /* was successful */
        {
            pthread_join(thread_info[i].thread, NULL);
        }
#endif
    }

    /* reset 'time is up' event */
    main_event.movenow = FALSE;
}

/* recursive part of check if capture sequences are equivalent */
/* bb -> current board */
/* posptr -> position list */
/* returns: TRUE if OK, FALSE if storage exceeded */
static bool equiv_search(bitboard *bb, poslist *posptr)
{
    movelist list;
    int m;

    /* generate capture moves only */
    gen_moves(bb, &list, NULL, FALSE);

    if (list.count == 0)
    {
        /* arrived at leaf depth, add this board to the list */
        if (posptr->count >= elements(posptr->pos))
        {
            printf("equiv_search too complex\n");
            return FALSE;
        }
        posptr->pos[posptr->count] = *bb;
        posptr->count++;
        return TRUE;
    }
    /* do the next level of captures */
    for (m = 0; m < list.count; m++)
    {
        if (!equiv_search(&list.move[m], posptr)) /* recurse */
        {
            return FALSE;
        }
    }
    return TRUE;
}

/* check if each capture sequence leads to the same set of board positions, */
/* making them equivalent, and sparing us the need (and time) to search */
/* listptr -> move list */
/* returns: TRUE if equivalent */
static bool equiv_captures(movelist *listptr)
{
    poslist posarray[2];
    int m, n, p;

    /* we hande only multiple captures */
    if (listptr->npcapt == 0 || listptr->count <= 1)
    {
        return FALSE;
    }

    p = 0;
    for (m = 0; m < listptr->count; m++)
    {
        posarray[p].count = 0;
        if (!equiv_search(&listptr->move[m], &posarray[p]))
        {
            return FALSE;
        }
        qsort(posarray[p].pos, posarray[p].count, sizeof(bitboard),
              (__compar_fn_t) bb_compare);
        if (p != 0)
        {
            /* compare second/third/etc. set of sorted positions to the first */
            if (posarray[0].count != posarray[1].count)
            {
                return FALSE;
            }
            for (n = 0; n < posarray[0].count; n++)
            {
                if (bb_compare(&posarray[0].pos[n], &posarray[1].pos[n])
                    != EQUAL)
                {
                    return FALSE;
                }
            }
        }
        p = 1;
    }
    return TRUE;
}

/* let engine determine the next move to be made */
/* listptr -> move list; the best move will be put in front */
/* maxdepth = ultimate iterative search depth */
void engine_think(movelist *listptr, int maxdepth)
{
    bitboard *bb;
    s32 *scores;
    lnentry moveln;
    char str[7];
    s32 best, nextbest;
    int d, i, m;

    if (get_bookmove(listptr))
    {
        printf("book move selected\n");
    }
    else if (listptr->count == 1)
    {
        printf("only one valid move, no need to search\n");
    }
    else if (equiv_captures(listptr))
    {
        printf("capture moves are all equivalent, no need to search\n");
    }
    else
    {
        memset(thread_info, 0, num_threads*sizeof thread_info[0]);
        scores = thread_info[0].scores;
        end_err = 0;

        /* the caller generated the moves for the root node */
        thread_info[0].movegen++;

        start_tick = last_tick = get_tick();
        fade_hist();

        /* may cutoff at any 5- or 6-pc win/loss position encountered */
        max_ply = MAXPLY;
        db_threshold = INFIN - max_ply;
        db_maxpc = 6;

        start_threads(listptr, maxdepth);

        /* iterative deepening */
        m = 0;
        for (d = 1; d <= maxdepth; d++)
        {
            m = pv_search0(d, listptr, scores, 0);

            fflush(stdout);

            if (main_event.any)
            {
                /* search was interrupted or time is up */
                break; /* out of iteration */
            }
            if (test_depth != 0 && d >= test_depth)
            {
                /* depth limit reached */
                break; /* out of iteration */
            }

            bb = &listptr->move[0];
            if (bb->white == 0 || bb->black == 0)
            {
                printf("best move takes all opponent's pieces\n");
                break;             /* no need for another iteration */
            }

            if (popcount(bb->white | bb->black) <= DTWENDPC)
            {
                if (endgame_dtw(&listptr->move[0], 1, &best))
                {
                    printf("best move's position is in dtw database\n");
                    break;         /* no need for another iteration */
                }
            }

            if (abs(scores[0]) > INFIN - MAXEXACT)
            {
                printf("found win or loss score from dtw database\n");
                break; /* no need for another iteration */
            }

            nextbest = -INFIN;
            for (i = 1; i < listptr->count; i++)
            {
                nextbest = max(nextbest, scores[i]);
            }
            if (nextbest < MAXEXACT - INFIN)
            {
                printf("remaining moves score a loss from dtw database\n");
                break; /* no need for another iteration */
            }

            if (abs(scores[0]) > db_threshold)
            {
                /* found a winning/losing move from wdl database, */
                /* search in next iteration for a quicker win / slower loss */
                /* with fewer pieces, by adjusting the cutoff threshold */
                if (abs(scores[0]) < INFIN - MAX5PLY)
                {
                    /* 6-pc win/loss found, now cutoff at any 5-pc win/loss */
                    max_ply = MAX5PLY;
                    db_maxpc = 5;
                }
                else
                {
                    /* 5-pc win/loss found, now keep searching for dtw */
                    max_ply = MAXEXACT;
                    db_maxpc = 4;
                }
                db_threshold = INFIN - max_ply;
                printf("entering iteration %d with threshold=%d maxply=%d\n",
                       d + 1, db_threshold, max_ply);
            }
        }

        stop_threads();

        if (main_event.any)
        {
            /* search was interrupted */
            return;
        }

        for (i = 1; i < num_threads; i++)
        {
            if (thread_info[i].completed >= d)
            {
                /* another thread has advanced past main thread depth; */
                /* use its best move and score instead if different */
                for (m = 1; m < listptr->count; m++)
                {
                    if (bb_compare(&thread_info[i].list.move[0],
                                   &listptr->move[m]) == EQUAL)
                    {
                        listptr->move[m] = listptr->move[0];
                        listptr->move[0] = thread_info[i].list.move[0];
                        if (listptr->lnptr != NULL)
                        {                    /* long notation too, if present */
                            moveln = listptr->lnptr[m];
                            listptr->lnptr[m] = listptr->lnptr[0];
                            listptr->lnptr[0] = moveln;
                        }
                        scores[m] = scores[0];
                        scores[0] = thread_info[i].scores[0];
                        if (verbose_info)
                        {
                            sprint_move(str, &listptr->move[0]);
                            printf("choosing move=%sfrom t%d with completed ",
                                   str, i);
                            sprint_move(str, &listptr->move[m]);
                            printf("depth %d instead of move=%sat depth %d\n",
                                   thread_info[i].completed, str, d);
                        }
                    }
                }
                d = thread_info[i].completed;
            }
        }

        if (verbose_info)
        {
            printf("tid, gencalls, evaluations, egdb dtw, wdl\n");
            for (i = 0; i < num_threads; i++)
            {
                printf("t%d %" PRIu64 " %" PRIu64 " %" PRIu64 " %" PRIu64 "\n",
                       i, thread_info[i].movegen, thread_info[i].eval,
                       thread_info[i].dtw, thread_info[i].wdl);
            }
            printf("tid, nodes total, nonleaf, leaf\n");
            for (i = 0; i < num_threads; i++)
            {
                printf("t%d %" PRIu64 " %" PRIu64 " %" PRIu64 "\n",
                       i, thread_info[i].node, thread_info[i].nonleaf,
                       thread_info[i].node - thread_info[i].nonleaf);
            }
            printf("tid, tt probes, hits, bestmoves, stores\n");
            for (i = 0; i < num_threads; i++)
            {
                printf("t%d %" PRIu64 " %" PRIu64 " %" PRIu64 " %" PRIu64 "\n",
                       i, thread_info[i].ttprobe, thread_info[i].tthit,
                       thread_info[i].ttbest, thread_info[i].ttstore);
            }
#ifdef CUT
            printf("tid, cut tests, hits, probes\n");
            for (i = 0; i < num_threads; i++)
            {
                printf("t%d %" PRIu64 " %" PRIu64 " %" PRIu64 "\n", i,
                       thread_info[i].cuttst, thread_info[i].cuthit,
                       thread_info[i].cutprobe);
            }
#endif
#ifdef ETC
            printf("tid, etc tests, hits, cuts\n");
            for (i = 0; i < num_threads; i++)
            {
                printf("t%d %" PRIu64 " %" PRIu64 " %" PRIu64 "\n", i,
                       thread_info[i].etctst, thread_info[i].etchit,
                       thread_info[i].etccut);
            }
#endif
        }
        if (verbose_info || end_err != 0)
        {
            printf("egdb errors=%" PRIu64 "\n", end_err);
        }
        printf("reached depth=%d:%d score=%d\n", d, m, scores[0]);
    }
    return;
}

/* let engine ponder while it is the opponent's turn; */
/* this fills the transposition table, speeding up the */
/* next search for our side */
/* bb -> current board */
/* maxdepth = ultimate iterative search depth */
/* returns: TRUE if further pondering still useful */
bool engine_ponder(bitboard *bb, int maxdepth)
{
    int d;

    if (verbose_info)
    {
        printf("starting pondering\n");
    }

    memset(thread_info, 0, num_threads*sizeof thread_info[0]);

    /* generate the moves for the root node */
    gen_moves(bb, &thread_info[0].list, NULL, TRUE);
    if (thread_info[0].list.count == 0)
    {
        if (verbose_info)
        {
            printf("pondering but no moves\n");
        }
        return FALSE;
    }
    thread_info[0].movegen++;

    start_tick = last_tick = get_tick();
    fade_hist();

    /* may cutoff at any 5- or 6-pc win/loss position encountered */
    max_ply = MAXPLY;
    db_threshold = INFIN - max_ply;
    db_maxpc = 6;

    start_threads(&thread_info[0].list, maxdepth);

    /* iterative deepening */
    for (d = 1; d <= maxdepth; d++)
    {
        pv_search0(d, &thread_info[0].list, thread_info[0].scores, 0);

        fflush(stdout);

        if (main_event.any)
        {
            /* search was interrupted */
            break; /* out of iteration */
        }
    }

    stop_threads();

    if (main_event.any)
    {
        /* search was interrupted */
        return TRUE;
    }

    if (verbose_info)
    {
        printf("pondering reached max depth\n");
    }
    return FALSE;
}
