chessy/src/Minimax.cpp

#include "Minimax.h"
#include "ChessGame.h"
#include "Search.h"

#include <iostream>

#include <functional>
#include <limits>
#include <chrono>

using namespace chessy;


/*size_t chessy::perft(std::ostream& out, ChessGame& chessGame, int depth)
{
    size_t result = 0;

    std::function<void(const MoveInfo&, ChessGame&, int, bool)> searcher;
    std::function<void(ChessGame&, int, bool)> iterate;

    // apply a move and search deeper
    searcher = [&result, &iterate] (const MoveInfo& mi, ChessGame& cg,
                                    int depth, bool print)
    {
        if (depth > 1) {
            UndoInfo ui = cg.doMove(mi);
            size_t interRes = result;
            iterate(cg, depth - 1, false);
            if (print)
                std::cout << mi.move.asString() << ": " <<
                    (result - interRes) << std::endl;
            cg.undoMove(ui);
        }
        else {
            if (print)
                std::cout << mi.move.asString() << ": " <<
                    1 << std::endl;
            result++;
        }
    };

    // iterate through all positions in the current position
    iterate = [&searcher] (ChessGame& cg, int depth, bool print)
    {
        Search<decltype(searcher)&> search (searcher, cg);
        if (cg.getTurn() == WHITE_SIDE)
            search.iterateAll<WHITE_SIDE>(cg, depth, print);
        else 
            search.iterateAll<BLACK_SIDE>(cg, depth, print);
    };


    using namespace std::chrono;

    auto begin = high_resolution_clock::now();
    iterate(chessGame, depth, true);
    auto end = high_resolution_clock::now(); 
    auto millis = duration_cast<milliseconds>(end - begin);
    double seconds = millis.count() / 1000.0;
    size_t nodesPerSecond = (result * 1000 * 1000 * 1000) /
        duration_cast<nanoseconds>(end - begin).count();

    out << "Searched " << result << " nodes in " << seconds <<
        " seconds. (at " << nodesPerSecond << " nodes per second)" << std::endl;

    return result;
}*/
size_t chessy::perft(std::ostream& out, ChessGame& cg, int depth)
{
    std::function<size_t(bool, int)> iterate = [&](bool print, int depth) -> size_t {
        if (depth <= 0)
            return 1;
        std::vector<Move> moves;
        moves.reserve(50);
        if (cg.getTurn() == WHITE_SIDE)
            generateAllMoves<WHITE_SIDE, false>(cg, moves);
        else
            generateAllMoves<BLACK_SIDE, false>(cg, moves);

        size_t sum = 0;
        for (Move move : moves) {
            MoveInfo mi{ move, cg };
            UndoInfo ui = cg.doMove(mi);
            size_t v = iterate(false, depth - 1);
            if (print)
                out << mi.move.asString() << ": " << v << std::endl;
            sum += v;
            cg.undoMove(ui);
        }
        return sum;
    };


    using namespace std::chrono;
    
    auto begin = high_resolution_clock::now();
    size_t sum = iterate(true, depth);
    auto end = high_resolution_clock::now();

    auto millis = duration_cast<milliseconds>(end - begin);
    double seconds = millis.count() / 1000.0;
    size_t nodesPerSecond = (sum * 1000 * 1000 * 1000) /
        duration_cast<nanoseconds>(end - begin).count();

    out << "Searched " << sum << " nodes in " << seconds <<
        " seconds. (at " << nodesPerSecond << " nodes per second)" << std::endl;


    return sum;
}

#include <iostream>
using namespace std;

std::pair<Move, MoveValue> chessy::miniMax(ChessGame& cg, int depth, const TimeCheck& check)
{
    std::vector<Move> moves;
    moves.reserve(200);
    if (cg.getTurn() == WHITE_SIDE) {
        generateAllMoves<WHITE_SIDE, false>(cg, moves);
        orderMoves<WHITE_SIDE>(cg, moves);
    }
    else {
        generateAllMoves<BLACK_SIDE, false>(cg, moves);
        orderMoves<BLACK_SIDE>(cg, moves);
    }

    const Board& b = cg.getBoard();
    auto isCheck = [&cg, &b] () {
        return cg.getTurn() == BLACK_SIDE ? b.isCheck<WHITE_SIDE>() :
            b.isCheck<BLACK_SIDE>();
    };

    Move bestMove{ 0, 0 };
    MoveValue alpha = -1e+30;
    MoveValue beta = 1e+30;
    Move lastValidMove = bestMove;
    for (Move move : moves) {
        MoveInfo mi{ move, cg };
        UndoInfo ui = cg.doMove(mi);
        MoveValue val;
        if (isCheck()) {
            cg.undoMove(ui);
            continue;
        }
        else {
            lastValidMove = move;
            val = -negamaxImplementation(cg, depth - 1, -beta, -alpha, check);
        }
        //cout << move.asString() << ": " << val << endl;
        cg.undoMove(ui);
        if(val > alpha) {
            alpha = val;
            bestMove = move;
        }
        if (check())
            break;
    }
    if (bestMove.origin == 0 && bestMove.destination == 0) {
        bestMove = lastValidMove;
    }
    return { bestMove, alpha }; //negamaxImplementation(chessGame, 5);
}


MoveValue chessy::negamaxImplementation(ChessGame& cg, int depth,
        chessy::MoveValue alpha, chessy::MoveValue beta, const TimeCheck& check)
{
    if (depth < 3) {
        if (check())
            return alpha;
    }
    if (depth <= 0)
        return quiescence(cg, 3, alpha, beta);
        //return evaluate(cg);

    const Board& b = cg.getBoard();
    auto isCheck = [&cg, &b] (Side turn) {
        return turn == BLACK_SIDE ? b.isCheck<WHITE_SIDE>() :
            b.isCheck<BLACK_SIDE>();
    };

    std::vector<Move> moves;
    moves.reserve(80);
    if (cg.getTurn() == WHITE_SIDE) {
        generateAllMoves<WHITE_SIDE, false>(cg, moves);
        orderMoves<WHITE_SIDE>(cg, moves);
    }
    else {
        generateAllMoves<BLACK_SIDE, false>(cg, moves);
        orderMoves<BLACK_SIDE>(cg, moves);
    }

    bool thereIsMove = false;
    for (Move move : moves) {
        MoveInfo mi{ move, cg };
        UndoInfo ui = cg.doMove(mi);
        MoveValue val;
        if (isCheck(cg.getTurn()))
            val = -1e+30;
        else {
            val = -negamaxImplementation(cg, depth - 1, -beta, -alpha, check);
            thereIsMove = true;
        }
        cg.undoMove(ui);
        if(val >= beta)
            return beta;
        if(val > alpha)
            alpha = val;
    }
    if (!thereIsMove)
        return isCheck(otherSide(cg.getTurn())) ? -1e+30 : 0.0;
    return alpha;
}


MoveValue chessy::quiescence(ChessGame& cg, int maxDepth,
        MoveValue alpha, MoveValue beta)
{
    MoveValue standingPat = evaluate(cg);
    if (maxDepth <= 0)
        return standingPat;

    if (standingPat >= beta)
        return beta;
    if(standingPat > alpha)
        alpha = standingPat;

    HashValue hv = cg.getHash();
    const auto& history = cg.getHistory();
    int equalCount = 0;
    /*for (auto i = cg.getHistory().cend() - 1; i >= (history.size() > 100? history.cend()-99 : history.cbegin()); i--) {
        if (*i == hv) {
            equalCount++;
            if (equalCount >= 3)
                return 0;
        }
    }*/
    for (auto hash : history) {
        if (hash == hv) {
            equalCount++;
            if (equalCount >= 3)
                return 0;
        }
    }

    const Board& b = cg.getBoard();
    auto isCheck = [&cg, &b] (Side turn) {
        return turn == BLACK_SIDE ? b.isCheck<WHITE_SIDE>() :
            b.isCheck<BLACK_SIDE>();
    };

    std::vector<Move> moves;
    moves.reserve(50);
    if (cg.getTurn() == WHITE_SIDE) {
        generateAllMoves<WHITE_SIDE, true>(cg, moves);
        orderMoves<WHITE_SIDE>(cg, moves);
    }
    else {
        generateAllMoves<BLACK_SIDE, true>(cg, moves);
        orderMoves<BLACK_SIDE>(cg, moves);
    }

    bool thereIsMove = false;
    for (Move move : moves) {
        MoveInfo mi{ move, cg };
        UndoInfo ui = cg.doMove(mi);
        MoveValue val;
        if (isCheck(cg.getTurn()))
            val = -1e+30;
        else {
            val = -quiescence(cg, maxDepth - 1, -beta, -alpha);
            thereIsMove = true;
        }
        cg.undoMove(ui);
        if(val >= beta)
            return beta;
        if(val > alpha)
            alpha = val;
    }
    if (!thereIsMove)
        return isCheck(otherSide(cg.getTurn())) ? -1e+30 : 0.0;
    return alpha;
}
/*
MoveValue chessy::quiescence(ChessGame& cg, int maxDepth,
    MoveValue alpha, MoveValue beta)
{
    MoveValue standingPat = evaluate(cg);
    if (maxDepth <= 0)
        return standingPat;

    if (beta <= standingPat)
        return beta;
    if (alpha < standingPat)
        alpha = standingPat;

    const Board& b = cg.getBoard();
    auto isCheck = [&cg, &b] (Side turn) {
        return turn == BLACK_SIDE ? b.isCheck<WHITE_SIDE>() :
            b.isCheck<BLACK_SIDE>();
    };

    std::vector<Move> moves;
    moves.reserve(50);
    if (cg.getTurn() == WHITE_SIDE) {
        generateAllMoves<WHITE_SIDE, true>(cg, moves);
        orderMoves<WHITE_SIDE>(cg, moves);
    }
    else {
        generateAllMoves<BLACK_SIDE, true>(cg, moves);
        orderMoves<BLACK_SIDE>(cg, moves);
    }

    bool thereIsMove = false;
    for (Move move : moves) {
        MoveInfo mi{ move, cg };
        UndoInfo ui = cg.doMove(mi);
        MoveValue val;
        if (isCheck(cg.getTurn()))
            val = -1e+30;
        else {
            val = -quiescence(cg, maxDepth - 1, -beta, -alpha);
            if (val == 0.0f)
                int s = 23;
            thereIsMove = true;
        }
        cg.undoMove(ui);
        if(val >= beta)
            return beta;
        if(val > alpha)
            alpha = val;
    }
    if (!thereIsMove)
        return isCheck(otherSide(cg.getTurn())) ? -1e+30 : 0.0;
    return alpha;
}*/



/*
template MiniMax::BestMove MiniMax::minimax<WHITE_SIDE>(int);
template MiniMax::BestMove MiniMax::minimax<BLACK_SIDE>(int);

Move MiniMax::calculateBest(int depth)
{
    if (game.getTurn() == WHITE_SIDE) {
        BestMove bm = minimax<WHITE_SIDE>(depth);
        return bm.move;
    }
    else
        return minimax<BLACK_SIDE>(depth).move;
}


template<Side side>
float MiniMax::evaluate(void) const
{
    int piecePoints = 0;
    Board& bd = game.getBoard();
    Bitboard p = bd.getPawns<side>();
    Bitboard n = bd.getKnights<side>();
    Bitboard b = bd.getBishops<side>();
    Bitboard r = bd.getRooks<side>();
    Bitboard q = bd.getQueens<side>();
    Bitboard k = bd.getKing<side>();
    piecePoints += 1 * p.popcount();
    piecePoints += 3 * n.popcount();
    piecePoints += 3 * b.popcount();
    piecePoints += 4 * r.popcount();
    piecePoints += 6 * q.popcount();
    if (k == Bitboard(0ULL))
        piecePoints -= 100000;

    const Side other = otherSide(side);
    p = bd.getPawns<other>();
    n = bd.getKnights<other>();
    b = bd.getBishops<other>();
    r = bd.getRooks<other>();
    q = bd.getQueens<other>();
    k = bd.getKing<other>();
    piecePoints -= 1 * p.popcount();
    piecePoints -= 3 * n.popcount();
    piecePoints -= 3 * b.popcount();
    piecePoints -= 4 * r.popcount();
    piecePoints -= 6 * q.popcount();
    if (k == Bitboard(0ULL))
        piecePoints += 100000;
    
    return piecePoints;
}


template<Side side>
MiniMax::BestMove MiniMax::minimax(int depth)
{
    if (depth == 0) {
        return { {0, 0}, -evaluate<side>() };
    }

    BestMove bestMove = { {0, 0}, -std::numeric_limits<float>::infinity() };

    Board& board = game.getBoard();
    Bitboard friends;
    Bitboard enemies;
    if (side == WHITE_SIDE) {
        friends = board.getWhites();
        enemies = board.getBlacks();
    }
    else {
        friends = board.getBlacks();
        enemies = board.getWhites();
    }

    const Board temp = board;
    PawnPushGenerator<side> mg{ game };
    for (Move push : mg) {
        Bitboard& pawns = board.getPawns<side>();
        Bitboard pTemp = pawns;
        pawns.applyMove(push);
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = push;
        bestMove.overwriteIfBetter(m);
        pawns = pTemp;
    }

    PawnDoublePushGenerator<side> dp{ game };
    for (Move push : dp) {
        Bitboard& pawns = board.getPawns<side>();
        Bitboard pTemp = pawns;
        pawns.applyMove(push);
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = push;
        bestMove.overwriteIfBetter(m);
        pawns = pTemp;
    }

    PawnCaptureGenerator<side, LEFT> pl{ game };
    for (Move capture : pl) {
        Bitboard& pawns = board.getPawns<side>();
        board.removeAt(capture.destination);
        pawns.applyMove(capture);
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = capture;
        bestMove.overwriteIfBetter(m);
        board = temp;
    }
    
    PawnCaptureGenerator<side, RIGHT> pr{ game };
    for (Move capture : pr) {
        Bitboard& pawns = board.getPawns<side>();
        board.removeAt(capture.destination);
        pawns.applyMove(capture);
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = capture;
        bestMove.overwriteIfBetter(m);
        board = temp;
    }

    PromotionGenerator<side> pg{ game };
    for (Move promotion : pg) {
        Bitboard& pawns = board.getPawns<side>();
        board.removeAt(promotion.destination);
        pawns.applyMove(promotion);
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = promotion;
        bestMove.overwriteIfBetter(m);
        board = temp;
    }


    Bitboard& ns = board.getKnights<side>();
    PositionSet knights { ns };
    for (auto knight : knights) {
        for (auto pos : KnightMoveGenerator{ knight, friends }) {
            Move move = { knight, pos };
            board.removeAt(move.destination);
            ns.applyMove(move);
            BestMove m = minimax<otherSide(side)>(depth - 1);
            m.move = move;
            bestMove.overwriteIfBetter(m);
            board = temp;
        }
    }

    Bitboard& bs = board.getBishops<side>();
    PositionSet bishops { bs }; 
    for (auto bishop : bishops) {
        for (auto pos : PrimitiveBishopMoveGenerator{ bishop, enemies, friends }) {
            Move move = { bishop, pos };
            board.removeAt(move.destination);
            bs.applyMove(move);
            BestMove m = minimax<otherSide(side)>(depth - 1);
            m.move = move;
            bestMove.overwriteIfBetter(m);
            board = temp;
        }
    }

    Bitboard& rs = board.getRooks<side>();
    PositionSet rooks { rs }; 
    for (auto rook : rooks) {
        for (auto pos : PrimitiveRookMoveGenerator{ rook, enemies, friends }) {
            Move move = { rook, pos };
            board.removeAt(move.destination);
            rs.applyMove(move);
            BestMove m = minimax<otherSide(side)>(depth - 1);
            m.move = move;
            bestMove.overwriteIfBetter(m);
            board = temp;
        }
    }

    Bitboard& qs = board.getQueens<side>();
    PositionSet queens { qs };
    for (auto queen : queens) {
        for (auto pos : PrimitiveQueenMoveGenerator{ queen, enemies, friends }) {
            Move move = { queen, pos };
            board.removeAt(move.destination);
            qs.applyMove(move);
            BestMove m = minimax<otherSide(side)>(depth - 1);
            m.move = move;
            bestMove.overwriteIfBetter(m);
            board = temp;
        }
    }

    Bitboard& king = board.getKing<side>();
    Index kingIndex = king.getLeastSignificantBit();
    for (auto pos : KingMoveGenerator{ king, friends }) {
        Move move = { kingIndex, pos };
        board.removeAt(pos);
        king.applyMove(move);
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = move;
        //if (depth >= 3)
        //    std::cout << m.move.asString() << " " << bestMove.value << " -> " << m.value << std::endl;
        bestMove.overwriteIfBetter(m);
        board = temp;
    }

    if (side == WHITE_SIDE) {
        if (game.getCanCastleKingSide(side)) {
            if((board.getWhites().bits & 0x6) == 0) {
                Move kingMove = {3, 1};
                Move rookMove = {0, 2};
                king.applyMove(kingMove);
                rs.applyMove(rookMove);
                board = temp;
            }
        }
    }

    for (auto pos : CastlingGenerator<side>{ game }) {
        Move move = { kingIndex, pos };
        king.applyMove(move);
        
        BestMove m = minimax<otherSide(side)>(depth - 1);
        m.move = move;
        //if (depth >= 3)
        //    std::cout << m.move.asString() << " " << bestMove.value << " -> " << m.value << std::endl;
        bestMove.overwriteIfBetter(m);
        board = temp;
    }


    float v = evaluate<side>();
    bestMove.value *= 0.9f;
    bestMove.value += v * 0.2f;
    return -bestMove;
}
*/