\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Théorie des jeux combinatoires à information parfaite à deux joueurs

Définition


Un jeu combinatoire à information parfaite à deux joueurs (JCIP2) est un jeu :
  • à stratégie sans aléa,
  • sans information caché,
  • à deux joueurs jouant à tour de rôle.
  1. Le jeu de fléchette n'est pas un JCIP2 car il fait intervenir une partie de hasard.
  2. Le poker entre deux joueurs n'est pas un JCIP2 car les cartes des joueurs sont cachées.
  3. Pierre papier ciseaux lézard Spock entre deux joueurs n'est pas un JCIP2 car les joueurs ne jouent pas à tour de rôle.
  4. Le jeu du puissance 4 est un JCIP2.
  5. Le jeu du morpion est un JCIP2.
  6. Le jeu de dame est un JCIP2.
  7. Le jeu d'échec est un JCIP2.
  8. Le jeu d'othelo (reversi) est un JCIP2.

Définition


A tout JCIP2, on associe un graphe orienté \( J\) défini par : \[\Som(J)=\{\text{États possible du jeu}\}\] \[\Arc(J)=\{\text{Si on peut passé d'un état à un autre en un coup}\}\]
Considérons par exemple un damier de \( 3\times5\) cases et une tour1 placée en haut à gauche. Le but du jeu est de placer la tour en bas à droite. Deux joueurs déplace la pièce, à tour de rôle, en respectant la règle "On ne peut déplacer la pièce que vers le bas ou vers la droite". Il s'agit bien d'un JCIP2, dont les sommets du graphe représentent la position de la tour sur le damier et les arcs les mouvements possible de la pièce. \[ \xymatrix@R=2cm@C=3cm{ 1\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr] \ar[d]\ar@/_1pc/[dd]& 2\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar[d]\ar@/_1pc/[dd]& 3\ar[r]\ar@/^1pc/[rr]\ar[d]\ar@/_1pc/[dd]& 4\ar[r]\ar[d]\ar@/_1pc/[dd]& 5\ar[d]\ar@/_1pc/[dd]\\ 6\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr]\ar[d]& 7\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar[d]& 8\ar[r]\ar@/^1pc/[rr]\ar[d]& 9\ar[r]\ar[d]& 10\ar[d]\\ 11\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr]& 12\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]& 13\ar[r]\ar@/^1pc/[rr]& 14\ar[r]& 15} \] On voit que si un joueur est en \( 9\) alors il va nécessairement perdre. Ainsi pour gagner il suffit de faire en sorte que le joueur adverse se place en \( 9\) . Existe-t-il d'autre position offrant une stratégie gagnante ?

Définition


Le noyau d'un graphe orienté \( \G\) est un sous ensemble de \( \Som(\G)\) tel que :
  1. Les sommets de \( N\) sont deux à deux non adjacents : \[\forall (x,y)\in N^2,\qquad (x,y)\not\in\Arc(\G)\]
  2. Tout sommet qui n'est pas dans \( N\) a un prédécesseur dans \( N\) : \[\forall x\in Som(\G)-N, \ \exists y\in N,\qquad (x,y)\in \Arc(\G)\]
\[\xymatrix{ &a\ar[dl]&b\ar[dd]\ar[lld]&\\ f\ar[rrd]&&&c\ar@/_3.19pc/[llu]\ar@/^3.19pc/[lld]\\ &e\ar@/^7pc/[uu]\ar[lu]\ar[ruu]\ar[r]&d& }\] On peut vérifier que \( \{a,d\}\) est un noyau. \[ \xymatrix{ a\ar[r]&b\ar[d]\\ &c\ar[lu] } \] Ce graphe ne possède pas de noyau. Lorsque le graphe n'as pas de circuit, on peut donner un noyau. C'est l'algorithme de dénoyautage.

Proposition


Tout graphe orienté sans circuit possède un noyau
La preuve de ce résultat résulte de l'algorithme suivant.
§ Algorithme de dénoyautage. \( N = \varnothing\)
Tant que \( \Som(G)\neq\varnothing\)
\( N=N\cup\{\) Puits de \( G\}\)
Supprimer de \( G\) les éléments de \( N\) et leur prédécesseurs.
Fin tant que
Faisons tourner cet algorithme sur notre exemple du jeu de la tour.
\( \bullet\)
Étape initiale. \( N=\varnothing\) . \[ \xymatrix@R=1.79cm@C=3cm{ 1\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr] \ar[d]\ar@/_1pc/[dd]& 2\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar[d]\ar@/_1pc/[dd]& 3\ar[r]\ar@/^1pc/[rr]\ar[d]\ar@/_1pc/[dd]& 4\ar[r]\ar[d]\ar@/_1pc/[dd]& 5\ar[d]\ar@/_1pc/[dd]\\ 6\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr]\ar[d]& 7\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar[d]& 8\ar[r]\ar@/^1pc/[rr]\ar[d]& 9\ar[r]\ar[d]& 10\ar[d]\\ 11\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr]& 12\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]& 13\ar[r]\ar@/^1pc/[rr]& 14\ar[r]& 15} \]

\( \bullet\)
Le graphe précédent admet \( 15\) comme unique puits : \( N=\{15\}\) . On extrait du graphe le puits \( 15\) et ses prédécesseurs \( 5\) , \( 10\) , \( 11\) , \( 12\) , \( 13\) et \( 14\) . \[ \xymatrix@R=1.79cm@C=3cm{ 1\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@{..}@/^3pc/[rrrr] \ar[d]\ar@{..}@/_1pc/[dd]& 2\ar[r]\ar@/^1pc/[rr]\ar@{..}@/^2pc/[rrr]\ar[d]\ar@{..}@/_1pc/[dd]& 3\ar[r]\ar@{..}@/^1pc/[rr]\ar[d]\ar@{..}@/_1pc/[dd]& 4\ar@{..}[r]\ar[d]\ar@{..}@/_1pc/[dd]& 5\ar@{..}[d]\ar@{..}@/_1pc/[dd]\\ 6\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@{..}@/^3pc/[rrrr]\ar@{..}[d]& 7\ar[r]\ar@/^1pc/[rr]\ar@{..}@/^2pc/[rrr]\ar@{..}[d]& 8\ar[r]\ar@{..}@/^1pc/[rr]\ar@{..}[d]& 9\ar@{..}[r]\ar@{..}[d]& 10\ar@{..}[d]\\ 11\ar@{..}[r]\ar@{..}@/^1pc/[rr]\ar@{..}@/^2pc/[rrr]\ar@{..}@/^3pc/[rrrr]& 12\ar@{..}[r]\ar@{..}@/^1pc/[rr]\ar@{..}@/^2pc/[rrr]& 13\ar@{..}[r]\ar@{..}@/^1pc/[rr]& 14\ar@{..}[r]& 15} \]

\( \bullet\)
Le graphe précédent admet \( 9\) comme unique puits : \( N=\{9,15\}\) . On extrait du graphe le puits \( 9\) et ses prédécesseurs \( 4\) , \( 6\) , \( 7\) et \( 8\) . \[ \xymatrix@R=1.79cm@C=3cm{ 1\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/@{..}[rrr]\ar@/^3pc/@{..}[rrrr] \ar@{..}[d]\ar@/_1pc/@{..}[dd]& 2\ar[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@{..}[d]\ar@/_1pc/@{..}[dd]& 3\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@{..}[d]\ar@/_1pc/@{..}[dd]& 4\ar@{..}[r]\ar@{..}[d]\ar@/_1pc/@{..}[dd]& 5\ar@{..}[d]\ar@/_1pc/@{..}[dd]\\ 6\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@/^3pc/@{..}[rrrr]\ar@{..}[d]& 7\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@{..}[d]& 8\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@{..}[d]& 9\ar@{..}[r]\ar@{..}[d]& 10\ar@{..}[d]\\ 11\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@/^3pc/@{..}[rrrr]& 12\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]& 13\ar@{..}[r]\ar@/^1pc/@{..}[rr]& 14\ar@{..}[r]& 15} \]

\( \bullet\)
Le graphe précédent admet \( 3\) comme unique puits : \( N=\{3,9,15\}\) . On extrait du graphe le puits \( 3\) et ses prédécesseurs \( 1\) et \( 2\) . \[ \xymatrix@R=1.79cm@C=3cm{ 1\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@/^3pc/@{..}[rrrr] \ar@{..}[d]\ar@/_1pc/@{..}[dd]& 2\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@{..}[d]\ar@/_1pc/@{..}[dd]& 3\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@{..}[d]\ar@/_1pc/@{..}[dd]& 4\ar@{..}[r]\ar@{..}[d]\ar@/_1pc/@{..}[dd]& 5\ar@{..}[d]\ar@/_1pc/@{..}[dd]\\ 6\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@/^3pc/@{..}[rrrr]\ar@{..}[d]& 7\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@{..}[d]& 8\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@{..}[d]& 9\ar@{..}[r]\ar@{..}[d]& 10\ar@{..}[d]\\ 11\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]\ar@/^3pc/@{..}[rrrr]& 12\ar@{..}[r]\ar@/^1pc/@{..}[rr]\ar@/^2pc/@{..}[rrr]& 13\ar@{..}[r]\ar@/^1pc/@{..}[rr]& 14\ar@{..}[r]& 15} \]

\( \bullet\)
Le graphe est vide. Un noyau est donc \( N=\{3,9,15\}\)
L'existence du noyau garantie une stratégie non-perdante.

Proposition


Soit \( N\) un noyau d'un graphe d'un JCIP2. Un joueur dont la position au début de son tour n'est pas dans \( N\) a une stratégie non-perdante.

Démonstration

Le joueur joue et se place sur un sommet élément de \( N\) , ce qui est possible d'après la définition de noyau. Si ce sommet est un puits, le joueur à gagné. Sinon, toujours d'après la définition de noyau, l'adversaire ne pourra se placer que sur un sommet qui n'est pas dans \( N\) et le joueur recommence sa stratégie.
Reprenons le jeu de la tour. Le premier joueur (celui qui va gagner) se place en \( 3\) . L'autre joueur ne peut se placer qu'en \( 4\) , \( 5\) , \( 8\) ou \( 13\) . S'il c'est placé en \( 5\) ou en \( 13\) le premier joueur place la tour en \( 15\) et gagne. S'il c'est placé en \( 4\) ou \( 8\) , le premier joueur se place en \( 9\) . Le second joueur ne peut alors que se placer en \( 10\) ou \( 14\) ce qui fait gagner le premier joueur !



1la pièce aux échecs