Author: Alessandro Damiani
Date: 01:48:08 10/20/02
Go up one level in this thread
On October 20, 2002 at 00:34:04, Nagendra Singh Tomar wrote:
>On October 19, 2002 at 23:45:20, Antonio Dieguez wrote:
>
>>On October 19, 2002 at 22:02:53, Nagendra Singh Tomar wrote:
>>
>>>On October 19, 2002 at 21:22:57, Antonio Dieguez wrote:
>>>
>>>>
>>>>>I believe we do qsearch to see if there are any hidden surprises (a solution for
>>>>>the horizon effect). So the objective of doing a qsearch is to find whether the
>>>>>current positions score is really what we think or whether there is a big
>>>>>surprise which pulls it down drastically. So if we assume that the score is at
>>>>>least the static score then we are losing the advantages of qsearch, the reason
>>>>>at first place why we opted to do a qsearch
>>>>
>>>>'cuse me.
>>>>
>>>>what happens if there are no captures, you return the static score (I
>>>>suppose...) and clearly if the side to move has available captures then the
>>>>thing could only get cooler for it
>>>
>>>Not always..
>>>At least not for forced-capture cases. let me explain forced capture. Suppose at
>>>the end of the extensive search (qsearch root)
>>>we have our rook(trapped or pinned to a higher value piece so that it is
>>>immobile) and suppose the
>>>opponent's pawn is attacking it. The attacking pawn is also guarded by another
>>>pawn. The only way for us to avoid losing our rook is to capture the atatcking
>>>pawn by say our knight. This is a forced capture. now in the next move the
>>>opponents other pawn will take our knight so we lose our knight to the
>>>opponent's pawn. In this case the capture is leading to a worse score than the
>>>static score.
>>>We can have many such cases during the search. Rook and pawn are just symbolic
>>>of a high value and low value piece.
>>
>>you are completely right in what you mean. Personally I get out of the qsearch
>>in a few cases only sometimes when a pawn is attacking a piece, or a horse
>>attacking a rook or queen, or a bishop at.a rook on a corner, or a rook at.a
>>queen at b2/g2/b7/g7. That is something minimal to do though, I suposse there is
>>nothing so great to do in the qsearch anyway because that is the reason for the
>>main fullpowered search. At least one could add all the cases when there are a
>>piece enprise, but I didn't like that when I tried(so often not affecting in
>>nothing, except taking more time to reach depth)
>>
>>seeyou.
>
>
>All of that botheration can be taken care of just by being pessimistic and not
>assume that the static score is the best one (this is what I think Alessandro
>meant). So just if we remove the line as shown below
>
>if(score > alpha)
> {
> if(score >= beta)
> return score;
> alpha = score; /* remove this line */
> }
>
>we can have a pessimistic (and so more accurate) qsearch.
>
no. in my previous post I saved time by referencing Don Beals work with
null-move in the qsearch. To be clear, here is his algorithm out of my mind:
int qsearch(int lower, int upper)
{
// we are pessimistic: our best score is the enemy threat
make(null-move);
best= -captsearch(-upper, -lower);
unmake(null-move);
// no need to score better than the upper bound:
if (best>=upper)
return best;
// improve our best score by searching moves:
for each tactical move m do {
make(m);
value= -qsearch(-upper, -best);
unmake(m);
if (value>best) {
if (value>=upper)
return value;
best= value;
};
};
return best;
}
with
int captsearch(int lower, int upper)
{
// we are optimistic: our best score is the static score (no enemy threat)
best= staticEval();
// no need to score better than the upper bound:
if (best>=upper)
return best;
// improve our best score by searching moves:
for each capture m do {
make(m);
value= -captsearch(-upper, -best);
unmake(m);
if (value>best) {
if (value>=upper)
return value;
best= value;
}
};
return best;
}
Explanation:
- qsearch searches tactical moves. these are not just captures, but also threats
to other pieces like knight attacks rook or checks. if all of them are searched
or not is up to the programmer.
- in qsearch() and captsearch() a move is searched with the window (best, upper)
and not with (lower, upper)! this means, we are considering the enemy threat in
the search, until there is no one (in the sense that it doesn't hurt us enough:
score of enemy threat >= upper).
- captsearch is a pure capture search. only captures are searched. same here: if
all of them are searched or not is up to the programmer.
- just if you didn't know it: make(null-move) is aquivalent to change side to
move. the inverse is then also clear.
- I didn't add the code to avoid making a null-move when in check to simplify
the algorithm. in the end we have something like the following in qsearch.
if (inCheck)
best= -MATE+ply;
else {
make(null-move);
best= -captsearch(-upper, -lower);
unmake(null-move);
if (best>=upper)
return best;
}
So, pessimistic means: set our initial best score to the score of the null-move,
which is the enemy threat.
If you didn't know null-move I suggest you read about this topic. Here is a good
link: http://www.seanet.com/~brucemo/topics/topics.htm
Alessandro
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.