5 ms·

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, va

by gjem97 10y ago

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.

tromp 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. 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...
- slm_HN 10y ago
  >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.
  - rspeer 10y ago
    This is a distinction in terminology that has no effect on gameplay.
    - SamReidHughes 10y ago
      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.
      - schoen 10y ago
        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! http://www.fide.com/component/handbook/?id=171&view=article 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)
      - rspeer 10y ago
        Okay, you're right. I didn't think of that kind of situation arising, and that's awesome.
    - Scarblac 10y ago
      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.
- mikeash 10y ago
  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.
  - tscs37 10y ago
    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.
    - mikeash 10y ago
      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?
      - tscs37 10y ago
        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.
- schoen 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. 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!
- 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 ago
    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.
    - schoen 10y ago
      Actually, 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 ago
        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.
DennisP 10y ago
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.

by gjem97 10y ago

tromp 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. 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...

slm_HN 10y ago
>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.
- rspeer 10y ago
  This is a distinction in terminology that has no effect on gameplay.
  - SamReidHughes 10y ago
    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.
    - schoen 10y ago
      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! http://www.fide.com/component/handbook/?id=171&view=article 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)
    - rspeer 10y ago
      Okay, you're right. I didn't think of that kind of situation arising, and that's awesome.
  - Scarblac 10y ago
    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.
mikeash 10y ago
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.
- tscs37 10y ago
  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.
  - mikeash 10y ago
    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?
    - tscs37 10y ago
      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.
schoen 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. 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!
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 ago
  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.
  - schoen 10y ago
    Actually, 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 ago
      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.

DennisP 10y ago

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.