Page 1 of 2
Can someone explain this?
Posted: Thu Oct 08, 2009 12:00 am
by Michel
Code: Select all
value = sort->value; // history score
if (!in_check && depth <= 6 && node_type != NodePV
&& new_depth < depth && value < HistoryValue/(depth/3+1)
&& played_nb >= 1+depth && !move_is_dangerous(move,board)){
continue;
}
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?
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 12:39 am
by 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
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 12:57 am
by bob
Michel wrote:Code: Select all
value = sort->value; // history score
if (!in_check && depth <= 6 && node_type != NodePV
&& new_depth < depth && value < HistoryValue/(depth/3+1)
&& played_nb >= 1+depth && !move_is_dangerous(move,board)){
continue;
}
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.
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 7:51 am
by 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/(depth/3+1)
&& played_nb >= 1+depth && !move_is_dangerous(move,board)){
continue; <---------------
}
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.
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 8:38 am
by Edsel Apostol
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/(depth/3+1)
&& played_nb >= 1+depth && !move_is_dangerous(move,board)){
continue; <---------------
}
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.
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 9:17 am
by 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).
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 10:28 am
by Uri Blass
Michel wrote:Code: Select all
value = sort->value; // history score
if (!in_check && depth <= 6 && node_type != NodePV
&& new_depth < depth && value < HistoryValue/(depth/3+1)
&& played_nb >= 1+depth && !move_is_dangerous(move,board)){
continue;
}
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
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 10:47 am
by mcostalba
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.
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 11:25 am
by Edsel Apostol
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.
Re: Can someone explain this?
Posted: Thu Oct 08, 2009 2:37 pm
by 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.