Fruit and History Reductions

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ed

Fruit and History Reductions

Post by ed » Thu Jul 19, 2007 3:50 pm

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

Re: Fruit and History Reductions

Post by Peter Fendrich » Thu Jul 19, 2007 4:23 pm

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

Re: Fruit and History Reductions

Post by Vempele » Thu Jul 19, 2007 4:59 pm

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
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

Re: Fruit and History Reductions

Post by ed » Thu Jul 19, 2007 9:00 pm

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

Re: Fruit and History Reductions

Post by bob » Thu Jul 19, 2007 9:16 pm

ed wrote:
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
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
Posts: 281
Joined: Thu Mar 16, 2006 6:39 pm

Re: Fruit and History Reductions

Post by Cardoso » Fri Jul 20, 2007 10:49 am

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

Re: Fruit and History Reductions

Post by Uri Blass » Fri Jul 20, 2007 1:29 pm

bob wrote:
ed wrote:
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
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

User avatar
hgm
Posts: 23000
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fruit and History Reductions

Post by hgm » Fri Jul 20, 2007 1:57 pm

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

Re: Fruit and History Reductions

Post by Uri Blass » Fri Jul 20, 2007 2:34 pm

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.
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

User avatar
hgm
Posts: 23000
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Fruit and History Reductions

Post by hgm » Fri Jul 20, 2007 2:39 pm

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

Post Reply