8 ms·
Chess invariants
- unprovable 5mo agoIf you like this, you're probably gonna like this: https://en.wikipedia.org/wiki/Chessboard_complex https://en.wikipedia.org/wiki/Chessboard_complex
- srean 5mo agoThis is delightful. Thanks.
- yewenjie 5mo ago> Chess is a lot trickier than it looks. It has so many rules: castling, en passant, pawn promotion, pinning, the discovered check, and the deadlock case of stalemate. Nit: Pinning and the discovered check are not really rules, but rather names of tactics.
- JohnKemeny 5mo agoWell, if a piece is pinned it's illegal to move it. Rule 3.9.2: No piece can be moved that will either expose the king of the same colour to check or leave that king in check.
- TheOtherHobbes 5mo agoUnlike en-passant and castling, pinning and discovered checks are consequences of lower-level rules. At the "Is this move legal?" level, they don't need unique rules of its own if the lower-level rules are specified correctly.
- JohnKemeny 5mo ago3.9.2: no piece can be moved if that exposes or leaves its own king in check.
- 333c 5mo agoThat's a consequence of not being allowed to put yourself in check (by any means).
- anamexis 5mo agoThe only way to put yourself in check is by moving.
- 333c 5mo agoDid you mean putting your opponent in check? In chess, you are not allowed to put yourself in check.
- anamexis 5mo agoYou said “ That's a consequence of not being allowed to put yourself in check (by any means).” My point is that there are no other means.
- 333c 5mo agoI was replying to a comment quoting an official rule saying "no piece can be moved if that exposes or leaves its own king in check." I was pointing out that that specific rule (read to mean that moving a piece pinned against a king is not allow) is not strictly necessary. Putting oneself in check is not allowed regardless of whether it's because you moved a piece that was pinned against your king or moved your king directly into the line of sight of an opponent's piece. These are the different "means." As a sibling comment points out, "The only action you can ever take in chess is moving," so it's not particularly meaningful to say that the only way to put yourself in check is by moving.
- anamexis 5mo agoAnd likewise, it's not particularly meaningful to say "That's a consequence of not being allowed to put yourself in check (by any means)." The rule, "3.9.2: no piece can be moved if that exposes or leaves its own king in check." covers both the case of moving a pinned piece as well as moving the king into check, i.e. it covers all "means" of putting yourself into check.
- gobdovan 5mo agoYou can also pin a pawn to a queen, but the pawn can still legally move.
- HiroProtagonist 5mo agoYou're both right, depending on whether you mean relative pin vs absolute pin.
- munchler 5mo agoThe point is that, logically, the first part of that rule (“expose the king”) is implied by the second part (“leave that king”), so the first part is redundant. You could simplify the rule to: No piece can be moved that will leave the king of the same color in check.
- emil-lp 5mo agoYou should submit it to FIDE.
- deleted 5mo ago[deleted]
- gpm 5mo agoPedantically I disagree, to leave something in a condition it must have been in that condition in the first place. We could have a game where you're allowed to place your king in check, but if it is in check at the start of your turn you must fix that. While we're being pedantic though it's not a property of the piece that might be able to be moved that will place the king in check. It's a property of the move. For example we might imagine you have a rook between an enemy rook and your king. You can move the rook along the line between the enemy rook and the king, but not perpendicular to it. The rule should be: No move can be made where the moving players king is in check in the resulting position
- saberience 5mo agoPinning isn’t a rule, it’s just something that arises from other rules. Also, pinning can happen with pieces that don’t include a king, which means you can just move out of the pin and expose whatever other piece. It’s just a chess tactic, not a rule. It’s like saying a chess skewer is a rule too.
- wavemode 5mo agoThat rule doesn't mean it's illegal to move a piece that's pinned. It just means that it's illegal to move it to a square that would expose the king. For example a pawn that's pinned vertically can still push forward, it just can't capture diagonally. That's why treating colloquial concepts like "pinning" as though they are rules in and of themselves is not really precise or productive.
- zonotope 5mo agoWell, a minor piece can be pinned in front of a queen. It would be legal to move the minor piece in that case, but you'd most likely lose the game if both sides' material were even before the move. Pinning is a tactic, not a rule.
- juujian 5mo agoAnd discovered check means that it is not sufficient to check the position of the piece you have moved, you also need to check the position of other pieces to see whether there is a new check.
- NicoHartmann 5mo agoI can't wait to show this to my manager next time he asks why it's taking three weeks to build a simple CRUD app. "Look, if this guys TLA+ logic struggles to model a 1,500-year-old game without crying over a French pawn-capture rule, you can't expect me to integrate Stripe billing without a few state invariant violations."
- epolanski 5mo agoPayments have a gargantuan amount of possible transitions and invariants that are far from trivial to encode.
- NicoHartmann 5mo agoI showed this to my manager and his response was: "So... three days?"
- vintermann 5mo agoThat king promotion rule sounds like it made the game more fun.
- rauljara 5mo agoAnyone know what language is being used in the blogpost?
- nonethewiser 5mo agoTLA+ i think
- grg0 5mo agoCorrect. Also: https://www.learntla.com/ https://www.learntla.com/
- phoe-krk 5mo agoScreenshots of code? In 2026?...
- grg0 5mo agoThat's how you know "principal research scientist" are true credentials. I'm sure the offline version is a postscript instead of pdf.
- fnord77 5mo agoside question, which CS class(es) teach about invariants?
- pramodbiligiri 5mo agoUsually goes under Formal Methods: https://github.com/luigiapetre/Formal-Methods-Courses https://github.com/luigiapetre/Formal-Methods-Courses There’s a book called Logic for Programmers: https://leanpub.com/logic#table-of-contents https://leanpub.com/logic#table-of-contents
- anthk 5mo agoA bit expensive. Just get Swi Prolog. https://www.swi-prolog.org/ https://www.swi-prolog.org/ The Simply Logical book as a start: https://book.simply-logical.space/src/simply-logical.html https://book.simply-logical.space/src/simply-logical.html you can get a PDF just fine. Also, for hardcore mode, get paper and pen, I'm not kidding: (again, just use SWI Prolog): https://www.ida.liu.se/~ulfni53/lpp/bok/ https://www.ida.liu.se/~ulfni53/lpp/bok/ Another approach. Scheme and Logic: S9 Scheme, get the bleeding edge version and compile it. Enough to do the book: https://www.t3x.org/s9fes/ https://www.t3x.org/s9fes/ Sketchy Lisp, intro to Scheme: https://archive.org/details/sketchy-lisp https://archive.org/details/sketchy-lisp Logic Progamming in Scheme: https://www.t3x.org/amk/index.html https://www.t3x.org/amk/index.html
- ventana 5mo agoThe well-known algorithms book Cormen et al. describes a lot of algorithms using loop invariants. I must say I never really liked this approach but I admit it makes things easier to reason about.
- duesabati 5mo agoWhile I think everything written in this post is correct, what really is starting bothering me is this over-focus/attention on data even when what you want to express is behavior, let me explain: The post talks about "transition invariants" that should be somehow different from "state invariants" yet it describe them as: > These are predicates over a <<state, next-state>> pair ... i.e. it still is about state, but I find it much more useful to focus on behavior so instead of thinking about how state transition you focus on what the program is allowed to perform, regardless of the underlying data structure. What I mean is that I'd like the code to tell me why a certain piece can't do such move instead of why it cannot transition it's position to another position and basically dumping its state in my head and there I have to execute the program myself.
- seanhunter 5mo ago> instead of thinking about how state transition you focus on what the program is allowed to perform The state transition is what the program is or isn't allowed to perform. The state they're talking about in the invariant isn't the program state, it's the game state.
- ferd 5mo agoShameless plug: a code walkthru modeling the rules of chess, ment as an exercise/teaching functional programming (in Clojure): https://neuroning.com/boardgames-exercise/notebooks/walkthrough/ https://neuroning.com/boardgames-exercise/notebooks/walkthro... The implementation makes it really easy to add new piece types or rules. For example, here's the full logic for rooks (sans castling): (defn expand-pmove-for-rook [pmove] (->> pmove (expand-pmove-dirs [↑ ↓ ← →]) (pmoves-discard #(or (pmove-on-same-player-piece? %) (pmove-changed-direction? %))) (map pmoves-finish-capturing-opponent-piece) (pmoves-finish-and-continue))))
- deleted 5mo ago[deleted]
- nilslindemann 5mo agoI read these images of source code the same way as I read images of math formulas on Wikipedia: Not at all.
- vunderba 5mo ago> Chess is a lot trickier than it looks. It has so many rules: castling, en passant, pawn promotion, pinning, the discovered check, and the deadlock case of stalemate. As a kid playing chess with other neighborhood kids back in the day, absolutely none of us even knew about the en passant rule. My first exposure around the same time was completely by accident thanks to a passing reference in a CRPG called Betrayal at Krondor. It comes up in a story about a game that nearly costs an innkeeper her establishment when she loses because of a move she didn’t even know existed.
- cainxinth 5mo agoA lot of adult players don’t know it either. If I play a casual game with someone who doesn’t know about en passant and they make a move that opens them up to it, I don’t attempt to take the piece, but I do point it out to them and recommend we use the rule in future games.
- teiferer 5mo agoThis is just the beginning. You could create more and more advanced invariants. And I am sure that this could be a way to "solve" chess, i.e., prove that it's a draw with perfect play.
- arvyy 5mo agodoubtful, or at least not useful ones. Like, you could describe some invariant along the lines of "the position is winning for the side-to-move, iff there exists move, such that position' := ApplyMove(position, move) is losing for the (now other) side-to-move". But that's just restating minimax algorithm that people have known for 50 years. As someone dabbling abit around chess engine development, I'm very often impressed by the many intricacies and observations made by people who pushed the envelope. It just doesn't sound plausible people wouldn't have discovered these killer invariants by now if they existed
- teiferer 5mo agoI agree it's hard and non-obvious. If it wasn't then chess would have long been solved by now. Let's start from the other end. Just a pawn and two kings. It's possible to describe some quite succinct rules for when that's a draw versus a win for the side with the pawn. Agreed? Club players know these by heart. You could write that doen as invariants. As long as the side with the pawn stays inside the "green zone" of the state space, there is nothing the other side can do to void mate. And vice versa, if the game is in the red zone and the other player manages to stay inside that red zone, there is nothing the side with the pawn can do to win. Those areas of the state space, green and red zones, can be described as invariants, in contrast to just enumerating them. It's very compact and can easily be checked by a machine that it's correct. Now let's add a pawn. And another. And a rook perhaps. The more you add, the harder the condition is to describe, but we live in the age of billion-node-sized neural nets, we have the resources. Eventually you get all pieces on the board, and if the starting position satisfies the draw invariant, that's it. And likely the 960 freestyle chess positions too.
- necklesspen 5mo ago
- AMerrit 5mo agoA nice read. I've been playing around with my own chess program and trying to implement a lot of chess variants like Double Chess and 7 Queen's Chess.
- sobellian 5mo agoThe historical rules also left ambiguous promotion to the opposite color: https://chess.stackexchange.com/questions/8291/pawn-promotion-endgame-problem-white-to-move-and-mate-in-1 https://chess.stackexchange.com/questions/8291/pawn-promotio.... This rule was clarified later to restrict to the same color.
- CSMastermind 5mo ago> The player’s choice is not restricted to pieces that have been captured previously I grew up playing chess but my grandfather always insisted that pawns could only be promoted to captured pieces so when I played him we had to play a that variant. I suspect this came from players not having extra pieces with their chess sets.
- vitally3643 5mo agoThat and just avoiding the obvious advantage of promoting every piece to a queen every time. Puts more constraint on the game which usually makes for more interesting play
- mathgradthrow 5mo agoSo many of these invariants are redundant and so few of them encode any of the interesting rules of chess.
- anthk 5mo ago[dead]
- shellfinity 5mo ago[flagged]
- stymaar 5mo ago> apparently it wasn't until 19th century that people made clear that you couldn't promote a pawn to a King, surprising an attempted checkmate by responding Le roi est mort, vive le roi! That's the coolest thing ever though, why would you ban such a move, where's the rule of cool when you need it most?
- TacticalCoder 5mo ago> It is a concurrent system, but with a very specific kind of concurrency: interleaved execution. More specifically, taking turns: white, then black, then white. "Chess is a game of imperfect information, but with a very specific kind of imperfectness: fully available information. More specifically, ever single information is visible: you see all your opponents' pieces and he sees all yours, you see how much time he's got left, and he sees how much time you have left". Who knew it? Chess is actually a concurrent game of imperfect information: with that definition, it's not unlike a real-time strategy game like Warcraft 3. Who would have guessed it?
- somat 5mo agoI sometimes dream of actual concurrent wego chess. It ends up a bit involved without a computer, each side has to commit to a move in secret(write it down on a pad) then comes the tricky part, a solid set of rules for situations that don't resolve cleanly under normal chess. stuff like collisions(do we bounce, halt, mutual annihilation?), pass throughs, escapes. I don't play much chess but it sounds like it could be a lot of fun.
- gryn 5mo agohuh ? where did you see the second quote, I can't find it the post. Was it there before ? the game is very much a game of perfect information.
- TZubiri 5mo ago0.01% chance you are a genius stumbling unto a whole new paradigm 99.9% chance you could have solved this in a couple of hours with some ifs and loops