History pruning / move ordering question

[jd1]

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[50]={0},
					historyLeafPruningCount[50]={0};

.....
.....
if (value>bestmove){

// SAVE AVERAGE HISTORY VALUE OF MOVES THAT RAISES ALPHA   
if(depth<=1){
	historyLeafPruningStat[ply]+=historyTable[color][board.square[m.from]][m.to];
	historyLeafPruningCount[ply]++;
	}
}


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

// history leaf pruning
	if(depth<=1 &&
		historyLeafPruningCount[ply]!=0 &&
		historyTable[1-color][board.square[m.to]][m.to]<(float)historyLeafPruningStat[ply]/historyLeafPruningCount[ply]*0.1){
			board.unmakeMove();
			continue;
	}

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[6] = {0, 4, 7, 12, 19, 28};

// later in futility pruning ...

// move count based pruning             
if (quiet_move_count >= QuietMoveCountLimit[depth])continue;

Regards,
Jerry

[elcabesa]

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]

[Don]

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]

[jd1]

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

[Rebel]

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.

[lucasart]

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.