What program first used hard pruning?

[bob]

if i am not wrong a big improvement in computerchess maked Sargon with the alpha beta cutoff ??

Nope. Alpha/Beta was discovered in the late 50's by Newell, SImon and Shaw if my memory is correct. Just a tad before Sargon was developed.

[lkaufman]

Do you know when the idea of different extension or reduction rules for PV and non-PV nodes was introduced?

[Don]

I know all this, but my question is whether hard pruning can possibly ever help results AT A GIVEN DEPTH. It would seem to be impossible, but in Komodo we actually observed a gain in Elo AT FIXED DEPTH for pruning on the last ply. Have you ever observed this in SF, and/or can you explain it?

"serendipity".



No rational explanation I can think of where you throw moves out and get a better result, unless your evaluation is bad and throwing out moves eliminates positions you evaluate badly.

One theory is that since moves are ordered by history, a pruned move that actually would have been chosen on the last ply is one with a better eval but a worse history than the chosen move. Apparently good history is more important than the apparent change in the score on the last ply, given a large difference in history. Another theory is that if many moves say the position is bad, but one says it's good, maybe the good move is an illusion more often than not. Either of these theories seem right to anyone?

My comment has to be that this is again serendipity. You mis-evaluate a move if you search it, so you produce a better result if you prune it. Ideally you would not prune a good move, nor would you search a bad move to any significant depth. Realistically, however...

I think you are right, but it's not serendipity, it's EXACTLY what is happening. It doesn't seem far fetched at all. We order by aged history and it's a very powerful mechanism for move ordering. We have found that the history table is a much more reliable predictor of move quality than the evaluation function. For example the pawn move e4-e5 will usually look pretty good according to the evaluation function, but the history table may put in far down in the list because it just doesn't "work out" very well in the search tree. So forward pruning will save us from thinking that the position deserves to be scored by this move.

There are a ton of examples, for instance putting a rook on the 7th rank. Evaluation function loves that move, but it may immediately be chased back or attacked. The history table knows this move is not workable yet but the evaluation function doesn't.

So by only looking at a few proven moves and forward pruning before getting "fooled" by the evaluation function we are simply pruning out moves that history knows is bad, even if they superficially look good.

I think it's a fact of life that the rook does not always belong on the 7th rank, the pawn should not always be advanced, the knight in the center is not always better than a knight on f3 and so on. On the last ply, most of these moves are just noise.

[Uri Blass]

I think that maybe a better solution is simply to change the evaluation function during the game.

If you find that e4-e5 is bad based on history table then you should change your piece square table to reduce the score for a pawn at e5(in this case you are not going to plan to push the pawn in fixed depth search because your evaluation is going to tell you that it is bad in the specific game.

The evaluation function is going to get again the default values when you start a new game or if you find later in the game that having a pawn at e5 is good based on history table.

[Don]

I think that maybe a better solution is simply to change the evaluation function during the game.

If you find that e4-e5 is bad based on history table then you should change your piece square table to reduce the score for a pawn at e5(in this case you are not going to plan to push the pawn in fixed depth search because your evaluation is going to tell you that it is bad in the specific game.

The evaluation function is going to get again the default values when you start a new game or if you find later in the game that having a pawn at e5 is good based on history table.

That's a very interesting idea.

I'm not so sure the evaluation function is "wrong" as it is just subject to local tactics. But even if that is the case it may be a good thing to do because it's a more immediately relevant score.

The question is whether there is a clean way to implement this that does not do more damage than good. The evaluation says you want to place your rook on d7 IF YOU CAN. But you sometime cannot because it's either defended or it just doesn't flow with the game.

You would also get the recursive effect of modifying the score, which would affect the history, which would affect the next score, etc.

But it does sound interesting. I would have to think of how it might be implemented and perhaps give this a try.

[Antonio Torrecillas]

I think that maybe a better solution is simply to change the evaluation function during the game.

If you find that e4-e5 is bad based on history table then you should change your piece square table to reduce the score for a pawn at e5(in this case you are not going to plan to push the pawn in fixed depth search because your evaluation is going to tell you that it is bad in the specific game.

The evaluation function is going to get again the default values when you start a new game or if you find later in the game that having a pawn at e5 is good based on history table.

That's a very interesting idea.

I'm not so sure the evaluation function is "wrong" as it is just subject to local tactics. But even if that is the case it may be a good thing to do because it's a more immediately relevant score.

The question is whether there is a clean way to implement this that does not do more damage than good. The evaluation says you want to place your rook on d7 IF YOU CAN. But you sometime cannot because it's either defended or it just doesn't flow with the game.

You would also get the recursive effect of modifying the score, which would affect the history, which would affect the next score, etc.

But it does sound interesting. I would have to think of how it might be implemented and perhaps give this a try.

In this line of ideas, a year ago I experimented with a "servo evaluation".
A piece square table was calculated from the history table after each iteration.
Getting a probability from the history table p = goods/total
and then with a logistic function I calculated each square of the pst table. V[color][piece][square] = -k*log((1/p)-1);
This calculation is performed between each iteration with the previous iteration data.

My conclusion is that the benefit of the system came from the reduction
of the horizon effect.On the other hand, this was only effective at a certain depth
(information contained in the history table).
The difficulty lies in establishing appropriate feedback to each position.(constant K).
If it was small it has no effect on the search, if too large, it completely distorted the results.

regards, Antonio.

[Don]

I think that maybe a better solution is simply to change the evaluation function during the game.

If you find that e4-e5 is bad based on history table then you should change your piece square table to reduce the score for a pawn at e5(in this case you are not going to plan to push the pawn in fixed depth search because your evaluation is going to tell you that it is bad in the specific game.

The evaluation function is going to get again the default values when you start a new game or if you find later in the game that having a pawn at e5 is good based on history table.

That's a very interesting idea.

I'm not so sure the evaluation function is "wrong" as it is just subject to local tactics. But even if that is the case it may be a good thing to do because it's a more immediately relevant score.

The question is whether there is a clean way to implement this that does not do more damage than good. The evaluation says you want to place your rook on d7 IF YOU CAN. But you sometime cannot because it's either defended or it just doesn't flow with the game.

You would also get the recursive effect of modifying the score, which would affect the history, which would affect the next score, etc.

But it does sound interesting. I would have to think of how it might be implemented and perhaps give this a try.

In this line of ideas, a year ago I experimented with a "servo evaluation".
A piece square table was calculated from the history table after each iteration.
Getting a probability from the history table p = goods/total
and then with a logistic function I calculated each square of the pst table. V[color][piece][square] = -k*log((1/p)-1);
This calculation is performed between each iteration with the previous iteration data.

My conclusion is that the benefit of the system came from the reduction
of the horizon effect.On the other hand, this was only effective at a certain depth
(information contained in the history table).
The difficulty lies in establishing appropriate feedback to each position.(constant K).
If it was small it has no effect on the search, if too large, it completely distorted the results.

regards, Antonio.

This is in the spirit of monte carlo evaluation - it's NOT the same as monte carlo as used in GO, but it has some of the characteristics of letting the search impact the evaluation function directly (as opposed to indirectly

[michiguel]

I think that maybe a better solution is simply to change the evaluation function during the game.

If you find that e4-e5 is bad based on history table then you should change your piece square table to reduce the score for a pawn at e5(in this case you are not going to plan to push the pawn in fixed depth search because your evaluation is going to tell you that it is bad in the specific game.

The evaluation function is going to get again the default values when you start a new game or if you find later in the game that having a pawn at e5 is good based on history table.

That's a very interesting idea.

I'm not so sure the evaluation function is "wrong" as it is just subject to local tactics. But even if that is the case it may be a good thing to do because it's a more immediately relevant score.

The question is whether there is a clean way to implement this that does not do more damage than good. The evaluation says you want to place your rook on d7 IF YOU CAN. But you sometime cannot because it's either defended or it just doesn't flow with the game.

You would also get the recursive effect of modifying the score, which would affect the history, which would affect the next score, etc.

But it does sound interesting. I would have to think of how it might be implemented and perhaps give this a try.

In this line of ideas, a year ago I experimented with a "servo evaluation".
A piece square table was calculated from the history table after each iteration.
Getting a probability from the history table p = goods/total
and then with a logistic function I calculated each square of the pst table. V[color][piece][square] = -k*log((1/p)-1);
This calculation is performed between each iteration with the previous iteration data.

My conclusion is that the benefit of the system came from the reduction
of the horizon effect.On the other hand, this was only effective at a certain depth
(information contained in the history table).
The difficulty lies in establishing appropriate feedback to each position.(constant K).
If it was small it has no effect on the search, if too large, it completely distorted the results.

regards, Antonio.

The key here is to calculate the PST from history. It is not trivial at all because the number of parameters in the PST is smaller, which means that an accurate way may involve some sort of fitting. However, I think that there is potential with this concept and deserves to be explored.

The other problem will be the hash table, but I guess that it would be the least of the problems.

Miguel
PS: would it be possible to continue this thread in the technical forum and take it out of this one, which has become a crappy one? I almost missed this.

[Don]

Yes, I think it was silly to put this in general topics - it should have been a technical question.

I think that maybe a better solution is simply to change the evaluation function during the game.

If you find that e4-e5 is bad based on history table then you should change your piece square table to reduce the score for a pawn at e5(in this case you are not going to plan to push the pawn in fixed depth search because your evaluation is going to tell you that it is bad in the specific game.

The evaluation function is going to get again the default values when you start a new game or if you find later in the game that having a pawn at e5 is good based on history table.

That's a very interesting idea.

I'm not so sure the evaluation function is "wrong" as it is just subject to local tactics. But even if that is the case it may be a good thing to do because it's a more immediately relevant score.

The question is whether there is a clean way to implement this that does not do more damage than good. The evaluation says you want to place your rook on d7 IF YOU CAN. But you sometime cannot because it's either defended or it just doesn't flow with the game.

You would also get the recursive effect of modifying the score, which would affect the history, which would affect the next score, etc.

But it does sound interesting. I would have to think of how it might be implemented and perhaps give this a try.

In this line of ideas, a year ago I experimented with a "servo evaluation".
A piece square table was calculated from the history table after each iteration.
Getting a probability from the history table p = goods/total
and then with a logistic function I calculated each square of the pst table. V[color][piece][square] = -k*log((1/p)-1);
This calculation is performed between each iteration with the previous iteration data.

My conclusion is that the benefit of the system came from the reduction
of the horizon effect.On the other hand, this was only effective at a certain depth
(information contained in the history table).
The difficulty lies in establishing appropriate feedback to each position.(constant K).
If it was small it has no effect on the search, if too large, it completely distorted the results.

regards, Antonio.

The key here is to calculate the PST from history. It is not trivial at all because the number of parameters in the PST is smaller, which means that an accurate way may involve some sort of fitting. However, I think that there is potential with this concept and deserves to be explored.

The other problem will be the hash table, but I guess that it would be the least of the problems.

Miguel
PS: would it be possible to continue this thread in the technical forum and take it out of this one, which has become a crappy one? I almost missed this.