From 811f834984b4f04b71dfe53453a08ec30f6fba52 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 11 Apr 2016 20:04:48 +0200 Subject: Connection between the "sign" of a partizan game and the "signs" of its options. --- notes-mitro206.tex | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 50 insertions(+), 2 deletions(-) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index e9fd843..b3df179 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -5470,7 +5470,6 @@ définition, et de même « Blaise a une stratégie gagnante dans [le jeu joueur a une stratégie gagnante dans [le jeu impartial] $\tilde G_{\mathrm{R}}$ » et de même en échangeant simultanément Blaise et Roxane et $L$ et $R$. Bref, on a les équivalences suivantes : - \begin{center} \begin{tabular}{ccccc} $G\doteq 0$&ssi&$\tilde G_{\mathrm{L}}\doteq 0$&et&$\tilde G_{\mathrm{R}}\doteq 0$\\ @@ -5481,7 +5480,6 @@ $G\geq 0$&ssi&&&$\tilde G_{\mathrm{R}}\doteq 0$\\ $G\leq 0$&ssi&$\tilde G_{\mathrm{L}}\doteq 0$&&\\ \end{tabular} \end{center} - où lorsque $H$ est un jeu combinatoire impartial on a écrit $H\doteq 0$ pour dire que sa position initiale est une P-position (si on préfère, $\gr(H) = 0$) et $H\fuzzy 0$ pour dire qu'elle est une @@ -5533,6 +5531,56 @@ On voit bien qu'il s'agit de jeux très différents, et la première construction (la somme disjonctive de jeux partisans) est plus naturelle si on doit étudier quel joueur a une avance sur lequel. +\thingy Même si la construction $\tilde G$ n'est pas compatible avec +la somme comme on vient de l'expliquer, on peut se rappeler que, pour +toute position $x$ d'un jeu impartial $H$, on a $x \doteq 0$ si et +seulement si $y \fuzzy 0$ pour tout voisin sortant $y$ de $x$, et +inversement $x \fuzzy 0$ si et seulement si $y \doteq 0$ pour un +voisin sortant $y$ de $x$ (c'est une reformulation +de \ref{definition-grundy-kernel}). On en déduit : + +\begin{prop} +Soit $G$ un jeu combinatoire partisan bien-fondé. Alors pour toute +option $x$ de $G$ (identifiée au jeu ayant $x$ pour position +initiale) : +\begin{itemize} +%% \item On a $x \doteq 0$ si et seulement si : $\ell \vartriangleleft 0$ +%% pour tout voisin sortant \emph{bleu} $\ell$ de $x$, et $r +%% \vartriangleright 0$ pour tout voisin sortant \emph{rouge} +%% $r$ de $x$. +%% \item On a $x > 0$ si et seulement si : $\ell \geq 0$ pour au moins un +%% voisin sortant \emph{bleu} $\ell$ de $x$, et $r \vartriangleright 0$ +%% pour tout voisin sortant \emph{rouge} $r$ de $x$. +%% \item On a $x < 0$ si et seulement si : $\ell \vartriangleleft 0$ pour +%% tout voisin sortant \emph{bleu} $\ell$ de $x$, et $r \leq 0$ pour au +%% moins un voisin sortant \emph{rouge} $r$ de $x$. +%% \item On a $x \fuzzy 0$ si et seulement si : $\ell \geq 0$ pour au moins un +%% voisin sortant \emph{bleu} $\ell$ de $x$, et $r \leq 0$ pour au +%% moins un voisin sortant \emph{rouge} $r$ de $x$. +\item On a $x \geq 0$ si et seulement si : $r \vartriangleright 0$ + pour tout voisin sortant \emph{rouge} $r$ de $x$. +\item On a $x \leq 0$ si et seulement si : $\ell \vartriangleleft 0$ + pour tout voisin sortant \emph{bleu} $\ell$ de $x$. +\item On a $x \vartriangleright 0$ si et seulement si : $\ell \geq 0$ + pour au moins un voisin sortant \emph{bleu} $\ell$ de $x$. +\item On a $x \vartriangleleft 0$ si et seulement si : $r \leq 0$ pour + au moins un voisin sortant \emph{rouge} $r$ de $x$. +\end{itemize} +Autrement dit : une position positive est une position depuis laquelle +Roxane ne peut jouer que vers des positions non négatives +(=strictement positives ou floues) ; et une position négative est une +position depuis laquelle Blaise ne peut jouer que vers des positions +non positives (=strictement négatives ou floues). +\end{prop} +\begin{proof} +On a par exemple $x \geq 0$ ssi et seulement si $\tilde x_{\mathrm{R}} +\doteq 0$, soit si et seulement si tout $\tilde y_{\mathrm{L}} = +(y,\mathrm{L})$ voisin sortant de $\tilde x_{\mathrm{R}} = +(x,\mathrm{R})$ vérifie $\tilde y_{\mathrm{L}} \fuzzy 0$, c'est-à-dire +$y \vartriangleright 0$ pour tout $y$ voisin sortant rouge de $x$. +Les autres cas sont analogues. +\end{proof} + -- cgit v1.2.3