bob wrote:silentshark wrote:Don wrote:silentshark wrote:Don wrote:
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.