Evaluating every node?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

Evaluating every node?

Post by Greg Strong » Sat Jan 03, 2009 11:03 pm

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

User avatar
hgm
Posts: 23718
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Evaluating every node?

Post by hgm » Sat Jan 03, 2009 11:17 pm

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

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Evaluating every node?

Post by Bill Rogers » Sun Jan 04, 2009 5:46 am

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
Posts: 3824
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Evaluating every node?

Post by jdart » Sun Jan 04, 2009 3:22 pm

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
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Re: Evaluating every node?

Post by gladius » Mon Jan 05, 2009 6:13 am

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
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: Evaluating every node?

Post by Tord Romstad » Mon Jan 05, 2009 7:28 am

gladius wrote: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

Re: Evaluating every node?

Post by Stan Arts » Mon Jan 05, 2009 9:58 pm

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

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Evaluating every node?

Post by Bill Rogers » Mon Jan 05, 2009 11:21 pm

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
Posts: 538
Joined: Tue Dec 12, 2006 9:10 am

Re: Evaluating every node?

Post by gladius » Tue Jan 06, 2009 7:54 am

Tord Romstad wrote: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

Re: Evaluating every node?

Post by Stan Arts » Tue Jan 06, 2009 12:48 pm

Bill Rogers wrote: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

Post Reply