Loading...
#include "Search.h"
#include "Tablero.h"
#include "tui.h"
#include "Jugada.h"
#include "Line.h"
#include "TimeManager.h"
#include <vector>
#include <algorithm>
#include <stdint.h>
#include <string.h>

static const int NullMoveR = 3;
static const int NullMoveMinimalMaterial = 600;		     		// Para intentar nullmove al que le toca mover tiene
																// que tener al menos ese material.
static const int CanReduceMinOrdering = 75;
static const int MinReductionDepth = 2;
static const int lmrMoveTriesHashValid = 2;
static const int lmrMoveTriesHashInvalid = 6;

Search::Search(SearchHandler& handle) : handle(handle), searchedNodes(0), hash(handle.getHashtable()),
		stopSearching(false), startTime(0)
{
}

void Search::SearchHandler::setBestMove(Jugada bestMove) {
    boost::mutex::scoped_lock lock(bestMoveMutex);
    this->bestMove = bestMove;
}

Jugada Search::SearchHandler::getBestMove() {
    boost::mutex::scoped_lock lock(bestMoveMutex);
    return bestMove;
}

void Search::SearchHandler::setUpdated(bool updated) {
    boost::mutex::scoped_lock lock(updatedMutex);
    this->updated = updated;
    //cout << "updated: " << updated << endl;
}
bool Search::SearchHandler::isUpdated() {
    boost::mutex::scoped_lock lock(updatedMutex);
    return this->updated;
}

void Search::SearchHandler::setPv(Line pv) {
    boost::mutex::scoped_lock lock(pvMutex);
    this->pv = pv;
}
Line Search::SearchHandler::getPv() {
    boost::mutex::scoped_lock lock(pvMutex);
    return pv;
}

bool Search::SearchHandler::isRunning() {
	boost::mutex::scoped_lock lock(isRunningMutex);
	return running;
}

void Search::SearchHandler::setRunning(bool running) {
	boost::mutex::scoped_lock lock(isRunningMutex);
	this->running = running;
}

bool Search::canReduce ( const Tablero& t, const Jugada &move ) {
	if ( move.getOrdenamiento()<CanReduceMinOrdering && !t.esJaque() )
	/*if ( move.getTipo()==JUGADA_NORMAL && move.getCoronacion()==VACIA && t.getCasilla(move.getHasta()).getPieza()==VACIA )*/ {
		//cout << "S";
		return true;
	}
	else {
		//cout << "N";
		return false;
	}
}

int Search::failsoftQSearch ( Tablero &t ,int alpha, int beta, int depth ) {

	searchedNodes++;
    int val;    // El valor del nodo actual, contendra valor de hash si se encuentra, sino evaluacion estatica
    bool isCheck = t.esJaque();

	val = t.getStaticEval();

	/*
	if ( t.getMaterialValue(t.getTurno())>NullMoveMinimalMaterial &&
		val < alpha &&		// Condicion evidente pero que ayuda a acelerar
		(val+t.getMostValuableCapture(t.getTurno())+QSearchMVCPruningMarging) < alpha )
		return alpha;
	*/

	if ( isCheck && depth<=2 )
		val = -Infinity;

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

    vector<Jugada> vMoves;
    if ( isCheck && depth<=2 ) {
    	t.generarMovimientos(vMoves);
    }
    else {
    	t.qGenerateMoves(vMoves);
    }

    std::sort(vMoves.begin(),vMoves.end());

    for ( vector<Jugada>::iterator it=vMoves.begin();it!=vMoves.end();++it ) {
        t.hacerJugada(*it);
        if ( !t.esLegal() ) {
            t.desHacerJugada(*it);
            continue;
        }
        val = -failsoftQSearch(t, -beta, -alpha, depth+1);
        t.desHacerJugada(*it);
        if ( val>=beta )
            return val;
        if ( val>alpha ) {
            alpha=val;
        }
    }

    return alpha;

}

int Search::failSoftAlphaBeta ( Tablero& t, int alpha, int beta, int ply, int maxPly, Line& pv, bool allowNullMovePruning ) {
    searchedNodes++;

    if ( (searchedNodes&50000) == 50000 && getMilliTime()-startTime>handle.getTimeLimit() ) {
		stopSearching = true;
	}
    if ( stopSearching ) {
    	return alpha;
    }

    if ( ply>=maxPly ) {
        pv.clear();
        return failsoftQSearch(t, alpha, beta, 0);
    }

    Line line;
    int thisNodeDepth = maxPly-ply;
    int val;    // El valor del nodo actual, contendra valor de hash si se encuentra, sino evaluacion estatica
    Jugada hashMove;
    Hashtable::Entry hashEntry;
    int hashLowerBoundValue = Infinity;
    bool foundHashEntry = hash.probe(t.getKey(), hashEntry);
    if ( foundHashEntry ) {
        hashMove = hashEntry.getBest();
        if ( hashEntry.getDepth()>=thisNodeDepth ) {
        	if ( (hashEntry.getFlags()==Hashtable::Entry::flagExact) ||
        		 (hashEntry.getFlags()==Hashtable::Entry::flagAlpha && hashEntry.getValue()<alpha) ||
				 (hashEntry.getFlags()==Hashtable::Entry::flagBeta && hashEntry.getValue()>beta) ) {
                pv = line;
                pv.addMove(hashMove);
				return hashEntry.getValue();
        	}
        	if ( hashEntry.getFlags()!=Hashtable::Entry::flagAlpha )
        		hashLowerBoundValue = hashEntry.getValue();
        }
    }

    bool isCheck = t.esJaque();
    if ( allowNullMovePruning
    		&& !isCheck
            //&& ( !(foundHashEntry && hashEntry.getFlags()!=Hashtable::Entry::flagExact) || val>beta )	// Regla logica: ~PvQ == P->Q
    		&& hashLowerBoundValue > beta
            && t.getMaterialValue(t.getTurno())>NullMoveMinimalMaterial
            /*&& ply>0 */
            && thisNodeDepth>=2 ) {
        t.doNullMove();
        Line nada;
        int nullMoveVal = -failSoftAlphaBeta(t, -beta, -beta+1, ply+1, maxPly-NullMoveR, nada, false);
        t.undoNullmove();

        if ( nullMoveVal>=beta ) {
            return beta;
        }
    }
    vector<Jugada> vMoves;
    t.generarMovimientos(vMoves);
    bool hashMoveIsValid = false;
    if ( foundHashEntry && hashEntry.getFlags()!=Hashtable::Entry::flagAlpha ) {
		for ( vector<Jugada>::iterator it=vMoves.begin();it!=vMoves.end();++it ) {
			if ( *it==hashMove ) {
				it->setOrdenamiento(Infinity<<4);
				hashMoveIsValid = true;
			}
		}
    }

    std::sort(vMoves.begin(),vMoves.end());

    uint8_t hashFlag = Hashtable::Entry::flagAlpha;
    int legalMoves = 0;
    int alphaImproves = 0;
    int thisMoveMaxPly = maxPly;
    for ( vector<Jugada>::iterator it=vMoves.begin();it!=vMoves.end();++it ) {
        
        // Calculo de reducciones:
        if ( alphaImproves==0 && !isCheck )  {
        	if ( (hashMoveIsValid && legalMoves>=lmrMoveTriesHashValid ) || legalMoves>=lmrMoveTriesHashInvalid )
        		thisMoveMaxPly = maxPly - 1;
        }

        t.hacerJugada(*it);
        if ( !t.esLegal() ) {
            t.desHacerJugada(*it);
            continue;
        }
        legalMoves++;
        if ( !t.repeatedPosition() ) {
        	if ( thisMoveMaxPly!=maxPly && canReduce(t, *it) && thisNodeDepth>MinReductionDepth ) {
        		val = -failSoftAlphaBeta( t, -beta, -alpha, ply+1, thisMoveMaxPly, line, true);
        		if ( val>alpha ) {
        			thisMoveMaxPly=maxPly;
        			val = -failSoftAlphaBeta( t, -beta, -alpha, ply+1, thisMoveMaxPly, line, true);
				}
        	}
        	else {
        		thisMoveMaxPly=maxPly;
        		val = -failSoftAlphaBeta( t, -beta, -alpha, ply+1, thisMoveMaxPly, line, true);
        	}
        }
        else
            val = 0;
        t.desHacerJugada(*it);

        if ( val>=beta ) {
            if ( val<Infinity-250 )
                hash.record(t.getKey(), *it, thisNodeDepth, val, Hashtable::Entry::flagBeta);
            //pv = line;
            //pv.addMove(*it);
            return val;
        }
        if ( val>alpha ) {
            pv = line;
            pv.addMove(*it);
            alpha=val;
            hashFlag = Hashtable::Entry::flagExact;
            alphaImproves++;
        }
    }
    if ( legalMoves==0 ) {
        pv.clear();
        if ( t.esJaque() ) {
            int mateScore = -Infinity+ply;
            return mateScore;     // Jaque mate
        }
        else {
            int drawScore = 0;
            return drawScore;
        }
    }

    hash.record( t.getKey(), pv.firstMove(), thisNodeDepth, alpha, hashFlag );
    return alpha;
}

void Search::rootSearch() {
    Tablero& t=handle.getT();
    startTime = getMilliTime();
    vector<Jugada> vMoves;
    t.generarMovimientos(vMoves);
    vector<Jugada>::iterator it=vMoves.begin();
    while ( it!=vMoves.end() ) {
        Jugada move = *it;
        t.hacerJugada(move);
        if ( !t.esLegal() ) {
            it = vMoves.erase(it);
        }
        else {
            it->setOrdenamiento(-failsoftQSearch(t,-Infinity,Infinity,0));
            ++it;
        }
        t.desHacerJugada(move);
    }
    std::sort(vMoves.begin(), vMoves.end());
    for ( int depth=2;getMilliTime()-startTime<handle.getTimeLimit()/2;depth++ ) {
        bool foundPv = false;
        int alpha = -Infinity;
        int beta = Infinity;
        for ( vector<Jugada>::iterator it = vMoves.begin();
                it!=vMoves.end() && (getMilliTime()-startTime)<handle.getTimeLimit();
                ++it ) {
            Jugada currentMove = *it;
            t.hacerJugada(currentMove);
            reSearch:
            if ( !foundPv ) {
                Line pv;
                int val = -failSoftAlphaBeta(t, -beta, -alpha, 0, depth, pv, true);
                foundPv = true;

                if ( val > alpha && !stopSearching ) {
                	alpha = val;
					pv.addMove(currentMove);
					handle.setPv(pv);
					handle.setBestMove(currentMove);
					handle.setSearchedNodes(searchedNodes);
					handle.setValue(alpha);
					handle.setSearchTime(getMilliTime()-startTime);
					handle.setSearchedDepth(depth);
					handle.setUpdated(true);
                }

            }
            else if (!stopSearching) {
                beta = alpha + 1;
                Line pv;
                int val = -failSoftAlphaBeta(t, -beta, -alpha, 0, depth, pv, true);
                if ( val>alpha ) {
                    foundPv = false;
                    unsigned index = it - vMoves.begin();
                    for ( ;index>0;--index )
                        vMoves[index] = vMoves[index-1];
                    vMoves[0] = currentMove;
                    goto reSearch;
                }
            }
            t.desHacerJugada(currentMove);
        }
    }

}

void Search::operator() () {
    handle.setRunning(true);
    stopSearching = false;
    Jugada move = handle.getBManager().getBookMove(handle.getT());
    if ( move.isValid() ) {
		handle.setBestMove(move);
    }
    else {
    	rootSearch();
    }
    handle.setRunning(false);
}