Reply
 
LinkBack Thread Tools Display Modes
  #1   Report Post  
Old May 21st 04, 06:01 PM
pd42
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

What do the top chess programs do?

There are at least two ways of evaluation: in one extreme, position
evaluation fully takes place incrementally, i.e the score is
incrementally updated in the do_move and undo_move routines (it's easy
to imagine this scheme for the material balance component), in the
other extreme it ONLY takes place at the leaves (more expensive but
also more versatile). You can also apply both, i.e. material
evaluation is done incrementally, pawn structure / king safety is only
done at the leaves. Thanks.
  #2   Report Post  
Old May 21st 04, 08:14 PM
Robert Hyatt
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

pd42 wrote:
What do the top chess programs do?


There are at least two ways of evaluation: in one extreme, position
evaluation fully takes place incrementally, i.e the score is
incrementally updated in the do_move and undo_move routines (it's easy
to imagine this scheme for the material balance component), in the
other extreme it ONLY takes place at the leaves (more expensive but
also more versatile). You can also apply both, i.e. material
evaluation is done incrementally, pawn structure / king safety is only
done at the leaves. Thanks.


Not that I would say "Crafty is a top chess program" but it updates material
incrementally, but does all evaluation at the endpoints. Some of the positional
eval could be done incrementally, and perhaps will be one day. But it changes so
frequently, from a software engineering standpoint it is better to keep all the
eval code in one place, rather than scattered around in MakeMove()/UnmakeMove() as
well...

For efficiency, do everything possible incrementally. You only do it when it needs to
be done, rather than at ever position...



--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170
  #3   Report Post  
Old May 22nd 04, 07:58 AM
pd42
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

Robert Hyatt wrote in message ...
pd42 wrote:
What do the top chess programs do?


There are at least two ways of evaluation: in one extreme, position
evaluation fully takes place incrementally, i.e the score is
incrementally updated in the do_move and undo_move routines (it's easy
to imagine this scheme for the material balance component), in the
other extreme it ONLY takes place at the leaves (more expensive but
also more versatile). You can also apply both, i.e. material
evaluation is done incrementally, pawn structure / king safety is only
done at the leaves. Thanks.


Not that I would say "Crafty is a top chess program" but it updates material
incrementally, but does all evaluation at the endpoints. Some of the positional
eval could be done incrementally, and perhaps will be one day. But it changes so
frequently, from a software engineering standpoint it is better to keep all the
eval code in one place, rather than scattered around in MakeMove()/UnmakeMove() as
well...

For efficiency, do everything possible incrementally. You only do it when it needs to
be done, rather than at ever position...



For your information, if I do 100% incrementally I get 800,000 nodes
per second. After switching to 100% endpoint evaluation, this drops
down to 200,000 nodes per second. However, a speed-up factor of at
least 35 is needed to do an extra ply. So 4 times faster may sound
great, but it doesn't help much. Still: I want to stick to 100%
incremental and see where this ends up.

Only doing incremental eval when it needs to be done will need
(possibly lots of) extra 'housekeeping', it will actually resemble
endpoint evaluation. So I wonder how this should be implemented, any
examples?
  #5   Report Post  
Old May 22nd 04, 11:10 PM
Simon Krahnke
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

* pd42 (08:58) wrote:

However, a speed-up factor of at least 35 is needed to do an extra ply.


Your search has an effective branching factor of 35? That ist more than
the average full minimax branching factor.

Quiescence explosion?

mfg, simon .... l


  #6   Report Post  
Old May 23rd 04, 01:13 AM
Robert Hyatt
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

pd42 wrote:
Robert Hyatt wrote in message ...
pd42 wrote:
What do the top chess programs do?


There are at least two ways of evaluation: in one extreme, position
evaluation fully takes place incrementally, i.e the score is
incrementally updated in the do_move and undo_move routines (it's easy
to imagine this scheme for the material balance component), in the
other extreme it ONLY takes place at the leaves (more expensive but
also more versatile). You can also apply both, i.e. material
evaluation is done incrementally, pawn structure / king safety is only
done at the leaves. Thanks.


Not that I would say "Crafty is a top chess program" but it updates material
incrementally, but does all evaluation at the endpoints. Some of the positional
eval could be done incrementally, and perhaps will be one day. But it changes so
frequently, from a software engineering standpoint it is better to keep all the
eval code in one place, rather than scattered around in MakeMove()/UnmakeMove() as
well...

For efficiency, do everything possible incrementally. You only do it when it needs to
be done, rather than at ever position...



For your information, if I do 100% incrementally I get 800,000 nodes
per second. After switching to 100% endpoint evaluation, this drops
down to 200,000 nodes per second. However, a speed-up factor of at
least 35 is needed to do an extra ply. So 4 times faster may sound
great, but it doesn't help much. Still: I want to stick to 100%
incremental and see where this ends up.


First, 4x sounds wrong. That suggests that your evaluation is over 75%
of the _total_ time being used. That seems improbable.

However, you only need a factor of 3 or so to get another ply assuming
you are doing a normal alpha/beta search with null-move R=2/3 or whatever.


Only doing incremental eval when it needs to be done will need
(possibly lots of) extra 'housekeeping', it will actually resemble
endpoint evaluation. So I wonder how this should be implemented, any
examples?


Not really. In Cray Blitz I did about 1/3 incremental, 2/3 at endpoints.
I can't see how to do a really complex eval incrementally, as a single scoring
term could depend on the location of multiple pieces, which makes incremental
updating very difficult.


--
Robert M. Hyatt, Ph.D. Computer and Information Sciences
University of Alabama at Birmingham
(205) 934-2213 136A Campbell Hall
(205) 934-5473 FAX Birmingham, AL 35294-1170
  #7   Report Post  
Old May 23rd 04, 08:56 AM
Tord Kallqvist Romstad
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

Robert Hyatt writes:

pd42 wrote:

For your information, if I do 100% incrementally I get 800,000 nodes
per second. After switching to 100% endpoint evaluation, this drops
down to 200,000 nodes per second. However, a speed-up factor of at
least 35 is needed to do an extra ply. So 4 times faster may sound
great, but it doesn't help much. Still: I want to stick to 100%
incremental and see where this ends up.


First, 4x sounds wrong. That suggests that your evaluation is over 75%
of the _total_ time being used. That seems improbable.


Why? The last time I profiled my program, the evaluation consumed
almost exactly 75% of the processor time. I have no reason to believe
that this number is unusual.

--
Tord Romstad
  #9   Report Post  
Old May 23rd 04, 12:33 PM
pd42
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

Robert Hyatt wrote in message ...
pd42 wrote:
Robert Hyatt wrote in message ...
pd42 wrote:
What do the top chess programs do?


There are at least two ways of evaluation: in one extreme, position
evaluation fully takes place incrementally, i.e the score is
incrementally updated in the do_move and undo_move routines (it's easy
to imagine this scheme for the material balance component), in the
other extreme it ONLY takes place at the leaves (more expensive but
also more versatile). You can also apply both, i.e. material
evaluation is done incrementally, pawn structure / king safety is only
done at the leaves. Thanks.

Not that I would say "Crafty is a top chess program" but it updates material
incrementally, but does all evaluation at the endpoints. Some of the positional
eval could be done incrementally, and perhaps will be one day. But it changes so
frequently, from a software engineering standpoint it is better to keep all the
eval code in one place, rather than scattered around in MakeMove()/UnmakeMove() as
well...

For efficiency, do everything possible incrementally. You only do it when it needs to
be done, rather than at ever position...



For your information, if I do 100% incrementally I get 800,000 nodes
per second. After switching to 100% endpoint evaluation, this drops
down to 200,000 nodes per second. However, a speed-up factor of at
least 35 is needed to do an extra ply. So 4 times faster may sound
great, but it doesn't help much. Still: I want to stick to 100%
incremental and see where this ends up.


First, 4x sounds wrong. That suggests that your evaluation is over 75%
of the _total_ time being used. That seems improbable.

However, you only need a factor of 3 or so to get another ply assuming
you are doing a normal alpha/beta search with null-move R=2/3 or whatever.


Only doing incremental eval when it needs to be done will need
(possibly lots of) extra 'housekeeping', it will actually resemble
endpoint evaluation. So I wonder how this should be implemented, any
examples?


Not really. In Cray Blitz I did about 1/3 incremental, 2/3 at endpoints.
I can't see how to do a really complex eval incrementally, as a single scoring
term could depend on the location of multiple pieces, which makes incremental
updating very difficult.


I still think incremental is in principal superior due to its speed
increase, but yes: I also admit that it will need a complete
rethinking of evaluation.

Mathematically speaking, isn't it true that if you differentiate the
endpoint evaluation function, you end up with its íncremental
evaluation function?

What I mean to say is that it must somehow be possible to transform
any endpoint formulation into an incremental formulation (this can be
done even with pawn structure, which depends on the location of
multiple pieces, you just will get multiple differences, one for each
piece). The math can be worked out.
  #10   Report Post  
Old May 23rd 04, 12:35 PM
pd42
 
Posts: n/a
Default Incremental evaluation, leaf evaluation, or hybrid?

Simon Krahnke wrote in message ...
* pd42 (08:58) wrote:

However, a speed-up factor of at least 35 is needed to do an extra ply.


Your search has an effective branching factor of 35? That ist more than
the average full minimax branching factor.

Quiescence explosion?

mfg, simon .... l


See my reply to Tord Kallqvist Romstad's message
Reply
Thread Tools
Display Modes

Posting Rules

Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT +1. The time now is 10:43 AM.

Powered by vBulletin® Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Copyright ©2004-2019 ChessBanter.
The comments are property of their posters.
 

About Us

"It's about Chess"

 

Copyright © 2017