Somme disjonctive

En mathématiques des jeux combinatoires , la somme ou somme disjonctive de deux jeux est un jeu dans lequel les deux jeux sont joués en parallèle, chaque joueur étant autorisé à se déplacer dans un seul des jeux par tour. Le jeu de somme se termine lorsqu'il ne reste plus de coups dans aucun des deux jeux parallèles, auquel cas (en jeu normal ) le dernier joueur à se déplacer gagne. Cette opération peut être étendue aux sommes disjonctives de n'importe quel nombre de jeux, encore une fois en jouant les jeux en parallèle et en se déplaçant dans exactement un des jeux par tour. C'est l'opération fondamentale qui est utilisée dans le théorème de Sprague-Grundy pour les jeux impartiaux et qui a conduit au domaine de la théorie des jeux combinatoires pour les jeux partisans .

Les sommes disjonctives apparaissent dans les jeux qui se décomposent naturellement en composants ou régions qui n'interagissent pas, sauf dans le sens où chaque joueur doit à son tour choisir un seul composant dans lequel jouer. Des exemples de tels jeux sont Go , Nim , Sprouts , Domineering , le jeu des Amazones et les jeux de coloriage de cartes .

Dans de tels jeux, chaque composante peut être analysée séparément pour des simplifications qui n'affectent pas son résultat ou le résultat de sa somme disjonctive avec d'autres jeux. Une fois cette analyse effectuée, les composantes peuvent être combinées en prenant la somme disjonctive de deux jeux à la fois, en les combinant en un seul jeu avec le même résultat que le jeu d'origine.

L'opération somme a été formalisée par Conway (1976). C'est une opération commutative et associative : si deux jeux sont combinés, le résultat est le même quel que soit l'ordre dans lequel ils sont combinés, et si plus de deux jeux sont combinés, le résultat est le même quel que soit la manière dont ils sont groupés.

La négation − G d'un jeu G (le jeu formé par l'échange des rôles des deux joueurs) forme un inverse additif sous des sommes disjonctives : le jeu G + − G est un jeu nul (gagné par celui qui joue en second) utilisant une stratégie d'écho simple dans laquelle le deuxième joueur copie à plusieurs reprises le coup du premier joueur dans l'autre jeu. Pour deux jeux G et H quelconques , le jeu H + G + − G a le même résultat que H lui-même (bien qu'il puisse avoir un plus grand nombre de coups disponibles).

Sur la base de ces propriétés, la classe des jeux combinatoires peut être considérée comme ayant la structure d'un groupe abélien , bien qu'avec une classe propre d'éléments plutôt que (comme c'est plus courant pour les groupes) un ensemble d'éléments. Pour une sous-classe importante des jeux appelée les nombres surréels , il existe un opérateur de multiplication qui étend ce groupe à un corps .

Pour les jeux de misère impartiaux, une théorie analogue des sommes peut être développée, mais avec moins de ces propriétés : ces jeux forment un monoïde commutatif avec un seul élément inversible non trivial, appelé étoile ( * ), d'ordre deux.

• Conway, John Horton (1976), Sur les nombres et les jeux , Academic Press.