Optimizing pruning

[Mangar]

Hi,

I am currently working on optimizing parameter for pruning techniques in Spike (only pruning, not reduction of search depth). All pruning techniques I know of works as follow:

If (some_eval + margin <= alpha) or (some_eval - margin >= beta)
prune.

Some of them are done in front of the move loop and some are done inside the move loop.

My interest is in optimizing the margin. Some tests revealed for me that margin could be a function of the following parameter:

* remaining_search_depth (found in all implementation I know)
* move_no (found inside the move loop for late move reduction related prunings)
* king attack
* passed pawns
* game phase

anybody allready tested with one of "additional" parameters (king attack, passed pawns, game phase) or something else?

Greetings Volker

[mcostalba]

Hi,

I am currently working on optimizing parameter for pruning techniques in Spike (only pruning, not reduction of search depth). All pruning techniques I know of works as follow:

If (some_eval + margin <= alpha) or (some_eval - margin >= beta)
prune.

Some of them are done in front of the move loop and some are done inside the move loop.

My interest is in optimizing the margin. Some tests revealed for me that margin could be a function of the following parameter:

* remaining_search_depth (found in all implementation I know)
* move_no (found inside the move loop for late move reduction related prunings)
* king attack
* passed pawns
* game phase

anybody allready tested with one of "additional" parameters (king attack, passed pawns, game phase) or something else?

Greetings Volker

IMHO king attack, passed pawns, game phase should end up in some_eval.

In particular "game phase" seems theoretical wrong to be put in the margin given that is already taken in account in some_eval (at least in SF is and in all the engines that have double evaluation accounting for mid and end game).

I think that to have a clear picture is useful to produce two lists:

Parameters that influence "margin", and parameters that influence "some_eval", then the next step is to remove redundancies, i.e. parameters that appears in both lists.

Redundancies, except for very specific cases, only clutter the picture and makes difficult to understand why a tweak works.

[hgm]

Well, either I misunderstand you, or I disagree. A Chess position has two important characteristic: an estimate for the average outcome, and an estimate for the reliability of this estimate. Eval takes care of the first.

But sometimes eval çan be very unreliable. If I hve a highly advanced passer, it will either promote or it will be eaten. So I will end up with a +4 or a -1 score (say he has to give his Rook for it when it makes it). The best I can do without knowng the outcome (i.e. without further search) is to take an eaverage score, say +1.5, over the normal material. That is nice for the average, but in practice always off by 2.5, as the real outcome will never be +2.5, but either -1 or +4.

It wuld be very logical to use such an uncertainty estimate to affect futility margins. In a quiet position you can reliably prune with a small margin, in a wild position almst anything can happen, and you cannot prune at all. Things like advanced passers, low King Safety and such do make the outcome of a position vary over a much larger range than it could in absence of these features. Eval cannot take care of this.

[mcostalba]

Well, either I misunderstand you, or I disagree. A Chess position has two important characteristic: an estimate for the average outcome, and an estimate for the reliability of this estimate. Eval takes care of the first.

But sometimes eval çan be very unreliable. If I hve a highly advanced passer, it will either promote or it will be eaten. So I will end up with a +4 or a -1 score (say he has to give his Rook for it when it makes it). The best I can do without knowng the outcome (i.e. without further search) is to take an eaverage score, say +1.5, over the normal material. That is nice for the average, but in practice always off by 2.5, as the real outcome will never be +2.5, but either -1 or +4.

It wuld be very logical to use such an uncertainty estimate to affect futility margins. In a quiet position you can reliably prune with a small margin, in a wild position almst anything can happen, and you cannot prune at all. Things like advanced passers, low King Safety and such do make the outcome of a position vary over a much larger range than it could in absence of these features. Eval cannot take care of this.

Yes, these are good points, but IMHO is important to apply your consideration when you have already a clear picture.

The 2 lists help to clear the picture, once you have done this is easier to find and justify what things could be re-used also in pruning and what should be not.

Anyhow to expand you reasoning, the IMHO correct approach is that the uncertainty estimate should be given by evaluation too.

IOW evaluation should return a pair of values: the score and the uncertainty

The search will use those value for pruning decision, but I think the corect approach is to have compeltely ortoghonal information between search and evaluation. The fact that traditional evaluation returns just the score and the uncertainty estimate of _that_ score is more or less carried on by the search is a little bit blurried for my taste (probably it belongs to tradition becasue engines have always been built like that) and could be an interesting approach trying to move the uncertainty estimate (or a big part of it) to evaluation.

IMHO current searches are too smart and evaluations are too dumb in this regard. Please note that I am _NOT_ advocating heavy evaluations in the traditional terms, i.e. evaluations crapped full of useless rules. I am proposing that the evaluations should evaluate also the uncertainty estimate of their score, and return this info to the search. But evaluations should do so keeping simple and light regarding chess knwoledge, I don't believe in fat evaluations. I believe in smart evaluations. But are two compeltely different concepts that only to someone look similar

[hgm]

I agree that what you propose is the fundamentally correct way to handle matters. But even after decades of pondering it, I have not found a satisfactory way to implement the use of such (averge, uncertainty) pairs. You would have to completely abandon minimax (and thus alpha-beta), fr starters.

How would you score a node from which two moves are possible, one that returned (+1, +/-0.5) and the other that returned (+2, +/-4) ? How would you maintain the window limits? In alpha-beta they are just scores of moves branching off the current line. So if scores become pairs, how would you decide whether to take a beta cutoff? If beta = (+1, +/-0.5), and you now find a move with score (+2, +/-4), would you take a cutoff?

The risk of such schemes is that you would not take a cutoff as often as with plain minimax, because some of the pairs do not have an obvious < or > relation. This could make it expensive, and as a result not competative.

And even then: coupling the uncertainty to the search is a logical thing to do. If you find a move that is 'promising' (i.e. large score, but also large uncertainty) you can do two things when you decide the uncertaanty is too big to waarrant cutoff: try to search an alternative move at the same depth, in the hope it will have smaller uncertainty, or search the promising move deeper, in the hope this will remove the uncertainty. I don't think there will be an obvious superiority of one method over the other. It will depend on the position. But perhaps in such a way that a compratively cheap analysis of the position tells you what to prefer.

[mcostalba]

How would you score a node from which two moves are possible, one that returned (+1, +/-0.5) and the other that returned (+2, +/-4) ?

This is an interesting matter. But please note that _currently_ all the searches (I am known of) do not do this, but use a straight compare of eval against beta to decide to cut off.

Said that your idea is not bad, what we would need is someone well versed in statistic (unfortunatly very rare on this forum )

The problem to solve is that of the optimum choice, the choice that guarantees the best results in terms of ELO gains.

IOW given a vector of possible moves m[], each one associated to a pair score and uncertainity v[s, v] the problem is to find a function F() so that:

F(v[]) --> max (Sb, Ub) -> best move Mb

Where Mb is the best possible move, i.e. the move that maximize the winning changes in that position.

A possible function F() could be of type:

Code: Select all

F(s, v) = s - k*v

so that, for instance for k=0.2 in your case we should have:

(+1, +/-0.5) -> 1 - 0.2*0.5 = 0.9

(+2, +/-4) -> 2 - 0.2*4 = 1.2

and according to this rule we are going to chose the second move.

Now the only problem is to fine tune 'k'

[Ralph Stoesser]

Now the only problem is to fine tune 'k'

Question is also how to calculate a reasonable accurate uncertainty value in evaluate() for a given position.

[Rein Halbersma]

How would you score a node from which two moves are possible, one that returned (+1, +/-0.5) and the other that returned (+2, +/-4) ?

This is an interesting matter. But please note that _currently_ all the searches (I am known of) do not do this, but use a straight compare of eval against beta to decide to cut off.

Said that your idea is not bad, what we would need is someone well versed in statistic (unfortunatly very rare on this forum )

The problem to solve is that of the optimum choice, the choice that guarantees the best results in terms of ELO gains.

IOW given a vector of possible moves m[], each one associated to a pair score and uncertainity v[s, v] the problem is to find a function F() so that:

F(v[]) --> max (Sb, Ub) -> best move Mb

Where Mb is the best possible move, i.e. the move that maximize the winning changes in that position.

A possible function F() could be of type:

Code: Select all

F(s, v) = s - k*v

so that, for instance for k=0.2 in your case we should have:

(+1, +/-0.5) -> 1 - 0.2*0.5 = 0.9

(+2, +/-4) -> 2 - 0.2*4 = 1.2

and according to this rule we are going to chose the second move.

Now the only problem is to fine tune 'k'

The mean-variance scheme that you are describing is often used in insurance and investment porfolios. The sum of mean minus k * variance is called the certainty equivalent wealth. It is a very useful approximation to make comparisons in the face of uncertainty (provided you can measure them accurately).

The optimal value of 'k' depends on the engine-author's level of risk-aversion. If you add the variance than your engine will be risk-seeking, so changing the sign of 'k' is somewhat similar to a contempt factor.

In any case, such an approach would naturally lead to Monte Carlo type of searches. See the enormous recent literature on Go.

[mcostalba]

Now the only problem is to fine tune 'k'

Question is also how to calculate a reasonable accurate uncertainty value in evaluate() for a given position.

Yes, that's the problem. It needs to be monotonic and more or less linear, it doesn't matter is accurate because 'k' coefficent will take care of this.

BTW I didn't know I have "invented" a statistical method used in insurances

[michiguel]

I agree that what you propose is the fundamentally correct way to handle matters. But even after decades of pondering it, I have not found a satisfactory way to implement the use of such (averge, uncertainty) pairs. You would have to completely abandon minimax (and thus alpha-beta), fr starters.

How would you score a node from which two moves are possible, one that returned (+1, +/-0.5) and the other that returned (+2, +/-4) ? How would you maintain the window limits? In alpha-beta they are just scores of moves branching off the current line. So if scores become pairs, how would you decide whether to take a beta cutoff? If beta = (+1, +/-0.5), and you now find a move with score (+2, +/-4), would you take a cutoff?

It is actually easy to make that decision. If we assume that the estimation of the eval score follows a gaussian curve, and the estimate for the evaluation is x, and the uncertainty is measured as estimate of the standard error (sx), then you choose the move that gives you the lowest integral value of the gauss curve below x-beta, with sigma sx. That is, you estimate which move gives you the highest probability to be above beta.

Or better, you calculate a "Z" value, which is a normalized eval that tells you how many sigmas you are above beta. That actually is cheaper to calculate and follows the same idea of the above paragraph.

Note that this is how humans evaluate. You prefer to be a knight up in a relatively quiet position than being a rook up in a wild situation with both kings dancing on the middle of the board and advanced passed pawns.

The problem is, the estimation of the uncertainty becomes as important as the eval itself. Unfortunately, that uncertainty is not simple to calculate with accuracy. We will need to measure the uncertainty of the uncertainty I thought about this a long time ago and abandoned the idea for this reason. I do not think it is impossible, but it will require a complete redesign of how things are done respect to eval.

It is more realistic that eval pass this uncertainty to search, so it will make decisions regarding to pruning and extending. It is still in my to-do list because I did not get to the stage of implementing pruning in my engine. However, I think that there are other cheaper ways to do that, considering the inaccuracy (or lack of wisdom from my part) of the "uncertainty" value.

Miguel
PS: Of course, this idea of introducing uncertainty into the equation is very old, for instance:
http://www.sciencedirect.com/science?_o ... 82284a6636

The risk of such schemes is that you would not take a cutoff as often as with plain minimax, because some of the pairs do not have an obvious < or > relation. This could make it expensive, and as a result not competative.

And even then: coupling the uncertainty to the search is a logical thing to do. If you find a move that is 'promising' (i.e. large score, but also large uncertainty) you can do two things when you decide the uncertaanty is too big to waarrant cutoff: try to search an alternative move at the same depth, in the hope it will have smaller uncertainty, or search the promising move deeper, in the hope this will remove the uncertainty. I don't think there will be an obvious superiority of one method over the other. It will depend on the position. But perhaps in such a way that a compratively cheap analysis of the position tells you what to prefer.