Qsearch:
Code: Select all
enum NodeType { NonPV, PV };
template <NodeType nodeType>
int qsearch(int alpha, int beta)
{
int bestValue, value;
bool givesCheck;
U64 AttackedSqs = STM ? Position::AttackedSquares<Black>() : Position::AttackedSquares<White>();
U64 InCheck = AttackedSqs&BitBoards[STM + King];
if (InCheck) bestValue = -Value_Infinite;
else
{
bestValue = Evaluate();
if (bestValue >= beta) return bestValue;// Stand pat
if (( nodeType == PV) && bestValue > alpha) alpha = bestValue;
}
Move Available[218];
const size_t MoveCount = (STM ? Position::QGenerator<White>(Available, InCheck, AttackedSqs) : Position::QGenerator<Black>(Available, InCheck, AttackedSqs)) - Available;
Position::ScoreMoves(Available, MoveCount);
std::sort(Available, Available + MoveCount, Srtfun);
for (size_t i = 0; i < MoveCount; ++i)
{
if (((!InCheck)&((TypeBoard[Available[i].To] != 0)/*|(Available[i].Type!=ENPASSANT)*/)) && (Position::see_sign(Available[i]) < 0)) continue;
Position::MakeMove(Available[i]);
value = -qsearch<NT>(-beta, -alpha);
Position::UnMakeMove(Available[i]);
if (value > bestValue)
{
bestValue = value;
if (value > alpha)
{
if (( nodeType == PV) && value < beta) alpha = value;
else return value;// Fail high
}
}
}
if (MoveCount == 0) if (InCheck) return -Value_Mate + ply;
return bestValue;
}
Code: Select all
int searchNonPV(int alpha, int depth)/*beta=alpha+1*/
{
//basic insufficient material detection
if (IsDraw()) return Value_Draw;
//Three-fold repetition detection: try the other approaches too
int IndexofLastIrreversible = GameRecordCounter < HalfMoveClock ? 0 : GameRecordCounter - HalfMoveClock;
for (int i = GameRecordCounter - 2; i >= IndexofLastIrreversible; i--) if (Positionkey == GameRecord[i]) return Value_Draw;
if (depth == 0) return qsearch<NonPV>(alpha, alpha + 1);
int bestValue = -Value_Infinite, value;
U64 AttackedSqs = STM ? Position::AttackedSquares<Black>() : Position::AttackedSquares<White>();
U64 InCheck = AttackedSqs&BitBoards[STM + King];
Move Available[218];
const size_t NMoves = (STM ? Position::GenerateMoves<White>(Available, InCheck, AttackedSqs) : Position::GenerateMoves<Black>(Available, InCheck, AttackedSqs)) - Available;
Position::ScoreMoves(Available, NMoves);
std::sort(Available, Available + NMoves, Srtfun);
for (size_t i = 0; i < NMoves; i++)
{
Position::MakeMove(Available[i]);
value = -searchNonPV(-(alpha + 1), depth - 1);
Position::UnMakeMove(Available[i]);
if (value > bestValue)
{
bestValue = value;
if (value > alpha)
{
if ((TypeBoard[Available[i].To] == 0)) UpdateKillersAndHistory(Available[i], depth);
break;// Fail high:>=beta=alpha+1
}
}
}
if (NMoves == 0) bestValue = InCheck ? -Value_Mate + ply : Value_Draw;
return bestValue;
}
Code: Select all
int searchPV(int alpha, int beta, int depth)
{
//basic insufficient material detection
if (IsDraw()) return Value_Draw;
//Three-fold repetition detection: try the other approaches too
int IndexofLastIrreversible = GameRecordCounter < HalfMoveClock ? 0 : GameRecordCounter - HalfMoveClock;
for (int i = GameRecordCounter - 2; i >= IndexofLastIrreversible; i--) if (Positionkey == GameRecord[i]) return Value_Draw;
if (depth == 0) return qsearch<PV>(alpha, beta);
int bestValue = -Value_Infinite, value;
U64 AttackedSqs = STM ? Position::AttackedSquares<Black>() : Position::AttackedSquares<White>();
U64 InCheck = AttackedSqs&BitBoards[STM + King];
Move Available[218];
const size_t NMoves = (STM ? Position::GenerateMoves<White>(Available, InCheck, AttackedSqs) : Position::GenerateMoves<Black>(Available, InCheck, AttackedSqs)) - Available;
Position::ScoreMoves(Available, NMoves);
std::sort(Available, Available + NMoves, Srtfun);
for (size_t i = 0; i < NMoves; i++)
{
Position::MakeMove(Available[i]);
if (i > 0) value = -searchNonPV(-(alpha + 1), depth - 1);
if (i == 0 || (value > alpha && (value < beta))) value = -searchPV(-beta, -alpha, depth - 1);
Position::UnMakeMove(Available[i]);
if (value > bestValue)
{
bestValue = value;
if (value > alpha)
{
if (value < beta) alpha = value;
else
{
if ((TypeBoard[Available[i].To] == 0)) UpdateKillersAndHistory(Available[i], depth);
break; // Fail high
}
}
}
}
if (NMoves == 0) bestValue = InCheck ? -Value_Mate + ply : Value_Draw;
return bestValue;
}
Code: Select all
Move SearchRoot(size_t maxdepth)
{
Move BestMove;;
int value;
U64 AttackedSqs = STM ? Position::AttackedSquares<Black>() : Position::AttackedSquares<White>();
U64 InCheck = AttackedSqs&BitBoards[STM + King];
Move Available[218];
const size_t NMoves = (STM ? Position::GenerateMoves<White>(Available, InCheck, AttackedSqs) : Position::GenerateMoves<Black>(Available, InCheck, AttackedSqs)) - Available;
std::pair<Move, int> RootMoves[218];
Position::ScoreMoves(Available, NMoves);
for (size_t i = 0; i < NMoves; i++) RootMoves[i] = std::make_pair(Available[i], int(Available[i].OrderingScore));
std::stable_sort(RootMoves, RootMoves + NMoves, SrtfunRN);
for (size_t d = 1; (d <= maxdepth); d++)
{
int alpha = -Value_Infinite, beta = Value_Infinite;
for (size_t i = 0; i < NMoves; i++)
{
Position::MakeMove(RootMoves[i].first);
if (i > 0) value = -searchNonPV(-(alpha + 1), d - 1);
if (i == 0 || (value > alpha)) value = -searchPV(-beta, -alpha, d - 1);
assert(abs(value) < Value_Mate);
Position::UnMakeMove(RootMoves[i].first);
if (value > alpha)
{
alpha = value;
BestMove=RootMoves[i].first;
RootMoves[i].second = value;
}
else RootMoves[i].second = -Value_Infinite;//by what should they be ordered ?
}
if (abs(alpha) >= Value_Mate_In_Max_Ply)
{
auto MateIn = (Value_Mate - abs(alpha)) / 2;
std::cout << "info depth " << d << " score mate " << (alpha >= 0 ? MateIn + 1 : -MateIn) << " time " << TimeManager::Elapsed() << " pv " << Parser::MoveToAlgebraicNotation(BestMove) << std::endl;
break;
}
else std::cout << "info depth " << d << " score cp " << (alpha * 100 / PawnValueEg) << " time " << TimeManager::Elapsed() << " pv " << Parser::MoveToAlgebraicNotation(BestMove) << std::endl;
std::stable_sort(RootMoves, RootMoves + NMoves, SrtfunRN);
if (TimeManager::Stop()) break;
}
return BestMove;
}