Main
Date: 23 Jan 2007 23:09:43
From: Loomis Philanthrope
Subject: update material evaluation incrementally?
I am wondering if the top chess programs calculate material values only
at the terminal nodes where the evaluation function is called, or do
they keep a running count of material at each move. Is there a
significant difference in speed between the two methods?

Has anyone here experimented with each method and found there is or
isn't a real difference between them?

Thanks,
Loomis




 
Date: 01 Feb 2007 11:38:34
From: Ian Osgood
Subject: Re: update material evaluation incrementally?
On Jan 24, 7:24 am, Loomis Philanthrope
<[email protected] > wrote:
> David Richerby wrote:
> > I've not experimented but the advantage of running counts seems to be
> > obvious and significant, without adding a significant amount of code.
>
> This is what I thought as well. Especially since 30% of my engine's time
> is spent in the eval function and a fair portion of that is spent
> administering the loop over the piece list and switching on piece type.
> I figured if I eliminated that loop in favor of a few subtractions and
> additions as pieces are captured and un-captured there would be a
> difference.
>
> But after I made the changes, the engine played the same moves in nearly
> the same amount of time. It seemed quite odd to me, so I wanted to know
> if anyone else had tried this and what results they got.
>
> Loomis

In my simple TSCP-derived program, incremental material and pawn
evaluation sped up the search by over 30%. It may depend on how
complex your evaluation is (what proportion the material calculation
is to the rest of your eval terms). The more complex your evaluation,
the less benefit you get from simple incremental updates.

For further insight, you should ask again on the Computer Chess Club
(http://www.talkchess.com/).

Ian



  
Date: 02 Feb 2007 10:15:20
From: David Richerby
Subject: Re: update material evaluation incrementally?
Ian Osgood <[email protected] > wrote:
> In my simple TSCP-derived program, incremental material and pawn
> evaluation sped up the search by over 30%. It may depend on how
> complex your evaluation is (what proportion the material calculation
> is to the rest of your eval terms). The more complex your
> evaluation, the less benefit you get from simple incremental
> updates.

As I said before, in many cases, material alone is enough to cause a
cut-off. This means that, by evaluating material separately, you
often don't have to call the evaluation function at all.


Dave.

--
David Richerby Broken Umbrella (TM): it's like an
www.chiark.greenend.org.uk/~davidr/ umbrella but it doesn't work!


 
Date: 24 Jan 2007 09:40:51
From: David Richerby
Subject: Re: update material evaluation incrementally?
Loomis Philanthrope <[email protected] > wrote:
> I am wondering if the top chess programs calculate material values
> only at the terminal nodes where the evaluation function is called,
> or do they keep a running count of material at each move. Is there a
> significant difference in speed between the two methods?

I imagine they keep a running count -- my engine certainly did, but it
was hardly top-class!

Keeping a running count means that, for each leaf on the tree, you
have to do two operations for each capture in the line leading to the
leaf (one to decrease the material count when making the move and one
to increase it again when the move is un-made). But that's worst-case
because some of those operations will be shared between different
leaves. Counting at each leaf means you have to do one operation for
each piece at each leaf. That has to be much more expensive.

Also, there's the point that the material count alone will very often
be enough to cut off the search without even looking at the rest of
the evaluation function.


> Has anyone here experimented with each method and found there is or
> isn't a real difference between them?

I've not experimented but the advantage of running counts seems to be
obvious and significant, without adding a significant amount of code.
Of course, many things that are `obviously true' about chess engines
turn out to be false. :-)


Dave.

--
David Richerby Permanent Mouldy Dish (TM): it's like
www.chiark.greenend.org.uk/~davidr/ a fine ceramic dish but it's starting
to grow mushrooms and it'll be there
for ever!


  
Date: 24 Jan 2007 10:24:26
From: Loomis Philanthrope
Subject: Re: update material evaluation incrementally?
David Richerby wrote:
> I've not experimented but the advantage of running counts seems to be
> obvious and significant, without adding a significant amount of code.

This is what I thought as well. Especially since 30% of my engine's time
is spent in the eval function and a fair portion of that is spent
administering the loop over the piece list and switching on piece type.
I figured if I eliminated that loop in favor of a few subtractions and
additions as pieces are captured and un-captured there would be a
difference.

But after I made the changes, the engine played the same moves in nearly
the same amount of time. It seemed quite odd to me, so I wanted to know
if anyone else had tried this and what results they got.

Loomis