/*----------------------------------------------------------------------
 | AB.C								940426
 |
 | Contains all ab-search functions.
 +----------------------------------------------------------------------*/


#include "var.h"


static ValueType Ab(Signed1 depth, ValueType alpha, ValueType beta,
                                    PathType ** bestPath);
static void     PutMoveInFront(MoveType * moveList, Unsigned1 nrMoves,
                                               MoveType * ttMove);
static double   PercFilled(void);
static Unsigned4 NrFilled(void);
static Unsigned4 ExpectedCollisions(Unsigned4 nodes);


/*----------------------------------------------------------------------
 | Search							940426
 |
 | Search for the best move at the root of the tree.
 +----------------------------------------------------------------------*/
void            Search(Signed1 searchDepth, MoveType * move, ValueType * bestValue)
{
    Unsigned1       nrMoves;
    MoveType       *moveList,
                    tempMove;
    ValueType       value,
                    alfa,
                    beta;
    Signed2         i,
                    j;
    Unsigned4       count,
                    ttNodes={0},
                    tot;
    Signed1         depth;
    double          timeUsed;
    Boolean         printDepth;
    PathType       *mainLine[MaxMoves],
                   *tempPath;
    Signed1         ttDepth={0};
    Unsigned1       flag;
    MoveType        ttMove;
    ValueType       ttValue;
    char            s[MaxMoveLength + 1];

    nrGenerates = nrMovesGenerated = 0;
    printDebug = False;
    StartTime();
    computer = toMove;
    stopSearching = False;
    for (i = 0; i < MaxMoves; i++) {
        mainLine[i] = NULL;
    }
    nrInternalNodes = nrLeafNodes = nrQuiesNodes = 0;
    nrTotalNodes = nrExtraNodes = 0;
    nrCollisions = nrHits = nrReads = nrWrites = 0;
    nrIllegalMoves = 0;
    if (searchDepth == 0) {
        PreProcessing();
        value = Quiescence(-Infinity, Infinity, &(mainLine[0]), -2, 0, 0, 0);
        PrintSearchInfo(timeUsed, 0, value, mainLine[0]);
        FreePath(mainLine[0]);
        move->from = 0;
        return;
    }
    if (searchDepth > MaxSearchDepth) {
        searchDepth = MaxSearchDepth;
    }
    startPly = nrGamePlies;
    if (startPly > 255) {
        printf("Warning: startPly too big!\n");
        startPly = 255;
    }
    /* Clear transposition tables */
    if (useTransTable && !timeStamp) {
        tot = useTwoLevelTable ? 1L << (nrTtBits + 1) : 1L << nrTtBits;
        for (count = 0; count < tot; count++) {
            if (GetFlag(&(transTable[count])) != NoEntry &&
                GetPly(&(transTable[count])) + keepPly < nrGamePlies) {
                ClearEntry(&(transTable[count]));
            }
        }
    }
    if (useTransTable) {
        printf("[%lu positions remaining in transposition table]\n", NrFilled());
    }
    ClearHistoryTables();
    PreProcessing();
    GenerateMoves(&moveList, &nrMoves);
    if (nrMoves == 0) {
        if (Attacked(kingSquare[toMove], (SquareType) ! toMove)) {
            printf("Mate\n");
        } else {
            printf("Stalemate\n");
        }
        move->from = 0;
        return;
    }
    HeapSort(moveList, nrMoves);
    GetMoveFromTransTable(ttMove, ttDepth, ttValue, flag, ttNodes);
    if (ttDepth != -1 && IsIllegal(ttMove)) {
        SPrintMove(s, ttMove);
        printf("Illegal move %s\n", s);
        ttDepth = -1;
        nrIllegalMoves++;
    }
    if (useTtMove && ttDepth != -1) {
        PutMoveInFront(moveList, nrMoves, &ttMove);
    }
    for (i = 0; i < nrMoves; i++) {
        AllocatePathMove(mainLine[i]);
        SPrintMove(mainLine[i]->moveString, moveList[i]);
        mainLine[i]->move = moveList[i];
    }
    for (depth = 1; depth <= searchDepth; depth++) {
        ++nrInternalNodes;
        if (++nrTotalNodes - nrExtraNodes >= testNrNodes && testNrNodes != -1) {
            stopSearching = True;
            break;
        }
        for (i = 0; i < nrMoves; i++) {
            if (interActive) {
                printf("%s (%2d/%2d)\r", mainLine[i]->moveString, i + 1, nrMoves);
                fflush(stdout);
            }
            DoMove(&(moveList[i]));
            if (i == 0) {       /* first move: aspiration search */
                if (depth == 1) {
                    alfa = -Infinity;
                    beta = Infinity;
                } else {        /* depth > 1 */
                    alfa = *bestValue - pieceValue[WhitePawn];
                    beta = *bestValue + pieceValue[WhitePawn];
                }
                value = -Ab(depth - 1, -beta, -alfa, &(mainLine[i]->next));
                if (value >= beta && !stopSearching) {  /* Fail high */
                    PrintSearchInfo(timeUsed, depth, Infinity, mainLine[i]);
                    *bestValue = -Ab(depth - 1, -Infinity, -value,
                                     &(mainLine[i]->next));
                    printDepth = False;
                } else if (value <= alfa && !stopSearching) {   /* Fail low */
                    PrintSearchInfo(timeUsed, depth, -Infinity, mainLine[i]);
                    *bestValue = -Ab(depth - 1, -value, Infinity, &(mainLine[i]->next));
                    printDepth = False;
                } else {        /* Na fail high or low */
                    if (!stopSearching) {
                        *bestValue = value;
                    } else if (depth == 1) {
                        *bestValue = 0; /* Unknown best value */
                    }
                    printDepth = True;
                }
                if (printDepth) {
                    PrintSearchInfo(timeUsed, depth, *bestValue, mainLine[0]);
                } else {
                    PrintSearchInfo(timeUsed, 0, *bestValue, mainLine[0]);
                }
            } else {            /* rest of the moves: zero window */
                value = -Ab(depth - 1, -*bestValue - 1, -*bestValue,
                            &(mainLine[i]->next));
                if (value > *bestValue && !stopSearching) {     /* Fail high */
                    PrintSearchInfo(timeUsed, 0, Infinity, mainLine[i]);
                    *bestValue = -Ab(depth - 1, -Infinity, -value,
                                     &(mainLine[i]->next));
                    tempMove = moveList[i];
                    tempPath = mainLine[i];
                    for (j = i; j > 0; j--) {
                        moveList[j] = moveList[j - 1];
                        mainLine[j] = mainLine[j - 1];
                    }
                    moveList[0] = tempMove;
                    mainLine[0] = tempPath;
                    PrintSearchInfo(timeUsed, 0, *bestValue, mainLine[0]);
                }               /* if fail high */
            }                   /* rest of the moves */
            UndoMove();
            if (stopSearching) {
                break;
            }
            if (*bestValue == Mate - depth) {   /* Shortest mate found */
                printf("--> Shortest mate found, stop searching\n");
                stopSearching = True;
                break;
            }
        }                       /* for move */
        StopTime(timeUsed);
        printf("====================[ %.2f ]====================\n", timeUsed);
        if (!IsCaptureMove(moveList[0].type)) {
            historyTable[toMove][moveList[0].from][moveList[0].to] +=
                1 << depth;
        }
        if (*bestValue <= -MateValue) { /* Best value loses */
            printf("--> Best value loses, stop searching\n");
            depth++;
            break;
        }
        if (stopSearching) {
            depth++;
            break;
        }
    }                           /* for depth */
    *move = moveList[0];
    FreeMoveList(moveList);
    for (i = 0; i < MaxMoves; i++) {
        FreePath(mainLine[i]);
    }
    nrTotalNodes -= nrExtraNodes;       /* When using BigAll */
    printf("%lu nodes (int:%lu, leaf:%lu, quies:%lu), %lu n/s\n",
           nrTotalNodes, nrInternalNodes, nrLeafNodes, nrQuiesNodes,
           (nrTotalNodes == 0 || timeUsed == 0) ? 0 :
           (Unsigned4) (nrTotalNodes / timeUsed));
    if (useTransTable) {
        PutMoveInTransTable(*move, depth - 1, *bestValue, Valid,
                            nrTotalNodes + nrExtraNodes);
        printf("%lu filled (%5.2f%%), %lu reads, %lu hits (%5.2f%%) %lu writes\n",
        NrFilled(), PercFilled(), nrReads, nrHits, nrHits * 100.0 / nrReads,
               nrWrites);
        printf("%lu collisions, %lu expected\n", nrCollisions,
               ExpectedCollisions(NrFilled() + nrCollisions));
        if (nrIllegalMoves != 0) {
            printf("ERROR: %d illegal moves\n", nrIllegalMoves);
        }
    }
    printf("%lu moves in %lu times (%5.2f)\n", nrMovesGenerated, nrGenerates,
           nrMovesGenerated * 1.0 / nrGenerates);
}                               /* Search */


/*----------------------------------------------------------------------
 | Ab								940502
 |
 | This is the recursive alpha-beta search procedure.
 +----------------------------------------------------------------------*/
static          ValueType
                Ab(Signed1 depth, ValueType alpha, ValueType beta,
                                   PathType ** bestPath)
{
    Unsigned1       nrMoves;
    MoveType       *moveList,
                    ttMove={0};
    ValueType       value,
                    bestValue,
                    ttValue={0};
    Signed2         i;
    PathType       *tempPath;
    Boolean         betterMoveFound,
                    firstMove;
    MoveType        bestMove,
                    pathMove;
    Signed1         ttDepth={0};
    Unsigned1       flag={0};
    char            s[MaxMoveLength + 1]={0};
    ValueType       maxAlpha;
    Unsigned4       ttNodes={0},
                    startNodes;

    maxAlpha = alpha;
    if (nrGamePlies - startPly <= debugDepth) {
        PrintGame(startPly, nrGamePlies - 1);
        printf("%lu (%ld, %ld), (%x, %x)\n", nrTotalNodes, alpha, beta,
               hashValue[nrGamePlies][0], hashValue[nrGamePlies][1]);
    }
    startNodes = nrTotalNodes;
    /* Repetition of position or 50 move rule? */
    if (ItIsADraw()) {
        ++nrLeafNodes;
        if (++nrTotalNodes - nrExtraNodes >= testNrNodes && testNrNodes != -1) {
            stopSearching = True;
        }
        return (Draw);
    }
    GetMoveFromTransTable(ttMove, ttDepth, ttValue, flag, ttNodes);
    if (ttDepth != -1 && nrGamePlies - startPly <= debugDepth) {
        char            sss[10];
        SPrintMove(sss, ttMove);
        printf("From table: %s (val:%d, depth:%d, flag:%d)\n",
               sss, ttValue, ttDepth, flag);
    }
    if (ttDepth != -1 && IsIllegal(ttMove)) {
        SPrintMove(s, ttMove);
        printf("Illegal move %s\n", s);
        ttDepth = -1;
        nrIllegalMoves++;
    }
    /* Use ttValue */
    if (useTtValue && ttDepth >= depth) {
        if (keepMethod == BigAll) {
            nrTotalNodes += ttNodes;
            nrExtraNodes += ttNodes;
        }
        if (flag == Valid) {
            ++nrLeafNodes;
            if (++nrTotalNodes - nrExtraNodes >= testNrNodes && testNrNodes != -1) {
                stopSearching = True;
            }
            FreePath(*bestPath);
            AllocatePathMove(*bestPath);
            SPrintMove((*bestPath)->moveString, ttMove);
            (*bestPath)->move = ttMove;
            if (nrGamePlies - startPly <= debugDepth) {
                printf("TT (valid) cut-off\n");
            }
            return (ttValue);
        } else if (flag == LowerBound) {
            if (ttValue > maxAlpha) {
                maxAlpha = ttValue;
            }
        } else {                /* flag == UpperBound */
            if (beta > ttValue) {
                beta = ttValue;
            }
        }
        if (maxAlpha >= beta) {
            ++nrLeafNodes;
            if (++nrTotalNodes - nrExtraNodes >= testNrNodes && testNrNodes != -1) {
                stopSearching = True;
            }
            FreePath(*bestPath);
            AllocatePathMove(*bestPath);
            SPrintMove((*bestPath)->moveString, ttMove);
            (*bestPath)->move = ttMove;
            if (nrGamePlies - startPly <= debugDepth) {
                printf("TT cut-off\n");
            }
            return (ttValue);
        }
    }                           /* if ttDepth >= depth */
    /* Leaf node */
    if (depth == 0) {
        bestValue = Quiescence(maxAlpha, beta, bestPath, ttDepth, ttValue, flag,
                               ttNodes);
        /* Add '.' to show where quiescence starts */
        if (*bestPath != NULL && (*bestPath)->moveString[0] != '.') {
            for (i = MaxMoveLength - 1; i > 0; i--) {
                (*bestPath)->moveString[i] = (*bestPath)->moveString[i - 1];
            }
            (*bestPath)->moveString[0] = '.';
            (*bestPath)->moveString[MaxMoveLength - 1] = '\0';
        }
        return (bestValue);
    }
    firstMove = True;
    nrMoves = 0;
    ++nrInternalNodes;
    if (++nrTotalNodes - nrExtraNodes >= testNrNodes && testNrNodes != -1) {
        stopSearching = True;
        return (-Infinity);
    }
    /* Try refutation table move first */
    if (useRefTable && *bestPath != NULL) {
        if ((*bestPath)->moveString[0] == '.') {
            /* Remove '.' for it's no longer quiescence search */
            for (i = 0; i < MaxMoveLength - 2; i++) {
                (*bestPath)->moveString[i] = (*bestPath)->moveString[i + 1];
            }
            (*bestPath)->moveString[MaxMoveLength - 2] = ' ';
            (*bestPath)->moveString[MaxMoveLength - 1] = '\0';
        }
        firstMove = False;
        pathMove = (*bestPath)->move;
        DoMove(&pathMove);
        bestValue = -Ab(depth - 1, -beta, -maxAlpha, &((*bestPath)->next));
        UndoMove();
        bestMove = pathMove;
        if (stopSearching) {
            return (-Infinity);
        }
        if (bestValue >= beta) {
            goto BetaCutOff;
        }
        if (bestValue > maxAlpha) {
            maxAlpha = bestValue;
        }
    } else {
        pathMove.from = 0;      /* no refutation table move */
        FreePath(*bestPath);
        *bestPath = NULL;
    }

    /* Try transposition table move */
    if (useTtMove && ttDepth >= 0 && !EqualMoves(&ttMove, &pathMove)) {
        if (!firstMove) {       /* Refutation move already examined */
            tempPath = NULL;
            DoMove(&ttMove);
            value = -Ab(depth - 1, -maxAlpha - 1, -maxAlpha, &tempPath);
            if (value > bestValue && !stopSearching) {  /* fail high */
                betterMoveFound = True;
                FreePath((*bestPath)->next);
                (*bestPath)->next = tempPath;
                if (value < beta && depth > 0) {        /* re-search */
                    bestValue = -Ab(depth - 1, -Infinity, -value, &((*bestPath)->next));
                } else {
                    bestValue = value;
                }
            } else {
                betterMoveFound = False;
            }
            UndoMove();
            if (betterMoveFound) {
                SPrintMove((*bestPath)->moveString, ttMove);
                (*bestPath)->move = ttMove;
                bestMove = ttMove;
                if (bestValue >= beta) {
                    goto BetaCutOff;
                }
                if (bestValue > maxAlpha) {
                    maxAlpha = bestValue;
                }
            } else {
                FreePath(tempPath);
            }
            if (stopSearching) {
                return (-Infinity);
            }
        } else {                /* No refutation move, so *bestPath equals
                                 * NULL */
            firstMove = False;
            AllocatePathMove(*bestPath);
            DoMove(&ttMove);
            bestValue = -Ab(depth - 1, -beta, -maxAlpha, &((*bestPath)->next));
            UndoMove();
            bestMove = ttMove;
            SPrintMove((*bestPath)->moveString, ttMove);
            (*bestPath)->move = ttMove;
            if (stopSearching) {
                return (-Infinity);
            }
            if (bestValue >= beta) {
                goto BetaCutOff;
            }
            if (bestValue > maxAlpha) {
                maxAlpha = bestValue;
            }
        }
    } else {
        ttMove.from = 0;        /* no transposition table move */
    }

    /* Rest of the moves */
    GenerateMoves(&moveList, &nrMoves);
    if (nrMoves == 0) {
        ++nrLeafNodes;
        --nrInternalNodes;
        if (Attacked(kingSquare[toMove], (SquareType) ! toMove)) {
            return (-Mate + (nrGamePlies - startPly));
        } else {
            return (Draw);      /* Stalemate */
        }
    }
    /* !!! Check evasion: "if (nrCheck) ++depth;" !!! */

    /* Construct heap */
    for (i = nrMoves / 2 - 1; i > 0; i--) {
        SiftDown(moveList, (Unsigned1) i, (Unsigned1) (nrMoves - 1));
    }
    for (i = nrMoves - 1; i >= 0; i--) {
        if (i != 0) {           /* Put best move above in list */
            SiftDown(moveList, (Unsigned1) 0, (Unsigned1) i);
        }
        /* Refutation or transposition table move already examined */
        if (EqualMoves(&(moveList[0]), &pathMove) ||
            EqualMoves(&(moveList[0]), &ttMove)) {
            goto Next;
        }
        betterMoveFound = False;
        DoMove(&(moveList[0]));
        if (firstMove) {
            AllocatePathMove(*bestPath);
            bestValue = -Ab(depth - 1, -beta, -maxAlpha, &((*bestPath)->next));
            betterMoveFound = True;
            firstMove = False;
        } else {                /* Not the first move */
            tempPath = NULL;
            value = -Ab(depth - 1, -maxAlpha - 1, -maxAlpha, &tempPath);
            if (value > bestValue && !stopSearching) {  /* fail high */
                FreePath((*bestPath)->next);
                (*bestPath)->next = tempPath;
                betterMoveFound = True;
                if (value < beta && depth > 0) {        /* re-search */
                    bestValue = -Ab(depth - 1, -Infinity, -value, &((*bestPath)->next));
                } else {
                    bestValue = value;
                }
            }
        }
        UndoMove();

        if (stopSearching) {
            FreeMoveList(moveList);
            FreePath(tempPath);
            return (-Infinity);
        }
        if (betterMoveFound) {
            SPrintMove((*bestPath)->moveString, moveList[0]);
            (*bestPath)->move = moveList[0];
            bestMove = moveList[0];
            if (bestValue >= beta) {
                goto BetaCutOff;
            }
            if (bestValue > maxAlpha) {
                maxAlpha = bestValue;
            }
        } else {
            /* Druk variant af als diep genoeg en zo */
            FreePath(tempPath);
        }
Next:
        if (i != 0) {
            moveList[0] = moveList[i];
        }
    }                           /* for moves */

BetaCutOff:
    if (nrMoves) {
        FreeMoveList(moveList);
    }
    if (!IsCaptureMove(bestMove.type)) {
        historyTable[toMove][bestMove.from][bestMove.to] += 1 << depth;
    }
    if (bestValue <= alpha) {
        flag = UpperBound;
    } else if (bestValue >= beta) {
        flag = LowerBound;
    } else {
        flag = Valid;
    }
    PutMoveInTransTable(bestMove, depth, bestValue, flag,
                        nrTotalNodes - startNodes);
    if (nrGamePlies - startPly <= debugDepth) {
        char            sss[10];
        SPrintMove(sss, bestMove);
        printf("To table: %s (val:%d, depth:%d, flag:%d)\n",
               sss, bestValue, depth, flag);
    }
    return (bestValue);
}                               /* Ab */


/*----------------------------------------------------------------------
 | FreePath							940506
 |
 | Frees a move path.
 +----------------------------------------------------------------------*/
void            FreePath(PathType * path)
{
    if (path == NULL) {
        return;
    }
    FreePath(path->next);
    free(path);
    nrAllocPathMoves--;
}                               /* FreePath */


static void     PutMoveInFront(MoveType * moveList, Unsigned1 nrMoves,
                                               MoveType * ttMove)
{
    Signed2         i,
                    j;

    for (i = 0; i < nrMoves; i++) {
        if (EqualMoves(&(moveList[i]), ttMove)) {
            for (j = i; j > 0; j--) {
                moveList[j] = moveList[j - 1];
            }
            moveList[0] = *ttMove;
            break;
        }
    }
}                               /* PutMoveInFront */


static double   PercFilled(void)
{
    return (NrFilled() * 100.0 / (useTwoLevelTable ? 1L << (nrTtBits + 1)
                                  : 1L << nrTtBits));
}                               /* PercFilled */


static          Unsigned4
                NrFilled(void)
{
    Unsigned4       i,
                    nr,
                    tot;

    nr = 0;
    tot = useTwoLevelTable ? 1L << (nrTtBits + 1) : 1L << nrTtBits;
    for (i = 0; i < tot; i++) {
        if (GetFlag(&(transTable[i])) != NoEntry) {
            ++nr;
        }
    }
    return (nr);
}                               /* PercFilled */


static          Unsigned4
                ExpectedCollisions(Unsigned4 nodes)
{
    Unsigned4       tot;

    tot = useTwoLevelTable ? 1L << (nrTtBits + 1) : 1L << nrTtBits;
    return ((Unsigned4) (nodes - tot * (1 - exp((double) -1 * nodes / tot))));
}                               /* ExpectedCollisions */
