History pruning / move ordering question

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.
jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Thu May 23, 2013 4:49 am

elcabesa wrote:today I tried playing with history leaf pruning.
I simple calculate an average HistoryValue that cause alpha to raise indexed by the distance from the root.
Then at depth 1 I prune the quiet move with history <0.1 average HistoryValue.
some first test seems to give me an elo improvement. I'll try to be more precise tomorrow :)

Code: Select all

global...
unsigned long long 	historyLeafPruningStat&#91;50&#93;=&#123;0&#125;,
					historyLeafPruningCount&#91;50&#93;=&#123;0&#125;;

.....
.....
if &#40;value>bestmove&#41;&#123;

// SAVE AVERAGE HISTORY VALUE OF MOVES THAT RAISES ALPHA   
if&#40;depth<=1&#41;&#123;
	historyLeafPruningStat&#91;ply&#93;+=historyTable&#91;color&#93;&#91;board.square&#91;m.from&#93;&#93;&#91;m.to&#93;;
	historyLeafPruningCount&#91;ply&#93;++;
	&#125;
&#125;


....
....
....
//INSIDE THE FUTILITY PRUNING 

// history leaf pruning
	if&#40;depth<=1 &&
		historyLeafPruningCount&#91;ply&#93;!=0 &&
		historyTable&#91;1-color&#93;&#91;board.square&#91;m.to&#93;&#93;&#91;m.to&#93;<&#40;float&#41;historyLeafPruningStat&#91;ply&#93;/historyLeafPruningCount&#91;ply&#93;*0.1&#41;&#123;
			board.unmakeMove&#40;);
			continue;
	&#125;
Hi Marco,

I expect you should be able to get an sizeable improvement from this eventually :)

Some observations:
1. Why do you make the move before trying history leaf (and I presume also futility) pruning? It seems to me that this is a waste of CPU time.

2. Most engines index the history table by [color][piece][to] rather than by [color][from][to], possibly you might like to try it.

3. Eventually you should be able to prune more (0.1x seems very conservative) and also at higher remaining depths too, I would think.

4. Your idea of calculating an average history value by ply seems interesting! I haven't seen this before.

5. Have you tried pruning based on the number of quiet moves played instead (or maybe you already have late move pruning)? Stockfish does this, and it works for Toga too, e.g.:

Code: Select all

static const int QuietMoveCountLimit&#91;6&#93; = &#123;0, 4, 7, 12, 19, 28&#125;;

// later in futility pruning ...

// move count based pruning             
if &#40;quiet_move_count >= QuietMoveCountLimit&#91;depth&#93;&#41;continue;

Regards,
Jerry

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: History pruning / move ordering question

Post by elcabesa » Thu May 23, 2013 6:08 pm

1. Why do you make the move before trying history leaf (and I presume also futility) pruning? It seems to me that this is a waste of CPU time.
it's because I only test if a move is a chech after doing it. So i need to make the move to understand if it's a check
2. Most engines index the history table by [color][piece][to] rather than by [color][from][to], possibly you might like to try it.
if you look another time you'll see I'm doing [color][piece][to]
:)
3. Eventually you should be able to prune more (0.1x seems very conservative) and also at higher remaining depths too, I would think.
yes probably I could prune even more.
4. Your idea of calculating an average history value by ply seems interesting! I haven't seen this before.
I did it because I didn't know in advance what time control is used in games so I didn't know the average value of the history. I tried to gather some statistics and eventually I used this stat as a parameter for pruning.
5. Have you tried pruning based on the number of quiet moves played instead (or maybe you already have late move pruning)? Stockfish does this, and it works for Toga too, e.g.:
I already did it :)[/quote]

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: History pruning / move ordering question

Post by Don » Thu May 23, 2013 6:42 pm

elcabesa wrote:
1. Why do you make the move before trying history leaf (and I presume also futility) pruning? It seems to me that this is a waste of CPU time.
it's because I only test if a move is a chech after doing it. So i need to make the move to understand if it's a check.
I have a routine that tell me if a move is going to be check without making the move, but it's probably not worth but a little.

However, it really pays to have a routine that generates only quiet checking moves. But that's probably a different issue.
2. Most engines index the history table by [color][piece][to] rather than by [color][from][to], possibly you might like to try it.
if you look another time you'll see I'm doing [color][piece][to]
:)
3. Eventually you should be able to prune more (0.1x seems very conservative) and also at higher remaining depths too, I would think.
yes probably I could prune even more.
4. Your idea of calculating an average history value by ply seems interesting! I haven't seen this before.
I did it because I didn't know in advance what time control is used in games so I didn't know the average value of the history. I tried to gather some statistics and eventually I used this stat as a parameter for pruning.
5. Have you tried pruning based on the number of quiet moves played instead (or maybe you already have late move pruning)? Stockfish does this, and it works for Toga too, e.g.:
I already did it :)
[/quote]
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

jd1
Posts: 266
Joined: Wed Oct 24, 2012 12:07 am

Re: History pruning / move ordering question

Post by jd1 » Thu May 23, 2013 9:03 pm

elcabesa wrote:
1. Why do you make the move before trying history leaf (and I presume also futility) pruning? It seems to me that this is a waste of CPU time.
it's because I only test if a move is a chech after doing it. So i need to make the move to understand if it's a check
2. Most engines index the history table by [color][piece][to] rather than by [color][from][to], possibly you might like to try it.
if you look another time you'll see I'm doing [color][piece][to]
:)
Oh yes, sorry for not looking thoroughly enough!
3. Eventually you should be able to prune more (0.1x seems very conservative) and also at higher remaining depths too, I would think.
yes probably I could prune even more.
4. Your idea of calculating an average history value by ply seems interesting! I haven't seen this before.
I did it because I didn't know in advance what time control is used in games so I didn't know the average value of the history. I tried to gather some statistics and eventually I used this stat as a parameter for pruning.
Thanks for explaining, I might try something similar :)
5. Have you tried pruning based on the number of quiet moves played instead (or maybe you already have late move pruning)? Stockfish does this, and it works for Toga too, e.g.:
I already did it :)
[/quote]

All the best to you and Vajolet,
Jerry

User avatar
Rebel
Posts: 4788
Joined: Thu Aug 18, 2011 10:04 am

Re: History pruning / move ordering question

Post by Rebel » Fri May 24, 2013 7:47 am

lucasart wrote: Anyway, there are many variations of the idea to test, and it's very possible that what works best for Komodo is not what works best for Jazz, Stockfish or DiscoCheck. For now I'll try things one at a time:
- use it as a third killer for move ordering
- use it as an LMR veto
- remove the 2nd killer and use the refutation move in its stead (for ordering and as LMR veto)
- try other variations like fsq/tsq instead of piece/tsq. perhaps even your piece/fsq/tsq.
Another (minor one) to try, don't change killer moves when you are moving out of check, like capture moves it pollutes. Or create a special killer slot for king in check situations. As you can imagine this is no biggie.

User avatar
lucasart
Posts: 3046
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: History pruning / move ordering question

Post by lucasart » Fri May 24, 2013 3:31 pm

Rebel wrote: Another (minor one) to try, don't change killer moves when you are moving out of check, like capture moves it pollutes. Or create a special killer slot for king in check situations. As you can imagine this is no biggie.
I've tried that already. Unfortunately it doesn't seem to work for me, although it's not a clear regression either.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

Post Reply