Order

[sje]

Maybe I'm missing something here, but why generate non-captures without first ensuring that there's no cutoff caused by a "bad" capture?

It did not help when I tried it, and the benefit _used_ to be that I used the history heuristic so that I could actually try some non-captures before those bad captures were tried. I removed the history stuff a couple of years ago when I discovered it was not helping at all any longer.

I think that what's happening is that if a cutoff doesn't happen by the end of the usual preliminary move generations, then the search is probably at an ALL node and there isn't going to be any cutoff at all. So it won't make a difference with delaying non capture move generation as it will happen anyway most (almost all?) of the time.

[bob]

If I get this far, I generate non-captures next, but the captures with SEE < 0 are on the front of the list, so they get searched first. Good for tactical tests usually, bad in general. But I don't want to take the time to move them down or skip over them and have to come back, although I might try this latter idea to see if it is better for normal positions.

Maybe I'm missing something here, but why generate non-captures without first ensuring that there's no cutoff caused by a "bad" capture?

It did not help when I tried it, and the benefit _used_ to be that I used the history heuristic so that I could actually try some non-captures before those bad captures were tried. I removed the history stuff a couple of years ago when I discovered it was not helping at all any longer.

I still think that answer did not address Steven's questions, which is, why generate non-captures before exhausting all captures?

I thought my answer was perfectly clear. I _used_ to search

1. hash move
2. winning/equal captures
3. killers
4. history moves
5. rest of moves.

To do history moves I needed the rest of the moves. I no longer do that, but losing captures are not going to be best in 99.9% of positions, most likely they come into play only in tactical test positions that involve sacrifices. I could search the losers first today since I no longer do history moves. But I never saw any point to changing the code since I don't think there is any benefit.

If I understand it correctly, Crafty does it this way:
1. generate captures
2. try good captures
3. try killers
4. generate non-captures (append to the list of bad captures).
5. try bad captures and non-captures

Why not this:
1. generate captures
2. try good captures
3. try killers
4. try bad captures
5. generate non-captures
6. try non-captures

If you get a cut-off in (4), you don't need to do (5) which is time-consuming.

I would agree, but (4) is _highly_ unlikely to be good. Else I would not be using SEE to discard them. I don't even search SEE < 0 moves in qsearch, for example... They are almost always bad... It would not be that hard to fix, but it would be additional code in NextMove() that would not really help at all, so I have left it alone.

[Harald Johnsen]

I guess bad captures (SEE < 0) are more often good moves, to the point of causng a cutoff, than the killer move. This might partly be due to the fact that most people do not allow bad captures to become killer moves.

From memory, when searching 'bad captures' last, only 1 see capture < 0 out of 1000 will cause a cutoff.
I'll try to check how this ratio changes if I try bad captures just after 'killers', or before 'killers'.

HJ.

[hgm]

But does this 1 in 1000 statistic also apply to SEE<0 captures that have already proven to be cut-moves in the sibbling node?

[bob]

But does this 1 in 1000 statistic also apply to SEE<0 captures that have already proven to be cut-moves in the sibbling node?

It is pretty low. I can instrument Crafty to gather some of this data. It is easy enough to measure how often the "bad captures" cause a cutoff since I try them before non-captures anyway. When I am in the "rest-of-the-moves" NextMove() phase, any capture must be a SEE loser. I can count the number I try, and the number that fail high and run a 40K set of games to see what the total looks like...

By "it" I am talking about the case where a "bad SEE capture" actually fails high, which would be a prerequisite for it becoming a killer anyway. Actually, I can allow captures to become killers easily enough, but I would probably want to not allow "good captures" to get in there as it would just thrash the normal killers since captures are the best move in the majority of full-width nodes.

[hgm]

Yes, of course. Any move that would be tried before the killers anyway would serve no purpose, and just flush out legitimate killers. But it seems logical to me to allow any move that would be searched after the killers to 'jump the queue' if it has proven to be good.

The main weakness of the kiler heuristic seems to me that it is too easy for a specific refutation to push out a general refutation. I'd much rather have a filter that would prevent moves that are tacticlly related to the move they refute from becomming killer. Perhaps it would be a good idea to reserve one killer slot for the refutation of the null move.

[bob]

Yes, of course. Any move that would be tried before the killers anyway would serve no purpose, and just flush out legitimate killers. But it seems logical to me to allow any move that would be searched after the killers to 'jump the queue' if it has proven to be good.

The main weakness of the kiler heuristic seems to me that it is too easy for a specific refutation to push out a general refutation. I'd much rather have a filter that would prevent moves that are tacticlly related to the move they refute from becomming killer. Perhaps it would be a good idea to reserve one killer slot for the refutation of the null move.

I have tried a ton of different approaches to this problem. In Cray Blitz we used 4 killers (I will have to look at the public source to see if that version did.) It also would try the killers from ply-2, ply-4, etc as well before giving up. But on a vector machine the cost was almost nil for doing that. At one point I took it out and Harry complained that it hurt problem solutions although it seemed to play slightly better in games...

There are probably several "classes" of moves that could use their own killer. You mentioned the null-move. Non-captures tend to have a more useful killer because there so many non-capture moves that leave you exposed to a material loss or threat. Checks might be another case, where the checks are less frequent, but the same escape move is always best, assuming a capture won't do the trick...

In Crafty I can sort of tell what "kind" of move is being tried at the previous ply, and so I could adjust where I look for a killer for that particular type of move. At least it is something to think about.

[Harald Johnsen]

From memory, when searching 'bad captures' last, only 1 see capture < 0 out of 1000 will cause a cutoff.
I'll try to check how this ratio changes if I try bad captures just after 'killers', or before 'killers'.

HJ.

My memory is bad, this is not the ratio of 'bad' captures causing a cutoff, it's the number of bad captures causing a cutoff vs total number of captures causing a cutoff.
So out of 1000 captures causing a cutoff one capture was a 'bad' capture.
Those numbers do not include quiescent search.

btw all versions of cyrano dumps those cutoff numbers at the end of the analyze, you can see them in your UI log window/file (number of cutoff from hash move, killers, good/equal capt, bad capt, non capt).

HJ.