From f5458a6634c5ceb75a4b780b6f061948fdaaca14 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Sun, 14 Feb 2016 22:52:05 +0100 Subject: Gale-Stewart games. --- notes-mitro206.tex | 16 +++++++++++++++- 1 file changed, 15 insertions(+), 1 deletion(-) diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 1752080..17c4908 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -489,7 +489,9 @@ déclarée nulle (ceci ne peut pas se produire lorsque le graphe $G$ est « bien-fondé »). On verra qu'il s'agit là du cadre général dans lequel on étudie la théorie combinatoire des jeux impartiaux à information parfaite -(cf. \ref{definition-impartial-combinatorial-game}). +(cf. \ref{definition-impartial-combinatorial-game}), et qu'un des +joueurs a forcément une stratégie gagnante ou bien les deux joueurs +une stratégie assurant le nul (si le nul est possible). Dans une variante du jeu, celui qui ne peut plus jouer gagne au lieu de perdre : on parle alors de la variante « misère » du jeu. @@ -546,6 +548,18 @@ peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en a une. +\thingy Les \textbf{jeux de Gale-Stewart} : soit $A$ une partie de +$\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$. +Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans +le premier cas) ou de $\{0,1\}$ (dans les deux suivants). Ils jouent +un nombre infini de tours, « à la fin » desquels la suite de leurs +coups définit un élément de $\mathbb{N}^{\mathbb{N}}$ ou de +$\{0,1\}^{\mathbb{N}}$ ou, en les considérant comme la suite des +chiffres binaires d'un réel commençant par $0.$, de $[0,1]$ : si cet +élément appartient à $A$, Alice gagne, sinon c'est Bob (la partie +n'est jamais nulle). \emph{Il n'est pas vrai} qu'un des deux joueurs +possède forcément une stratégie gagnante. + \subsection{Remarques} -- cgit v1.2.3