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.
User avatar
xr_a_y
Posts: 454
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: 468
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: 454
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: 3015
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Sven
Posts: 3762
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: 822
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.

jackd
Posts: 25
Joined: Mon Dec 10, 2018 1:45 pm
Full name: jack d.

Re: Staged move generation and killers

Post by jackd » Wed Dec 26, 2018 5:25 pm

^^

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

User avatar
hgm
Posts: 23152
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Staged move generation and killers

Post by hgm » Thu Dec 27, 2018 10:02 am

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
Posts: 3762
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 » Thu Dec 27, 2018 11:16 am

hgm wrote:
Thu Dec 27, 2018 10:02 am
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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

User avatar
hgm
Posts: 23152
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Staged move generation and killers

Post by hgm » Fri Dec 28, 2018 2:12 pm

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

Post Reply