Chess invariants
Le jeu d'échecs comporte de nombreuses règles et peut se voir comme un système concurrent à exécution intercalée où les joueurs jouent à tour de rôle. Dans l'analyse formelle on modélise le jeu et on distingue les invariants d'état (propriétés sur un seul état) des invariants de transition (propriétés sur une paire état→état), ces derniers aidant à raisonner sur les changements. Parmi les invariants d'état figurent des contrôles de type et de présence des rois, la parité du tour (les blancs aux coups pairs, les noirs aux impairs) et l'exigence que le joueur ayant fini son coup ne soit pas en échec. Les invariants de transition imposent que le compteur de coups augmente et que le tour alterne, interdisent l'apparition de pièces ex nihilo, limitent les captures à une par coup et peuvent affirmer qu'exactement deux cases changent par mouvement. Des coups spéciaux modifient ces contraintes : le roque affecte quatre cases, l'en passant capture une pièce hors de la case d'arrivée, la promotion de pion change la nature de la pièce sans augmenter le nombre total, et il est noté historiquement que l'interdiction de promouvoir en roi a été clarifiée au XIXe siècle.