calling eval() at all depths in the search tree?

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.
Post Reply
User avatar
silentshark
Posts: 274
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

calling eval() at all depths in the search tree?

Post by silentshark » Sat May 01, 2010 5:26 pm

Hello all,

My program has only ever called its evaluation function at the tips of the search tree.

Other programs (Rebel is one example) seem to call the eval function at every depth in the tree. I've been experimenting with this, and can see some benefits.

The main one for me has been making "smarter" pruning decisions. I've long used a form of forward pruning, where if the material value is way above beta, and we're near the leaves of the tree, we take a risk and prune. This works quite well, but sometimes prunes away really interesting lines, for example where one side sacs a pawn or two (or a piece?!) for a king attack. With the benefit of having the positional score, I can be smarter about this kind of pruning..

There is also a downside, though in a performance hit.

I need more test games to see if this is a win overall.

Anyhow, what are others doing these days? Is calling eval() throughout the tree just the done thing?

Regards,
Tom

Jorge Garcia
Posts: 61
Joined: Wed Oct 21, 2009 11:50 pm
Location: Barcelona Spain

Re: calling eval() at all depths in the search tree?

Post by Jorge Garcia » Sat May 01, 2010 7:35 pm

Hi,
It's interesting because you do accurate pruning that way, but the problem is that calling eval at all depths is very time costing. Rebel used with success null move pruning for the first 7-8 plies and then static evaluation pruning for the nexts.
I've tested something similar in the past with toga, but the downside of performance was a great handicap.
I think the idea could work, but we need a fast way to evaluate the board to avoid the downside of performance.
Best Regards

User avatar
silentshark
Posts: 274
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: calling eval() at all depths in the search tree?

Post by silentshark » Sat May 01, 2010 8:43 pm

Jorge Garcia wrote:Hi,
It's interesting because you do accurate pruning that way, but the problem is that calling eval at all depths is very time costing. Rebel used with success null move pruning for the first 7-8 plies and then static evaluation pruning for the nexts.
I've tested something similar in the past with toga, but the downside of performance was a great handicap.
I think the idea could work, but we need a fast way to evaluate the board to avoid the downside of performance.
Best Regards
I was pretty surprised at the performance hit. At least for my engine, it wasn't as massive as I feared - it was like a 20-30% slowdown in nps. Infer from that what you will, maybe my eval sucks!

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

Re: calling eval() at all depths in the search tree?

Post by hgm » Sat May 01, 2010 9:45 pm

85% of my nodes are QS nodes. So calling eval in the other nodes as well is not a big deal...

User avatar
Greg Strong
Posts: 388
Joined: Sun Dec 21, 2008 5:57 pm
Location: Washington, DC

Re: calling eval() at all depths in the search tree?

Post by Greg Strong » Sun May 02, 2010 12:36 am

Hey, Tom

With Quadrox, I do basically this too. I use a full eval in Q-Search, and a slightly lighter "quick" eval in the main part of the search, but it's still pretty heavy. Most programs I've looked at (like Stockfish) use a very, very light "quick" eval that is little more than the material balance. My quick eval determines full mobility for all pieces, which is expensive, but it allows me to know which squares are attacked by which side for better pruning decisions as you suggest. It definitely helps for pruning decisions. I also use it for LMR - if the move to be reduced hangs the moving piece, I reduce two ply instead of just one. The definitely helps, as long as you don't do it with pawns.

Does the benefit justify the extra cost? Excellent question, and your timing is perfect, as just last night I started putting in #defines so that I can build the program both ways for testing :) Earliest tests seem to show that the extra cost is justified, _but_ it should be noted that the program has always had this extra cost and information during the last couple of years of tweeking and optimizing paramters. It could well be that with a different set of values the faster version is better... I hope to devote more resources to it but there's so many things I want to test.

Glad to see that someone else is doing this. Asside from Rebel, I didn't know of any other programs that attempted to perform a heavy eval at every node and try to make it pay off through use of the extra information it generates.

Cheers,
Greg

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: calling eval() at all depths in the search tree?

Post by mcostalba » Sun May 02, 2010 6:04 am

Greg Strong wrote:Hey, Tom

With Quadrox, I do basically this too. I use a full eval in Q-Search, and a slightly lighter "quick" eval in the main part of the search, but it's still pretty heavy. Most programs I've looked at (like Stockfish) use a very, very light "quick" eval that is little more than the material balance.
This was until version 1.7 ;-)

User avatar
silentshark
Posts: 274
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: calling eval() at all depths in the search tree?

Post by silentshark » Sun May 02, 2010 8:00 am

mcostalba wrote:
Greg Strong wrote:Hey, Tom

With Quadrox, I do basically this too. I use a full eval in Q-Search, and a slightly lighter "quick" eval in the main part of the search, but it's still pretty heavy. Most programs I've looked at (like Stockfish) use a very, very light "quick" eval that is little more than the material balance.
This was until version 1.7 ;-)
ok, so now SF is doing a full eval throughout the tree? I know, I could just check the source..

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: calling eval() at all depths in the search tree?

Post by zamar » Sun May 02, 2010 1:03 pm

silentshark wrote:
ok, so now SF is doing a full eval throughout the tree?
Yes (except when in check).
Joona Kiiski

yoshiharu
Posts: 56
Joined: Sat Nov 11, 2006 10:14 pm

Re: calling eval() at all depths in the search tree?

Post by yoshiharu » Thu May 06, 2010 8:34 am

Greg Strong wrote: Glad to see that someone else is doing this. Asside from Rebel, I didn't know of any other programs that attempted to perform a heavy eval at every node and try to make it pay off through use of the extra information it generates.
For what it's worth, there's also me with my engine ;-)
Anyways, when I was thinking to take it off (I already had a compile switch),
I was reinforced in the decision of keeping it instead by a post of Tord himself on this board, IIRC, that was pretty convincing.

For improving the speed, I use an evaluation cache, and I must say that the speed difference is very tiny.
Consider also that the number of internal nodes in normal search is dominated by the number of leaves/nodes-in-qsearch...

Cheers, Mauro

Post Reply