I don't understand why verifying the checkmate end state is any harder than playing each turn.
They say
> For checkmate and stalemate, to verify the condition all possible moves have to be calculated and verified, which is unfeasible on the blockchain.
But "all possible moves" is only one-move deep. We're generally talking a couple dozen possible moves at most. If the system can't calculate a couple dozen possible moves, how is all the basic move logic being done "on chain," as they say?
I have to admit ignorance about this implementation, but as I understand it evaluating a single move is computationally much simpler. That is given a piece, validate that the proposed move (decided on by a human) conforms to the rules of chess, and is valid for the given board state. Verifying a checkmate (even if only verifying checkmates proposed by a human player), means going through every one of the opponents pieces to see if it can be used to improve to a non-check state.
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.
They could have simply adopted blitz chess rules, where the goal is to capture the opponent king, and leaving your king in check is not illegal, to avoid all this extra computation...
> 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.
I was going to make a counter-argument but then I realized that this system doesn't normally enumerate legal moves, simply verify legality of moves that are actually played, which is a crucial distinction here.
Thanks for making this observation; I found it a pretty subtle point!
>They could have simply adopted blitz chess rules, where the goal is to capture the opponent king, and leaving your king in check is not illegal, to avoid all this extra computation...
Those are not blitz chess rules. The goal of blitz is still checkmate, not capturing the opponent's king. USCF, FIDE, WBCA all agree, leaving a king in check is an illegal move and loses the game as soon as it is pointed out.
I don't know. One time I played a blitz game where extreme time pressure left me getting my king chased across the board. I moved it next to my opponent's king and then captured his king with mine on the next move.
Presumably blitz rules didn't actually allow you to move your king into check like that, but maybe blitz games more routinely include illegal moves that are never detected?
Edit: there is a relevant distinction like this according to FIDE!
In normal play, when "it is found that an illegal move has been completed, the position immediately before the irregularity shall be reinstated." (7.5a)
But in rapidplay (including blitz), "[i]f the opponent does not claim and the arbiter does not intervene, the illegal move shall stand and the game shall continue." (A.4)
The FIDE laws still seem to assume the presence of an arbiter, which wouldn't always be the case for blitz games outside of a tournament or other formal event. But I guess there is an official notion even according to FIDE that illegal moves (including moving into check!) can be allowed in a blitz game if nobody notices them, which is not the case in a standard game.
Nonetheless, for all types of games, "[l]eaving one’s own king under attack, exposing one’s own king to attack and also ’capturing’ the opponent’s king are not allowed." (1.2)
It does, because of stalemate. In normal chess that is a draw, in chess-with-king-capturing it's usually a loss.
And stalemate is huge, e.g. many K+pawn vs K endgames are drawn because of stalemate, without stalemate a one pawn advantage would be much more significant.
The average branching factor for chess is about 35 moves, so verifying check would typically require looking at roughly 35 moves, while verifying checkmate would require about 1,225 moves. I'm surprised that a factor of 35 is enough to push it over the edge, but I guess Ethereum contracts need to be fairly limited.
I wonder if it's cheaper to verify a proof of checkmate that someone else computes. I'm not sure exactly what such a proof would look like, but there are lots of problems where finding a proof is hard, but verifying one is easy. Then you could make the checkmating player prove that it's checkmate and provide that proof along with their final move, and the contract could just verify it.
The problem on Ethereum is not that it's limited, the EVM is capable of handling it.
The problem here is that there is a cap of how much gas[1] a block may consume which is the moving average of consumed gas plus some extra.
A few contracts got stuck that way; by getting to a point where they could no longer use that much gas.
[1]: Gas in Ethereum refers to the amount of value paid for computation, once gas runs out the execution is terminated and the gas subtracted from the senders account.
I've heard of gas, but I'm not entirely familiar with the cap. I thought it was determined by how much the contract wanted to spend. Are you saying there's a fixed cap as well?
Upfront all transactions must pay for the computation they expect to have. The user (or whatever) decided how much has may be spent.
When the transaction runs, gas is consumed. If the transaction finished or there is no more gas, computation stops.
Now, transactions have no limit but blocks of transactions have. This is to prevent a single person creating and mining gigantic transaction to stall the network.
This limit is dynamic and you can raise it by having the network use more gas until the moving average climbs high enough.
Makes sense, thanks for explaining! Basing the limit on the moving average is an interesting choice and I wonder what sort of long-term consequences it will have on people's behavior. Seems like there's some potential for weird feedback loops.
> 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."
There 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.
It 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.
Alternate solution: (1) Player A announces "checkmate." (2) Player B either agrees (ending game), or moves a piece. (3) If Player B moved, then player A can end the game by capturing the king.
This could allow for player error, but to prevent that you simply have client-side code perform the steps.
Perhaps they meant that only certain "stalemates" are computationally infeasible with their ethereum platform? There are stalemates where it is impossible to checkmate the King, but where the players can just keep making moves indefinitely.
Those aren't stalemates, technically speaking. Such a game would end either when the players both realized it's pointless and agreed to a draw, or when it's gone on long enough for the same position to repeat three times, and one player claims a draw. The second case may well be computationally infeasible too, since it would involve keeping and searching the entire history of the game.
Edit - I suppose it is a draw rather than a stalemate
Fide Rules 5.2 (B)
The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was legal. (See Article 9.6)
Oh yes, I was thinking of a case where checkmate is theoretically possible, but where your opponent can thwart it indefinitely with good play. But as you say, that's a draw rather than a stalemate. Which is not a particularly important distinction, I will admit!
Programming all the draw scenarios in chess wouldn't be completely trivial. If you add clocks to the game then you also need to account for when you flag but your opponent cannot win the game with legal moves. There are some strange edge-cases here for pawns vs minor pieces.
The starting position is probably "a case where checkmate is theoretically possible, but where your opponent can thwart it indefinitely with good play".
Heh, indeed. I think what I meant was that your opponent can thwart it, in practice, given the actual abilities of both players. Things like the 50 move rule and the repetition rule are ways to detect this condition without actually having to figure out a way to analyze their abilities to decide whether a position is practically unwinnable.
Yes, that one is quite hard to get right for normal chess engines too, and it usually isn't done.
E.g. if both sides have only a bishop left, then if the two bishops are on squares of the same color checkmate isn't possible, but if they are on different colors then checkmate is possible in a corner. Or pawn formations in the middle of the board that prevent breakthroughs.
Most online chess sites only consider the obvious case of king + bishop or knight vs king to be a draw under that rule (and king v king, obviously).
Searching the history to enforce the threefold repetition rule[1] wouldn't be efficient, but the fifty-move rule[2] could be pretty cheaply implemented (one cell of state for a counter, an increment-and-check per move, and resetting the counter to 0 on the relevant moves).
There isn't really any need to check the board state is in checkmate anyway. It's a nice feature, but admitting checkmate is essentially the same as resigning, so just let the player carry on and give them an "I resign" button. They can't make a move, they have no choice but to click it. If they don't click it within a given timeframe that's the same as if they just walked away mid-game.
You'd probably need a second button that instigates the stalemate procedure if both players have pressed it because that's a much more complex problem.
42 comments
[ 5.0 ms ] story [ 108 ms ] threadhttps://news.ycombinator.com/newsguidelines.html
link to their github repo for ethereum chess: https://github.com/ise-ethereum/on-chain-chess
They say
> For checkmate and stalemate, to verify the condition all possible moves have to be calculated and verified, which is unfeasible on the blockchain.
But "all possible moves" is only one-move deep. We're generally talking a couple dozen possible moves at most. If the system can't calculate a couple dozen possible moves, how is all the basic move logic being done "on chain," as they say?
They could have simply adopted blitz chess rules, where the goal is to capture the opponent king, and leaving your king in check is not illegal, to avoid all this extra computation...
I was going to make a counter-argument but then I realized that this system doesn't normally enumerate legal moves, simply verify legality of moves that are actually played, which is a crucial distinction here.
Thanks for making this observation; I found it a pretty subtle point!
Those are not blitz chess rules. The goal of blitz is still checkmate, not capturing the opponent's king. USCF, FIDE, WBCA all agree, leaving a king in check is an illegal move and loses the game as soon as it is pointed out.
Edit: there is a relevant distinction like this according to FIDE!
http://www.fide.com/component/handbook/?id=171&view=article
In normal play, when "it is found that an illegal move has been completed, the position immediately before the irregularity shall be reinstated." (7.5a)
But in rapidplay (including blitz), "[i]f the opponent does not claim and the arbiter does not intervene, the illegal move shall stand and the game shall continue." (A.4)
The FIDE laws still seem to assume the presence of an arbiter, which wouldn't always be the case for blitz games outside of a tournament or other formal event. But I guess there is an official notion even according to FIDE that illegal moves (including moving into check!) can be allowed in a blitz game if nobody notices them, which is not the case in a standard game.
Nonetheless, for all types of games, "[l]eaving one’s own king under attack, exposing one’s own king to attack and also ’capturing’ the opponent’s king are not allowed." (1.2)
And stalemate is huge, e.g. many K+pawn vs K endgames are drawn because of stalemate, without stalemate a one pawn advantage would be much more significant.
I wonder if it's cheaper to verify a proof of checkmate that someone else computes. I'm not sure exactly what such a proof would look like, but there are lots of problems where finding a proof is hard, but verifying one is easy. Then you could make the checkmating player prove that it's checkmate and provide that proof along with their final move, and the contract could just verify it.
The problem here is that there is a cap of how much gas[1] a block may consume which is the moving average of consumed gas plus some extra.
A few contracts got stuck that way; by getting to a point where they could no longer use that much gas.
[1]: Gas in Ethereum refers to the amount of value paid for computation, once gas runs out the execution is terminated and the gas subtracted from the senders account.
When the transaction runs, gas is consumed. If the transaction finished or there is no more gas, computation stops.
Now, transactions have no limit but blocks of transactions have. This is to prevent a single person creating and mining gigantic transaction to stall the network.
This limit is dynamic and you can raise it by having the network use more gas until the moving average climbs high enough.
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."
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!
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.
This could allow for player error, but to prevent that you simply have client-side code perform the steps.
Fide Rules 5.2 (B)
The game is drawn when a position has arisen in which neither player can checkmate the opponent’s king with any series of legal moves. The game is said to end in a ‘dead position’. This immediately ends the game, provided that the move producing the position was legal. (See Article 9.6)
Programming all the draw scenarios in chess wouldn't be completely trivial. If you add clocks to the game then you also need to account for when you flag but your opponent cannot win the game with legal moves. There are some strange edge-cases here for pawns vs minor pieces.
Example:
https://www.chess.com/forum/view/livechess/draw-by-insuffici...
E.g. if both sides have only a bishop left, then if the two bishops are on squares of the same color checkmate isn't possible, but if they are on different colors then checkmate is possible in a corner. Or pawn formations in the middle of the board that prevent breakthroughs.
Most online chess sites only consider the obvious case of king + bishop or knight vs king to be a draw under that rule (and king v king, obviously).
[1]: https://en.wikipedia.org/wiki/Threefold_repetition [2]: https://en.wikipedia.org/wiki/Fifty-move_rule
You'd probably need a second button that instigates the stalemate procedure if both players have pressed it because that's a much more complex problem.