diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 33 |
1 files changed, 32 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index c07b1a4..ec5c1e1 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -3733,7 +3733,7 @@ ordinal $\alpha$ : (cf. \ref{introduction-nim-game}) avec une seule ligne d'allumettes ayant initialement $\alpha$ allumettes. Ce jeu s'appelle parfois le \index{nimbre}« nimbre » associé à l'ordinal $\alpha$. -\item Deux jeux \emph{partiaux} (=partisans), où un joueur n'a aucun +\item Deux jeux \emph{partisans} (=partiaux), où un joueur n'a aucun coup possible (il a donc immédiatement perdu si c'est à son tour de jouer, ce qui rend le jeu, pris isolément, encore plus inintéressant que le précédent) : un jeu « bleu » ou « positif », dans lequel seul @@ -5167,6 +5167,37 @@ du jeu $G \oplus *1$. % % +\section{Notions sur les combinatoires partisans à information parfaite}\label{section-combinatorial-partizan-games} + +\subsection{Différences avec les jeux impartiaux} + +\begin{defn}\label{definition-partizan-combinatorial-game} +Soit $G$ un graphe orienté dont l'ensemble $E$ des arêtes est réunion +de deux sous-ensembles $L$ (les arêtes \emph{bleues}) et $R$ (les +arêtes \emph{rouges}) et soit $x_0$ un sommet de $G$. Le +\index{partisan (jeu)}\index{information parfaite (jeu + à)}\defin[combinatoire (jeu)]{jeu combinatoire partisan à + information parfaite} associé à ces données est défini de la manière +suivante : partant de $x = x_0$, Blaise (=joueur Bleu, =joueur gauche, +=Left) et Roxane (=joueur Rouge, =joueur droite, =Right) choisissent +tour à tour un voisin sortant de $x$ avec la contrainte supplémentaire +que chacun doit suivre une arête de sa couleur, autrement dit, Blaise +choisit une arête bleue $(x_0,x_1) \in L$ de $G$, puis Roxane choisit +une arête rouge $(x_1,x_2) \in R$ de $G$, puis Blaise choisit une +arête $(x_2,x_3) \in L$, et ainsi de suite. Si un joueur ne peut plus +jouer, il a perdu ; si la confrontation dure un temps infini, elle est +considérée comme nulle (ni gagnée ni perdue par les joueurs). On peut +considérer le jeu où Blaise commence (qu'on vient de décrire) ou celui +où Roxane commence (exactement analogue : Roxane choisit $(x_0,x_1) +\in R$ puis Blaise choisit $(x_1,x_2) \in L$, etc.). +\end{defn} + + + +% +% +% + \printindex |