Author: Robert Hyatt
Date: 06:20:38 04/11/00
Go up one level in this thread
On April 11, 2000 at 05:41:04, Severi Salminen wrote:
>Hi!
>
>The next is from www.xs4all.nl/~verhelst/chess/search.html
>It is the principal of negamax algorithm. But I don't quite understand it. If we
>make, say, 1 ply search (white to move), then the evaluation is negated and
>compared to the best value found so far. But bigger evaluation is better for
>white and now bigger is negated and so it becomes smaller. So better evaluation
>doesn't increase the value of best. What am I missing?
if you think of ply 1, 3, 5, ..., 2N+1 as being "max" nodes where the best score
is taken and backed up, and plyh 2, 4, ..., 2N as being "min" nodes where the
worst (smallest) score is taken and backed up. Then think about this:
v=max(s1,s2,s3,s4,s5,s6,...) will return the largest score, right?
v=max(-s1,-s2,-s3,-s4,-s5,-s6,...) will return the smallest score, right?
so if you _really_ return -v, if you are at a max node, you return the - score
back to a min node for testing as above. If you are at a min node, you return
- - score back to a max node for testing.
The point is that min and max now look exactly the same, always choosing the
largest score... eliminates 1/2 of the usual testing that is done for the min
side but not the max side and vice-versa...
>
>int NegaMax (pos, depth)
>{
> if (depth == 0) return Evaluate(pos);
> best = -INFINITY;
> succ = Successors(pos);
> while (not Empty(succ))
> {
> pos = RemoveOne(succ);
> value = -NegaMax(pos, depth-1);
> if (value > best) best = value;
> }
> return best;
>}
>
>Severi
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.