222
Théorie combinatoire des jeux
FIGURE 14.2 - Fin de partie à Domineering.
+
+
EE
FIGURE 14.3 - Décomposition en sous jeux de la fin de partie.
14.2 Les nombres surréels
Les nombres surréels les plus simples comptent pour une région le nombre de coups
qu'un joueur peut jouer dans cette région. Le nombre le plus simple est O. Pour représenter
les nombres plus élaborés, on représente un doublet composé d'une partie gauche qui
correspond à la position atteinte après le meilleur coup du joueur Gauche (dans notre cas
on choisira Vertical), et d'une partie droite qui correspond à la position atteinte après le
meilleur coup du joueur Droit (dans les exemples qui suivent Horizontal). Par exemple le
nombre 1 se représente avec {OI} : si Ve rtical joue il n'a plus de coup, et Horizontal n'a
pas de coup. Le nombre 0 se représente {}. Le nombre 2 se représente {11} = { { OI} 1} =
{ { {} 1 } 1 }. De même il existe des nombres négatifs pour les points de Ve rtical. On a ainsi
-1 = {IO}et - 2 = {1 - 1}.
On peut aussi avoir des jeux qui correspondent à des fractions ainsi { Ol 1} = �. On a
b '
A
1
1
1
ien sur 2 + 2 = .
II existe aussi des infinitésimaux comme {OIO} = * qui est plus petit que tout les
nombres positifs et plus grand que tous les nombres négatifs. D'autres infinitésimaux
courants sont {OI*} =t et son opposé {*IO} =.!. .
Des exemples de régions associées à leurs nombres sont données dans la figure 14.4.
Pour aller plus loin dans la théorie combinatoire des jeux, la lecture de "Lessons in