Staged move generation

[Ras]

the hash move was played in a certain position, and and saved with that position; so if it was valid when it was saved, it should be valid when retrieved.

Unless you have a full hash collision, in which case you may get sporadic crashes.

[eligolf]

Any ideas why this would fail? Am I thinking something wrong here?

I've seen messages that the hash move also needs to be checked for validity.

I've always found that a bit strange, because the hash move was played in a certain position, and and saved with that position; so if it was valid when it was saved, it should be valid when retrieved. I could be wrong though, that there's some finesse I (yet) don't know about.

But... there are positions that don't give you a hash move. (If I remember correctly, those are the positions which evaluation doesn't even get to alpha during the search; the ones between alpha and beta are PV nodes, and the ones from beta and up are cut nodes, and both should give you a hash move.) Do you check if you actually _HAVE_ a hash move before you try to play it?

edit: seems you do; at least as far as I understand. You check if you _don't_ have a TT-move and then jump to the captures instead of checking if you _do_ have a hash move. Personally I prefer to put the "what to do if..." in the first part of the "if" if possible.

Yeh it should always be legal to play, but I also check every move for legality (in the if statement about makeMove since I only generate pseudo legal moves) so it shouldn't be that. I think I will need some more time to look into staged move generation and maybe leave this to the side for now. It shouldn't be that hard but it seems I get weird errors when doing things that I think is logical. Maybe something else in my code is screwing things up, not sure what that would be though since perft is completing fine and I don't have any prunings except alpha/beta in my negamax yet. thanks for all the input though, it really helped me understand how the concept looks like

[mvanthoor]

Yeh it should always be legal to play, but I also check every move for legality (in the if statement about makeMove since I only generate pseudo legal moves) so it shouldn't be that. I think I will need some more time to look into staged move generation and maybe leave this to the side for now. It shouldn't be that hard but it seems I get weird errors when doing things that I think is logical. Maybe something else in my code is screwing things up, not sure what that would be though since perft is completing fine and I don't have any prunings except alpha/beta in my negamax yet. thanks for all the input though, it really helped me understand how the concept looks like

I forgot about the thing Ras mentioned above: you can have a hash collision. This means that the position on the board has the same Zobrist hash as a _different_ position in the TT. You will then get the move from the TT, but that is for a different position. If you are just move ordering / picking, you won't find the move in the move list, so it won't ever be picked. If you are playing it using staged move generation, the move is either not legal, it could be a stupid move to make (even if it is legal, because it comes from a different position), or the entire engine could crash.

I'd check the TT move for "is it even possible to play" (type of piece on the from square is the same as the one on the board, the to-square doesn't have one of your own pieces) just as you would with the killers.

[Ronald]

Illegal hashmoves can also occur in multithreading situations where a hashkey of one thread is combined with a hashdata of another thread due to usually not locking the hashentry and/or misalignment of hashentries. It has led to multiple engine crashes in past seasons of TCEC tournaments.

You can end up with 2 types of illegal hashmoves. The first type is a hasmove that is illegal in the current position, but has a "correct syntax" because it is a real move. The second type is a misformed move, because the original/underlying data is just a random number. Depending on the move encoding of the engine, this can lead for instance to a move square 183 to square 78 etc. This type can occur with misaligned entries and one thread is changing a part of the entry, while another thread changes another part of the entry concurrently.

Type 1 illegality can not be avoided (due to possible same hashkey for different positions) and should always be checked. Type 2 illegality takes more effort to check and can be avoided by correctly aligning the hashentries.

[hgm]

It is not realy important whether your hash move is legal or even pseudo-legal. Just that it produces a valid game state after applying it to the current position, and will be properly taken back. How much you can afford depends on how you program your MakeMove, and with sufficient care you might be able to afford anything. Points of worry are usually moving an empty square or opponent, capture of a friendly piece, or capture of a King. Often in connection with how your in-check test works.

[mvanthoor]

It is not realy important whether your hash move is legal or even pseudo-legal. Just that it produces a valid game state after applying it to the current position, and will be properly taken back. How much you can afford depends on how you program your MakeMove, and with sufficient care you might be able to afford anything. Points of worry are usually moving an empty square or opponent, capture of a friendly piece, or capture of a King. Often in connection with how your in-check test works.

All the checks for a legal hash move could of course be built into the MakeMove function.

- from-square and to-square needs to be on the board (in my case, 0 <= sq <= 63)
- from-square needs to contain the piece type in the move
- (maybe I should also add the piece color. For version 5 of my engine I might add another mailbox table for "color" next to the one for "piece_type", or I might switch to 12 piece types instead of 6. This is to prevent the fact that the piece type on the square could be correct, but the color of the piece isn't.)
- to-square must be empty or contain an opponent piece, which is not the opponent's king

If on of the checks fails, the MakeMove function quits returns false (= illegal move). Then you don't ever have to check any move for executability (is that a word?) in the search / staged move generation. The downside is that you're checking EVERY move for executability, which costs the time of at least evaluating the if-statement, even though this check is not always necessary.

[Ras]

All the checks for a legal hash move could of course be built into the MakeMove function.

I check pseudo-legality in the hash lookup itself because if that fails, I treat the whole lookup as "no match".

[hgm]

There is no need to check the square numbers: the worst that can happen in case of a collision is that you get a move that was intended for another position. A move that strays off board will never be valid in any position, so it can never be found in the TT. Beware for move code 0, though, which might be in unused TT entries. If your hash signature would ever be 0, it would have a much larger probability to collide (with such an unused entry) than other keys. Such a 0 move would either refer to an empty square, or make a piece capture itself, and thus might already be removed by other tests.

I never store the type of the moving piece in the move, and most certainly not in the hash entry (where space is at a premium). So there is nothing to test in that respect.

The color of the moved piece (taken from the game state, not the move) can be important, though: moving an opponent piece in your own turn it might check you, and the check test might not detect this. If you use the 'super-piece method' for check detection it will detect any check, so you can forego the color test if you use that.

Capturing your own pieces can be OK as long as you do not assume it is opponent color when removing it from the game state.

Moves will contain the info whether they are promotions or not, and what to promote to. This can go awry when you assume the piece that is replaced will always be a Pawn. If you take care to remove the actual piece that was on the board from the game state, there will be no harm in promoting non-pawns, as long as they are not Kings.

Moving empty squares might cause problems if you use the piece code of the mover to index a piece list, and the piece list has no element for 'empty square'. I always make sure that it does; that also makes it possible to treat making of captures and non-captures the same way, the former just capturing the empty square, and accessing the dummy element in the piece list for removing it.

Most check tests go berserk when the King is gone, so it usually remains important to test whether the captured or promoted piece is a King.

[Ronald]

As long as you're not using the hashmove at the root, you don't need to do a full legality check. It can be a little annoying if the engine gives a bestmove for a Queen making a knightmove..

In most cases making an illegal move in the search tree that doesn't "brake" anything will have little impact on the outcome of the search. You will always need to do some basic checks in order to not brake anything, and doing a full pseudo legality check is not much more complex, so I would opt for the last.

It makes things much easier if you add the moved piece to the info of the hashmove. I don't have it in my movelist but when I store a move as a killer or hashmove I "reuse" the order part of the move to store the piece. I think you don't need the color of the moved piece, you just need to make sure that the piece on the board is the same as the color to move (and the same piece as is stored in the move).

[hgm]

Unless you store the moved piece in the hash table this would not give you any discrimination against a collision. And the space required to do it would provide more safety when used for extra key bits. Even when you would use the hash move at the root, the chances that the collision happens there is astronomically small. At least when you don't use an extremely short signature. I think most people use at least 32 bits. The worry is more that the collision happens elsewhere in the tree (which is millions of times more likely) and then crashes the engine.

I am not sure you have to 'always check something'; you can write MakeMove / UnMake in such a way that it is resistant to anything, and this might not require any extra work except for the 'rare moves' such as castling and promotion. (Note that engines typically never execute any castling code, as they castle in book.)