SEE on non-capture moves in main search

[gladius]

I'm experimenting with my move scoring and decided to test running my SEE on every move. The idea was, for non-captures, if the move hung the piece, the SEE would detect this and we could give the move a massive penalty.

It turns out about 33% of moves "hang" pieces (where hanging is defined as SEE value less than 0), but doing the SEE all the time made my search about 2.5x slower.

In the end, I think I won't use the SEE for scoring non-captures as it slows things down so much, but it seems there has to be a way to use the fact that 33% of moves in the main search hang pieces.

Has anyone experimented much with this?

[bob]

I think the problem is this: with things like hash moves, good captures, killers, etc, by the time you have tried all of those, either you have already failed high, or you are never going to fail high at this position. In the so-called ALL positions, ordering is irrelevant anyway, and wasting computing resources trying to improve ordering there is pointless. At the CUT nodes, you probably get the cut before you get a chance to take advantage of your idea. So you are just adding overhead to ALL nodes, without benefiting CUT nodes at all, which is just a time penalty...

[mjlef]

I'm experimenting with my move scoring and decided to test running my SEE on every move. The idea was, for non-captures, if the move hung the piece, the SEE would detect this and we could give the move a massive penalty.

It turns out about 33% of moves "hang" pieces (where hanging is defined as SEE value less than 0), but doing the SEE all the time made my search about 2.5x slower.

In the end, I think I won't use the SEE for scoring non-captures as it slows things down so much, but it seems there has to be a way to use the fact that 33% of moves in the main search hang pieces.

Has anyone experimented much with this?

I do SEE on non captures for move ordering reasons whenever I do late move reductions (say depth>2 or 3). This does nto slow things down much since it is not close to the horizon, and I think it both improves move ordering and helps LMR by outting the non-hanging non-captures to eb searchee first, and less likely to be reduced. I am less certian this helps real game play or not. It seems to me that if we bother to put locing SEE captures at the end of the move list, why not put losing non-captures there too?

Mark

[hgm]

I did the same thing in Joker, (SEEing non-captures and postponing search of bad ones), and noticed that even in the absence of any positive attempts to pick a good move (so no killer or history), it did not really result in a speedup.

I guess the answer is in what Bob says, and your own statistics: only 33% of the non-captures is bad. The SEE is expensive, and it still leaves you with 66% of the moves to search.

So singling out a good one would be much more effective than discriminating against SEE<0. If even a good one does not do it, you are likely to be in an all node and any further effort is wasted time.

So it all depends on how efficient your mechanisms are for picking out a good one. For if you would potentially leave a cut move amongst the masses, then it would make sense to cheaply discard the bad non-captures (SEE is cheaper than even QS), as the cut-move will make that eventually you don't have to search them.

So in situations where killer and history are less effective, you might still want to do it. In Joker I now do this if there is a threat detected (the null move fails low materially, although eval > beta). In that case the null-move refutation tells me which of my pieces is in trouble. To quickly filter out the cases where the threat can be trivially dodged by simply withdrawing the piece, I then move a single non-capture of the threatened piece in front of all captures that capture a lesser piece. And because I do it to only a single one, I want to make quite sure that it a withdrawal to a safe square. So I SEE all withdrawals until I find a safe one.

This captures tha vast majority of cases. If one safe withdrawal does not help, it is usually because the piece is pinned or tied (to defending another piece). In that case selectively identifying possible remedies is too complicated, (e.g. the solution might be to defend the piece it was tied to by other means), I just start IID at QS level to do a blind search. SEEing the non-captures is of no help there either.

[Tord Romstad]

I think the problem is this: with things like hash moves, good captures, killers, etc, by the time you have tried all of those, either you have already failed high, or you are never going to fail high at this position.

Perhaps, but if it were as simple as this, wouldn't the use of history counters also be worthless for move ordering?

With regard to SEE and move ordering, my intuition disagrees with my experience. This is what I have found:

• For captures, it is best to search the winning and equal captures before the losing captures, and to prune losing captures in the quiescence search. This makes perfect sense. However, among the winning and equal captures, MVV/LVA move ordering performs better than SEE move ordering, which is counter-intuitive to me. After some thought, I think I have an explanation: If there there is a winning capture in the position, this winning capture will usually still be available after the exchange of some more valuable piece. Exchanging strong pieces before capturing the hanging piece reduces the subtree size, because both sides will have fewer legal moves after the exchange (on average).
• For the non-capturing moves after the hash move and killers, history move ordering performs better than no move ordering, as expected. But trying to refine this by using SEE values does not work. I have tried to sort the moves into two groups, first searching non-captures with SEE value zero ordered by history scores, and then searching losing non-captures by their SEE values. This performs slightly worse than simplistic history move ordering for all moves. I have no idea why.
• Searching the losing captures after the non-captures is slightly better than searching them before the non-captures. This is not entirely unexpected, but intuitively I would expect that searching the losing non-captures after the losing captures (i.e. first the hash move, then winning and equal captures, then killers, then non-losing non-captures, then losing captures, and finally losing non-captures) would perform better still. Surprisingly, this is not the case.

It is very frustrating that I haven't found a way to use SEE to improve the ordering of non-captures, because calling the SEE for every move doesn't slow me down noticably. Perhaps I can find some other way to use the SEE values (pruning or reduction decisions, maybe).

Tord

[Tord Romstad]

So singling out a good one would be much more effective than discriminating against SEE<0. If even a good one does not do it, you are likely to be in an all node and any further effort is wasted time.

This is true for non-PV nodes, but not for PV nodes. Try to measure the relative frequency of the first, second, third (...) move being the best at PV nodes. Unless you are much better than me, the result will be rather depressing. The last time I measured, the first move was the best only about 65% of the time (IIRC). It was quite common that the best move occured near the end of the move list.

This means that it makes sense to make some extra effort to improve the move ordering at PV nodes. You can afford to do something very expensive, because the PV nodes are very few, and have big sub-trees. I think there is great scope for improvment in this area. Most programs use the same (or almost the same) move ordering techniques in PV nodes as in non-PV nodes. It is hard to believe that this approach is optimal.

Tord

[hgm]

Well, my gut reaction to this is that it would not matter, exactly because there are so few PV nodes. Are the sub-trees from PV nodes really that much bigger then from all nodes? I would guess that this matters only a factor ~2.

Since all my engines rely on an advanced IID scheme, I am probably not very sensitive to this effect anyway. By the time any significant depth is reached, the earlier iterations will have picked out the best move fairly reliably, and once a move scores above alpha, I keep it from then on in the early part of my move list.

I have thought about sorting the moves that failed low (as most tend to do when you search your best move first) by the minimum score obtained in all iterations. This to overcome the problem that with null-move pruning refutation of poor moves in generally becomes very 'laid back', as the refuting party makes no effort at all to prevent the score from creeping up to just below alpha. So at low depth the upper bounds you obtain are typically quite far below alpha (as null move is not allowed and the best captures are generally tried first and will serve as refutation), and then later iterations the leading side lets his gain (nearly) evaporate through null moving in the face of minor threats. So the deeper upper bounds usually are much less tight than the earlier ones.

But I haven't tried this yet.

Perhaps I should give Joker 'bound awareness', next to the 'depth awareness' it already has. With this I mean really let the search keep track of the bound type, ("are there moves that have been skipped that could be possibly better") rather than just assuming that out-of-window scores will be bounds. This would drive up the number of exact scores in the low-depth searches (e.g. a stand-pat score below alpha returned from a QS node is still exact, as would be the score in a cut-node where the cut-move happened to be searched last and returned an exact score. I am not sure this will help much: unlike the depth, the exactness will not propagate very far towards the root unless you are very inept in move ordering.

[Tord Romstad]

Well, my gut reaction to this is that it would not matter, exactly because there are so few PV nodes. Are the sub-trees from PV nodes really that much bigger then from all nodes? I would guess that this matters only a factor ~2.

The sub-trees below PV nodes are certainly a lot bigger, but exactly how much depends on the program. Many programs extend more and prune and reduce less in PV nodes, for these programs the factor will obviously be bigger.

In any case, the difference in tree size between a PV node and a non-PV is non-trivial, especially when move ordering is poor at the PV node. At a PV node, every time a move after the first returns a score above alpha, you have to do an expensive re-search with a big window. If the best move changes several times at the same PV node, it takes a lot of time to finish the node.

You can see this most clearly at the root of the tree. Consider how much longer it takes to complete an iteration when the best move changes multiple times. Exactly the same thing can happen at internal PV nodes, except that you don't see it as easily. The consequences can be quite bad, especially for PV nodes with a big remaining depth.

Since all my engines rely on an advanced IID scheme, I am probably not very sensitive to this effect anyway. By the time any significant depth is reached, the earlier iterations will have picked out the best move fairly reliably, and once a move scores above alpha, I keep it from then on in the early part of my move list.

But what happens if the score of the first move at a PV node suddenly drops by a big amount compared to the previous iterations? I think it might be a good idea to look for a good way to select a promising second move to search. One approach I have considered (but not yet tested) is to do an IID search with the first move removed from the move list at PV nodes where the score of the old best move drops a lot compared to the previous iteration.

Tord

[ed]

With regard to SEE and move ordering, my intuition disagrees with my experience. This is what I have found:

• For captures, it is best to search the winning and equal captures before the losing captures, and to prune losing captures in the quiescence search. - And skip minor promotions in QS as well, it helps too - This makes perfect sense. However, among the winning and equal captures, MVV/LVA move ordering performs better than SEE move ordering, which is counter-intuitive to me. After some thought, I think I have an explanation: If there there is a winning capture in the position, this winning capture will usually still be available after the exchange of some more valuable piece. Exchanging strong pieces before capturing the hanging piece reduces the subtree size, because both sides will have fewer legal moves after the exchange (on average).
• For the non-capturing moves after the hash move and killers, history move ordering performs better than no move ordering, as expected. But trying to refine this by using SEE values does not work. I have tried to sort the moves into two groups, first searching non-captures with SEE value zero ordered by history scores, and then searching losing non-captures by their SEE values. This performs slightly worse than simplistic history move ordering for all moves. I have no idea why.
• Searching the losing captures after the non-captures is slightly better than searching them before the non-captures. This is not entirely unexpected, but intuitively I would expect that searching the losing non-captures after the losing captures (i.e. first the hash move, then winning and equal captures, then killers, then non-losing non-captures, then losing captures, and finally losing non-captures) would perform better still. Surprisingly, this is not the case.

It is very frustrating that I haven't found a way to use SEE to improve the ordering of non-captures, because calling the SEE for every move doesn't slow me down noticably. Perhaps I can find some other way to use the SEE values (pruning or reduction decisions, maybe).

Add a quick piece-square evaluation to your move generator, it helps a lot. Description: http://www.top-5000.nl/authors/rebel/ch ... 20ORDERING

Regards,

Ed

Tord

[hgm]

OK, I see. I was thinking about a fixed-depth alpha-beta tree. But it is because of the extension/reduction policy.

But what happens if the score of the first move at a PV node suddenly drops by a big amount compared to the previous iterations? I think it might be a good idea to look for a good way to select a promising second move to search. One approach I have considered (but not yet tested) is to do an IID search with the first move removed from the move list at PV nodes where the score of the old best move drops a lot compared to the previous iteration.

It sounds like a good idea. I guess that the old PV move would disqualify itself anyway, as when you start the search at low depth its lower, but exact score would be satisfied from the hash table as it was already searched to higher depth.

I guess IID really should go like this:
1) Keep the depth, score and bound type for every move in the move list. When first entering the node, if hash and null move do not fail high, fill this from the hash.
2) reset the depth of all moves with upper-bound scores above the current alpha to -1, and their score to alpha.
3) As long (and as soon) as you have a move with a lower-bound score above beta, deepen that one. If the score remains good all the way, you are done.
4) Lacking such moves, look for the move with lowest depth. If that depth is the required depth, we are done. If not, and there are more of that depth, take the one with the highest score first.
5) if the depth is lower than required, search that move one deeper, with the current window (i.e. not upping alpha on any score above it that was not obtained at the currently requested depth or better!).
5) continue 3-5 until there are no more moves with depth below the requested one.

This is nearly how Joker's search works. (What lacks is that it does not reset the depth of moves with insufficiently sharp upper bounds.) It would pretty much solve the problem you sketch: If you were deepening evenly, and your PV move suddenly drops in score at depth d, you re-search all moves of which you are not yet sure at depth d-1 that they are no good, starting at d=0, in the hope to cheaply discover that there is one that might have some merit. The PV move will never be re-searched, as it already has an exact score at depth d. If none of the other moves at depth d-1 is able to beat alpha at depth d-1, there is little hope that they will be able to do so at depth d, and they will be searched to depth d in the order of their meaning-poor upper bounds (so that the ones we already know to be lousy for sure at least go in the end). But if some of them have scores above alpha at d-1, they are searched in the order of their scores, in the hope that they will not suffer the same drop as the old PV move.