Author: Alessandro Damiani
Date: 14:13:18 11/11/04
Go up one level in this thread
On November 11, 2004 at 15:46:18, milix wrote:
>On November 11, 2004 at 15:37:47, Alessandro Damiani wrote:
>
>>On November 11, 2004 at 14:06:53, milix wrote:
>>
>>>The below pseudocode (slightly modified) comes from the paper
>>>'Fail High Reductions' of Rainer Feldmann, 1996
>>>
>>>int FHR_negascout(alpha, beta, depth)
>>>{
>>> e = evaluate();
>>> t = threat();
>>> d = depth;
>>> fh_node = false;
>>> if (!in_check AND alpha==beta-1 AND e-t >= beta) {
>>> fh_node = true;
>>> d = d-1;
>>> }
>>> if (d <= 0) return quiescent(alpha, beta);
>>> N = generate_moves();
>>> low = alpha; high = beta; best = -INF;
>>> for_all_moves m[i], i=1..N {
>>> make_move(m[i]);
>>> score = -FHR_negascout(-high, -low, d-1);
>>> if (score>low AND score<beta AND i>1) {
>>> score = -FHR_negascout(-beta, -score, depth-1);
>>> }
>>> undo_move(m[i]);
>>> low = max(low,score); best = max(best,score);
>>> if (best >= beta) return best;
>>> high = low+1;
>>> }
>>> return best;
>>>}
>>>
>>>My question is about the condition:
>>> if (score>low AND score<beta AND i>1)
>>>
>>>Why score>low and i>1? I think that we expect this node to fail high,
>>>so if it didn't we must research. Same for the first move.
>>>So if the above are true the condition of research must be:
>>> if ((fh_node AND score<beta) OR (score>low AND score<beta AND i>1))
>>>
>>>Am I missing something?
>>>
>>
>>NegaScout:
>>i = 1: this is the first move. it is searched with a full window.
>>i > 1: for the remaining moves the null-window test is performed. if the score
>>is better than the current best score then the move is researched with a full
>>window.
>>
>>One invariant is: alpha <= low
>>With this, score > low implies score > alpha.
>>
>>Alessandro
>
>Hi Alessandro
>
>My question is: are we really need score > low(alpha) and score<beta to research
>or just score<beta? Remember this node is a fail high node.
A fail-high reduction is only performed in the case of
alpha == beta -1.
In most cases this is when a null-window test is performed. Since NegaScout
researches a move with the full window if it is better than the current best
move, the research of a fail-high node is already done to the non-reduced depth.
Therefore, there is no need to keep track of a fail-high node through the
variable fh_node.
Alessandro
This page took 0 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.