Another operator question for Marco..

[Eelco de Groot]

Hello Marco,

I just noticed something I do not really understand in the Stockfish 1.5 sources, in the quiescence search definition, and in the definition of search(), you want to determine if you can use the TT result again, but instead of asking whether tte->type() == VALUE_TYPE_EVAL
as was done in Stockfish 1.3 and 1.4, now in Stockfish 1.5 you use the bitwise AND operator '&' as follows:

Code: Select all

    else if (tte && (tte->type() & VALUE_TYPE_EVAL))
    {
        // Use the cached evaluation score if possible
        assert(ei.futilityMargin == Value(0));

Does this mean something like that tte->type() can be 4 or larger than 4?
Values smaller than 4 will not have the same bits set as VALUE_TYPE_EVAL when this is I presume 100 in bits, but larger values will. Am I understanding this correctly, and do you have an idea if this makes much difference?

Regards,

Eelco

I looked up the definition of the & operator here in the MSDN C++ Language reference, after some Googling: http://msdn.microsoft.com/en-us/library ... S.71).aspx

The board software does not like the (VS.71).aspx end of the URL it seems.

[mcostalba]

Hi Eelco,

because evaluation is very costly we try to store evaluation score in TT table along other values.

So a TT entry can be an upper bound (VALUE_TYPE_UPPER), a lower bound (VALUE_TYPE_LOWER) or an entry that simply keeps the evaluation score of that node (VALUE_TYPE_EVAL)

This is how it works in SF 1.4

In SF 1.5 we have realized that many times the evaluation score is _also_ the lower bound (for instance after returning from a stand pat in qsearch) or can be also an upper bound for instance in an ALL node when, after trying all the moves none is best then the node static value that is the evaluation of the node.

So the idea is to save a node score with _both_ the infos. This is the reason the value types are now defined as:

Code: Select all

enum ValueType {
  VALUE_TYPE_NONE = 0,
  VALUE_TYPE_UPPER = 1,  // Upper bound
  VALUE_TYPE_LOWER = 2,  // Lower bound
  VALUE_TYPE_EXACT = 3,  // Exact score
  VALUE_TYPE_EVAL  = 4,  // Evaluation cache
  VALUE_TYPE_EV_UP = 5,  // Evaluation cache for upper bound
  VALUE_TYPE_EV_LO = 6   // Evaluation cache for lower bound
};

So that, for instance when returning after a stand path cut-off the evaluation value will be saved with type VALUE_TYPE_EV_LO that is _both_ a lower bound type entry and also an evaluation score because:

Code: Select all

VALUE_TYPE_EV_LO & VALUE_TYPE_LOWER != 0

and

VALUE_TYPE_EV_LO & VALUE_TYPE_EVAL != 0

So, coming back to your question, when testing with:

Code: Select all

tte->type() & VALUE_TYPE_EVAL

We can determine if the entry score is the static evaluation of the node and so avoid to call evaluate() again. And we can do this in the case the TT entry refers to a pure evaluation score, to an evaluation score in an upper bound node or to an evaluation score in a lower bound node.


Hope it is clear.

[Eelco de Groot]

Thanks a lot for the explanation Marco!

I think I get the gist of it, and you have made the idea clear. What I don't quite see I hope I can figure it out now, what you say about the different lower and upper bounds often being the same as the static eval.

Something to chew on

I have not really touched any of the transposition table code in general, although I did try some vague ideas also there in the quiescence search about simply using the TT even if it was not an VALUE_TYPE_EVAL. I don't remember the details of what I tried Maybe I can try your new definitions in Ancalagon too The quiescence search in Ancalagon still also does use Null move and I also have modified Tord's use of the ei.futilityMargin in quiescence search. If it is of some value I will post about it of course.

(I thought the ei.futilityMargin could be related to the search explosions that Tord mentioned some time ago, but that is just a hunch. It may mean nothing)

But bugs in Ancalagon elsewhere at the moment, make it not so easy to go on, it is no good to keep changing things if there are bugs in other places.

Thanks Marco!

Eelco