// History pruning. See ok_to_prune() definition
if ( moveCount >= 2 + int(depth)
&& ok_to_prune(pos, move, ss[ply].threatMove, depth)
&& bestValue > value_mated_in(PLY_MAX))
continue;
This rule it means that if you are for instance at depth 2*OnePly (OnePly in Stockfish is 2) then after the move 2 + 4 = 6 you prune everything !!!!!
The only moves that are not pruned are the ones with a good history so that ok_to_prune() returns false.
You can imagine that with such a rule it is very easy to go deep with search and incredibly (at least for me) search quality doesn't seems to be too badly affected.
And you are sure that this is NOT very tactically dangerous?! Seems incredible for me...
Why? Sure, it sometimes misses a good move. But so does your quiescence search, and far more often. You wouldn't throw out your quiescence search because it is "tactically dangerous", would you?
Compared to most older programs, Stockfish uses a more gradual transition between the main search and the quiescence search. I don't see why this should be more dangerous than a sharp border, and in all the tests I have made, the gradual transition has performed much better.
Then I should implement history heuristic anyway to make this pruning possible?
I don't think it's really necessary. Just run enough tests to make sure you don't prune too many (or too few) moves. By the way, Marco's explanation was a little simplified: The ok_to_prune() function tests for several other conditions in addition to history counters before it decides whether a move can be safely pruned. Look at the code for details; it is reasonably well commented and should be easy to read.
metax wrote:I try all captures before the killers because I haven't got any SEE yet. But that was not my point. I wondered why the statistics didn't get better, but the _performance_ increased anyway, even from the starting position.
Well, there might be a difference at PV nodes, where you're not interested in a cutoff. If for example you show up at a quiet PV node, you will probably gain big time by having a killer move early in the list. Do you count PV nodes in your statistics?
Also, you don't need a see to sort the captures. Just assign them the value of the taken piece minus the value of the capturing piece. Search captures with values >= 0 directly after the hash move. Then search the killers.
By the way, do we want to have exchanges (BxN, RxR) in front of the killer moves?
metax wrote:I try all captures before the killers because I haven't got any SEE yet. But that was not my point. I wondered why the statistics didn't get better, but the _performance_ increased anyway, even from the starting position.
A possible explanation is that after a capture the search tree size is much more reduced (because you have less pieces) then after a non-capture move.
So keeping the same cut-off statistic now you search on a tree size that is in average smaller then before. You could easily confirm this idea by experiment, counting node counts at fixed depth with the different move orders.
since about 4 months, I am developing my engine ChessMind now. I implemented null move with R=3 (without verification), transposition tables and Futility pruning. The problem is the following:
I currently search at least 250 kilonodes per second, in a normal middlegame position 300 on average. That is not a very good value, but still OK in my opinion. My problem is the tree explosion. Other programs easily reach search depths of at least 14-15 in a few seconds, ChessMind reaches ply 7-8 in that time. This is because I need about 1.000.000 nodes to reach ply 8 or 9 in most middlegame positions, whereas other engines need 1.000.000 nodes to reach ply 14. My conclusion is that I have to improve my selective techniques, but how? I experimented a bit with some reductions if one side has lost too much material, but that either gave me not much performance or had very high tactical risks. For example, I found out that to reduce the tactical risk, I should not reduce captures, check or transposition table moves. I only allowed one reduction per branch and even if I reduced two plies if there was a very high material imbalance, that gave me not much and was tactically risky anyway.
What I do in the search is: At the root, I search the first move with an aspiration window of 200 centipawns around alpha. If it fails high or low, I open the window completely and search the first move again. After having searched the first move, I close the window. When a fail-high occurs, I search the move again with an open window. In the tree, I simply do "normal" alpha-beta, which means I take the given window.
I'm not sure if this is optimal because quite often, the engine isn't sure which one of two moves is better, and then fail-highs at the root occur which seems to take some performance.
As move ordering, I take the transposition table move (if available), then the two killer moves and MVV-LVA. I have no history heuristic or anything else than killer moves to order the non-captures because many people say that at today's search depths, history is only a random noise (would it be an idea to only count history moves until a given ply?).
I'm not sure about the different search algorithms, but I think PVS is to do at every node what I do only only at the root (correct me if I am wrong). I have heard that PVS is faster than alpha-beta if over about 90% of first moves in the tree fail high and slower at less than 90%. As my move ordering success is about 80-85% in middlegame, I haven't tried PVS yet.
Any ideas how I could reduce the number of nodes that have to be searched without dramatically increasing tactical risks?
After the TT move, you must try captures next. Preferably captures that SEE says do not lose material. But try them in MVV/LVA order as this reduces the size of the tree by a small amount.
I tried the idea with the pruning of moves whose index is greater than 2 + the remaining distance to horizon. But I have tactical problems, for example in that position:
ChessMind without that pruning sees the move 1...Rxe1! after some seconds and the mate in 9 after about 5 minutes on ply 13, which is very slow. I hoped to get a better performance with that trick, but now it doesn't even see the move 1...Rxe1 in 10 minutes even though it reaches ply 17. That seems to need some extra pruning...
metax wrote:I tried the idea with the pruning of moves whose index is greater than 2 + the remaining distance to horizon. But I have tactical problems, for example in that position:
ChessMind without that pruning sees the move 1...Rxe1! after some seconds and the mate in 9 after about 5 minutes on ply 13, which is very slow. I hoped to get a better performance with that trick, but now it doesn't even see the move 1...Rxe1 in 10 minutes even though it reaches ply 17. That seems to need some extra pruning...
I reduce everywhere, and prune in the last 4 plies. Crafty still sees this instantly:
only takes 2 plies and 10 milliseconds (or less, since this is rounded).
You just have to be selective in what you reduce or prune. Never when in check. Never if a move gives check. Never if the move might become a best move because of current material score and alpha/beta bounds comparison, etc.
metax wrote:The problem is that I don't have the information available if the move gives check...
You have to get it. Before you make any decisions, you can at least make the move, then you can determine whether it checked the opponent or not, and if so refuse to prune/reduce it, since it should trigger a check extension anyway...
metax wrote:I tried the idea with the pruning of moves whose index is greater than 2 + the remaining distance to horizon. But I have tactical problems, for example in that position:
ChessMind without that pruning sees the move 1...Rxe1! after some seconds and the mate in 9 after about 5 minutes on ply 13, which is very slow. I hoped to get a better performance with that trick, but now it doesn't even see the move 1...Rxe1 in 10 minutes even though it reaches ply 17. That seems to need some extra pruning...
I reduce everywhere, and prune in the last 4 plies. Crafty still sees this instantly:
only takes 2 plies and 10 milliseconds (or less, since this is rounded).
You just have to be selective in what you reduce or prune. Never when in check. Never if a move gives check. Never if the move might become a best move because of current material score and alpha/beta bounds comparison, etc.
I do not understand how you get mate in 8 in 2 plies espacially when not all the moves in the main line are checks or reply to check(4...Qg4 and 8.f5 Qxf5 9.a4)
Uri Blass wrote:I do not understand how you get mate in 8 in 2 plies espacially when not all the moves in the main line are checks or reply to check(4...Qg4 and 8.f5 Qxf5 9.a4)
Uri
Even if all moves _were_ checks or replies to check, I would not understand it, because only the checks are free, but not the replies. Or do I miss something?
and incredibly (at least for me) search quality doesn't seems to be too badly affected.