History heuristic and quiet move generation

[cdani]

Many engines try a few moves before generating quiet moves, namely killers, countermoves, and others.

In Andscacs I try hash move and null move threat before generating quiets, that is done immediately before trying the first killer. So the history [piece][to] of other moves than the one that caused a possible cutoff is updated when the killer moves are being tried. This history update of course cannot happen on other late quiet generation engines until this generation is done.

The idea of late generation of course is to save the time of generation of quiets on most possible nodes, but has this lack of history update drawback.

Is not that I can say if this is good or bad. Just that the engine obviously behaves differently and will be tuned differently once the decision of when to do the quiet move generation is made. Lmr will be tuned differently, different flavors of late move pruning also, etc.

[hgm]

I don't get what you are saying at all. Why can you not update history before move generation? You know the piece & to of the cut move, whether it was generated or not.

[cdani]

I was referring about decreasing the history of the other moves that have not caused the cutoff. The ones that the engine have tried but it don't have in a list, cannot be decreased.

[cdani]

I think I have to change this, and I will try to store the already tried moves before quiet generation, so I can defer the quiet move generation safely.

[hgm]

I was referring about decreasing the history of the other moves that have not caused the cutoff. The ones that the engine have tried but it don't have in a list, cannot be decreased.

And I suppose you could not do that right when you try them, because you want to make it dependent on whether there is a cutoff in that node?

But I don't see the problem. You know what you tried, so you can put that in a list. That list will never be very long. (Hash move + 2 killers?)

I put moves in a list anyway, before I try them. Only the null move has a separate recursive call, the only other recursion is when looping through the move list. Initially the list only contains the hash move, and each time you reach the end of the list, the next stage of the move generation is called to provide more moves. So hash move and killers would be in the list, if a killer fails high. And in particular, the killers would be in the non-capture section of the list.

[Steve Maughan]

In the main search (ie not the quiescent search) I generate all the moves after the null move has been tried. This keeps things simple (which is one of my design goals), and hardly impacts speed. In most engines they spend most of their time in the evaluation and generating captures in the quiescent search, so I believe doesn't impact speed too much (although I haven't tested it). It also means move ordering decisions and metrics are "pure", as they occur at the same time.

Steve

[cdani]

And I suppose you could not do that right when you try them, because you want to make it dependent on whether there is a cutoff in that node?

But I don't see the problem. You know what you tried, so you can put that in a list. That list will never be very long. (Hash move + 2 killers?)

I put moves in a list anyway, before I try them. Only the null move has a separate recursive call, the only other recursion is when looping through the move list. Initially the list only contains the hash move, and each time you reach the end of the list, the next stage of the move generation is called to provide more moves. So hash move and killers would be in the list, if a killer fails high. And in particular, the killers would be in the non-capture section of the list.

Yes, as I have commented after, adding a list of tried moves is the way to go. All this come due to having a bug in Andscacs that went unnoticed until after your first comment, that made me think that all was working as expected

In the main search (ie not the quiescent search) I generate all the moves after the null move has been tried.

At least saving the generation if the hash move works, is worth trying.