Evaluating every node?

[Don]

Hi all!

I was reading a paper by the author of Rebel about how his program worked (don't know how out-of-date the info is) but one of the unusual things he did was perform an evaluation of every node in the search. He described a couple of benefits such as using the info for better move ordering, deciding when a null search might be pointless, and deciding when it would be safe to perform a lazy eval at frontier nodes and in qsearch.

So, I was wondering. Does anyone here do an evaluation of every node presently? And, if so, what do you see as the benefit?

Thanks!
Greg

I don't believe Rebel really does fully evaluate every node. He goes on to later talk about the big savings he gets with lazy evaluation - and my understanding is that he has a cheap incremental evaluation that gives him an approximate score - I think that is the evaluation he is talking about.

[Bill Rogers]

I think Don is correct. It is my understanding that he generates piece square points for each move and if the move includes a capture that is also included. These are then used to order the moves before execution or deeper searches.
Bill

[Sven]

Hi all!

I was reading a paper by the author of Rebel about how his program worked (don't know how out-of-date the info is) but one of the unusual things he did was perform an evaluation of every node in the search. He described a couple of benefits such as using the info for better move ordering, deciding when a null search might be pointless, and deciding when it would be safe to perform a lazy eval at frontier nodes and in qsearch.

So, I was wondering. Does anyone here do an evaluation of every node presently? And, if so, what do you see as the benefit?

Thanks!
Greg

I don't believe Rebel really does fully evaluate every node. He goes on to later talk about the big savings he gets with lazy evaluation - and my understanding is that he has a cheap incremental evaluation that gives him an approximate score - I think that is the evaluation he is talking about.

I think Don is correct. It is my understanding that he generates piece square points for each move and if the move includes a capture that is also included. These are then used to order the moves before execution or deeper searches.
Bill

Don and Bill, you believe and think but maybe you have not recognized the relevant pieces of Ed's description about Rebel. It is right that Rebel (like some other current engines, too), according to Ed's description, has a piece-square score available that is incrementally updated. But that is not the point here. In fact Rebel

a) fully evaluates each node of the main search, above the horizon, and
b) under some given circumstances uses Lazy Evaluation within QS (at horizon and below) to avoid full eval there where possible.

While b) is mainly for speed, a) is especially important for Rebel's selective search concept but also for other things, as Greg mentioned.

The following is quoted from http://members.home.nl/matador/chess840.htm which is obviously the document Greg referred to. Note: Copyright © 1984 - 2009 Ed Schröder. [I hope it's ok that I quote it here, otherwise I apologize and kindly ask for the mods to take an appropriate action that preserves the main intent of my posting.]

When describing the problem of finding a good MARGIN for LazyEval:

Here is the compromise I found for the problem, it works very well for REBEL, but you must have the score of the depth-1 EVAL at your disposal.

The default value of MARGIN in REBEL is 0.50, however the difference of I_SCORE - SCORE of the depth-1 evaluation is added to MARGIN. I_SCORE - SCORE of one ply back in the tree in most cases will correctly represent what's going on on the board, its value is highly reliable and thus MARGIN is updated with this value.

This is just another example how useful it can be to do EVAL on every ply in the main search, in this case it solves the main drawback of LE while keeping MARGIN very low.

And later on:

Selective Search Techniques in REBEL (concept)

The first thing you will need to keep in mind is that REBEL's way of doing Selective Search demands doing a complete evaluation of each position in the Main-Search till horizon_depth-1.

You simply need to have decent information about the position before you can decide to prune a complete subtree, but let's start... take a deep breath first...

Sven

[Don]

Don and Bill, you believe and think but maybe you have not recognized the relevant pieces of Ed's description about Rebel. It is right that Rebel (like some other current engines, too), according to Ed's description, has a piece-square score available that is incrementally updated. But that is not the point here. In fact Rebel

a) fully evaluates each node of the main search, above the horizon, and
b) under some given circumstances uses Lazy Evaluation within QS (at horizon and below) to avoid full eval there where possible.

While b) is mainly for speed, a) is especially important for Rebel's selective search concept but also for other things, as Greg mentioned.

The following is quoted from http://members.home.nl/matador/chess840.htm which is obviously the document Greg referred to. Note: Copyright © 1984 - 2009 Ed Schröder. [I hope it's ok that I quote it here, otherwise I apologize and kindly ask for the mods to take an appropriate action that preserves the main intent of my posting.]

When describing the problem of finding a good MARGIN for LazyEval:

Here is the compromise I found for the problem, it works very well for REBEL, but you must have the score of the depth-1 EVAL at your disposal.

The default value of MARGIN in REBEL is 0.50, however the difference of I_SCORE - SCORE of the depth-1 evaluation is added to MARGIN. I_SCORE - SCORE of one ply back in the tree in most cases will correctly represent what's going on on the board, its value is highly reliable and thus MARGIN is updated with this value.

This is just another example how useful it can be to do EVAL on every ply in the main search, in this case it solves the main drawback of LE while keeping MARGIN very low.

And later on:

Selective Search Techniques in REBEL (concept)

The first thing you will need to keep in mind is that REBEL's way of doing Selective Search demands doing a complete evaluation of each position in the Main-Search till horizon_depth-1.

You simply need to have decent information about the position before you can decide to prune a complete subtree, but let's start... take a deep breath first...

Sven

Ok, I stand corrected then. I did not fully digest what he was doing and just skimmed. This is useful information to know, thanks for bringing it to our attention.