Introduction
Le jeu d'échecs est plus complexe qu'il n'y paraît, avec de nombreuses règles telles que le roque, la prise en passant, la promotion des pions, l'épinglage et le pat. Il s'agit d'un système concurrent, mais avec une forme spécifique de concurrence : l'exécution entrelacée. Plus précisément, les joueurs jouent à tour de rôle : blanc, puis noir, puis blanc.
Contexte Technique
Lorsque nous traitons des systèmes concurrents, nous les modélisons et en déduisons les invariants. Les invariants sont des propriétés qui doivent toujours être vraies. Il est utile de diviser les invariants de sécurité en deux catégories : les invariants d'état (qui sont des prédicats sur un seul état) et les invariants de transition (qui sont des prédicats sur une étape). Les invariants de transition sont moins couramment utilisés que les invariants d'état, mais ils peuvent être très utiles, en particulier lorsqu'on raisonne sur les transitions d'un système.
Les invariants d'état incluent TypeOK, qui vérifie que chaque variable vit dans l'espace approprié, OneKingPerColor et BothKingsOnBoard, qui sont des vérifications de cohérence. TurnParity est le premier invariant intéressant, qui relie deux variables d'état : les mouvements blancs se produisent sur les mouvements pairs, les mouvements noirs sur les mouvements impairs.
Analyse et Implications
Les invariants de transition sont des prédicats sur une paire d'états , écrits avec la forme entre crochets : [][P]_vars. Ils expriment comment les choses changent avec des contraintes. MoveCountStrictlyIncreases et TurnAlternates disent que chaque étape incrémente le compteur de mouvements avec les couleurs qui basculent. PieceCountNonIncreasing exclut l'apparition de pièces hors de l'air. SingleCapturePerMove resserre cela : au plus une pièce disparaît par étape.
ExactlyTwoSquaresChange est le plus fort ici, disant que précisément deux carrés changent par mouvement, la source (maintenant vide) et la destination (maintenant détenant la pièce qui bouge). C'est un modèle des règles de base du jeu d'échecs uniquement. Un exercice utile ici est de considérer lesquels de ces invariants survivent lorsque nous ajoutons le roque, les pions, la prise en passant.
Perspective
ExactlyTwoSquaresChange est violé lorsque nous ajoutons le roque : quatre carrés changent en un mouvement. De même, la prise en passant capture une pièce qui n'est pas sur le carré de destination, donc trois carrés changent. PieceCountNonIncreasing survive à la promotion des pions (lorsqu'un pion devient une reine, le décompte est inchangé). Il est important de noter que l'énumération des règles vous amène à réfléchir même avant l'analyse.
