Code: Select all
int q_search(int alpha, int beta)
{
if (!InCheck)
{
int stand_pat = Evaluate();
if (stand_pat >= beta) return beta;
if (alpha < stand_pat) alpha = stand_pat;
}
//score & sort
ScoreMoves();
sort();
for (size_t i = 0; i < MoveCount; ++i)
{
//don't prune promotions ? check stock fish source code
if ((!InCheck)& (!PROMOTION) && (Position::see_sign(Available[i]) < 0)) continue;
QNodeCount++;
Position::MakeMove(Available[i]);
int Score = -q_search(-beta, -alpha);
Position::UnMakeMove(Available[i]);
if (Score >= beta) return beta;
if (Score > alpha) alpha = Score;
}
if (MoveCount == 0) if (InCheck) return -Value_Mate + ply;
return alpha;
}
static int AlphaBeta(int alpha, int beta, int depthleft, bool AllowNull)
{
NNodeCount++;
//insufficient material detection , or (maxPly-1) to avoid problems on extensions
if (IsDraw()) return Value_Draw;
//Three-fold repetition detection
int IndexofLastIrreversible = GameRecordCounter < HalfMoveClock ? 0 : GameRecordCounter - HalfMoveClock;
for (int i = GameRecordCounter - 2; i >= IndexofLastIrreversible; i--) if (Positionkey == GameRecord[i]) return Value_Draw;
if (depthleft == 0) return q_search(alpha, beta);
if (ply > maxPly) maxPly = ply;
TTEntry entry;
bool found = false;
//see :http://www.stmintz.com/ccc/index.php?id=93732
if ((ply>1) && (found = TTProbe(entry)) && (entry.Depth >= depthleft))
{
if ((entry.Score >= beta) & (entry.bound == BoundType::Lower))
{
if (Quiet) UpdateKillersAndHistory(entry.move, depthleft);
return beta;
}
if ((entry.Score <= alpha) & (entry.bound == BoundType::Upper)) return alpha;
if (entry.bound == BoundType::Exact)return entry.move.Score;
}
#if NullMovePruning
int R = 2;
if (AllowNull & (!InCheck) &(depthleft > (R + 1)) & SideToMoveNonPawnMaterial())//is it okay to descend directly to the quiescence search ?!
{
R += (depthleft > 7);//todo : check if side to move has 2 or more pieces :http://chessprogramming.wikispaces.com/Null+Move+Pruning+Test+Results
//Make null move
ply++;//not needed !
STM = Color(7 - STM);//reverse side to move
U64 OldKey = Positionkey;
Positionkey ^= ZobristSide;
if (DoublePushSQ[1] != 0) Positionkey ^= GetEnpassantZobrist();
unsigned int EpTOld = DoublePushSQ[1];
DoublePushSQ[1] = 0;
//auto oldHMClock = HalfMoveClock;//Is a null move considered irreversible ?
//HalfMoveClock = 0;
int NMScore = -AlphaBeta(-beta, -beta + 1, depthleft - 1 - R, false);
//Unmake null move
ply--;
STM = Color(7 - STM);
DoublePushSQ[1] = EpTOld;
//HalfMoveClock = oldHMClock;
Positionkey = OldKey;
if (NMScore >= beta) return beta;
}
#endif
//Used for Scoring & sorting
ttMove = (found ? entry.move : Move());
//simple Check Extension
if (InCheck) depthleft++;//todo :test making it per move depending on it's SEE value ?
//score&sort : todo replace with a selection sort and split the generator
ScoreMoves();
sort();
Move mBest = Move();
BoundType bound = BoundType::Upper;
for (size_t i = 0; i < NMoves; i++)
{
Position::MakeMove(Available[i]);
auto Score =-AlphaBeta(-beta, -alpha, depthleft - 1, true);
Position::UnMakeMove(Available[i]);
if (Score >= beta)
{
if (Quiet) UpdateKillersAndHistory(Available[i], depthleft);
TTStore(Available[i], depthleft, BoundType::Lower, Score);
return beta;
}
if (Score > alpha)
{
bound = BoundType::Exact;
mBest = Available[i];
alpha = Score;
}
}
if (NMoves == 0)
{
auto Score = InCheck ? -Value_Mate + ply : Value_Draw;
TTStore(Move(), depthleft, BoundType::Exact, Score);
return Score;
}
TTStore(mBest, depthleft, bound, alpha);
return alpha;
}
///isn't it wrong to descend directly to qsearch at the first loop : d-1=0
Move IterativeDeepning(size_t maxdepth)
{
Move BestMove;
Move Available[218];
std::pair<Move, int> RMoves[218];
for (size_t i = 0; i < NMoves; i++) RMoves[i] = std::make_pair(Available[i],Position::SEE(Available[i]));
std::stable_sort(RMoves, RMoves + NMoves, SrtfunR);
maxPly = 0;
for (size_t d = 1; (d <= maxdepth); d++)
{
int alpha = -Value_Mate, beta = Value_Mate;
U64 PrevNodeCount = NNodeCount;
NNodeCount = 0ULL;
QNodeCount = 0ULL;
U64 sw = 0;
for (size_t i = 0; i < NMoves; i++)
{
Position::MakeMove(RMoves[i].first);
///******************************************************** d-1?
U64 pnodes = NNodeCount;
auto Score = -AlphaBeta(-beta, -alpha, d - 1, true);
RMoves[i].second = INT32_MAX - (NNodeCount - pnodes);
Position::UnMakeMove(RMoves[i].first);
if (Score > alpha)
{
alpha = Score;
BestMove = RMoves[i].first;
for (int j = sw - 1; j >= 0; j--) if (j + 1 < NMoves) std::swap(RMoves[j], RMoves[j + 1]);
std::swap(RMoves[i], RMoves[0]);
sw++;
}
}
if (abs(alpha) >= Value_Mate_In_Max_Ply)//optimize this section
{
std::cout << FormatResult<MateResult>(d, PrevNodeCount, TimeManager::Elapsed(), alpha, BestMove) << std::endl;
break;
}
else std::cout << FormatResult<NormalResult>(d, PrevNodeCount, TimeManager::Elapsed(), alpha, BestMove) << std::endl;
if (TimeManager::Stop()) break;
std::stable_sort(RMoves + 1, RMoves + NMoves, SrtfunR);
}
return BestMove;
}
2-is it okay to descend directly to qsearch after a null move ?
3-Can I use null move Reductions in endgame positions where null move pruning isn't applicable ?
5-Currently I'm using a basic TT with an Always Replace strategy , should I see a clear performance gain if I switch to a bucket system ?
4-What is the next step ? LMR ?
