Do you evaluate internal nodes?

[Tord Romstad]

I already asked this question in another thread, but it suddenly dawned on me that this was the perfect opportunity for me to try the "Add a Poll" feature of this forum.

I hope as many programmers as possible will participate in the poll. It will be very interesting to see the results.

Tord

[smcracraft]

Say I run evaluate() first thing in my search() before doing much
else.

What is the best way to use the returned evaluation in the search()
routine to get the most of "every-node-eval" method?

I have read Rebel's entire page many times, but I am searching for
a shorter, paragraph-type comment.

Greetings,

Stuart

[Volker Böhm]

Sometimes a simple question is hard to answer. Spike calls part of eval for futility pruning, but not in general. Thus I answered no.

Greetings Volker

[Tord Romstad]

Say I run evaluate() first thing in my search() before doing much else.

That's what I do. I call evaluate() directly after probing the transposition table.

What is the best way to use the returned evaluation in the search()
routine to get the most of "every-node-eval" method?

I use it for the following purposes:

• Avoiding unnecessary null move searches. If the static eval is below beta, it is unlikely that the null move search will return a score above beta, and I just skip the null move search.
• Avoiding unnecessary internal iterative deepening searches. If the static eval is too far below alpha, the search will probably fail low at this node, and the move ordering isn't very important.
• Futility pruning.
• Static null move pruning. If the static eval is sufficiently far above beta, the side to move has no hanging pieces, the remaining depth is small, and some additional tactical safety conditions are satisfied, I return a fail high score without a search.
• Making extension and reduction decisions. The static eval after making a move is compared to the static eval before the move was made in order to identify the most interesting moves.

The first item on this list is by itself more than enough to compensate for the expense of evaluating internal nodes in my program. Avoiding too many useless null move searches saves a lot of nodes.

Tord

[Anonymous]

Actually I don't call evaluate() in interior nodes, but I will of course experiment with it.

[Gian-Carlo Pascutto]

[*]Avoiding unnecessary null move searches. If the static eval is below beta, it is unlikely that the null move search will return a score above beta, and I just skip the null move search.

The first item on this list is by itself more than enough to compensate for the expense of evaluating internal nodes in my program. Avoiding too many useless null move searches saves a lot of nodes.

Tord

This one I find interesting, since I understood Fabien went the other way in Fruit 2.2.1 versus Fruit 2.1.

[Tord Romstad]

[*]Avoiding unnecessary null move searches. If the static eval is below beta, it is unlikely that the null move search will return a score above beta, and I just skip the null move search.

The first item on this list is by itself more than enough to compensate for the expense of evaluating internal nodes in my program. Avoiding too many useless null move searches saves a lot of nodes.

Tord

This one I find interesting, since I understood Fabien went the other way in Fruit 2.2.1 versus Fruit 2.1.

This is true, and yet another example that you can never assume that something works in your program just because it works in somebody else's program.

Tord

[Uri Blass]

Say I run evaluate() first thing in my search() before doing much
else.

What is the best way to use the returned evaluation in the search()
routine to get the most of "every-node-eval" method?

I have read Rebel's entire page many times, but I am searching for
a shorter, paragraph-type comment.

Greetings,

Stuart

I use it mainly for pruning decisions.

I have function that say
if (eval>beta+margin(depth....)) return beta

margin is of course bigger when the depth is bigger but it is also depended on other factors.

My function is very complicated and I do not remember the exact function and I do not want to share my source.

I will share some details:
1)margin is smaller in the endgame
2)margin is bigger when the king is under threat.
3)margin is bigger if the opponent control all the squares near the king.

Uri

To be more correct
Note that this not exactly what I have in the code but something equivalent and I only posted based on memory.

The name of the function that I have is different but this is the idea.

The code that I have exactly in my source is the following 2 lines:
j1=eval_dat[ply].evalfull-calculatemargin(nominal(depth),beta);
if (j1>=0) return beta;

evalfull is the evaluation but calculatemargin use a lot of global variables so practically it is a function of other paramaters.

Uri

[Uri Blass]

[*]Avoiding unnecessary null move searches. If the static eval is below beta, it is unlikely that the null move search will return a score above beta, and I just skip the null move search.

The first item on this list is by itself more than enough to compensate for the expense of evaluating internal nodes in my program. Avoiding too many useless null move searches saves a lot of nodes.

Tord

This one I find interesting, since I understood Fabien went the other way in Fruit 2.2.1 versus Fruit 2.1.

What is the difference that you see between fruit2.2.1 and fruit2.1

Based on fabien's posts
I understood that there were were only 2 differences:
The first difference is bonus for side to move and the second difference is
pruning.

I do not think that these differences justify changing the decision if to evaluate every node or not to do it.

In both cases fruit needs the static evaluation to decide if to avoid null move pruning(I do not do use it today in order to decide if to avoid null move search but it is one of the ideas that I may try).

Uri

[Uri Blass]

Sometimes a simple question is hard to answer. Spike calls part of eval for futility pruning, but not in general. Thus I answered no.

Greetings Volker

I wonder if you tried to evaluate every node and use it for pruning or reductions.

I use it mainly for pruning when for reduction I use mainly history based reduction.

I consider to change to glaurung type reduction of bad moves that seem better.

I believe that history based reduction can be productive but I also believe that practically evaluation based reduction can be better because after improving evaluation based reduction you may need to change the history based reduction to be based on different history if you want it to work and when you have limited time to experiment it may be better to improve evaluation based reduction.

Uri

[Tony van Roon-Werten]

I call evaluate in every node.

But to make it a bit more complicated, I call it after I made a move. ( Saves me a call to qsearch when eval<alpha on depth=1 nodes )

This evaluation can influence search by extensions (no reductions at the moment) fe if kingsafety goes up/down

Tony

[Uri Blass]

I call evaluate in every node.

But to make it a bit more complicated, I call it after I made a move. ( Saves me a call to qsearch when eval<alpha on depth=1 nodes )

This evaluation can influence search by extensions (no reductions at the moment) fe if kingsafety goes up/down

Tony

I think that calling eval after making a move is the normal way.
I see no reason to call it before making moves.

If I make move and undo it then the evaluation is already saved and I do not need to call evaluation before making another move.

Uri

[Tony van Roon-Werten]

I call evaluate in every node.

But to make it a bit more complicated, I call it after I made a move. ( Saves me a call to qsearch when eval<alpha on depth=1 nodes )

This evaluation can influence search by extensions (no reductions at the moment) fe if kingsafety goes up/down

Tony

I think that calling eval after making a move is the normal way.
I see no reason to call it before making moves.

If I make move and undo it then the evaluation is already saved and I do not need to call evaluation before making another move.

Uri

A general search function might look like this

Code: Select all

search(alpha,beta,ply,depth)
{
   if (depth<=0) return(qsearch(alpha,beta))
   evaluate()
   foreach (move in movelist)
   {
      makemove(move)
      score=-search(-beta,-alpha,depth-1)
      unmake_move(move)
      best_score=max(score,best_score)
   }
   return(best_score)
}
     

Mine looks like this

Code: Select all


search(alpha,beta,ply,depth)
{
   foreach (move in movelist)
   {
      makemove(move)

      score=-evaluate()
      if (depth<=1)
      {
         if (score>alpha) score=-(qsearch(-beta,-alpha))
      }
      else score=-search(-beta,-alpha,depth-1)

      unmake_move(move)
      best_score=max(best_score,score)
   }
   return(best_score)
}


That way I have knowledge, provided by the evaluation function, available before continuing/deciding on search.

Tony

[H.G.Muller]

This does not really change the logic of the program. It is just a technical optimization how to chop up the tree-walk into chuncks that are handled by a specific instance of the recursive call, in order to minimize the overhead associated with the recursion (the calling sequence pushing the arguments and the creation of the new stack frame for local variables).

The obvious way to do things (the first case) makes the last call at the leave nodes hardly do anything at all: it immediately calls another routine and passes the returned result back as its own, making the creation of the stack-frame a totally wasted effort: it is never used. So indeed it is much better to shift the transition between one level of recursion and the next somewhat down the branches towards the root, such that it is just beyond the point where the tree-walk would naturally end (or would shift to another mode, such as QS).

Great idea!

[Gian-Carlo Pascutto]

What is the difference that you see between fruit2.2.1 and fruit2.1

Based on fabien's posts
I understood that there were were only 2 differences:
The first difference is bonus for side to move and the second difference is
pruning.

The default settings in Fruit 2.2.1 differ from Fruit 2.1

[smcracraft]

I am a little surprised that so many evaluate all internal nodes.

I hope that is ALL rather than SOME that the poll is about.

I evaluate NO internal nodes.

I was scared off by Ed's REBEL page. It seemed too learned!

Stuart

[Uri Blass]

I am a little surprised that so many evaluate all internal nodes.

I hope that is ALL rather than SOME that the poll is about.

I evaluate NO internal nodes.

I was scared off by Ed's REBEL page. It seemed too learned!

Stuart

If internal nodes mean nodes that are not leaves of the tree then I evaluate all of them.

I also evaluate most of the leaves but there are cases when I prune without evaluation in the leaves because it is faster to do it.

Uri

[Alessandro Scotti]

I evaluate NO internal nodes.

I was scared off by Ed's REBEL page. It seemed too learned!

Actually I got the idea from Tord. I think it's worth many Elo points in Kiwi.

[Uri Blass]

In my case I invented it independently.
If my memory is correct movei evaluated internal nodes from the first version.

In the beginning the evaluation was very cheap and I always thought that evaluation should be used for tasks like pruning so not evaluating internal nodes seemed illogical to me and I never tried it.

Note that pruning is not the only thing that they are used for but it is the only thing that I chose to post about here.

Uri

[Naum]

It is funny that you guys started this thread, because I started experimenting with this on Sunday.
Currently I use eval only for the non-leaf futility pruning.

Last time I tried eval>=beta for null move (long time ago), it didn't work. Naum was searching much faster, but it was causing the 'blind spots' in the search.

On Sunday I had an idea that seems to be solving the blind spot problem in some test positions, but the test match against Fruit showed no improvement. I think that search is still unstable.

Did someone try maybe eval + [some margin] > beta as a condition?
Would be slower, but search might be more stable.

Alex