Evaluating every node?

[Greg Strong]

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

[hgm]

Joker does evaluate every node, to decide if he is going to do a null-move search.

[Bill Rogers]

My first chess program was only a one ply critter so I evaluated every move/node. Later when it could search 2 or more plys I stil evaluated every move/node. All I can say is that it works for me.
Bill

[jdart]

It's not common to do a full eval at every node (outside of the q-search).

However, many programs (Glaurung for example) do an approximate eval - for example material + piece/square tables - to do things like futility pruning and also to do eval-based null move reductions.

Arasan actually does a full eval for these functions but evaluations are cached in a hash table so it is not paying the full cost of eval at each node.

--Jon

[gladius]

I do an eval at every non-PV node in my program. This information (as with the others) is used to help in null-move, razoring and futility pruning. I prefer to use the full evaluation, as it's not too big of a speed hit, and the passed pawn/king safety terms can get pretty large for me. I'm surprised Glaurung throws those away, as I'm pretty sure they can be much larger than my program.

[Tord Romstad]

I do an eval at every non-PV node in my program. This information (as with the others) is used to help in null-move, razoring and futility pruning. I prefer to use the full evaluation, as it's not too big of a speed hit, and the passed pawn/king safety terms can get pretty large for me. I'm surprised Glaurung throws those away, as I'm pretty sure they can be much larger than my program.

I always use the full static eval in futility pruning. Moreover, I add the king attack score for the side not to move to the futility pruning margin, because it sometimes happens that a single small capture can eliminate the entire attack, and therefore improve the score by far more than the value of the captured piece.

I only use the approximate eval for deciding whether to do null move search, and for deciding whether to do a razoring search. Both of these seem rather safe to me, because the approximate eval is not used directly for any sort of pruning, but only to decide whether some pruning techniques are worth trying at this node.

By the way, in all my program versions up to Glaurung 1.2.1, I always evaluated all internal nodes. When I started programming, I assumed that everybody did so, and I was very surprised when I discovered that it was not so. I still think evaluating all nodes is the most natural approach; I regard my current leaf-node-only eval as nothing more than a long-lasting experiment to find out just how far it is possible to get without evaluating internal nodes.

Tord

[Stan Arts]

Even if you use evaluation to make lots of decisions, you should still hardly evaluate every node, mostly because you try to make decisions/conditions in order of speed. fe. at every node in full width search I know if the side to move is in check, and when in check is often a reason not to do any pruning or reduction at this node. Evaluation (very costly) is often my very last condition.

So even when you use evaluations all over the place, you still shouldn't do them in advance, but judge at each case if it's absolutely nescesary. (in a lot of cases it isn't, and save your program a huge speeddrop)

Stan

[Bill Rogers]

Sorry Stan but I do not agree with you at all. I evaluate every move and if during that I discover that my king is in check I eliminate that move from the rest. After completing the first ply, I then sort the moves based up their initial evals, grab the best one and create the next ply in which every move is also evaluated, etc. I have found that it is almost as fast as going to depth first and then evaluatiing the entire board. In fact the second method sometime requires me to examine some moves to a certain dept that should not have even been considered in the first place.
All I can say to you is if you are happy in the way that you do it then be happy as for me a some others we like the way we do it as it appears to work just fine for us.
Bill

[gladius]

I always use the full static eval in futility pruning. Moreover, I add the king attack score for the side not to move to the futility pruning margin, because it sometimes happens that a single small capture can eliminate the entire attack, and therefore improve the score by far more than the value of the captured piece.

I only use the approximate eval for deciding whether to do null move search, and for deciding whether to do a razoring search. Both of these seem rather safe to me, because the approximate eval is not used directly for any sort of pruning, but only to decide whether some pruning techniques are worth trying at this node.

By the way, in all my program versions up to Glaurung 1.2.1, I always evaluated all internal nodes. When I started programming, I assumed that everybody did so, and I was very surprised when I discovered that it was not so. I still think evaluating all nodes is the most natural approach; I regard my current leaf-node-only eval as nothing more than a long-lasting experiment to find out just how far it is possible to get without evaluating internal nodes.

Tord

Razoring especially I noticed a pretty huge difference between using full eval. and approximate eval. On a few positions it made tree size differences of 3-4x worse for using approximate eval. It saves me roughly 45kn/s or so using the approx. eval, but the tree size reduction is more than worth it.

Of course our razoring implementations may be vastly different. And yours is probably better as well .

[Stan Arts]

Sorry Stan but I do not agree with you at all.

Where does it say how I do things and how does it divide the computerchesscommunity into a me and you/us?

Advice specially true for computerchess: Delay things till you absolutely have to do them.

Ofcourse it's ok to use evaluation to help make intelligent decisions, and so do I. What I said is that you should put other faster conditions first, so that in practise you might be able to skip a lot of calls to evaluation, instead of always calling evaluation at every internal node when you might not use the information.

Stan