TTMove legality checking ? & Killers Move Format?

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
MahmoudUthman
Posts: 231
Joined: Sat Jan 17, 2015 10:54 pm

TTMove legality checking ? & Killers Move Format?

Post by MahmoudUthman » Wed Feb 08, 2017 4:42 am

Is it worth it to store the full move information in the TT or killers, for example the moving piece type , the captured piece type .. .etc
for example right now I store a move like this (6,6,2,2)bits <==> (fromSq,toSq,MoveType(Normal,Enpassant,Promotion,Castling),PromoType) , so if the the tt move was for example d1d5(normal) , d1d5(capture) both would result in the same value stored in the TT or killers ,which could result in a position accepting it as legal even if the move came from a similar position but with capturing or the captured piece being different , or even for quiets for example d1d5(queen) & d1d5(rook) , and so on !

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

Re: TTMove legality checking ? & Killers Move Format?

Post by hgm » Wed Feb 08, 2017 7:04 am

Killers should not be captures or promotions, as these will already have been searched by the time you get to the killers. If you observe that rule when storing them, it becomes redundant information. When testing thekillers for (pseudo-)legality, you should reject any move matching it that in the current position is a capture or promotion.

That only leaves the case where the mover is different. But if you only transfer killers between sibbling nodes, this should not be possible.The previous opponent move cannot alter the identity of my pieces.

User avatar
cdani
Posts: 2103
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: TTMove legality checking ? & Killers Move Format?

Post by cdani » Wed Feb 08, 2017 8:40 am

And about in the TT, the possibility that it happens is very low. And if it happens, the possibility that this changes the outcome of the analysis is also very low. A working and reliable engine is able to cope well with the TT incoherences.

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

Re: TTMove legality checking ? & Killers Move Format?

Post by Sven » Wed Feb 08, 2017 8:43 am

MahmoudUthman wrote:Is it worth it to store the full move information in the TT or killers, for example the moving piece type , the captured piece type .. .etc
for example right now I store a move like this (6,6,2,2)bits <==> (fromSq,toSq,MoveType(Normal,Enpassant,Promotion,Castling),PromoType) , so if the the tt move was for example d1d5(normal) , d1d5(capture) both would result in the same value stored in the TT or killers ,which could result in a position accepting it as legal even if the move came from a similar position but with capturing or the captured piece being different , or even for quiets for example d1d5(queen) & d1d5(rook) , and so on !
Regarding TT, I think you can simply ignore it since it is *very* unlikely that you get a collision (two different positions with two "identical" hash keys) while the stored TT move is also legal in the current position. And even if it actually happens it is most important not to make an illegal move on the board - so if you find "d1d5" in the TT and there is a legal move "d1d5" then I would simply accept it.

Regarding killers, see HGM's reply. Some engines ensure that killer moves are used for sibling nodes only, others don't. My engine currently doesn't. I once had an issue with killers when the stored move was "g7g5" resulting from a rook move but in the current position "g7g5" was a pawn's double step. Since I missed to check for the type of the moving piece I made the move without setting the double step bit, which in turn led to not setting the ep square ... Of course it was a bug, but even there I could fix it without extending the information I stored in the killer move table.

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

Re: TTMove legality checking ? & Killers Move Format?

Post by hgm » Wed Feb 08, 2017 9:23 am

In CrazyWa I clear the killer entries for ply+1 when I enter the node at 'ply'. This guarantees sibbling use of killers only. But I make one exception: when the previous move was a check evasion, I copy the killers from ply-1 there. The idea is that the check + evasion merely delayed things, forcing the opponent to postpone the normal refutation two ply because he had to resolve the check first. This does allow one of my pieces to replace another (if the check was a capture, and the evasion recaptured the checker). Too rare to have any impact. I do check the killers for pseudo-legality, so the worst that can happen is a sub-optimal move ordering.

As to hash moves: as mentioned, the chances fora mixup are astronomically small (unless you take very few bits in the signature, such as Stockfish). So you actually don't even have to worry about the move being legal. Whatever nonsense the engine would be doing has zero effect, as long as it doesn't crash. Who cares if a Rook moves from g1 to f3?

In CrazyWa there were some cases that could cause crashing, though:
*) Moving an opponent piece in my turn could put myself in check, in a way the King-capture detection in the daughter would not catch. This would lead to an unexpected King capture, which would abort move generation without properly terminating the move list, but also without aborting the node. Which then would lead to a segfault by overrun of the move stack during reading.
*) Likewise, capturing one of my own pieces with an empty square could put me in check as well.
*) Applying a promotion move to an already promoted piece would cause an invalid piece code (or a color flip), because the MakeMove code added the promotion increment to the original piece, rather than just replacing it.

I solved the first two problems by checking that the hash moves at least has a piece of my own in the from-sqaure. The third problem could be fixed by OR'ing the promotion increment to the original type in MakeMove, rather than adding it. Then promoting an already-promoted piece would just leave it itself.

Ras
Posts: 1094
Joined: Tue Aug 30, 2016 6:19 pm
Contact:

Re: TTMove legality checking ? & Killers Move Format?

Post by Ras » Fri Feb 10, 2017 12:20 am

I have added a TT move pseudo-legality check to NG-Play in case that there is a "best move" stored.

Due to memory constraints, I even have reduced the hash value storage from full 64 bits to the upper 32 bits plus fiddling in 6 additional bits into the alpha/beta/exact flag variable plus the hash table index, which gives effective 48 bits. According to a paper by Bob Hyatt, 48 bits are just as reliable as 64 bits.

In thousands of test games in the PC version, I have never seen the error message that would come up if an illegal move were fetched from the TT due to a hash collision.

User avatar
cdani
Posts: 2103
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: TTMove legality checking ? & Killers Move Format?

Post by cdani » Fri Feb 10, 2017 5:34 am

Ras wrote:I have added a TT move pseudo-legality check to NG-Play in case that there is a "best move" stored.

Due to memory constraints, I even have reduced the hash value storage from full 64 bits to the upper 32 bits plus fiddling in 6 additional bits into the alpha/beta/exact flag variable plus the hash table index, which gives effective 48 bits. According to a paper by Bob Hyatt, 48 bits are just as reliable as 64 bits.

In thousands of test games in the PC version, I have never seen the error message that would come up if an illegal move were fetched from the TT due to a hash collision.
To test the reliability of the pseudo-legality checker, I generate random moves just to be sure. Is true that happens really few, but happens enough to make your engine crash in the worst moment :-)

mjlef
Posts: 1367
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: TTMove legality checking ? & Killers Move Format?

Post by mjlef » Thu Feb 16, 2017 3:24 pm

hgm wrote:In CrazyWa I clear the killer entries for ply+1 when I enter the node at 'ply'. This guarantees sibbling use of killers only. But I make one exception: when the previous move was a check evasion, I copy the killers from ply-1 there. The idea is that the check + evasion merely delayed things, forcing the opponent to postpone the normal refutation two ply because he had to resolve the check first. This does allow one of my pieces to replace another (if the check was a capture, and the evasion recaptured the checker). Too rare to have any impact. I do check the killers for pseudo-legality, so the worst that can happen is a sub-optimal move ordering.
That is clever. Do you mind if I try that in Komodo? I would have to merge it with some other things we do when in check, but it sounds promising.

Mark

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

Re: TTMove legality checking ? & Killers Move Format?

Post by hgm » Thu Feb 16, 2017 6:57 pm

Of course you can try it in Komodo. I would not mention it if I wanted to keep it for myself!

Note that CrazyWa is an engine for Crazyhouse (and other games with piece drops), where checks are enormously more frequent then in chess variants without drops. In orthodox Chess the effect could be unmeasurably small, just because checks are so rare in the tree.

Post Reply