sort.cpp

超强国际象棋引擎

// sort.cpp

// includes

#include "move_list.h"
#include "check.h"
#include "evasion.h"
#include "move_gen.h"
#include "valid_move.h"
#include "search.h"
#include "see.h"
#include "sort.h"
#include "values.h"

// 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 pos_legal_evasion;
static int pos_see;

static int pos_evasionqs;
static int pos_check_qs;
static int pos_capture_qs;

static int code[256];

static uint16 killer[16][256][2];

static uint16 history[16][768];
static uint16 hist_hit[16][768];
static uint16 hist_tot[16][768];

// prototypes

static void note_quiet_moves(list_t *list, const board_t *board, int thread_id);
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, int thread_id);
static int capture_value(int move, const board_t *board);
static int quiet_move_value(int move, const board_t *board, int thread_id);
static int move_value_simple(int move, const board_t *board);

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

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

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

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

// functions

// sort_init()

void sort_init(int thread_id)
    {

    int i, height;
    int pos;

    // killer

    for ( height = 0; height < 256; height++ )
        {
        for ( i = 0; i < 2; i++ )
            killer[thread_id][height][i] = 0;
        }

    // history

    for ( i = 0; i < 768; i++ )
        history[thread_id][i] = 0;

    for ( i = 0; i < 768; i++ )
        {
        hist_hit[thread_id][i] = 1;
        hist_tot[thread_id][i] = 1;
        }

    // code[]

    for ( pos = 0; pos < 256; pos++ )
        code[pos] = GEN_ERROR;

    pos = 0;

    // main search

    pos_legal_evasion = pos;
    code[pos++] = GEN_LEGAL_EVASION;
    code[pos++] = GEN_END;

    pos_see = 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

    pos_evasionqs = pos;
    code[pos++] = GEN_EVASION_QS;
    code[pos++] = GEN_END;

    pos_check_qs = pos;
    code[pos++] = GEN_CAPTURE_QS;
    code[pos++] = GEN_CHECK_QS;
    code[pos++] = GEN_END;

    pos_capture_qs = pos;
    code[pos++] = GEN_CAPTURE_QS;
    code[pos++] = GEN_END;
    }

// sort_init()

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

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

    sort->depth = depth;
    sort->height = height;
    sort->capture_nb = 0;

    sort->trans_killer = trans_killer;
    sort->killer_1 = killer[thread_id][sort->height][0];
    sort->killer_2 = killer[thread_id][sort->height][1];

    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, thread_id);
        list_sort(sort->list);

        sort->gen = pos_legal_evasion + 1;
        sort->test = TEST_NONE;
        }
    else
        { // not in check

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

    sort->pos = 0;
    }

// sort_next()

int sort_next(sort_t *sort, int thread_id)
    {

    int move;
    int gen;

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

            // next move

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

            // 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)
                {
                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)
                {
                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;
                }
            else if(sort->test == TEST_QUIET)
                {
                if(move == sort->trans_killer)
                    continue;

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

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

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

                sort->value = history_prob(move, sort->board, thread_id);
                }
            else
                {

                return 0;
                }

            return move;
            }

        // next stage

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

        if(false) { }
        else if(gen == GEN_TRANS)
            {

            LIST_CLEAR(sort->list);

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

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

            gen_captures(sort->list, sort->board);
            sort->capture_nb = LIST_SIZE(sort->list);
            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 != 0)
                LIST_ADD(sort->list, sort->killer_1);

            if(sort->killer_2 != 0)
                LIST_ADD(sort->list, sort->killer_2);

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

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

            sort->test = TEST_QUIET;
            }
        else
            {
            return 0;
            }

        sort->pos = 0;
        }
    }

// sort_init_qs()

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

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

    if(ATTACK_IN_CHECK(sort->attack))
        {
        sort->gen = pos_evasionqs;
        }
    else if(check)
        {
        sort->gen = pos_check_qs;
        }
    else
        {
        sort->gen = pos_capture_qs;
        }

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

// sort_next_qs()

int sort_next_qs(sort_t *sort)
    {

    int move;
    int gen;

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

            // next move

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

            // test

            if(false) { }
            else if(sort->test == TEST_LEGAL)
                {
                if(!pseudo_is_legal(move, sort->board))
                    continue;
                }
            else if(sort->test == TEST_CAPTURE_QS)
                {
                if(!capture_is_good(move, sort->board))
                    continue;

                if(!pseudo_is_legal(move, sort->board))
                    continue;
                }
            else if(sort->test == TEST_CHECK_QS)
                {