An idea to compare PV with the same score

[Kempelen]

Hello,

An idea round my head:

As now, when alpha-beta search for a good move, it always compare new variation with alpha in the following way:

Code: Select all

....
eval = -search(-beta, -alpha);
if (eval > alpha) {
        if (eval >= beta) return eval;
        copy_new_pv(ply);
}
....

I am thinking in comparing alpha with ">=" and not with ">", and put an special condition which let me to choose a new PV when eval = alpha based on the quality of the path:

Code: Select all

...
eval = -search(-beta, -alpha)
if (eval >= alpha) {
          if (eval >= beta) return eval;
          if (eval == alpha && !best_path()) 
                      continue;
          cppy_new_pv(ply);
}
...

best_path will tell, for two PV with the same score, which will I prefer. I want to do this for various reason:
1) I will prefer PV with captures to PV with no captures (or promotions), so It will not play boring never-endings drawn positions. It will simplify and the drawn should came soon.
2) Other ideas like to prefer variations which moves go more into enemy camp, or those that will put pieces near king,....

I have a few questions about this, because I am not currently sure how to implement it well:
1) Is it the idea possible?
2) Is it my code good? or should I take into account other consideration? i.e. I dont know exactly what should I return when no pv is found and no fails high (normal conditions alpha is returned at the end of search function)
3) Do you think this could be a performance bottleneck?
4) Your opinion in general.

Thanks
Fermin

[hgm]

This will not work, unless you adjust your search window. A score equal to the existing alpha returned by an alpha-beta search will be an upper limit only, and can be arbitrarily poor in reality. In fact many moves that are no good at all return alpha.

To make sure a score of alpha means something, you would have to set the lower window limit to alpha-1 (i.e. eval = -search(-beta, 1-alpha)).

[Desperado]

Hi

if there is PV ( at least alpha+1 ) and a new second PV with the same score occurs,
then to decide on some criteria which one to follow sounds interesting.

( Hope i was understanding the idea correctly )

Finding some meaningful criterias will be challenging. To ignore
the implicit pv because it was searched before another pv which is equal
can make sense for me in a way like...

Code: Select all

// best > alpha && best < beta

if( value > alpha && value<beta )
{
  if( value == best )
  {
    // my decision for new pv ( eg: based on your idea "path quality" )
  }
  if( value > best )
  {
     // new pv
  }
}

imho,
Michael

[Kempelen]

I will make same test with the idea in the following months. Anyway I did not expect any Elo gain (or insignificant, at the ends both pv has the same value), my original idea is to make the engine to play a bit more human-like, avoiding endless draws and make it prefers certain "style" moves.

[bob]

Hello,

An idea round my head:

As now, when alpha-beta search for a good move, it always compare new variation with alpha in the following way:

Code: Select all

....
eval = -search(-beta, -alpha);
if (eval > alpha) {
        if (eval >= beta) return eval;
        copy_new_pv(ply);
}
....

I am thinking in comparing alpha with ">=" and not with ">", and put an special condition which let me to choose a new PV when eval = alpha based on the quality of the path:

Code: Select all

...
eval = -search(-beta, -alpha)
if (eval >= alpha) {
          if (eval >= beta) return eval;
          if (eval == alpha && !best_path()) 
                      continue;
          cppy_new_pv(ply);
}
...

best_path will tell, for two PV with the same score, which will I prefer. I want to do this for various reason:
1) I will prefer PV with captures to PV with no captures (or promotions), so It will not play boring never-endings drawn positions. It will simplify and the drawn should came soon.
2) Other ideas like to prefer variations which moves go more into enemy camp, or those that will put pieces near king,....

I have a few questions about this, because I am not currently sure how to implement it well:
1) Is it the idea possible?
2) Is it my code good? or should I take into account other consideration? i.e. I dont know exactly what should I return when no pv is found and no fails high (normal conditions alpha is returned at the end of search function)
3) Do you think this could be a performance bottleneck?
4) Your opinion in general.

Thanks
Fermin

You realize that "==" is meaningless when comparing to a bound? less than is technically the same as less than or equal to, because a score of alpha is never a "real score" since it sits on the edge (bound) of the window.