Can someone explain this?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michel
Posts: 2047
Joined: Sun Sep 28, 2008 11:50 pm

Can someone explain this?

Post by Michel » Wed Oct 07, 2009 10:00 pm

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
Posts: 454
Joined: Sat Apr 04, 2009 4:44 pm
Location: Bulgaria
Contact:

Re: Can someone explain this?

Post by Mincho Georgiev » Wed Oct 07, 2009 10:39 pm

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
Posts: 20555
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Can someone explain this?

Post by bob » Wed Oct 07, 2009 10:57 pm

Michel wrote:

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
Posts: 2047
Joined: Sun Sep 28, 2008 11:50 pm

Re: Can someone explain this?

Post by Michel » Thu Oct 08, 2009 5:51 am

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
Posts: 762
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Can someone explain this?

Post by Edsel Apostol » Thu Oct 08, 2009 6:38 am

Michel wrote:
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
Posts: 2047
Joined: Sun Sep 28, 2008 11:50 pm

Re: Can someone explain this?

Post by Michel » Thu Oct 08, 2009 7:17 am

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
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Can someone explain this?

Post by Uri Blass » Thu Oct 08, 2009 8:28 am

Michel wrote:

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Can someone explain this?

Post by mcostalba » Thu Oct 08, 2009 8:47 am

Michel wrote: 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
Posts: 762
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Can someone explain this?

Post by Edsel Apostol » Thu Oct 08, 2009 9:25 am

Michel wrote:
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
Posts: 3757
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Can someone explain this?

Post by Daniel Shawul » Thu Oct 08, 2009 12:37 pm

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.

Post Reply