Fruit and History Reductions

[ed]

In the Fruit source code I find the following 2 parameters for History Reductions:

{ "History Pruning", true, "true", "check", "", NULL },
{ "History Move Number", true, "3", "spin", "min 1 max 10", NULL },
{ "History Threshold", true, "60", "spin", "min 0 max 100", NULL },

I am bad in code reading, what does "History Move Number" and "History Threshold" do?

Ed

[Peter Fendrich]

This is what it ment in Terra and still in Alaric:
History Move Number: The move number in your ordered list of moves t this node. The moves after that are regarded as "late" in LMR (Late Move Reduction)

History Treshold: You want to reduce "Late moves" (as above) but first you check that moves history performance. This is probably meassured differently in different programs (for instance number of fail high and fail low) and it is saved in the history table. If the move is "late" and its history value is below this treshold it is time to reduce!

/Peter

[Vempele]

In the Fruit source code I find the following 2 parameters for History Reductions:

{ "History Pruning", true, "true", "check", "", NULL },
{ "History Move Number", true, "3", "spin", "min 1 max 10", NULL },
{ "History Threshold", true, "60", "spin", "min 0 max 100", NULL },

I am bad in code reading, what does "History Move Number" and "History Threshold" do?

Ed

Which version of Fruit? I couldn't find "History Move Number" but it almost certainly means that at least this many moves have to be searched to full depth, seeing as played_nb >= HistoryMoveNb is one of the conditions, with played_nb being incremented at the end of the move loop.

History Threshold is the percentage of fail highs out of the total number of times the move has been tried (and been non-'tactical', the meaning of which I'm not sure about. It probably just excludes captures and promotions).

[ed]

This is what it ment in Terra and still in Alaric:
History Move Number: The move number in your ordered list of moves t this node. The moves after that are regarded as "late" in LMR (Late Move Reduction)

History Treshold: You want to reduce "Late moves" (as above) but first you check that moves history performance. This is probably meassured differently in different programs (for instance number of fail high and fail low) and it is saved in the history table. If the move is "late" and its history value is below this treshold it is time to reduce!

/Peter

Understood now. I don't use the LMR condition, I just don't reduce PVS moves, captures, promotions, checking moves, king out of check moves, mate threats and moves that are within a 1/4 pawn margin of alpha.

Ed

[bob]

This is what it ment in Terra and still in Alaric:
History Move Number: The move number in your ordered list of moves t this node. The moves after that are regarded as "late" in LMR (Late Move Reduction)

History Treshold: You want to reduce "Late moves" (as above) but first you check that moves history performance. This is probably meassured differently in different programs (for instance number of fail high and fail low) and it is saved in the history table. If the move is "late" and its history value is below this treshold it is time to reduce!

/Peter

Understood now. I don't use the LMR condition, I just don't reduce PVS moves, captures, promotions, checking moves, king out of check moves, mate threats and moves that are within a 1/4 pawn margin of alpha.

Ed

I've stopped using history stuff completely as well. There are other ways to decide to not reduce besides that...

[Cardoso]

Could you please tell me about those methods?
It has been some time I don't read the latest crafty's source.
Are those implemented in the latest version of crafty?

best regards,
alvaro

[Uri Blass]

This is what it ment in Terra and still in Alaric:
History Move Number: The move number in your ordered list of moves t this node. The moves after that are regarded as "late" in LMR (Late Move Reduction)

History Treshold: You want to reduce "Late moves" (as above) but first you check that moves history performance. This is probably meassured differently in different programs (for instance number of fail high and fail low) and it is saved in the history table. If the move is "late" and its history value is below this treshold it is time to reduce!

/Peter

Understood now. I don't use the LMR condition, I just don't reduce PVS moves, captures, promotions, checking moves, king out of check moves, mate threats and moves that are within a 1/4 pawn margin of alpha.

Ed

I've stopped using history stuff completely as well. There are other ways to decide to not reduce besides that...

I am not sure what do you mean that you stopped using history stuff completely.

Even without history counters you can use history stuff.

1)Do you have a rule never to reduce killer moves?
I think that if you have a rule never to reduce killer moves then this rule is based on history stuff because the question if a move is killer move is based on history of the search.

2)Do you have a rule never to reduce the first N moves for some N?
If you have a rule like that then again you use history stuff because
I assume that order of the first moves after good captures and killers is based on history tables and you practically do not reduce moves that caused cutoff more often by not reducing first N moves.

Uri

[hgm]

If I understood Bob right in earlier postings on move ordering, Crafty does not use history tables to order the non-captures, but just searches them in move-generation order.

I don't think the killer heuristic is related to what people call 'history tables'. Killers are (cut-)moves very recently used at the same level in the tree. Almost always that means that they are the (non-capture) refutation of a previous move from the same all-node. Most likely they were set by the null-move search from that node (if you do null move in all-nodes), if there were no captures to refute the null move, but there was a non-capture that did. (E.g. a fork, or a very good positional move such as a passer push or restauration of King safety.) And what works against the null move is likely to work against most other moves as well, as most moves do not really change very much.

The killers are thus really a very local thing, determined by the position from which the move that they refute was done.

[Uri Blass]

If I understood Bob right in earlier postings on move ordering, Crafty does not use history tables to order the non-captures, but just searches them in move-generation order.

I don't think the killer heuristic is related to what people call 'history tables'. Killers are (cut-)moves very recently used at the same level in the tree. Almost always that means that they are the (non-capture) refutation of a previous move from the same all-node. Most likely they were set by the null-move search from that node (if you do null move in all-nodes), if there were no captures to refute the null move, but there was a non-capture that did. (E.g. a fork, or a very good positional move such as a passer push or restauration of King safety.) And what works against the null move is likely to work against most other moves as well, as most moves do not really change very much.

The killers are thus really a very local thing, determined by the position from which the move that they refute was done.

1)I do not know about latest Crafty but I remember that at least old versions of Crafty used history tables to order the first moves.

They did not use them to order all moves and after some history moves Crafty did not use history tables to order the rest of the moves but simply ordered them based on the order of generation.

2)Bob wrote:
"I've stopped using history stuff completely as well. There are other ways to decide to not reduce besides that..."

I mentioned killer moves because I see the word history stuff as different than history tables and killer moves are clearly based on history stuff and the decision which moves to reduce is not based only on the position(for comparison decision always to extend checks is not based on history stuff and it is possible to have reduction decisions that are not based on history stuff).

Uri

[hgm]

I interpreted Bob's 'history stuff' as anything that depends on the history tables (e.g. reductions as well as move ordering).