What is "history pruning"?

[Vladimir Medvedev]

In Fruit's readme file I read some words about "History Pruning". What is this technique about? I could not find any information in search engines here and on CCC...

Please give some links or brief explanation... Reading Fruit's code to understand is not easy for me, it is not well commented...

Code: Select all

      // history pruning

      reduced = false;

      if (UseHistory && depth >= HistoryDepth && node_type != NodePV) {
         if (!in_check && played_nb >= HistoryMoveNb && new_depth < depth) {
            ASSERT(best_value!=ValueNone);
            ASSERT(played_nb>0);
            ASSERT(sort->pos>0&&move==LIST_MOVE(sort->list,sort->pos-1));
            value = sort->value; // history score
            if (value < HistoryValue) {
               ASSERT(value>=0&&value<16384);
               ASSERT(move!=trans_move);
               ASSERT(!move_is_tactical(move,board));
               ASSERT(!move_is_check(move,board));
               new_depth--;
               reduced = true;
            }
         }
      }


[Uri Blass]

The idea of history pruning is basically reducing depth of moves that did not fail high based on statistics.

if a move failed low and after it another move failed high then it is clear that the move that failed low is not the best move based on the program's calculation.

If it happen a lot of time to a1-b1(it can be also another move and I chose a1-b1 only as example) then the idea is that next time you reduce the depth of a1-b1 because you expect it to be a bad move.

You do not do it in case that a1-b1 is one of the first moves but you do it in case that a1-b1 is not one of the first moves.

Uri

[Stef Luijten]

History pruning seems to be a very powerfull technique.
Who invented it? do all strong programs have it?
I am thinking of adding history pruning in Wing, the main problem seems to be to determine a 'good' threshold.

[David Weller]

I tried History pruniing in my latest engine [though I may have rushed it a bit] and at first it looked impressive [due to the increased depths] but then it played worse

Turns out, maybe my implementation of the history data is not suited for the task.

Fabien has a more acurate way of calculating move stats.

Now I am trying as conservative settings as possible, to gain a little, but risk little also .... seems to be a wash

Like someone has said, its all about the threshholds.....

-David

Keep your eyes peeled for GES137 and Xpdnt100 coming to a web site near you [but dont hold you breath ]

[Ryan Benitez]

What I really want to know is why a reduction is called pruning?

[Dann Corbit]

What I really want to know is why a reduction is called pruning?

Imagine a grape vine with thousands of long and snaking tendrils. Some branches have very few grapes or are even diseased. You cut off the unproductive branches and the ones that are loaded with fruit and are the healthiest looking get more attention.

[Tony van Roon-Werten]

What I really want to know is why a reduction is called pruning?

Because it has the wrong name

It should be called history based reduction or something.

In its original form it was called Positional Quiescence Search (IIRC) but it was used oposite.
Moves with a good history were tried in quiescence search as well.

Tony

[Stef Luijten]

[quote="David Weller"]I tried History pruniing in my latest engine [though I may have rushed it a bit] and at first it looked impressive [due to the increased depths] but then it played worse

Turns out, maybe my implementation of the history data is not suited for the task.

Fabien has a more acurate way of calculating move stats.

Now I am trying as conservative settings as possible, to gain a little, but risk little also .... seems to be a wash

Like someone has said, its all about the threshholds.....

-David

This is how I do it: if the history table entry equals 0 (which means that this move has not led to a cut-off before), then I reduce this subtree with 1 full ply. By the way, I maintain 2 history table (one for each side). I haven't tried values higher than 0. It really results in an improvement for Wing, because less-interesting moves aren't searched as deep as 'better' moves, leaving much more time/depth for the 'better' moves.
There is some additional logic in my history pruning (don't allow it if razoring or futility pruning has already been done, etc).
Stef.

[David Weller]

reducing one ply is like pruning all the moves you would have searched at depth=1 - I guess - so you ARE removing nodes from the tree

I think this is what Dann was getting at. Good analogy Dann!

So 'reduction' is a 'kind' of pruning

The thing that keeps 'getting me', is that extensions and reductions seem to be too drastic a measure, and fractions dont seem to work for me iether

Fact is, on average, a 'check' isnt worth a whole extra ply[when you consider the cost], and its one of the most valuable extensions!

I am thinking of increasing reductions especially in extended sub-trees
so as to produce the net effect of 'reducing extensions'
- maybe I can 'extend reductions' too, the same way

Has anyone else had the same impression from extensions/reductions, or am I off?

Stef - It sounds similar to what I am trying now : anything with a history is good enough. I only gain a fraction of a ply in search depth, and still does badly in games. Apparently its broken

-David

[Uri Blass]

reducing one ply is like pruning all the moves you would have searched at depth=1 - I guess - so you ARE removing nodes from the tree

I think this is what Dann was getting at. Good analogy Dann!

So 'reduction' is a 'kind' of pruning

The thing that keeps 'getting me', is that extensions and reductions seem to be too drastic a measure, and fractions dont seem to work for me iether

Fact is, on average, a 'check' isnt worth a whole extra ply[when you consider the cost], and its one of the most valuable extensions!

I am thinking of increasing reductions especially in extended sub-trees
so as to produce the net effect of 'reducing extensions'
- maybe I can 'extend reductions' too, the same way

Has anyone else had the same impression from extensions/reductions, or am I off?

Stef - It sounds similar to what I am trying now : anything with a history is good enough. I only gain a fraction of a ply in search depth, and still does badly in games. Apparently its broken

-David

Some comments:
1)I do not think that on average check is not worth one ply.

2)If we talk about history pruning then I think that originally it gave me more plies because I used less other type of pruning.

I started by testing it in test suites and history pruning simply gave me better results in the ecmgcp test suite(I used it first in movei00_7_xx that was earlier version of 00_7_99 and I do not remember the exact version).

I think that you should not start by games but by test suites and if history pruning does not give you better results in test suites then something is probably wrong in it.

Note that in my case I have special conditions when not to use history pruning(for example I do not use it for moves that attack opponent heavy pieces)

When I saw failures in some test positions I tried to find out the reason for the failure and add conditions that prevent the failure.

Uri

[Volker Annuss]

I am thinking of increasing reductions especially in extended sub-trees
so as to produce the net effect of 'reducing extensions'
- maybe I can 'extend reductions' too, the same way

Has anyone else had the same impression from extensions/reductions, or am I off?

Hello David,

I do reducing extensions in the following way:

When there is a fractional part in the remaining depth, and there is neither an extension, nor a reduction in the current position: reduce by 1/7 ply.

So, most extensions only work, if they are close together.

Check, single reply and some others are extended by 6/7 plies.

Other situations, that would normally get extended 1/2 ply are extended by 4/7 plies.

Greetings,
Volker

[David Weller]

Thanks Volker,

I _think_ Crafty uses a similar approach.

Do you begin search with a fraction of an extension [eg., 2/7ths]?

I tried fractional extensions, and saw no difference really in performance,
But it may have been me [ as so many succeed with it ]

-David

[Volker Annuss]

I _think_ Crafty uses a similar approach.

Do you begin search with a fraction of an extension [eg., 2/7ths]?

Hello David,

I thought, I was the only one who reduces after extensions like that. I really don't know how Crafty does it.

The extensions start with 0, but that was different in early Versions of Hermann before I did the reductions after extension. Maybe it will change again. There is so much to test with extensions/reductions including history pruning...

Greetings,
Volker

[David Weller]

Volker,

You are right, I dont think he reduces as you do.

Yes, the number of parameters to experiment with are daunting indeed!

[smcracraft]

What I really want to know is why a reduction is called pruning?

Because it has the wrong name

It should be called history based reduction or something.

In its original form it was called Positional Quiescence Search (IIRC) but it was used oposite.
Moves with a good history were tried in quiescence search as well.

Tony

Tord likes to call it late move reduction.

I it as #ifdef LATEMOVEREDUCTION and #define LATEMOVEREDUCTION
in my default program.

The result was 1%-2% better results on my limited test suite, but since
it is much more selective, I left it in since I wanted to become a purist
selectively.



Stuart