movesort.cpp

/*
 * The MIT License (MIT)
 *
 * Copyright (c) 2016 Dan Ravensloft <dan.ravensloft@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

#include <stdlib.h>

#include "board.h"
#include "functions.h"

static inline int CompareMoves(const void * p1, const void * p2)
{
    if (((struct Move*)p1)->score >  ((struct Move *)p2)->score) return -1;
    if (((struct Move*)p1)->score == ((struct Move *)p2)->score) return 0;
    if (((struct Move*)p1)->score <  ((struct Move *)p2)->score) return +1;
}

void InitSort(struct Board * b, struct Sort * s, struct Move ttm)
{
    //s->movecount = GenerateCaptures(b, s->m, 0);
    //s->movecount = GenerateQuiets(b, s->m, s->movecount);

    /*if (ttm.from != ttm.dest) {
        for (s->i = 0; s->i < s->movecount; s->i++) {
            if (s->m[s->i].from == ttm.from &&
                s->m[s->i].dest == ttm.dest &&
                s->m[s->i].type == ttm.type) {
                s->m[s->i].score = 4000;
                break;
            }
        }
    }*/

    //qsort(s->m, s->movecount, sizeof(struct Move), CompareMoves);

    s->i = 0;
    s->quies = false;
    s->phase = 0;
}

void InitSortQuies(struct Board * b, struct Sort * s)
{
    //s->movecount = GenerateCaptures(b, s->m, 0);

    //qsort(s->m, s->movecount, sizeof(struct Move), CompareMoves);

    s->i = 0;
    s->quies = true;
    s->phase = 1;
    s->badcap_count = 0;
}

int NextMove(struct Board * b, struct Sort * s, struct Move * m)
{
    if (s->quies && s->phase > 2)
        return 0;

    switch (s->phase) {
    // TT Move.
    case 0:
        s->phase = 1;
        if (s->ttm.from != s->ttm.dest) {
            *m = s->ttm;
            return 1;
        }

    // Generate captures.
    case 1:
        s->movecount = GenerateCaptures(b, s->m, 0);
        s->i = 0;
        qsort(s->m, s->movecount, sizeof(struct Move), CompareMoves);

        s->badcap_count = 0;
        s->phase = 2;

    // Captures (winning/equal).
    case 2:
        while (s->i < s->movecount) {
            *m = s->m[s->i];
            s->i++;

            if (BadCapture(b, s->m[s->i])) {
                // In QS, skip losing captures. Otherwise, store them for later.
                if (s->quies)
                    continue;
                else {
                    s->badcap[s->badcap_count] = s->m[s->i];
                    s->badcap_count++;
                    continue;
                }
            }

            return 1;
        }

        s->phase = 4;
    // TODO: killers.

    // Generate quiet moves.
    case 3:
        s->movecount = GenerateQuiets(b, s->m, 0);

        s->i = 0;
        qsort(s->m, s->movecount, sizeof(struct Move), CompareMoves);

    // Quiet moves, sorted by PST difference.
    case 4:
        while (s->i < s->movecount) {
            *m = s->m[s->i];
            s->i++;

            return 1;
        }

    // Captures (losing) init
    case 5:
        s->i = 0;
        s->phase = 6;

    // Captures (losing)
    case 6:
        while (s->i < s->badcap_count) {
            *m = s->badcap[s->i];
            s->i++;

            return 1;
        }
    }
    return 0;
};

int MoveValue(struct Board * b, struct Move m)
{
    int value = 0, cap;

    char from = m.from & 63;
    char dest = m.dest & 63;
    char piece = m.piece & 7;
    char type = m.type & 15;
    bool capture = type == CAPTURE || type == CAPTURE_PROMOTION || type == ENPASSANT;

    uint64_t destbb = 1ULL << dest;

    // PST difference as base move score.
    if (!capture) {
        if (b->side == WHITE) {
            value = pst[piece][0][dest] - pst[piece][0][from];
        } else {
            value = pst[piece][0][dest^56] - pst[piece][0][from^56];
        }

        return value;
    }

    // SEE for winning captures and losing quiets.
    cap = NO_PIECE;
    if (destbb & b->pieces[PAWN])
        cap = PAWN;
    else if (destbb & b->pieces[KNIGHT])
        cap = KNIGHT;
    else if (destbb & b->pieces[BISHOP])
        cap = BISHOP;
    else if (destbb & b->pieces[ROOK])
        cap = ROOK;
    else if (destbb & b->pieces[QUEEN])
        cap = QUEEN;
    else if (destbb & b->pieces[KING])
        cap = KING;

    // The idea of sectioning the move sort scores comes from Rookie 2.
    // Thank you, Marcel van Kervinck!
    if (type != ENPASSANT)
       value = piecevals[cap] - piece;
    else
       value = piecevals[PAWN] - PAWN;

    return value;
}

// Idea taken from Sungorus
bool BadCapture(struct Board * b, struct Move m)
{
    int cap;

    char from = m.from & 63;
    char dest = m.dest & 63;
    char piece = m.piece & 7;
    char type = m.type & 7;

    uint64_t destbb = 1ULL << dest;

    cap = NO_PIECE;
    if (destbb & b->pieces[PAWN])
        cap = PAWN;
    else if (destbb & b->pieces[KNIGHT])
        cap = KNIGHT;
    else if (destbb & b->pieces[BISHOP])
        cap = BISHOP;
    else if (destbb & b->pieces[ROOK])
        cap = ROOK;
    else if (destbb & b->pieces[QUEEN])
        cap = QUEEN;
    else if (destbb & b->pieces[KING])
        cap = KING;

    if (piecevals[cap] >= piecevals[piece])
        return false;

    if (type == ENPASSANT)
        return false;

    return SEEMove(b, m) < 0;
}