Staged move generation and killers

[xr_a_y]

I am currently trying a staged move generator in Minic and want this work flow :
* return TT move
* Gen Cap and sort them (mvv-lva + see)
* return Good Cap
* return killers
* Gen quiet and sort them (history + pst)
* return quiet

But how do you ensure, without having generate the quiet moves first, that a move in the killer table is indeed ok ? My killer table is a simple 2 slots move array of size MAX_PLY.

[Robert Pope]

I am currently trying a staged move generator in Minic and want this work flow :
* return TT move
* Gen Cap and sort them (mvv-lva + see)
* return Good Cap
* return killers
* Gen quiet and sort them (history + pst)
* return quiet

But how do you ensure, without having generate the quiet moves first, that a move in the killer table is indeed ok ? My killer table is a simple 2 slots move array of size MAX_PLY.

Unless I am misunderstanding you, the same way you would validate that the TT move was okay:
1. Is the relative position of 'from' and 'to' legal, given the piece moving?
2. If not P/N/K, are the squares between 'from' and 'to' empty (a simple bitboard mask for a bb engine)
3. Special case castling, if you care.
4. Leaves king in check check, if you care.

[xr_a_y]

I am currently trying a staged move generator in Minic and want this work flow :
* return TT move
* Gen Cap and sort them (mvv-lva + see)
* return Good Cap
* return killers
* Gen quiet and sort them (history + pst)
* return quiet

But how do you ensure, without having generate the quiet moves first, that a move in the killer table is indeed ok ? My killer table is a simple 2 slots move array of size MAX_PLY.

Unless I am misunderstanding you, the same way you would validate that the TT move was okay:
1. Is the relative position of 'from' and 'to' legal, given the piece moving?
2. If not P/N/K, are the squares between 'from' and 'to' empty (a simple bitboard mask for a bb engine)
3. Special case castling, if you care.
4. Leaves king in check check, if you care.

I do not "validate" the TT move. I assume it is good as soon as it is not a type-2 collision. I was hoping for some trick for killers, I mean rather than indeed checking if the move is correct but I'll try that tomorow. Thanks

[Michael Sherwin]

I do not know if your engine is bitboard or not but what I do in RomiChess is store the move and capture bitboards without making a move list when moves are generated. So to validate any move or capture all I have to do is see if the toSq bit for any given piece is set. And because I do not want to generate that move again I just delete the bit. I do this for TT moves just to be safe.

[Sven]

I am currently trying a staged move generator in Minic and want this work flow :
* return TT move
* Gen Cap and sort them (mvv-lva + see)
* return Good Cap
* return killers
* Gen quiet and sort them (history + pst)
* return quiet

But how do you ensure, without having generate the quiet moves first, that a move in the killer table is indeed ok ? My killer table is a simple 2 slots move array of size MAX_PLY.

Unless I am misunderstanding you, the same way you would validate that the TT move was okay:
1. Is the relative position of 'from' and 'to' legal, given the piece moving?
2. If not P/N/K, are the squares between 'from' and 'to' empty (a simple bitboard mask for a bb engine)
3. Special case castling, if you care.
4. Leaves king in check check, if you care.

I do not "validate" the TT move. I assume it is good as soon as it is not a type-2 collision. I was hoping for some trick for killers, I mean rather than indeed checking if the move is correct but I'll try that tomorow. Thanks

You actually need to check at least whether a stored killer move is pseudo-legal in the current position (see below for a possible restricted definition of "pseudo-legal"). Usually you are at a sibling node of the node where the killer move had been found, and it is possible that the current node was reached by a move that captured the moving piece of the killer move. In some implementations killer moves from higher levels of the tree are considered as well, and in that case you might also have a current position where the destination square of your killer move is now occupied by a friendly piece. There might be other scenarios leading to a non-pseudo-legal killer move that I am currently not aware of.

Not validating the TT move may be less critical but I would always suggest to do so to be on the safe side, due to possible (rare but existing) hash collisions. For both TT and killer moves it should not be too much computation effort to check the minimum "pseudo-legality" requirements:

a) friendly piece on "from" square and
b) no friendly piece on "to square".

This should ensure not to crash the engine at least. Whether the stored move matches the capabilities of the moving piece is another issue. In my engine Jumbo I have started to implement staged move generation a couple of months ago. I do a full check for pseudo-legality of the TT move, and I did not notice a measurable strength decrease by doing so. Killer moves are not yet part of my staged move generation since that implementation is not finished yet, but once I do it I will definitely check for pseudo-legality of killer moves as well. One may like it or not, but I do not like the idea of doing a tree search after a knight move from c3 to g7 or a pawn moving backwards ...

[Joost Buijs]

Although I have a procedure to fully check legality of a move, I never use it. If the TT-move and the captures are not producing a cutoff, I just generate all non-captures and check the killers against them. Staged move generation doesn't help much anyway, with a bitboard move-generator generating all the moves doesn't take much longer as generating the captures alone, and in case the captures don't produce a cutoff, the whole process actually takes longer. Move generation takes a very tiny fraction of the total time spent in the engine, so at best staged move generation will give you a few percent gain in speed which is just worth a few Elo points. When your engine is top-notch, and you can't gain on anything else, it can be worth to try it.

[jackd]

^^

Just write a fast legal move generation and never worry about it again (or about checkmate).

[hgm]

Other cases that in the past have crashed my engines when I did not fully check pseudo-legality of killers are:
* under-promotion killers applied to a non-promotable piece.
* capture of a king
Whether it is necessary to test for those depends on how you implemented MakeMove and the check test.

[Sven]

Other cases that in the past have crashed my engines when I did not fully check pseudo-legality of killers are:
* under-promotion killers applied to a non-promotable piece.
* capture of a king
Whether it is necessary to test for those depends on how you implemented MakeMove and the check test.

It also depends on whether you allow captures or promotions as killer moves at all.

[hgm]

Well, I usually sort under-promotions with non-captures or bad captures, so it makes sense to allow them as killers.

As for the other case I start to suspect now that I was mistaken, and that this was really a case of insufficient validation of the hash move, not killer. If a King wanders in check you should already notice it during the captures, and thus never get to the killers, unless you execute killers that are not even pseudo-legal. (Which of course would lead to all kinds of nonsense.) But in a hash collision it can happen. My aim usually is to not waste more time on verifying hash moves beyond the point where they cannot crash the engine, since I use sufficiently many bits of the hash key to have no collissions at all during most games. For that it is often not even a problem if you capture your own pieces, move with opponent pieces, or even with empty squares. But loss of a King could lead to segfaulting during the check test