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
Fruit and History Reductions
Moderators: hgm, Rebel, chrisw
Re: Fruit and History Reductions
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
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
Re: Fruit and History Reductions
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.ed wrote: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
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).
Re: Fruit and History Reductions
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.Peter Fendrich wrote: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
Ed
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Fruit and History Reductions
I've stopped using history stuff completely as well. There are other ways to decide to not reduce besides that...ed wrote: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.Peter Fendrich wrote: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
Ed
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
Re: Fruit and History Reductions
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
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
-
- Posts: 10309
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Fruit and History Reductions
I am not sure what do you mean that you stopped using history stuff completely.bob wrote:I've stopped using history stuff completely as well. There are other ways to decide to not reduce besides that...ed wrote: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.Peter Fendrich wrote: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
Ed
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
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fruit and History Reductions
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.
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.
-
- Posts: 10309
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Fruit and History Reductions
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.hgm wrote: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.
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
-
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Fruit and History Reductions
I interpreted Bob's 'history stuff' as anything that depends on the history tables (e.g. reductions as well as move ordering).