quiescence
Noah Roberts
of chess engines and now I have some questions (I thought I understood
before).
In this discussion it was explained to me that the quiescence stops
before some captures (ie when one color would want to stop in an
exchange). This makes total sence to me, but most sites on the Internet
that describe the quiescence search explain it using all captures at the
very least. This is how I implemented mine and it would explain why my
engine became weaker when quiescence was used. Could someone shed some
light on this discrepency?
Also, how are quiescence searches implemented that stop before a bad
capture without implementing something similar to SEE?
NR
Robert Hyatt
> NR
If you look at most quiesce() functions, you see something
like this:
int Quiesce(args) {
alpha=Evaluate(args);
search whatever captures you want here;
}
The idea is that you first evaluate the position if you do
nothing (stand pat). Then you use a capture search to see if
making a capture can _raise_ that alpha bound any. If the
captures are bad, you will choose the score produced by "standing
pat" and there you go...
--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170
Gian-Carlo Pascutto
"Noah Roberts" <nrob...@dontemailme.com> wrote in message
news:3F6BBABB...@dontemailme.com...
> In rec.games.chinese-chess we started discussing the quiescence search
> of chess engines and now I have some questions (I thought I understood
> before).
>
> In this discussion it was explained to me that the quiescence stops
> before some captures (ie when one color would want to stop in an
> exchange). This makes total sence to me, but most sites on the Internet
> that describe the quiescence search explain it using all captures at the
> very least. This is how I implemented mine and it would explain why my
> engine became weaker when quiescence was used. Could someone shed some
> light on this discrepency?
Investigating all captures makes no sense. Why take a pawn with queen
if the opponent just captures your queen on the next ply?
> Also, how are quiescence searches implemented that stop before a bad
> capture without implementing something similar to SEE?
Via a 'standpat' option. You check your static evaluation. If it's > beta,
'doing nothing' (i.e. not capturing) is already good enough and you cut.
If not, you set alpha to the static evaluation score, because at the very
least you can do nothing (not capture) instead of playing a losing capture
move.
--
GCP
Noah Roberts
> If you look at most quiesce() functions, you see something
> like this:
>
> int Quiesce(args) {
> alpha=Evaluate(args);
> search whatever captures you want here;
> }
>
> The idea is that you first evaluate the position if you do
> nothing (stand pat). Then you use a capture search to see if
> making a capture can _raise_ that alpha bound any. If the
> captures are bad, you will choose the score produced by "standing
> pat" and there you go...
At
http://www.gamedev.net/reference/programming/features/chess5/page3.asp
it is said:
"You can simulate this situation by inserting the null move into the
quiescence search: if, in a given position during quiescence search, it
is revealed that the null move is better than any capture, you can
assume that continuing with captures from this position is a bad idea,
and that since the best move is a quiet one, this is a position where
the evaluation function itself should be applied!"
What is your take on the above?
Gian-Carlo Pascutto
> "You can simulate this situation by inserting the null move into the
> quiescence search: if, in a given position during quiescence search, it
> is revealed that the null move is better than any capture, you can
> assume that continuing with captures from this position is a bad idea,
> and that since the best move is a quiet one, this is a position where
> the evaluation function itself should be applied!"
>
> What is your take on the above?
'Nullmove' is just a very stupid and confusing way to say 'standpat'
in the above text.
--
GCP
Noah Roberts
Actually they are making null moves and continuing a quiescence search
on the resulting board.
I would think this would work differently than simply alpha = eval() and
am interested in what better developers than I have to say about this
difference.
>
> --
> GCP
>
>
Gian-Carlo Pascutto
> Gian-Carlo Pascutto wrote:
> > "Noah Roberts" <nrob...@dontemailme.com> wrote in message
> > news:3F6C8311...@dontemailme.com...
> >
> >
> >>"You can simulate this situation by inserting the null move into the
> >>quiescence search: if, in a given position during quiescence search, it
> >>is revealed that the null move is better than any capture, you can
> >>assume that continuing with captures from this position is a bad idea,
> >>and that since the best move is a quiet one, this is a position where
> >>the evaluation function itself should be applied!"
> >>
> >>What is your take on the above?
> >
> >
> > 'Nullmove' is just a very stupid and confusing way to say 'standpat'
> > in the above text.
>
> Actually they are making null moves and continuing a quiescence search
> on the resulting board.
They are not, please reread the text.
--
GCP
Dieter Buerssner
> If you look at most quiesce() functions, you see something
> like this:
>
> int Quiesce(args) {
> alpha=Evaluate(args);
> search whatever captures you want here;
> }
This looks a bit over simplified to be understandable (at least for me).
I could say, it looks wrong. You code snippet can actually decreasy alpha
(and thereby causing lots of unneeded overhead - sort of a half minimax
search).
My try (in pseudo code)
int Qsearch(int alpha, int beta)
{
int score = evaluate(); /* Setting alpha here is not wanted */
/* The stuff inside the if, is the main difference to a normal
non quiescent search. Leaving aside special cases without any
legal moves (mate or stalemate), which can be ignored in qsearch. */
if (score > alpha)
{
alpha = score;
if (score >= beta)
return score; /* or beta */
}
for (all "capture" moves)
{
Makemove();
score = -qsearch(-beta, -alpha);
UnmakeMove();
if (score > alpha)
{
alpha = score;
if (score >= beta)
return score; /* or beta */
}
}
return alpha; /* fail hard variant. Fail soft would need to
keep track of another var "bestscore" */
}
Regards,
Dieter
Pham Hong Nguyen
> capture without implementing something similar to SEE?
>
> NR
Here is the skeleton of queiescence taken from TSCP (snip some lines).
The implementation of stopping is the lines of comparision: if
(x>=beta), it means your current status or move is so good, no need to
examine other moves and your rival is probably to stop his previous
capture (say, capture a your pawn) to avoid your current so good
capture (say, capture a his queen), he may use another move/capture
instead.
int quiesce(int alpha,int beta)
{
/* check with the evaluation function */
x = eval();
if (x >= beta) /* Your current status is so good */
return beta;
if (x > alpha)
alpha = x;
gen_caps();
/* loop through the moves */
for (i = first_move[ply]; i < first_move[ply + 1]; ++i) {
makemove(gen_dat[i].m.b);
x = -quiesce(-beta, -alpha);
takeback();
if (x > alpha) {
if (x >= beta) /* Your current move is so good */
return beta;
alpha = x;
}
}
return alpha;
}
Hope that helps,
Pham