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.
User avatar
lucasart
Posts: 3041
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: History pruning / move ordering question

Post by lucasart » Wed May 15, 2013 1:33 am

Don wrote:
lucasart wrote: Now for using the refutation in LMR, I will simply try to use it as an LMR veto (like killers). Given the way DiscoCheck does search reductions (not quite standard and probably lame) reducing the reduction by one ply as you suggest, or not reducing at all the refutation move, would amount to the same.

But when using the refutation move as an LMR veto, I will use (2), because the fact that it's more specific probably means the cost is going to be less. For the moment it's looking very good, but I've just started the test, so I'm a bit worried to post early results and get too excited ;-)
Yes, this can be embarrassing. I sometimes call Larry and say, "it's off to a great start!!!" only be made a fool out of. Of course I know better but you want to see improvement so you get excited.
A good thing I didn't get overexcited, the result of my test is too close to call:
* 10k games in 10"+0.1"
* W: 2819 L: 2760 D: 4421, score = 50.3%, p-value = 78.5%

Anyway, I'll still commit, as it is slightly positive (even if within error bar) and more importaltly it reduces reductions, hence the risk of tactical accidents (which seem to be the cause of lots of losses at long TC when looking at Graham's tournaments).

This counter move heuristic is a real gem. Many things I need to try in DiscoCheck:

1. Joona Kiiski's idea:
1.0 using two slots instead of 1
1.1 why not N slots and seeing which N is best?
1.2 with that can the difference fsq/tsq instead of piece/tsq be finally measurable?

2. Daniel Homan's idea
2.0 using a double move refutation hash table (nice generalisation of the counter move heuristic)
2.1 why not N consecutive moves? (just as easy to implement with the added detail that if N is odd you must xor out the zobrist turn of play). Intuitively it seems unlikely that extending it t more than 2 moves will work, but te only way to know for sure is to test.
2.1 same question as for the basic counter move heuristic: use in LMR or just in ordering? (my guess is that doing both will be best in DiscoCheck)
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

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

Re: History pruning / move ordering question

Post by lucasart » Wed May 15, 2013 1:50 am

lucasart wrote: 2. Daniel Homan's idea
2.0 using a double move refutation hash table (nice generalisation of the counter move heuristic)
2.1 why not N consecutive moves? (just as easy to implement with the added detail that if N is odd you must xor out the zobrist turn of play). Intuitively it seems unlikely that extending it t more than 2 moves will work, but te only way to know for sure is to test.
2.1 same question as for the basic counter move heuristic: use in LMR or just in ordering? (my guess is that doing both will be best in DiscoCheck)
What is also nice about Daniel's double move refutation hash table, is that one of these two moves can be a null move. And we know that these are very frequent in modern chess engines. That could be part of the explanation why it outperforms significantly the basic counter move heuristic in his program EXChess.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: History pruning / move ordering question

Post by Evert » Wed May 15, 2013 9:35 am

lucasart wrote: (1) refutation[color][piece][tsq] used as a 3-rd killer for move ordering is a clear gain (about +9 ELO after 10000 games in 10"+0.1")
Same in Jazz, actually (verified).

Stockfish testing appears to suggest that there's actually more to be had here...

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

Re: History pruning / move ordering question

Post by lucasart » Wed May 15, 2013 10:28 am

So far the best implementation of counter move heuristic I could get is:
- refutation[color][piece][tsq]: nothing fancy, always overwrite (tried with two slots didn't work)
- use as 3-rd killer both for move ordering and as an LMR guard.

I'm now toying with Daniel Homan's double move refutation hash table, and so far the results are promosing. It seems clearly superior to the above! So (at least for DiscoCheck) there's more ELO to be had using this. And I really like this idea, because it's elegant and more general than the basic counter move heuristic.

My intuition tells me that the Null Move plays a role here. The point is that in the counter move heuristic you have to exclude it, because knowing that the previous move was null doesn't give you any information (there are lots of those in the search) to decide on a refutation candidate. But with double move hash key, you will have for example things like (e2e4, <null>) -> d2d4. So we can now provide good null refutation candidates with this double move refutation hash table.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: History pruning / move ordering question

Post by Evert » Wed May 15, 2013 11:31 am

lucasart wrote:So far the best implementation of counter move heuristic I could get is:
- refutation[color][piece][tsq]: nothing fancy, always overwrite (tried with two slots didn't work)
- use as 3-rd killer both for move ordering and as an LMR guard.

I'm now toying with Daniel Homan's double move refutation hash table, and so far the results are promosing. It seems clearly superior to the above! So (at least for DiscoCheck) there's more ELO to be had using this. And I really like this idea, because it's elegant and more general than the basic counter move heuristic.

My intuition tells me that the Null Move plays a role here. The point is that in the counter move heuristic you have to exclude it, because knowing that the previous move was null doesn't give you any information (there are lots of those in the search) to decide on a refutation candidate. But with double move hash key, you will have for example things like (e2e4, <null>) -> d2d4. So we can now provide good null refutation candidates with this double move refutation hash table.
I have "continuation" moves, which are the same as counter moves except indexed by the last move from the same side, and a "null killer", which is a killer that refuted a null move. I don't remember what each of those is worth, but it was less than the counter move itself. It sounds like this would partially do the same thing.

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

Re: History pruning / move ordering question

Post by lucasart » Wed May 15, 2013 11:34 am

Evert wrote: I have "continuation" moves, which are the same as counter moves except indexed by the last move from the same side, and a "null killer", which is a killer that refuted a null move. I don't remember what each of those is worth, but it was less than the counter move itself. It sounds like this would partially do the same thing.
You should try to replace your null killers and continuation moves alltogether with a double move refutation hash table.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

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

Re: History pruning / move ordering question

Post by Don » Wed May 15, 2013 1:05 pm

lucasart wrote:So far the best implementation of counter move heuristic I could get is:
- refutation[color][piece][tsq]: nothing fancy, always overwrite (tried with two slots didn't work)
- use as 3-rd killer both for move ordering and as an LMR guard.

I'm now toying with Daniel Homan's double move refutation hash table, and so far the results are promosing. It seems clearly superior to the above! So (at least for DiscoCheck) there's more ELO to be had using this. And I really like this idea, because it's elegant and more general than the basic counter move heuristic.
Note that how well these things work are going to depend a lot on what you already do. I'm pretty happy with how we do history for example because turning it off creates a drastic ELO reduction. So if you are not doing history really well this could be a major gain. If you are are, it might be a small gain or even a regression.

So anyway, I guess it goes without saying that you simply have to try it to see if it works for you.

My intuition tells me that the Null Move plays a role here. The point is that in the counter move heuristic you have to exclude it, because knowing that the previous move was null doesn't give you any information (there are lots of those in the search) to decide on a refutation candidate. But with double move hash key, you will have for example things like (e2e4, <null>) -> d2d4. So we can now provide good null refutation candidates with this double move refutation hash table.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

dchoman
Posts: 171
Joined: Wed Dec 28, 2011 7:44 pm
Location: United States

Re: History pruning / move ordering question

Post by dchoman » Wed May 15, 2013 4:20 pm

lucasart wrote:So far the best implementation of counter move heuristic I could get is:
- refutation[color][piece][tsq]: nothing fancy, always overwrite (tried with two slots didn't work)
- use as 3-rd killer both for move ordering and as an LMR guard.

I'm now toying with Daniel Homan's double move refutation hash table, and so far the results are promosing. It seems clearly superior to the above! So (at least for DiscoCheck) there's more ELO to be had using this. And I really like this idea, because it's elegant and more general than the basic counter move heuristic.

My intuition tells me that the Null Move plays a role here. The point is that in the counter move heuristic you have to exclude it, because knowing that the previous move was null doesn't give you any information (there are lots of those in the search) to decide on a refutation candidate. But with double move hash key, you will have for example things like (e2e4, <null>) -> d2d4. So we can now provide good null refutation candidates with this double move refutation hash table.
I was preventing sequences with null moves from contributing to this table on the logic that null moves are easy to refute anyway and that might fill up the table, but this is an interesting idea... particularly when the null move is the first move in the two-move sequence. I will try it.

- Dan

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

Re: History pruning / move ordering question

Post by jd1 » Mon May 20, 2013 10:25 pm

jdart wrote:I use 1. for ordering and 2. for pruning as Toga does. It is actually in one table but the table contains structs and different fields are used.

But I have other kinds of pruning besides history pruning, including Late Move Pruning, which ignores history. So the history pruning is not acting alone.
Ok, just to report: I got an amazing ~20 elo improvement after >4000 games simply by adding conservative late move pruning of quiet moves. Thanks for the suggestion!

Jerry

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

Re: History pruning / move ordering question

Post by elcabesa » Wed May 22, 2013 9:23 pm

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;

Post Reply