
// sort.cpp

// includes

#include "attack.h"
#include "board.h"
#include "colour.h"
#include "list.h"
#include "move.h"
#include "move_check.h"
#include "move_evasion.h"
#include "move_gen.h"
#include "move_legal.h"
#include "piece.h"
#include "search.h"
#include "see.h"
#include "sort.h"
#include "util.h"
#include "value.h"

// constants

static const int KillerNb = 2;

static const int HistorySize = 12 * 64;
static const int HistoryMax = 16384;

static const int TransScore   = +32766;
static const int GoodScore    =  +4000;
static const int KillerScore  =     +4;
static const int HistoryScore = -24000;
static const int BadScore     = -28000;

static const int CODE_SIZE = 256;

// macros

#define HISTORY_INC(depth) ((depth)*(depth))

// types

enum gen_t {
    GEN_ERROR,
    GEN_LEGAL_EVASION,
    GEN_TRANS,
    GEN_GOOD_CAPTURE,
    GEN_BAD_CAPTURE,
    GEN_KILLER,
    GEN_QUIET,
    GEN_EVASION_QS,
    GEN_CAPTURE_QS,
    GEN_CHECK_QS,
    GEN_END
};

enum test_t {
    TEST_ERROR,
    TEST_NONE,
    TEST_LEGAL,
    TEST_TRANS_KILLER,
    TEST_GOOD_CAPTURE,
    TEST_BAD_CAPTURE,
    TEST_KILLER,
    TEST_QUIET,
    TEST_CAPTURE_QS,
    TEST_CHECK_QS
};

// variables

static int PosLegalEvasion;
static int PosSEE;

static int PosEvasionQS;
static int PosCheckQS;
static int PosCaptureQS;

static int Code[CODE_SIZE];

static uint16 Killer[HeightMax][KillerNb];

static fail_high_stats_t FailHighStats[HistorySize];
static uint16 History[HistorySize];
static uint16 HistHit[HistorySize];
static uint16 HistTot[HistorySize];

// prototypes

static void note_captures     (list_t * list, const board_t * board);
static void note_quiet_moves  (list_t * list, const board_t * board);
static void note_moves_simple (list_t * list, const board_t * board);
static void note_mvv_lva      (list_t * list, const board_t * board);

static int  move_value        (int move, const board_t * board, int height, int trans_killer);
static int  capture_value     (int move, const board_t * board);
static int  quiet_move_value  (int move, const board_t * board);
static int  move_value_simple (int move, const board_t * board);

static int  history_prob      (int move, const board_t * board);

static bool capture_is_good   (int move, const board_t * board);

static int  mvv_lva           (int move, const board_t * board);

static int  history_index     (int move, const board_t * board);

// functions

// sort_init()

void sort_init() {

    int i, height;
    int pos;

    // killer

    for (height = 0; height < HeightMax; height++) {
        for (i = 0; i < KillerNb; i++) Killer[height][i] = MoveNone;
    }

    // history

    for (i = 0; i < HistorySize; i++) History[i] = 0;

    for (i = 0; i < HistorySize; i++) {
        HistHit[i] = 1;
        HistTot[i] = 1;
        FailHighStats[i].success = 1;
        FailHighStats[i].tried = 1;
    }

    // Code[]

    for (pos = 0; pos < CODE_SIZE; pos++) Code[pos] = GEN_ERROR;

    pos = 0;

    // main search

    PosLegalEvasion = pos;
    Code[pos++] = GEN_LEGAL_EVASION;
    Code[pos++] = GEN_END;

    PosSEE = pos;
    Code[pos++] = GEN_TRANS;
    Code[pos++] = GEN_GOOD_CAPTURE;
    Code[pos++] = GEN_KILLER;
    Code[pos++] = GEN_QUIET;
    Code[pos++] = GEN_BAD_CAPTURE;
    Code[pos++] = GEN_END;

    // quiescence search

    PosEvasionQS = pos;
    Code[pos++] = GEN_EVASION_QS;
    Code[pos++] = GEN_END;

    PosCheckQS = pos;
    Code[pos++] = GEN_CAPTURE_QS;
    Code[pos++] = GEN_CHECK_QS;
    Code[pos++] = GEN_END;

    PosCaptureQS = pos;
    Code[pos++] = GEN_CAPTURE_QS;
    Code[pos++] = GEN_END;

    ASSERT(pos<CODE_SIZE);
}

// sort_init()

void sort_init(sort_t * sort, board_t * board, const attack_t * attack, int depth, int height, int trans_killer) {

    ASSERT(sort!=NULL);
    ASSERT(board!=NULL);
    ASSERT(attack!=NULL);
    ASSERT(depth_is_ok(depth));
    ASSERT(height_is_ok(height));
    ASSERT(trans_killer==MoveNone||move_is_ok(trans_killer));

    sort->board = board;
    sort->attack = attack;

    sort->depth = depth;
    sort->height = height;

    sort->trans_killer = trans_killer;
    sort->killer_1 = Killer[sort->height][0];
    sort->killer_2 = Killer[sort->height][1];
    if (sort->height > 2) {
        sort->killer_3 = Killer[sort->height-2][0];
        sort->killer_4 = Killer[sort->height-2][1];
    }
    else {
        sort->killer_3 = MoveNone;
        sort->killer_4 = MoveNone;
    }

    if (ATTACK_IN_CHECK(sort->attack)) {

        gen_legal_evasions(sort->list,sort->board,sort->attack);
        note_moves(sort->list,sort->board,sort->height,sort->trans_killer);
        list_sort(sort->list);

        sort->gen = PosLegalEvasion + 1;
        sort->test = TEST_NONE;

    } else { // not in check

        LIST_CLEAR(sort->list);
        sort->gen = PosSEE;
    }

    sort->pos = 0;
}

// sort_next()

int sort_next(sort_t * sort) {

    int move;
    int gen;

    ASSERT(sort!=NULL);

    while (true) {

        while (sort->pos < LIST_SIZE(sort->list)) {

            // next move

            move = LIST_MOVE(sort->list,sort->pos);
            sort->value = 16384; // default score
            sort->pos++;

            ASSERT(move!=MoveNone);

            // test

            if (false) {

            } else if (sort->test == TEST_NONE) {

                // no-op

            } else if (sort->test == TEST_TRANS_KILLER) {

                if (!move_is_pseudo(move,sort->board)) continue;
                if (!pseudo_is_legal(move,sort->board)) continue;

            } else if (sort->test == TEST_GOOD_CAPTURE) {

                ASSERT(move_is_tactical(move,sort->board));

                if (move == sort->trans_killer) continue;

                if (!capture_is_good(move,sort->board)) {
                    LIST_ADD(sort->bad,move);
                    continue;
                }

                if (!pseudo_is_legal(move,sort->board)) continue;

            } else if (sort->test == TEST_BAD_CAPTURE) {

                ASSERT(move_is_tactical(move,sort->board));
                ASSERT(!capture_is_good(move,sort->board));

                ASSERT(move!=sort->trans_killer);
                if (!pseudo_is_legal(move,sort->board)) continue;

            } else if (sort->test == TEST_KILLER) {

                if (move == sort->trans_killer) continue;
                if (!quiet_is_pseudo(move,sort->board)) continue;
                if (!pseudo_is_legal(move,sort->board)) continue;

                ASSERT(!move_is_tactical(move,sort->board));

            } else if (sort->test == TEST_QUIET) {

                ASSERT(!move_is_tactical(move,sort->board));

                if (move == sort->trans_killer) continue;
                if (move == sort->killer_1) continue;
                if (move == sort->killer_2) continue;
                if (move == sort->killer_3) continue;
                if (move == sort->killer_4) continue;
                if (!pseudo_is_legal(move,sort->board)) continue;

                sort->value = history_prob(move,sort->board);

            } else {

                ASSERT(false);

                return MoveNone;
            }

            ASSERT(pseudo_is_legal(move,sort->board));

            return move;
        }

        // next stage

        gen = Code[sort->gen++];

        if (false) {

        } else if (gen == GEN_TRANS) {

            LIST_CLEAR(sort->list);
            if (sort->trans_killer != MoveNone) LIST_ADD(sort->list,sort->trans_killer);

            sort->test = TEST_TRANS_KILLER;

        } else if (gen == GEN_GOOD_CAPTURE) {

            gen_captures(sort->list,sort->board);
            note_mvv_lva(sort->list,sort->board);
            list_sort(sort->list);

            LIST_CLEAR(sort->bad);

            sort->test = TEST_GOOD_CAPTURE;

        } else if (gen == GEN_BAD_CAPTURE) {

            list_copy(sort->list,sort->bad);

            sort->test = TEST_BAD_CAPTURE;

        } else if (gen == GEN_KILLER) {

            LIST_CLEAR(sort->list);
            if (sort->killer_1 != MoveNone) LIST_ADD(sort->list,sort->killer_1);
            if (sort->killer_2 != MoveNone) LIST_ADD(sort->list,sort->killer_2);
            if (sort->killer_3 != MoveNone) LIST_ADD(sort->list,sort->killer_3);
            if (sort->killer_4 != MoveNone) LIST_ADD(sort->list,sort->killer_4);

            sort->test = TEST_KILLER;

        } else if (gen == GEN_QUIET) {

            gen_quiet_moves(sort->list,sort->board);
            note_quiet_moves(sort->list,sort->board);
            list_sort(sort->list);

            sort->test = TEST_QUIET;

        } else {

            ASSERT(gen==GEN_END);

            return MoveNone;
        }

        sort->pos = 0;
    }
}

// sort_init_qs()

void sort_init_qs(sort_t * sort, board_t * board, const attack_t * attack, bool check) {

    ASSERT(sort!=NULL);
    ASSERT(board!=NULL);
    ASSERT(attack!=NULL);
    ASSERT(check==true||check==false);

    sort->board = board;
    sort->attack = attack;

    if (ATTACK_IN_CHECK(sort->attack)) {
        sort->gen = PosEvasionQS;
    } else if (check) {
        sort->gen = PosCheckQS;
    } else {
        sort->gen = PosCaptureQS;
    }

    LIST_CLEAR(sort->list);
    sort->pos = 0;
}

// sort_next_qs()

int sort_next_qs(sort_t * sort) {

    int move;
    int gen;

    ASSERT(sort!=NULL);

    while (true) {

        while (sort->pos < LIST_SIZE(sort->list)) {

            // next move

            move = LIST_MOVE(sort->list,sort->pos);
            sort->pos++;

            ASSERT(move!=MoveNone);

            // test

            if (false) {

            } else if (sort->test == TEST_LEGAL) {

                if (!pseudo_is_legal(move,sort->board)) continue;

            } else if (sort->test == TEST_CAPTURE_QS) {

                ASSERT(move_is_tactical(move,sort->board));

                if (!capture_is_good(move,sort->board)) continue;
                if (!pseudo_is_legal(move,sort->board)) continue;

            } else if (sort->test == TEST_CHECK_QS) {

                ASSERT(!move_is_tactical(move,sort->board));
                ASSERT(move_is_check(move,sort->board));

                if (see_move(move,sort->board) < 0) continue;
                if (!pseudo_is_legal(move,sort->board)) continue;

            } else {

                ASSERT(false);

                return MoveNone;
            }

            ASSERT(pseudo_is_legal(move,sort->board));

            return move;
        }

        // next stage

        gen = Code[sort->gen++];

        if (false) {

        } else if (gen == GEN_EVASION_QS) {

            gen_pseudo_evasions(sort->list,sort->board,sort->attack);
            note_moves_simple(sort->list,sort->board);
            list_sort(sort->list);

            sort->test = TEST_LEGAL;

        } else if (gen == GEN_CAPTURE_QS) {

            gen_captures(sort->list,sort->board);
            note_mvv_lva(sort->list,sort->board);
            list_sort(sort->list);

            sort->test = TEST_CAPTURE_QS;

        } else if (gen == GEN_CHECK_QS) {

            gen_quiet_checks(sort->list,sort->board);

            sort->test = TEST_CHECK_QS;

        } else {

            ASSERT(gen==GEN_END);

            return MoveNone;
        }

        sort->pos = 0;
    }
}

// good_move()

void good_move(int move, const board_t * board, int depth, int height) {

    int index;
    int i;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);
    ASSERT(depth_is_ok(depth));
    ASSERT(height_is_ok(height));


    if (move_is_tactical(move,board)) return;

    // killer

    if (Killer[height][0] != move) {
        Killer[height][1] = Killer[height][0];
        Killer[height][0] = move;
    }

    ASSERT(Killer[height][0]==move);
    ASSERT(Killer[height][1]!=move);

    // history

    index = history_index(move,board);

    History[index] += HISTORY_INC(depth);

    if (History[index] >= HistoryMax) {
        for (i = 0; i < HistorySize; i++) {
            History[i] = (History[i] + 1) / 2;
        }
    }
}

// history_good()

void history_good(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    if (move_is_tactical(move,board)) return;

    // history

    index = history_index(move,board);

    HistHit[index]++;
    HistTot[index]++;

    if (HistTot[index] >= HistoryMax) {
        HistHit[index] = (HistHit[index] + 1) / 2;
        HistTot[index] = (HistTot[index] + 1) / 2;
    }

    ASSERT(HistHit[index]<=HistTot[index]);
    ASSERT(HistTot[index]<HistoryMax);
}

// history_bad()

void history_bad(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    if (move_is_tactical(move,board)) return;

    // history

    index = history_index(move,board);

    HistTot[index]++;

    if (HistTot[index] >= HistoryMax) {
        HistHit[index] = (HistHit[index] + 1) / 2;
        HistTot[index] = (HistTot[index] + 1) / 2;
    }

    ASSERT(HistHit[index]<=HistTot[index]);
    ASSERT(HistTot[index]<HistoryMax);
}

// history_very_bad()

void history_very_bad(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    //if (move_is_tactical(move,board)) return;

    // history

    index = PIECE_TO_12(board->square[MOVE_TO(move)]) * 64 + SQUARE_TO_64(MOVE_TO(move));

    HistTot[index] += 100;

    if (HistTot[index] >= HistoryMax) {
        HistHit[index] = (HistHit[index] + 1) / 2;
        HistTot[index] = (HistTot[index] + 1) / 2;
    }

    ASSERT(HistHit[index]<=HistTot[index]);
    ASSERT(HistTot[index]<HistoryMax);
}

// history_tried()

void history_tried(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    if (move_is_tactical(move,board)) return;

    // history

    index = history_index(move,board);

    FailHighStats[index].tried++;
}

// history_success()

void history_success(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    if (move_is_tactical(move,board)) return;

    // history

    index = history_index(move,board);

    FailHighStats[index].success++;
}

bool history_reduction(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    // history

    index = history_index(move,board);

    if(FailHighStats[index].success > FailHighStats[index].tried / 8)
        return false;
    return true;
}

// note_moves()

void note_moves(list_t * list, const board_t * board, int height, int trans_killer) {

    int size;
    int i, move;

    ASSERT(list_is_ok(list));
    ASSERT(board!=NULL);
    ASSERT(height_is_ok(height));
    ASSERT(trans_killer==MoveNone||move_is_ok(trans_killer));

    size = LIST_SIZE(list);

    if (size >= 2) {
        for (i = 0; i < size; i++) {
            move = LIST_MOVE(list,i);
            list->value[i] = move_value(move,board,height,trans_killer);
        }
    }
}

// note_captures()

static void note_captures(list_t * list, const board_t * board) {

    int size;
    int i, move;

    ASSERT(list_is_ok(list));
    ASSERT(board!=NULL);

    size = LIST_SIZE(list);

    if (size >= 2) {
        for (i = 0; i < size; i++) {
            move = LIST_MOVE(list,i);
            list->value[i] = capture_value(move,board);
        }
    }
}

// note_quiet_moves()

static void note_quiet_moves(list_t * list, const board_t * board) {

    int size;
    int i, move;

    ASSERT(list_is_ok(list));
    ASSERT(board!=NULL);

    size = LIST_SIZE(list);

    if (size >= 2) {
        for (i = 0; i < size; i++) {
            move = LIST_MOVE(list,i);
            list->value[i] = quiet_move_value(move,board);
        }
    }
}

// note_moves_simple()

static void note_moves_simple(list_t * list, const board_t * board) {

    int size;
    int i, move;

    ASSERT(list_is_ok(list));
    ASSERT(board!=NULL);

    size = LIST_SIZE(list);

    if (size >= 2) {
        for (i = 0; i < size; i++) {
            move = LIST_MOVE(list,i);
            list->value[i] = move_value_simple(move,board);
        }
    }
}

// note_mvv_lva()

static void note_mvv_lva(list_t * list, const board_t * board) {

    int size;
    int i, move;

    ASSERT(list_is_ok(list));
    ASSERT(board!=NULL);

    size = LIST_SIZE(list);

    if (size >= 2) {
        for (i = 0; i < size; i++) {
            move = LIST_MOVE(list,i);
            list->value[i] = mvv_lva(move,board);
        }
    }
}

// move_value()

static int move_value(int move, const board_t * board, int height, int trans_killer) {

    int value;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);
    ASSERT(height_is_ok(height));
    ASSERT(trans_killer==MoveNone||move_is_ok(trans_killer));

    if (false) {
    } else if (move == trans_killer) { // transposition table killer
        value = TransScore;
    } else if (move_is_tactical(move,board)) { // capture or promote
        value = capture_value(move,board);
    } else if (move == Killer[height][0]) { // killer 1
        value = KillerScore;
    } else if (move == Killer[height][1]) { // killer 2
        value = KillerScore - 2;
    } else if (height > 2 && move == Killer[height-2][0]) { // killer 3
        value = KillerScore - 1;
    } else if (height > 2 && move == Killer[height-2][1]) { // killer 4
        value = KillerScore - 3;
    } else { // quiet move
        value = quiet_move_value(move,board);
    }

    return value;
}

// capture_value()

static int capture_value(int move, const board_t * board) {

    int value;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    ASSERT(move_is_tactical(move,board));

    value = mvv_lva(move,board);

    if (capture_is_good(move,board)) {
        value += GoodScore;
    } else {
        value += BadScore;
    }

    ASSERT(value>=-30000&&value<=+30000);

    return value;
}

// quiet_move_value()

static int quiet_move_value(int move, const board_t * board) {

    int value;
    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    ASSERT(!move_is_tactical(move,board));

    index = history_index(move,board);

    value = HistoryScore + History[index];
    ASSERT(value>=HistoryScore&&value<=KillerScore-4);

    return value;
}

// move_value_simple()

static int move_value_simple(int move, const board_t * board) {

    int value;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    value = HistoryScore;
    if (move_is_tactical(move,board)) value = mvv_lva(move,board);

    return value;
}

// history_prob()

static int history_prob(int move, const board_t * board) {

    int value;
    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    ASSERT(!move_is_tactical(move,board));

    index = history_index(move,board);

    ASSERT(HistHit[index]<=HistTot[index]);
    ASSERT(HistTot[index]<HistoryMax);

    value = (HistHit[index] * 16384) / HistTot[index];
    ASSERT(value>=0&&value<=16384);

    return value;
}

// capture_is_good()

static bool capture_is_good(int move, const board_t * board) {

    int piece, capture;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    ASSERT(move_is_tactical(move,board));

    // special cases

    if (MOVE_IS_EN_PASSANT(move)) return true;
    if (move_is_under_promote(move)) return false; // REMOVE ME?

    // captures and queen promotes

    capture = board->square[MOVE_TO(move)];

    if (capture != Empty) {

        // capture

        ASSERT(move_is_capture(move,board));

        if (MOVE_IS_PROMOTE(move)) return true; // promote-capture

        piece = board->square[MOVE_FROM(move)];
        if (VALUE_PIECE(capture) >= VALUE_PIECE(piece)) return true;
    }

    return see_move(move,board) >= 0;
}

// mvv_lva()

static int mvv_lva(int move, const board_t * board) {

    int piece, capture, promote;
    int value;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    ASSERT(move_is_tactical(move,board));

    if (MOVE_IS_EN_PASSANT(move)) { // en-passant capture

        value = 5; // PxP

    } else if ((capture = board->square[MOVE_TO(move)]) != Empty) { // normal capture

        piece = board->square[MOVE_FROM(move)];

        value = PIECE_ORDER(capture) * 6 - PIECE_ORDER(piece) + 5;
        ASSERT(value>=0&&value<30);

    } else { // promote

        ASSERT(MOVE_IS_PROMOTE(move));

        promote = move_promote(move);

        value = PIECE_ORDER(promote) - 5;
        ASSERT(value>=-4&&value<0);
    }

    ASSERT(value>=-4&&value<+30);

    return value;
}

// history_index()

static int history_index(int move, const board_t * board) {

    int index;

    ASSERT(move_is_ok(move));
    ASSERT(board!=NULL);

    ASSERT(!move_is_tactical(move,board));

    index = PIECE_TO_12(board->square[MOVE_FROM(move)]) * 64 + SQUARE_TO_64(MOVE_TO(move));

    ASSERT(index>=0&&index<HistorySize);

    return index;
}

// end of sort.cpp

