see.cpp

超强国际象棋引擎

// see.cpp

// includes

#include "attack.h"
#include "move.h"
#include "see.h"
#include "values.h"

// macros

#define ALIST_CLEAR(alist) ((alist)->size=0)

// types

struct alist_t
    {
    int size;
    int square[15];
    };

struct alists_t
    {
    alist_t alist[2][1];
    };

// prototypes

static int see_rec(alists_t *alists, const board_t *board, int color, int to, int piece_value);

static void alist_build(alist_t *alist, const board_t *board, int to, int color);
static void alists_hidden(alists_t *alists, const board_t *board, int from, int to);

static void alist_add(alist_t *alist, int square, const board_t *board);
static void alist_remove(alist_t *alist, int pos);
static int alist_pop(alist_t *alist, const board_t *board);

// functions

// see_move()

int see_move(int move, const board_t *board)
    {

    int att, def;
    int from, to;
    alists_t alists[1];
    int value, piece_value;
    int piece, capture;
    alist_t *alist;
    int pos;

    // init

    from = MOVE_FROM(move);
    to = MOVE_TO(move);

    // move the piece

    piece_value = 0;
    piece = board->square[from];

    att = PIECE_COLOUR(piece);
    def = COLOUR_OPP(att);

    // promote

    if(MOVE_IS_PROMOTE(move))
        {
        piece = move_promote(move);
        }

    piece_value += VALUE_PIECE(piece);

    // clear attacker lists

    ALIST_CLEAR(alists->alist[1]);
    ALIST_CLEAR(alists->alist[0]);

    // find hidden attackers

    alists_hidden(alists, board, from, to);

    // capture the piece

    value = 0;

    capture = board->square[to];

    if(capture != 0)
        {
        value += VALUE_PIECE(capture);
        }

    // promote

    if(MOVE_IS_PROMOTE(move))
        {
        value += VALUE_PIECE(piece) - 100;
        }

    // en-passant

    if(MOVE_IS_EN_PASSANT(move))
        {
        value += 100;
        alists_hidden(alists, board, SQUARE_EP_DUAL(to), to);
        }

    // build defender list

    alist = alists->alist[def];

    alist_build(alist, board, to, def);

    if(alist->size == 0)
        return value; // no defender => stop SEE

    // build attacker list

    alist = alists->alist[att];

    alist_build(alist, board, to, att);

    // remove the moved piece (if it's an attacker)

    for ( pos = 0; pos < alist->size && alist->square[pos] != from; pos++ )
    ;

    if(pos < alist->size)
        alist_remove(alist, pos);

    // SEE search

    value -= see_rec(alists, board, def, to, piece_value);

    return value;
    }

// see_square()

int see_square(const board_t *board, int to, int color)
    {

    int att, def;
    alists_t alists[1];
    alist_t *alist;
    int piece_value;
    int piece;

    // build attacker list

    att = color;
    alist = alists->alist[att];

    ALIST_CLEAR(alist);
    alist_build(alist, board, to, att);

    if(alist->size == 0)
        return 0; // no attacker => stop SEE

    // build defender list

    def = COLOUR_OPP(att);
    alist = alists->alist[def];

    ALIST_CLEAR(alist);
    alist_build(alist, board, to, def);

    // captured piece

    piece = board->square[to];

    piece_value = VALUE_PIECE(piece);

    // SEE search

    return see_rec(alists, board, att, to, piece_value);
    }

// see_rec()

static int see_rec(alists_t *alists, const board_t *board, int color, int to, int piece_value)
    {

    int from, piece;
    int value;

    // find the least valuable attacker

    from = alist_pop(alists->alist[color], board);

    if(from == 0)
        return 0; // no more attackers

    // find hidden attackers

    alists_hidden(alists, board, from, to);

    // calculate the capture value

    value = +piece_value; // captured piece

    if(value == 10000)
        return value;     // do not allow an answer to a king capture

    piece = board->square[from];
    piece_value = VALUE_PIECE(piece);

    // promote

    if(piece_value == 100 && SQUARE_IS_PROMOTE(to))
        {
        piece_value = 1000;
        value += 1000 - 100;
        }

    value -= see_rec(alists, board, COLOUR_OPP(color), to, piece_value);

    if(value < 0)
        value = 0;

    return value;
    }

// alist_build()

static void alist_build(alist_t *alist, const board_t *board, int to, int color)
    {

    const sq_t *ptr;
    int from;
    int piece;
    int delta;
    int inc;
    int sq;
    int pawn;

    // piece attacks

    for ( ptr = &board->piece[color][0]; (from = *ptr) != 0; ptr++ )
        {

        piece = board->square[from];
        delta = to - from;

        if(PSEUDO_ATTACK(piece, delta))
            {

            inc = DELTA_INC_ALL(delta);
            sq = from;

            do
                {
                sq += inc;

                if(sq == to)
                    { // attack
                    alist_add(alist, from, board);
                    break;
                    }
                } while (board->square[sq] == 0);
            }
        }

    // pawn attacks

    inc = PAWN_MOVE_INC(color);
    pawn = PAWN_MAKE(color);

    from = to - (inc - 1);

    if(board->square[from] == pawn)
        alist_add(alist, from, board);

    from = to - (inc + 1);

    if(board->square[from] == pawn)
        alist_add(alist, from, board);
    }

// alists_hidden()

static void alists_hidden(alists_t *alists, const board_t *board, int from, int to)
    {

    int inc;
    int sq, piece;

    inc = DELTA_INC_LINE(to - from);

    if(inc != 0)
        { // line

        sq = from;
        do sq -= inc;

        while((piece = board->square[sq]) == 0);

        if(SLIDER_ATTACK(piece, inc))
            {
            alist_add(alists->alist[PIECE_COLOUR(piece)], sq, board);
            }
        }
    }

// alist_add()

static void alist_add(alist_t *alist, int square, const board_t *board)
    {

    int piece;
    int size, pos;

    // insert in MV order

    piece = board->square[square];
    size = ++alist->size;

    for ( pos = size - 1; pos > 0 && piece > board->square[alist->square[pos - 1]]; pos-- )
        {
        alist->square[pos] = alist->square[pos - 1];
        }

    alist->square[pos] = square;
    }

// alist_remove()

static void alist_remove(alist_t *alist, int pos)
    {

    int size, i;

    size = alist->size--;

    for ( i = pos; i < size - 1; i++ )
        {
        alist->square[i] = alist->square[i + 1];
        }
    }

// alist_pop()

static int alist_pop(alist_t *alist, const board_t *board)
    {

    int sq;
    int size;

    sq = 0;
    size = alist->size;

    if(size != 0)
        {
        size--;
        sq = alist->square[size];
        alist->size = size;
        }

    return sq;
    }

// end of see.cpp