Can someone explain this?

[Michel]

Code: Select all

      
          value = sort->value; // history score
          if (!in_check && depth <= 6  && node_type != NodePV
                  && new_depth < depth && value < HistoryValue/&#40;depth/3+1&#41; 
                  && played_nb >= 1+depth && !move_is_dangerous&#40;move,board&#41;)&#123;                      
                        continue;
          &#125;

This is Toga's code for history pruning. However I don't understand why this is supposed to
work. Moves with low history value are pruned. But then they can never become the best move. So their history value cannot improve.

The test depth<=6 is probably supposed to soften this effect but is it enough?

[Mincho Georgiev]

Not quite correct. You see, the simplified logic is that if the move is made in a PV-NODE and causes cut-off, the history value will be increased though.

node_type != NodePV

[bob]

Code: Select all

      
          value = sort->value; // history score
          if (!in_check && depth <= 6  && node_type != NodePV
                  && new_depth < depth && value < HistoryValue/&#40;depth/3+1&#41; 
                  && played_nb >= 1+depth && !move_is_dangerous&#40;move,board&#41;)&#123;                      
                        continue;
          &#125;

This is Toga's code for history pruning. However I don't understand why this is supposed to
work. Moves with low history value are pruned. But then they can never become the best move. So their history value cannot improve.

The test depth<=6 is probably supposed to soften this effect but is it enough?

They are not pruned. They are searched to a reduced depth. And what happens at this node is not necessarily what happens at other nodes in the tree, and since the history counters are global, they do get changed. They are not worth a flip for this purpose (pruning/reduction decisions) but that is a different topic.

[Michel]

They are not pruned. They are searched to a reduced depth.

No they are really pruned. Look at the continue statement (this is a loop over the valid moves)

Code: Select all

     
          value = sort->value; // history score
          if (!in_check && depth <= 6  && node_type != NodePV
                  && new_depth < depth && value < HistoryValue/&#40;depth/3+1&#41;
                  && played_nb >= 1+depth && !move_is_dangerous&#40;move,board&#41;)&#123;                     
                        continue;   <---------------
          &#125; 

You are referring to LMR. This is done elsewhere in the search. It does not use history counters AFAICS (in contrast to Fruit 2.1).

You see, the simplified logic is that if the move is made in a PV-NODE and causes cut-off, the history value will be increased though.

I guess you are right. I had overlooked the restriction to non-PV nodes.

[Edsel Apostol]

They are not pruned. They are searched to a reduced depth.

No they are really pruned. Look at the continue statement (this is a loop over the valid moves)

Code: Select all

     
          value = sort->value; // history score
          if (!in_check && depth <= 6  && node_type != NodePV
                  && new_depth < depth && value < HistoryValue/&#40;depth/3+1&#41;
                  && played_nb >= 1+depth && !move_is_dangerous&#40;move,board&#41;)&#123;                     
                        continue;   <---------------
          &#125; 

You are referring to LMR. This is done elsewhere in the search. It does not use history counters AFAICS (in contrast to Fruit 2.1).

You see, the simplified logic is that if the move is made in a PV-NODE and causes cut-off, the history value will be increased though.

I guess you are right. I had overlooked the restriction to non-PV nodes.

I am not sure what did you mean but I think it still uses history counters. The value assigned in sort->value contains that.

[Michel]

I am not sure what did you mean but I think it still uses history counters. The value assigned in sort->value contains that.

Do people actually read each other posts . Of course the code I quoted uses history counters. I didn't quite understand how it was supposed to work (I think I do now).

But then Bob Hyatt started talking about LMR. I replied to him by saying that LMR in Toga does not explicitly use history counters as far as I can see (it uses them implicitly of course since the history counters are used for move ordering).

[Uri Blass]

Code: Select all

      
          value = sort->value; // history score
          if (!in_check && depth <= 6  && node_type != NodePV
                  && new_depth < depth && value < HistoryValue/&#40;depth/3+1&#41; 
                  && played_nb >= 1+depth && !move_is_dangerous&#40;move,board&#41;)&#123;                      
                        continue;
          &#125;

This is Toga's code for history pruning. However I don't understand why this is supposed to
work. Moves with low history value are pruned. But then they can never become the best move. So their history value cannot improve.

The test depth<=6 is probably supposed to soften this effect but is it enough?

The condition depth<=6 means that moves with low history value can become best move because not all the searches are to depth that is lower than 6.

Uri

[mcostalba]

The test depth<=6 is probably supposed to soften this effect but is it enough?

On one side you want to have many values in history, on the other side you don't want to have random noise in history.

These two aspects are one against the other. So the _standard_ compromise is to value more history values from high depths then from low depths.

There are two reasons for this

1) High depth nodes are far less, so history values from high depths are less and will not randomize the table as easy as low depth values.

2) The gain in time saving you have from a cut-off at high depth is much bigger then a cut-off at low depth


So the compromise in Toga (but also in other engines) is to _risk_ to loose some good cut-off at low depth to keep the table clean and so have a bigger probability to catch a cut-off at higher depth that pays more in terms of time savings.

[Edsel Apostol]

I am not sure what did you mean but I think it still uses history counters. The value assigned in sort->value contains that.

Do people actually read each other posts . Of course the code I quoted uses history counters. I didn't quite understand how it was supposed to work (I think I do now).

But then Bob Hyatt started talking about LMR. I replied to him by saying that LMR in Toga does not explicitly use history counters as far as I can see (it uses them implicitly of course since the history counters are used for move ordering).

The last time I really studied Toga was a long time ago and I remembered that it is still using History counters for LMR that time. I've checked the latest version and you are right, it does't use them anymore explicitly. It was a mistake on my part.

As for your question how it should work, History pruning in Toga/Fruit/Stockfish/Glaurung prunes moves based on the percentage/probability of that move giving a cut-off as retrieved from the history counters. It's like a beta cut-off statistic thing. Moves that has not been searched will not be pruned but those moves that has been searched at least a few times and has a cutoff probability less than the defined threshold will be pruned.

In my opinion it is only good at fast time controls but would not be that effective when used in longer time controls. That's why I'm not using it on my engine, though I'm tempted to put it in as it was around 40 elo worth in my previous engine two years ago.

[Daniel Shawul]

And also , the move pruned at iteration x will get out of the horizon (depth <= 6) on next bigger iterations. I actually had (depth < iteration_depth / 3) as a criterion.