5 ms·
> Verifying checkmate is essentially doing a 2-ply search: for all moves i can make, the opponent has a reply that captures my king. This is more work than veri
by DocSavage 10y ago
> Verifying checkmate is essentially doing a 2-ply search: for all moves i can make, the opponent has a reply that captures my king. This is more work than verifying normal moves, where a 1-ply search suffices to check that kings are not left in check.
Isn't checkmate a very constrained 2-ply search? If you have a 1-ply search that suffices to check that kings are not left in check, isn't the checkmate simply using that search for each of the maximum 9 board positions (including current one) that the king can occupy? I must be missing something about blockchain computation because the article says this:
"In order to verify a checkmate, Grau wrote, all possible moves must be calculated and verified, which he and his peers found was not feasible on the blockchain."
- TylerE 10y agoThere are many ways out of a check besides moving the king - capturing the checking piece, interposing another piece in between (Which can even expose a check on the OTHER king), etc.
- schoen 10y agoActually, you've just listed both of the other ways of eliminating check. https://en.wikipedia.org/wiki/Check_(chess)#Getting_out_of_check https://en.wikipedia.org/wiki/Check_(chess)#Getting_out_of_c... While your analysis is right, you don't really need the "etc." at the end!
- AstralStorm 10y agoIt is a highly constrained search though. You need to verify moves against the piece that is checking only and then verify if the move potentially preventing the check does not discover another check. Even easier in case of double checks, since you exclude captures. Verifying a tie or mate due to repetition is more tricky for a usual test, but not if you hash the whole board state.