Staged move generation and killers

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
xr_a_y
Posts: 272
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Staged move generation and killers

Post by xr_a_y » Tue Nov 13, 2018 5:34 pm

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
Posts: 436
Joined: Sat Mar 25, 2006 7:27 pm

Re: Staged move generation and killers

Post by Robert Pope » Tue Nov 13, 2018 6:41 pm

xr_a_y wrote:
Tue Nov 13, 2018 5:34 pm
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.

User avatar
xr_a_y
Posts: 272
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Staged move generation and killers

Post by xr_a_y » Tue Nov 13, 2018 9:30 pm

Robert Pope wrote:
Tue Nov 13, 2018 6:41 pm
xr_a_y wrote:
Tue Nov 13, 2018 5:34 pm
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
Posts: 2831
Joined: Fri May 26, 2006 1:00 am
Location: OH, USA

Re: Staged move generation and killers

Post by Michael Sherwin » Wed Nov 14, 2018 5:54 am

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.
Regards,
Mike

Sven
Posts: 3706
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Staged move generation and killers

Post by Sven » Wed Nov 14, 2018 7:42 am

xr_a_y wrote:
Tue Nov 13, 2018 9:30 pm
Robert Pope wrote:
Tue Nov 13, 2018 6:41 pm
xr_a_y wrote:
Tue Nov 13, 2018 5:34 pm
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 ...
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Joost Buijs
Posts: 772
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: Staged move generation and killers

Post by Joost Buijs » Wed Nov 14, 2018 3:46 pm

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.

Post Reply