Page 1 of 3
Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 12:31 am
by MahmoudUthman
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 :
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
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 ?
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 12:46 am
by kbhearn
That is PVS in its simplest form as far as i can see, try the page on alpha-beta, and specificly the negamax framework section for a more compact representation of the core of alpha-beta search.
http://chessprogramming.wikispaces.com/Alpha-Beta
PVS is an addition to that to search a well-ordered alpha-beta tree faster and is simple enough to implement at a later time once you've understood plain ol alpha-beta.
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 10:25 am
by tpetzke
Welcome to chess programming
but I don't know how to incorporate it in my program, where (in which method ,and is it in search or evaluation)
This is the search algorithm, but as Kevin stated start with NegaMax (this removes all this zero window stuff and is still powerful)
also what is Quiescence Search is it important
Yes it is important for a good playing strength, not necessarily that your search algorithm works. For a start you can just replace the call to qSearch with a call to eval (make sure to adjust the sign of eval to the side to move for negamax). Without qSearch your engine might want to play a Queen captures Pawn move in the last ply of search and consider this a good move although the pawn is protected and you will lose your queen next move. qSearch will extend the search in that case a bit so you see that the pawn capture is not good.
You don't have to use a special move generator for this (this would be another optimization). Just use the one you have and skip all non captures/ non queen promotion moves.
finally what are the most important "easy to mid difficult" heuristics/techniques to implement after this ?
The most important/easiest pruning method to implement would then be the null move heuristic.
EDIT: Actually even before that improve your move ordering, this will give you the biggest improvement and is necessary for alpha / beta to show its advantage over mini/max.
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 11:18 am
by SMIRF
While I am also just about to optimize my quiescence search, it would be helpful to know, whether there are common testing examples.
Those examples should provide their node expansions' count at a given alpha/beta range. This would help to review the quality of the used move sort and the correctness of the quiescence procedure.
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 5:20 pm
by Sven
Hi Mahmoud,
since I find mixing fail-soft and fail-hard confusing (you can read more about it in the CPW if you want to know the difference) I prefer to write the search based on fail-soft only. A very basic alpha-beta negamax search with quiescence search could look like this:
Code: Select all
int qSearch(int alpha, int beta)
{
int bestScore = evaluate();
if (bestScore >= beta) return bestScore;
generateLegalQSMoves();
for (all moves) {
makeMove(move);
int score = -qSearch(-beta, -Max(alpha, bestScore));
unmakeMove(move);
if (score > bestScore) {
bestScore = score;
if (bestScore >= beta) break;
}
}
return bestScore;
}
int search(int alpha, int beta, int depthLeft, int height)
{
if (depthLeft == 0) return qSearch(alpha, beta);
generateLegalMoves();
if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
int bestScore = -INF;
for (all moves) {
makeMove(move);
int score = -search(-beta, -Max(alpha, bestScore), depthLeft - 1, height + 1);
unmakeMove(move);
if (score > bestScore) {
bestScore = score;
if (bestScore >= beta) break;
if (height == 0 && bestScore > alpha) {
bestRootMove = move;
}
}
}
return bestScore;
}
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 8:37 pm
by Henk
Sven Schüle wrote:Hi Mahmoud,
since I find mixing fail-soft and fail-hard confusing (you can read more about it in the CPW if you want to know the difference) I prefer to write the search based on fail-soft only. A very basic alpha-beta negamax search with quiescence search could look like this:
Code: Select all
int qSearch(int alpha, int beta)
{
int bestScore = evaluate();
if (bestScore >= beta) return bestScore;
generateLegalQSMoves();
for (all moves) {
makeMove(move);
int score = -qSearch(-beta, -Max(alpha, bestScore));
unmakeMove(move);
if (score > bestScore) {
bestScore = score;
if (bestScore >= beta) break;
}
}
return bestScore;
}
int search(int alpha, int beta, int depthLeft, int height)
{
if (depthLeft == 0) return qSearch(alpha, beta);
generateLegalMoves();
if (numberOfLegalMoves == 0) return (isInCheck() ? -(INF - height) : 0);
int bestScore = -INF;
for (all moves) {
makeMove(move);
int score = -search(-beta, -Max(alpha, bestScore), depthLeft - 1, height + 1);
unmakeMove(move);
if (score > bestScore) {
bestScore = score;
if (bestScore >= beta) break;
if (height == 0 && bestScore > alpha) {
bestRootMove = move;
}
}
}
return bestScore;
}
When can we expect a tutorial "How to create a top chess engine in 24 days" ?
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 8:49 pm
by mar
Henk wrote:When can we expect a tutorial "How to create a top chess engine in 24 days" ?
I think for some "How to fix bugs" would be even more useful
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 8:51 pm
by Henk
mar wrote:Henk wrote:When can we expect a tutorial "How to create a top chess engine in 24 days" ?
I think for some "How to fix bugs" would be even more useful
Only amateurs like me don't use a version control system.
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 9:47 pm
by tpetzke
Only amateurs like me don't use a version control system.
You don't need one. A random mover like is best developed with random changes.
Re: Search algorithm in it's simplest forum
Posted: Thu Feb 26, 2015 10:32 pm
by cdani
Henk wrote:Only amateurs like me don't use a version control system.
I use a text file to take note of the changes, and I copy all the versions in a folder.