move count based pruning

[bob]

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

Most of the programs I've seen that do order based pruning are sorting the moves based on history scores, which I would consider a fairly weak ordering algorithm. Plus Stockfish and others exclude moves that for one reason or another look likely to be worth examining (pawn push is one example).

I am personally convinced that this sorting method is of no use. I reported a few years ago that when I originally started testing the "history pruning" idea from Fruit, I could not find a history threshold that made any difference whatsoever. Most eventually concluded that history counters are worthless for making these reduction decisions and the term "LMR" was born to replace "history pruning" (which should have been called history-based reductions).

I spent a ton of time analyzing the history counters, and after doing a long run and then correlation analysis, I found, surprisingly, that the history counters were more closely correlated to a purely random set of numbers than to anything meaningful. At that point, I removed the counters and started to use other ideas to control reductions and things got much better. And before you ask, I tried several flavors of counters. from the simple <piece><to> to <piece><from><to> and everything in between. At that point, I also removed the history ordering heuristic since it was quite obvious that it was just a random process. And Crafty got a bit stronger, again. Random is hardly ever an optimal solution to anything (perhaps Monte Carlo methods is one well-known exception).

I tried this - the version that played in the recent ACCA tourney had a version of it - but I didn't like it and took it out. Now I have a fairly non-aggressive version back in. Empirically it seems to work for many programs, but it still seems risky to me, more so than LMR or futility pruning, because you are trusting the ordering + selection rules and those are not reliable.

The thing you have to watch out for is what is fact vs what is urban legend. For example, "don't reduce checks." You should experiment. I do reduce unsafe checks and got an Elo boost as a result. For check extensions, I don't extend unsafe checks and got another Elo boost. I do reduce captures SEE categorized as < 0, and got yet another boost. Yet these were considered to be incorrect in looking at most open-source programs and following discussions. My next test is going to deal with passed pawn pushes, which is also probably going to "go against the grain" of conventional thought.

[bob]

I still believe there is a far better way to choose what to reduce or not, which doesn't rely on linear position in a list, which mine still does.

You have to forget the "position in a list" point of view. To understand the concept you have to look at that as a diminishing probability of finding a cut-off move: that's what move counting pruning / reducing is all about. The list is just an implementation detail.

The point is that "after I have tried n moves I have smaller probability to find a cut-off in the rmaining m-n moves that I had at move 0"

That's the concept in its plain and simple terms. The list and the counter is just an implementation that fits well.

Please, for the last time, remove your focus from the "ALL" nodes idea. I agree that reducing real ALL node moves is a good idea. In fact, pruning them is a good idea since you do not need them at all.

Instead, focus on that 10% error rate where you should fail high on the first move at a node, which means the very next ply should encounter an ALL node, but doesn't because your first move is not "good enough". On _that_ node, you think it is ALL, but it is not. And that is where error gets introduced. You searched an inferior move at the current position, you expect your opponent to find it at the next ply and refute it. But if you reduce that one killer move that refutes it, you are now walking down a minefield and the result will be bad.

So yes, reducing effort in real ALL nodes is a proven good idea. But we have enough error that the "real ALL nodes" part of the above is not so easy to get right. We generally get it right 9 of every 10 times. Would you repeatedly risk everything you own for 100% return 90% of the time, but 10% of the time you lose everything? You are guaranteed to go broke.

If you do all the analysis of this stuff that I have done, you come to two conclusions:

(1) yes, the idea works (reductions based on moves searched so far).

(2) yes, it has significant error rates and can potentially be improved, significantly. This is the thing I have been talking about. Everyone is focusing on point (1) above, which I don't argue with at all. I'm just saying it can be done far more accurately than just a count-based simplistic approach.

[silentshark]

This is all great debate..



But do any of you have any hard data on whether LMP (not LMR) is worthwhile?

My data is this - after 1300 games, I am seeing a +20 ELO improvement using a simple LMP scheme. This is in addtion to other pruning like LMR and null move. Of course, there's still a reasonable margin of error after that number of games.. Note this is "first cut", a very suboptimal implementation of LMP, I'm sure.

I'd be interested to see what Crafty could gain from a simple LMP scheme.

I'd also be interested to see what Komodo would lose by removing its LMP.

And what would SF lose by removing its LMP?

[Don]

None of this changes my belief that you must try to always include the best move and that with any reasonable move ordering you can expect to find this move early in the list. The law of diminishing returns kicks in with a vengeance.

Also with no ordering at all you can expect to find a cut-off move early in the list....or don't find at all.

In my opinion, LMR is less about cut-offs and more about making sure you include the "best" move.

What you say is true of course, a powerful aspect of LMR is that if have not gotten a cut-off you probably won't and so it won't matter which moves you look at (because the search will fail low whether you happened to pick out the best move or not.) But I like to view this as a side-affect.

Imagine using LMR on PV nodes (where the alpha/beta window width is not artificially reduced.) LMR is still powerful and in this case there is no ambiguity about it's purpose - it is going to work well as long as you include the best move and it's not going to work well if you don't.

In my view it's conceptually simpler and more in the spirit of LMR to think of that way. The fact that in some positions you don't need the best move is a fortuitous thing that works to your advantage - but it's not the primary thing.

I know this might be considered just semantics but I think that I can argue that it's more correct in some sense than viewing is a gadget to achieve cut-offs with less work, although both are essentially correct. It's always useful to recast problems to see their various aspects - sort of like look at a diamond in different lighting conditions and different angles.

My primary argument for seeing it this way is simple. Remove alpha/beta and look at LMR from a purely mini-max point of view. Would it still work? Although I have not tried this exact experiment, I'm quite certain that LMR in a mini-max program would be far superior to mini-max without LMR. In fact it would probably be worth hundreds of ELO instead of just the 150-200 ELO it is worth in Komodo.

IMHO good ordering is just a second order optimization above something that already works independently from the order of the moves. And this something that works is move counting based pruning / reducing.

I agree with you on this. But experiments with Komodo prove empirically that this is a MAJOR second order optimization. One of the discoveries Larry and I have found is that once you have good move ordering, improving it does not speed the program up very much, but it helps LMR a LOT. We had previously always assumed that the benefit of better move ordering was pretty much equally divided between smaller trees AND increased likelihood that the best move would be searched full width.

Going along with this we found that we could push LMR farther if we payed attention to how the moves were ordered.

But my point is that IMHO we are _still_ far to find the optimal move counting rule (out of possible thousands) to prune / reduce the move under hypotesis of totally unsorted non-captures. We had a breakthrough about one year ago when in Ippo was shown a working multi reducing LMR approach that now have been adopted by almost all the engines. This demonstartes that IMHO there is still big room for improvment in statistical shaping the reducing / pruning rules, before to go to consider a better non-captures ordering.

We discovered progressive reductions on our own. In fact, a couple of years ago we were worried about the fact that Stockfish was still STRONGER than Komodo and they were not doing this! Our fear is that we would lose a lot of ground when other programs discovered these things. And of course we did lose ground when Stockfish started doing this.

Larry and I joked privately between ourselves about how difficult it would be to catch Stockfish if "they knew what we know" and also about how easy it would be to improve Stockfish but how hard it was to improve Komodo - even though Stockfish was ahead of us!

At that time we did not know anything about what Rybka was doing. Larry did not even know what LMR was and I had to teach him about this - now he is an equal in the engineering of the algorithms we use.

Even though Larry does not write a single line of code, he is an engineer at heart.

Strangely people is concentrated in finding a better ordering (possibly because is a more traditional and well unnderstood argument) then in finding a rule that better takes advantage of the statistical properites of teh search, as the multi reduced LMR was.

I have dreamed of this for a long time. In fact I am interested in applying the Bradley Terry model to the tree search in a probabilistic way. I believe that it's all about making sure the best move is included but it's possible using the Bradley Terry model and statistics gathered during the search (or off-line) to apply this principle in a much more formal way. We do it now with ad-hoc and simplistic rules but I have told Larry many times that I would like to completely scrap our search and rethink it from the ground up, trying to come up with new and interesting ideas and to give some real structure and formalism to existing ideas. Right now Komodo is no different than any other program which is a nasty collection of ad-hoc rules with tons of special case code and exceptions.

One thing that has always bothered me for instance is the sudden transition from main search to quies search. The distinctions is more blurred than it used to be, but so far it's still very clearly identifiable in any program I have looked at. I would like to do something about that and not just ad-hoc but in a very organized and logical way.

[michiguel]

None of this changes my belief that you must try to always include the best move and that with any reasonable move ordering you can expect to find this move early in the list. The law of diminishing returns kicks in with a vengeance.

Also with no ordering at all you can expect to find a cut-off move early in the list....or don't find at all.

In my opinion, LMR is less about cut-offs and more about making sure you include the "best" move.

What you say is true of course, a powerful aspect of LMR is that if have not gotten a cut-off you probably won't and so it won't matter which moves you look at (because the search will fail low whether you happened to pick out the best move or not.) But I like to view this as a side-affect.

Imagine using LMR on PV nodes (where the alpha/beta window width is not artificially reduced.) LMR is still powerful and in this case there is no ambiguity about it's purpose - it is going to work well as long as you include the best move and it's not going to work well if you don't.

In my view it's conceptually simpler and more in the spirit of LMR to think of that way. The fact that in some positions you don't need the best move is a fortuitous thing that works to your advantage - but it's not the primary thing.

I know this might be considered just semantics but I think that I can argue that it's more correct in some sense than viewing is a gadget to achieve cut-offs with less work, although both are essentially correct. It's always useful to recast problems to see their various aspects - sort of like look at a diamond in different lighting conditions and different angles.

My primary argument for seeing it this way is simple. Remove alpha/beta and look at LMR from a purely mini-max point of view. Would it still work? Although I have not tried this exact experiment, I'm quite certain that LMR in a mini-max program would be far superior to mini-max without LMR. In fact it would probably be worth hundreds of ELO instead of just the 150-200 ELO it is worth in Komodo.

IMHO good ordering is just a second order optimization above something that already works independently from the order of the moves. And this something that works is move counting based pruning / reducing.

I agree with you on this. But experiments with Komodo prove empirically that this is a MAJOR second order optimization. One of the discoveries Larry and I have found is that once you have good move ordering, improving it does not speed the program up very much, but it helps LMR a LOT. We had previously always assumed that the benefit of better move ordering was pretty much equally divided between smaller trees AND increased likelihood that the best move would be searched full width.

Going along with this we found that we could push LMR farther if we payed attention to how the moves were ordered.

But my point is that IMHO we are _still_ far to find the optimal move counting rule (out of possible thousands) to prune / reduce the move under hypotesis of totally unsorted non-captures. We had a breakthrough about one year ago when in Ippo was shown a working multi reducing LMR approach that now have been adopted by almost all the engines. This demonstartes that IMHO there is still big room for improvment in statistical shaping the reducing / pruning rules, before to go to consider a better non-captures ordering.

We discovered progressive reductions on our own. In fact, a couple of years ago we were worried about the fact that Stockfish was still STRONGER than Komodo and they were not doing this! Our fear is that we would lose a lot of ground when other programs discovered these things. And of course we did lose ground when Stockfish started doing this.

Larry and I joked privately between ourselves about how difficult it would be to catch Stockfish if "they knew what we know" and also about how easy it would be to improve Stockfish but how hard it was to improve Komodo - even though Stockfish was ahead of us!

At that time we did not know anything about what Rybka was doing. Larry did not even know what LMR was and I had to teach him about this - now he is an equal in the engineering of the algorithms we use.

Even though Larry does not write a single line of code, he is an engineer at heart.

Strangely people is concentrated in finding a better ordering (possibly because is a more traditional and well unnderstood argument) then in finding a rule that better takes advantage of the statistical properites of teh search, as the multi reduced LMR was.

I have dreamed of this for a long time. In fact I am interested in applying the Bradley Terry model to the tree search in a probabilistic way. I believe that it's all about making sure the best move is included but it's possible using the Bradley Terry model and statistics gathered during the search (or off-line) to apply this principle in a much more formal way. We do it now with ad-hoc and simplistic rules but I have told Larry many times that I would like to completely scrap our search and rethink it from the ground up, trying to come up with new and interesting ideas and to give some real structure and formalism to existing ideas. Right now Komodo is no different than any other program which is a nasty collection of ad-hoc rules with tons of special case code and exceptions.

One thing that has always bothered me for instance is the sudden transition from main search to quies search. The distinctions is more blurred than it used to be, but so far it's still very clearly identifiable in any program I have looked at. I would like to do something about that and not just ad-hoc but in a very organized and logical way.

We can think there is no sudden transition if you use LMP. In Quies() you use captures, promotions, and maybe checks. in frontier nodes, you use those plus killers, + a handful of moves, in prefontier nodes you use few more, and more... etc.

The last plies of search() become a super quies search that gets weaker until it reaches the weakest of all = quies.

I find something funny about this discussion. The idea of pruning based on move counting is not really new. It was suggested here in ~2002 by... yes... by Bob! I have that in my notes (and still commented out in the code). At that time I tested it not very thoroughly and it did not work for me.

Miguel

[Don]

I do not believe that statistical sampling will ever beat "the real deal" in terms of what to reduce or not reduce. It could be improved, but more direct application of chess knowledge makes more sense. Otherwise we could do evaluation in the same way and not have so many different terms for various chess features.

The "real deal" is very difficult to come by. Are you aware of the recent amazing progress in computer go? They are using a combination of tree search and statistical methods (based on Monte Carlo methods.) They call it MCTS which stands for Monte Carlo Tree Search. Essentially they find out what the "real deal" really is by playing a lot of (somewhat random) games. It is all about statistical sampling now.

And it is the "real deal" in the sense that no non Monte Carlo Go program these days has any chance to compete.

I think Marco probably has it right in this regard. I don't like it any more than you do, but I think it's likely the case that the best programs in a few years will be much more about probability and statistics and sampling. I don't what exact form this will take, if I did I would be doing it now!

Of course in theory it probably seems cleaner and simpler to just write a function to "give you the right answer", the "real deal" as you say and this is probably what you are imagining as being possible. But this is MUCH harder than statistical sampling.

When I first started playing with Monte Carlo and Go I spend a lot of time trying to write an evaluation function that had some kind of reasonable sense of the goodness of a go position. GO is really hard - there is no known simple and fast evaluation function that works very well. What is trivial for a human to see at a glance seems impossible to program heuristically.

Then I started playing random games to see what move was wining the most games. I quickly discovered that playing 1000 games and keeping statistics on which points were alive at the end of the games was the evaluation function I always wanted! It was amazingly good at having a "feel" for which points were safe and which were dicey and which groups were alive. It wasn't perfect, but it beat anything I could manually construct by a long shot. But then people started utilizing the statistics in interesting ways and improving the "Monte Carlo" playouts by using various methods (many of them also statistical in nature) the programs really took off.

In MCTS, the entire search tree is directed solely by statistical methods. Whether you try a move or not is based on complex formulas about prior results. It's actually quite incredible and it has caused programs to do what many predicted could never happen in the foreseeable future, programs reaching the Dan level.

Bob, do you remember when people were saying that about Chess? They would never reach expert, they would never reach master, etc? In chess it happened gradually, but in GO it happened very suddenly due to statistical methods.

I don't want to give the wrong impression, Go program are still no where close to the top human players, but the progress in just 2 or 3 years was totally insane.

[Don]

One thing that has always bothered me for instance is the sudden transition from main search to quies search. The distinctions is more blurred than it used to be, but so far it's still very clearly identifiable in any program I have looked at. I would like to do something about that and not just ad-hoc but in a very organized and logical way.

We can think there is no sudden transition if you use LMP. In Quies() you use captures, promotions, and maybe checks. in frontier nodes, you use those plus killers, + a handful of moves, in prefontier nodes you use few more, and more... etc.

The last plies of search() become a super quies search that gets weaker until it reaches the weakest of all = quies.
Miguel

It's not really that simple. There are 2 other clear differences that I see in every program:

1. In quies you can "stand pat" even if you don't like any of the moves.

2. In quies you have no depth limit except of course you have to stop when you run out of captures.

The "main" search as such is different in BOTH of these regards. I don't think it would be a major thing if all you had to do was fold in a few more moves to make the transition, but as you see this search is fundamentally different in more ways that just the selection of what moves to try.

Even if there is nothing substantially better than this I would like to at least formalize it a bit and put it into a more logical framework.

[bob]

None of this changes my belief that you must try to always include the best move and that with any reasonable move ordering you can expect to find this move early in the list. The law of diminishing returns kicks in with a vengeance.

Also with no ordering at all you can expect to find a cut-off move early in the list....or don't find at all.

In my opinion, LMR is less about cut-offs and more about making sure you include the "best" move.

What you say is true of course, a powerful aspect of LMR is that if have not gotten a cut-off you probably won't and so it won't matter which moves you look at (because the search will fail low whether you happened to pick out the best move or not.) But I like to view this as a side-affect.

Imagine using LMR on PV nodes (where the alpha/beta window width is not artificially reduced.) LMR is still powerful and in this case there is no ambiguity about it's purpose - it is going to work well as long as you include the best move and it's not going to work well if you don't.

In my view it's conceptually simpler and more in the spirit of LMR to think of that way. The fact that in some positions you don't need the best move is a fortuitous thing that works to your advantage - but it's not the primary thing.

I know this might be considered just semantics but I think that I can argue that it's more correct in some sense than viewing is a gadget to achieve cut-offs with less work, although both are essentially correct. It's always useful to recast problems to see their various aspects - sort of like look at a diamond in different lighting conditions and different angles.

My primary argument for seeing it this way is simple. Remove alpha/beta and look at LMR from a purely mini-max point of view. Would it still work? Although I have not tried this exact experiment, I'm quite certain that LMR in a mini-max program would be far superior to mini-max without LMR. In fact it would probably be worth hundreds of ELO instead of just the 150-200 ELO it is worth in Komodo.

IMHO good ordering is just a second order optimization above something that already works independently from the order of the moves. And this something that works is move counting based pruning / reducing.

I agree with you on this. But experiments with Komodo prove empirically that this is a MAJOR second order optimization. One of the discoveries Larry and I have found is that once you have good move ordering, improving it does not speed the program up very much, but it helps LMR a LOT. We had previously always assumed that the benefit of better move ordering was pretty much equally divided between smaller trees AND increased likelihood that the best move would be searched full width.

Going along with this we found that we could push LMR farther if we payed attention to how the moves were ordered.

But my point is that IMHO we are _still_ far to find the optimal move counting rule (out of possible thousands) to prune / reduce the move under hypotesis of totally unsorted non-captures. We had a breakthrough about one year ago when in Ippo was shown a working multi reducing LMR approach that now have been adopted by almost all the engines. This demonstartes that IMHO there is still big room for improvment in statistical shaping the reducing / pruning rules, before to go to consider a better non-captures ordering.

We discovered progressive reductions on our own. In fact, a couple of years ago we were worried about the fact that Stockfish was still STRONGER than Komodo and they were not doing this! Our fear is that we would lose a lot of ground when other programs discovered these things. And of course we did lose ground when Stockfish started doing this.

Larry and I joked privately between ourselves about how difficult it would be to catch Stockfish if "they knew what we know" and also about how easy it would be to improve Stockfish but how hard it was to improve Komodo - even though Stockfish was ahead of us!

At that time we did not know anything about what Rybka was doing. Larry did not even know what LMR was and I had to teach him about this - now he is an equal in the engineering of the algorithms we use.

Even though Larry does not write a single line of code, he is an engineer at heart.

Strangely people is concentrated in finding a better ordering (possibly because is a more traditional and well unnderstood argument) then in finding a rule that better takes advantage of the statistical properites of teh search, as the multi reduced LMR was.

I have dreamed of this for a long time. In fact I am interested in applying the Bradley Terry model to the tree search in a probabilistic way. I believe that it's all about making sure the best move is included but it's possible using the Bradley Terry model and statistics gathered during the search (or off-line) to apply this principle in a much more formal way. We do it now with ad-hoc and simplistic rules but I have told Larry many times that I would like to completely scrap our search and rethink it from the ground up, trying to come up with new and interesting ideas and to give some real structure and formalism to existing ideas. Right now Komodo is no different than any other program which is a nasty collection of ad-hoc rules with tons of special case code and exceptions.

One thing that has always bothered me for instance is the sudden transition from main search to quies search. The distinctions is more blurred than it used to be, but so far it's still very clearly identifiable in any program I have looked at. I would like to do something about that and not just ad-hoc but in a very organized and logical way.

We can think there is no sudden transition if you use LMP. In Quies() you use captures, promotions, and maybe checks. in frontier nodes, you use those plus killers, + a handful of moves, in prefontier nodes you use few more, and more... etc.

The last plies of search() become a super quies search that gets weaker until it reaches the weakest of all = quies.

I find something funny about this discussion. The idea of pruning based on move counting is not really new. It was suggested here in ~2002 by... yes... by Bob! I have that in my notes (and still commented out in the code). At that time I tested it not very thoroughly and it did not work for me.

Miguel

It was also discussed in 1996 between Bruce Moreland and myself, + others. But at that time, the depth was so limited, it really seemed to hurt. And we did not try the "counter" approach first, which further hurt things.

[bob]

This is all great debate..



But do any of you have any hard data on whether LMP (not LMR) is worthwhile?

My data is this - after 1300 games, I am seeing a +20 ELO improvement using a simple LMP scheme. This is in addtion to other pruning like LMR and null move. Of course, there's still a reasonable margin of error after that number of games.. Note this is "first cut", a very suboptimal implementation of LMP, I'm sure.

I'd be interested to see what Crafty could gain from a simple LMP scheme.

I'd also be interested to see what Komodo would lose by removing its LMP.

And what would SF lose by removing its LMP?

Give me some details about what you are doing and I can test. Our futility code has a bit of the LMP concept embedded since early moves (good moves, hopefully) don't get discarded, although this is only done in the last 4 plies at present.

[bob]

I do not believe that statistical sampling will ever beat "the real deal" in terms of what to reduce or not reduce. It could be improved, but more direct application of chess knowledge makes more sense. Otherwise we could do evaluation in the same way and not have so many different terms for various chess features.

The "real deal" is very difficult to come by. Are you aware of the recent amazing progress in computer go? They are using a combination of tree search and statistical methods (based on Monte Carlo methods.) They call it MCTS which stands for Monte Carlo Tree Search. Essentially they find out what the "real deal" really is by playing a lot of (somewhat random) games. It is all about statistical sampling now.

Been aware of it for some time. And have also been aware of the rather serious shortcoming it has as well, since "deep threats" are completely misunderstood because of the very fast games used in the MC analysis. It's an idea. And for go, because of the branching factor, it appears to be better than normal alpha/beta search. We are not "there" in computer chess however. AB works more than good enough.

And it is the "real deal" in the sense that no non Monte Carlo Go program these days has any chance to compete.

I think Marco probably has it right in this regard. I don't like it any more than you do, but I think it's likely the case that the best programs in a few years will be much more about probability and statistics and sampling. I don't what exact form this will take, if I did I would be doing it now!

Of course in theory it probably seems cleaner and simpler to just write a function to "give you the right answer", the "real deal" as you say and this is probably what you are imagining as being possible. But this is MUCH harder than statistical sampling.

(1) much harder to do;

(2) much more accurate, too.

When I first started playing with Monte Carlo and Go I spend a lot of time trying to write an evaluation function that had some kind of reasonable sense of the goodness of a go position. GO is really hard - there is no known simple and fast evaluation function that works very well. What is trivial for a human to see at a glance seems impossible to program heuristically.

Then I started playing random games to see what move was wining the most games. I quickly discovered that playing 1000 games and keeping statistics on which points were alive at the end of the games was the evaluation function I always wanted! It was amazingly good at having a "feel" for which points were safe and which were dicey and which groups were alive. It wasn't perfect, but it beat anything I could manually construct by a long shot. But then people started utilizing the statistics in interesting ways and improving the "Monte Carlo" playouts by using various methods (many of them also statistical in nature) the programs really took off.

In MCTS, the entire search tree is directed solely by statistical methods. Whether you try a move or not is based on complex formulas about prior results. It's actually quite incredible and it has caused programs to do what many predicted could never happen in the foreseeable future, programs reaching the Dan level.

Bob, do you remember when people were saying that about Chess? They would never reach expert, they would never reach master, etc? In chess it happened gradually, but in GO it happened very suddenly due to statistical methods.

If such a program could rip thru Fine's book with near-perfect accuracy, I would be impressed. But it is unlikely in the extreme, because the nature of chess is deeper and narrower, compared to go. Different tree shapes require different search approaches, mainly because for some trees, alpha/beta just can't go deep enough.

I don't want to give the wrong impression, Go program are still no where close to the top human players, but the progress in just 2 or 3 years was totally insane.