move count based pruning

[silentshark]

As used in Stockfish..

Seems like the deal is this - at a given depth, after a certain number of moves have been searched (and some other conditions are met, like not being in check) - don't search the move.

The further from the leaves you are, the more moves need to have been searched before this kicks in.

Simple, and similar to LMR, but more aggressive; we prune instead of reduce if conditions are met.

I imagine this can cut huge swathes out of search trees. Anyone had any luck with implementation?

(I'm currently testing an implementation which is a little less agressive than that in Stockfish, and it seems to be more-or-less a wash).

[Don]

As used in Stockfish..

Seems like the deal is this - at a given depth, after a certain number of moves have been searched (and some other conditions are met, like not being in check) - don't search the move.

The further from the leaves you are, the more moves need to have been searched before this kicks in.

Simple, and similar to LMR, but more aggressive; we prune instead of reduce if conditions are met.

I imagine this can cut huge swathes out of search trees. Anyone had any luck with implementation?

(I'm currently testing an implementation which is a little less agressive than that in Stockfish, and it seems to be more-or-less a wash).

I do this in Komodo, but I don't take it too far. Depending on which version of Komodo we are talking about I do either 2 or 3 ply of this near the leaf nodes.

[silentshark]

I do this in Komodo, but I don't take it too far. Depending on which version of Komodo we are talking about I do either 2 or 3 ply of this near the leaf nodes.

I may have got it wrong, but I was staggered at how aggressive the Stockfish implementation seemed to be - pruning stuff from move 4 onward at depth 1, for instance.. are you willing to share Komodo's paramters in this area?

[Don]

I do this in Komodo, but I don't take it too far. Depending on which version of Komodo we are talking about I do either 2 or 3 ply of this near the leaf nodes.

I may have got it wrong, but I was staggered at how aggressive the Stockfish implementation seemed to be - pruning stuff from move 4 onward at depth 1, for instance.. are you willing to share Komodo's paramters in this area?

It's not big deal - this is one of those things that might work better in some programs more than others.

Basically, the current version of Komodo does not do LMR on the last 2 ply. If we are NOT in a PV node and on the last 2 ply of the search I will look at either 10 or 6 legal moves and throw out everything else. However I will not do this if the mover is in check or has just given check or the move is considered interesting - but I think only passed pawn push to the 6th or 7th triggers what is interesting.

For some reason we consider legal moves for this idea, for most other things I count quiet move, such as for LMR I requires N quiet moves before doing further reductions as we traverse the move list. I'm not sure why we are not consistent about this but it must have tested well.

[silentshark]

I do this in Komodo, but I don't take it too far. Depending on which version of Komodo we are talking about I do either 2 or 3 ply of this near the leaf nodes.

I may have got it wrong, but I was staggered at how aggressive the Stockfish implementation seemed to be - pruning stuff from move 4 onward at depth 1, for instance.. are you willing to share Komodo's paramters in this area?

It's not big deal - this is one of those things that might work better in some programs more than others.

Basically, the current version of Komodo does not do LMR on the last 2 ply. If we are NOT in a PV node and on the last 2 ply of the search I will look at either 10 or 6 legal moves and throw out everything else. However I will not do this if the mover is in check or has just given check or the move is considered interesting - but I think only passed pawn push to the 6th or 7th triggers what is interesting.

For some reason we consider legal moves for this idea, for most other things I count quiet move, such as for LMR I requires N quiet moves before doing further reductions as we traverse the move list. I'm not sure why we are not consistent about this but it must have tested well.

Well, the parameters I'm trying are as follows:

@depth1, prune after 8 moves
@depth2, prune after 10 moves
@depth3, prune after 14 moves
@depth4, prune after 20 moves
@depth5, prune after 20 moves
@depth6, prune after 40 moves

After approx 250 games, I'm not seeing any elo boost or loss - as with most other changes I try these days

[bob]

I do this in Komodo, but I don't take it too far. Depending on which version of Komodo we are talking about I do either 2 or 3 ply of this near the leaf nodes.

I may have got it wrong, but I was staggered at how aggressive the Stockfish implementation seemed to be - pruning stuff from move 4 onward at depth 1, for instance.. are you willing to share Komodo's paramters in this area?

It's not big deal - this is one of those things that might work better in some programs more than others.

Basically, the current version of Komodo does not do LMR on the last 2 ply. If we are NOT in a PV node and on the last 2 ply of the search I will look at either 10 or 6 legal moves and throw out everything else. However I will not do this if the mover is in check or has just given check or the move is considered interesting - but I think only passed pawn push to the 6th or 7th triggers what is interesting.

For some reason we consider legal moves for this idea, for most other things I count quiet move, such as for LMR I requires N quiet moves before doing further reductions as we traverse the move list. I'm not sure why we are not consistent about this but it must have tested well.

Well, the parameters I'm trying are as follows:

@depth1, prune after 8 moves
@depth2, prune after 10 moves
@depth3, prune after 14 moves
@depth4, prune after 20 moves
@depth5, prune after 20 moves
@depth6, prune after 40 moves

After approx 250 games, I'm not seeing any elo boost or loss - as with most other changes I try these days

Unless you have a _really_ strong ordering algorithm, using the count is not very good. I have tried using a static evaluation call, and ordering based on those values, and found no gain at all. No loss either. But no gain. (measured in Elo on cluster-testing).

I do use the common futility idea in the last 4 plies of the search, with a tapered bound. I compare the current material value (or full score in the test I mentioned above) to alpha, and prune if it is too far below. "too far" gets bigger as I get away from the tips, the values can be found in Crafty's source and were tuned by millions of games of testing. I think it makes way more sense to prune or reduce based on a moves characteristics, not where it appears in the move list. There are positions where all moves are good, and none should be pruned or reduced. There are positions where all are bad and all should be pruned or reduced. Using some static "count" is a very gross approximation function that has really significant error, even if it is carefully tuned for best performance. This just means that it works well slightly more times than it works poorly. There is a lot of room to improve things.

I have been unable, so far, to improve things by pruning closer to the root. The last 4 plies offer a clear gain. Going to remaining-depth = 5, I was unable to find any "threshold value" that improved things. I'd rather not prune if there is no gain or loss, since I know it adds error. And to date, I've not found anything for remaining-depth >= 5 that works. Doesn't mean I won't, but does mean I haven't.

[Don]

I do this in Komodo, but I don't take it too far. Depending on which version of Komodo we are talking about I do either 2 or 3 ply of this near the leaf nodes.

I may have got it wrong, but I was staggered at how aggressive the Stockfish implementation seemed to be - pruning stuff from move 4 onward at depth 1, for instance.. are you willing to share Komodo's paramters in this area?

It's not big deal - this is one of those things that might work better in some programs more than others.

Basically, the current version of Komodo does not do LMR on the last 2 ply. If we are NOT in a PV node and on the last 2 ply of the search I will look at either 10 or 6 legal moves and throw out everything else. However I will not do this if the mover is in check or has just given check or the move is considered interesting - but I think only passed pawn push to the 6th or 7th triggers what is interesting.

For some reason we consider legal moves for this idea, for most other things I count quiet move, such as for LMR I requires N quiet moves before doing further reductions as we traverse the move list. I'm not sure why we are not consistent about this but it must have tested well.

Well, the parameters I'm trying are as follows:

@depth1, prune after 8 moves
@depth2, prune after 10 moves
@depth3, prune after 14 moves
@depth4, prune after 20 moves
@depth5, prune after 20 moves
@depth6, prune after 40 moves

After approx 250 games, I'm not seeing any elo boost or loss - as with most other changes I try these days

Unless you have a _really_ strong ordering algorithm, using the count is not very good. I have tried using a static evaluation call, and ordering based on those values, and found no gain at all. No loss either. But no gain. (measured in Elo on cluster-testing).

I do use the common futility idea in the last 4 plies of the search, with a tapered bound. I compare the current material value (or full score in the test I mentioned above) to alpha, and prune if it is too far below. "too far" gets bigger as I get away from the tips, the values can be found in Crafty's source and were tuned by millions of games of testing. I think it makes way more sense to prune or reduce based on a moves characteristics, not where it appears in the move list.

I used to believe that with all my heart, but I have gradually come to the conclusion that it is folly. And here is why:

If there was a beauty pageant for warthogs, the most beautiful warthog wins. Same principle.

The issue is not how good any particular move is, but how good it is compared to the OTHER candidates. If you only played one move at each node, it would be ok as long as it was the BEST move - even if the move was an ugly move.

If you have the means to understand which moves are good and bad, shouldn't it be reflected in how you order the moves ANYWAY?

There are positions where all moves are good, and none should be pruned or reduced. There are positions where all are bad and all should be pruned or reduced.

Oh no, I think you really have this wrong. The general principle is that if all the moves are good, you can play any one of them. Ideally you want to always include the very best move but this is just not practical unless you enjoy having a slow program that plays lousy chess.

The main principle (and the devil is in the details) is that you want to play the very best move, OR ONE CLOSE TO IT, without spending much effort on the other moves.

There is nothing else that I know of that captures this principle better than the moves position in the move list. The most logical way to follow this principle is to first order the moves and then pick them in order from best to worst.

That is not to say that other tradeoffs are not involved but I think they end up being equivalent. For example it may be cheaper to see if a piece is attacked and needs to be moved AFTER you generate and sort the moves - but when that happens you probably wasted a lot of time - in the knowledge that most of the time it will save time. You are essentially making a late decisions that the move SHOULD have been placed earlier in the list.

Using some static "count" is a very gross approximation function that has really significant error, even if it is carefully tuned for best performance. This just means that it works well slightly more times than it works poorly. There is a lot of room to improve things.

I definitely agree with you here. I still think the move count is a big part of this but perhaps some kind of probability calculation should be folded in. If we have some kind of statistical sense of how good each move is, we can compare them in terms of the their relative value to each other. But there is no getting around the fact that you are going to want to try what you perceive the best move first, then the second best move, etc.

There has been some interesting work in GO on assigning ELO ratings to individual moves. Look for papers on the Bradley Terry model. If you had an "ELO" rating of the quality of every move you could see the moves in the proper context which is relative to other moves. It's not the absolute value of the move that is important. Again, it's the Warthog principle, if I am only rated 1200 ELO but everyone else in the tournament is rated below 500 ELO, then I would be the heavy favorite. It doesn't matter than I am not a very good player.

I think the principle you are looking for is how to estimate our confidence in a move. Checking moves can be ridiculously bad or ridiculously good and just the fact that it gives check makes it dangerous (or we might say that it increases the likelihood that it is a surprisingly good move.) That is why we sometimes decide not to reduce checking moves even though they appear to lose big but we will not hesitate to reduce some other move that does not lose as much!

I have been unable, so far, to improve things by pruning closer to the root. The last 4 plies offer a clear gain. Going to remaining-depth = 5, I was unable to find any "threshold value" that improved things. I'd rather not prune if there is no gain or loss, since I know it adds error. And to date, I've not found anything for remaining-depth >= 5 that works. Doesn't mean I won't, but does mean I haven't.

[silentshark]

Unless you have a _really_ strong ordering algorithm, using the count is not very good. I have tried using a static evaluation call, and ordering based on those values, and found no gain at all. No loss either. But no gain. (measured in Elo on cluster-testing).

well, I don't have good move ordering (nothing fancy anyway). When it comes to making these pruning decisions it's just based on history counters.

Yes, the move count based pruning feels very crude, yet it clearly works for the stockfish folk, so maybe there is something there?

Current test version (using params in the previous post) is losing about 10 elo compared to the one without this pruning. I will have another go at tuning, because I feel there's something here, and I'm sure that more pruning at depth=1 is possible. I do LMR at depths 2 and above, and null moves down to depth 1. So why not something "LMR-like" at depth 1 - like this move count based pruning.

I will try with a less aggressive set of parameters, and report back.

Bob/ Don - thanks for your interesting pointers on this one.

[mcostalba]

Unless you have a _really_ strong ordering algorithm, using the count is not very good.

I don't agree here (of course )

First you have to clearly identify 2 indpenedent key aspect of move counting. In particular to prune moves after a given threshold counter (depth dependent).

1) Pure statistical effect: even if the moves are completely random (as in Crafty non-captures ones if I don't get wrong) there is a benefit because if each move has the same probability 'p' to be the cut-off one then the best decision policy semmes to be anyhow something like "try n moves out of m, if you don't find anything the probability that the cut-off is in the remaining m-n moves is very low", of this probability I don't know the formula but I assume that is depth dependant and increases when depth increase, so has a sense to tailor this rule making thresold 'n' a value depth dependant (as is in almost all the engines). Someone versed in statistic could perhaps find the formula in the ideal case all the moves are independent and have the same probability to be the cut-off. I would be not surprised if the optimal decision alghortim would turn out to be as described here.


2) Move ordering effect: If we have a good ordering then, of course, the above descibed decision policy get an extra boost for the reason that the probability is no more the same, but the first moves are also the most probable, so the acucmulated probability is bigger.

This is for the quality description of why move counting works (IMHO). Now to proceed on (without usual handwaving) we must quantify the contribution of the 2 components: how much the strenght of the pruning is given by the first component and how much by the second ?

Well, this could turn out surprisingly not so difficult to measure. Indeed given an engine could be possible to build up 3 versions of the engine:

A) Original version, as the engine is.

B) Same as original but with ordering of non-captures removed. The ELO difference between this version and A measures the contribution of (2).

C) Same as original but with move count pruning removed. The ELO difference between this version and B measures the contribution of (1).


My bet is that contribution of (1) is much bigger then contribution of (2).

[zamar]

Yes, the move count based pruning feels very crude, yet it clearly works for the stockfish folk, so maybe there is something there?

(1) Of course there is sth in it. Number of examined moves affects probabilities as Marco wrote.

(2) It's also true that current system in Stockfish is very crude.

(3) I personally believe there is room for improvement, but it's of course very difficult.

(4) Optimal solution would consider all major factors:
a) MoveCount
b) beta - staticEval
c) move properties (checks, pins, escapes, threats...)

and using some magical formula decide whether to a) prune b) reduce X plies c) play the move d) extend

Now just find the magic formula