Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 12:31 am
I'm a beginner in chess engine programming so far I have implement Strictly Legal move generator and verified it's correctness using perft routine ,I'm trying to implement the search and evalution functions but to no avail ,reading the source code of several other programmers even simple one's like TSCP the search routine is full of heuristic and transposition code...etc which makes it pretty much hard for me to understand , could someone provide an example search routine out of this PVS algorithm with heuristic whatsoever :
those is the pseudo code posted on chess programming wiki, but I don't know how to incorporate it in my program, where(in which method ,and is it in search or evaluation) , when and if I should check for check/stale mate , how to do that properly and if there is any other thing, (what score should I return for both and does it depend on the side to move),also what is Quiescence Search is it important ,and do I need to implement a special move generator for it (right now the move generator generates captures then quiets and in case of evasion king moves then captures and blocks),finally what are the most important "easy to mid difficult" heuristics/techniques to implement after this ?
Code: Select all
int PVS(alfa,beta,depthleft) {
if( depthleft <= 0 ) return qsearch(alpha, beta);
// using fail soft with negamax:
make first move
bestscore = -PVS(-beta, -alpha, depthleft-1);
unmake first move
if( bestscore > alpha ) {
if( bestscore >= beta )
return bestscore;
alpha = bestscore;
}
for( all remaining moves ) {
make move
score = -zwSearch(-alpha-1, -alpha, depthleft-1); // alphaBeta or zwSearch
if( score > alpha && score < beta ) {
// research with window [alpha;beta]
score = -PVS(-beta, -alpha, depthleft-1);
if( score > alpha )
alpha = score;
}
unmake move
if( score > bestscore ) {
if( score >= beta )
return score;
bestscore = score;
}
}
return bestscore;
}
// fail-hard zero window search, returns either beta-1 or beta
int zwSearch(int beta, int depth ) {
// alpha == beta - 1
// this is either a cut- or all-node
if( depth == 0 ) return quiesce(beta-1, beta);
for ( all moves) {
make
score = -zwSearch(1-beta, depth - 1);
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
}
return beta-1; // fail-hard, return alpha
}
int Quiesce( int alpha, int beta ) {
int stand_pat = Evaluate();
if( stand_pat >= beta )
return beta;
if( alpha < stand_pat )
alpha = stand_pat;
until( every_capture_has_been_examined ) {
MakeCapture();
score = -Quiesce( -beta, -alpha );
TakeBackMove();
if( score >= beta )
return beta;
if( score > alpha )
alpha = score;
}
return alpha