Arbre de positions

Martial · January 2021

Salut à tous,

En toute logique, après le chap 24 je vais maintenant m'attaquer au chap 23.
Pour l'instant je suis seulement en train de poser les jalons... Et déjà je suis confronté à un dilemme, au sujet des jeux infinis à information parfaite.

Pour simplifier, les "moves" sont dans $\omega$.

Dans la version classique, on se fixe une règle du jeu $A \subseteq \omega^{\omega}$. I joue $u_0 \in \omega$, II joue $u_1$ etc, et I gagne si la suite $(u_0,u_1,...)$ est dans $A$.

Mais certains auteurs (par exemple Louveau pour ne pas le citer) imposent des conditions plus drastiques. On se fixe un arbre $T \subseteq X^{< \omega}$, élagué non vide. Je ne me souviens plus de ce que ça veut dire, mais je peux le retrouver. On se fixe aussi une partie $A \subseteq [T]$, où $[T]$ désigne l'ensemble des branches infinies de $T$.
I joue $u_0$, avec $(u_0) \in T$.
II répond $u_1$ avec $(u_0,u_1) \in T$.
I joue $u_2$ avec $(u_0,u_1,u_2) \in T$ etc.
Et I gagne si $(u_0,u_1,...) \in A$.
Ce que je voudrais savoir c'est quel est l'avantage de la version "arboricole" par rapport à la version classique.
Si quelqu'un a des infos là-dessus...

Merci d'avance

Martial

Maxtimax · January 2021

Avant d'avoir tout lu j'allais te corriger, et je pense que ma correction (erronée :-D) montre l'intérêt de la version arboricole :

pour moi, $A$ ne s'appelle pas "règle du jeu", mais "ensemble de gain" (ou toute traduction de "payoff set") - c'est là où si on tombe, on gagne (enfin, Alice gagne)

C'est $T$, la règle du jeu ! $T$ restreint les mouvements de Alice et Bob : on ne peut jouer qu'en restant dans $T$. Par exemple, si tu veux encoder les échecs dans ce formalisme, et que $X$ est l'ensemble des positions du plateau avec des pièces dessus, tu ne peux pas aller partout ! L'ensemble des positions dans lesquelles tu peux aller (en tant qu'Alice ou Bob) dépend des positions précédentes, et ça c'est parfaitement encodé dans ton arbre $T$ (+ hypothèses d'élagage etc.)

A la fin, Alice gagne toujours is $u\in A$, pas $T$ (ni $[T]$ : $[T]$ est l'ensemble des parties qui auraient pu être jouées un jour, $A\subset [T]$ est l'ensemble des parties gagnantes)

Je me souviens que j'avais fait mon (un de mes) TIPE sur la détermination de Borel, et j'avais à un moment introduit les règles additionnelles (c'est ça que je voulais te corriger, j'allais écrire "si $A$ c'est les règles, alors $A\subset \omega^{<\omega}$ plutôt, non? ") alors que je rechignais un peu (je voulais gagner de la place) donc je crois que c'était important à un moment, je ne sais plus trop pourquoi cependant

Martial · January 2021

@Max : merci pour la coquille, je viens de rectifier le $A$ à la place du $T$. J'avais compris, c'était vraiment une coquille !

L'expression "règle du jeu" est de moi, je ne savais pas comment traduire "payoff set".

J'ai très bien compris ton point de vue, la comparaison de $T$ avec les règles du jeu d'échecs est géniale... mais dans le jeu d'échecs l'ensemble des coups que tu peux jouer à l'instant $t$ ne dépend que de la position actuelle, non ? (Ou alors tu fais appel aux règles qui obligent la partie à être nulle, genre pas d'avance de pions ni de prise de pièce pendant 50 coups = partie nulle).

Bon, bref, ça c'est un détail. L'essentiel c'est que j'aie compris que $T$ est l'analogue des règles du jeu d'échecs.

Mais il y a encore un truc qui me chiffonne : pourquoi certains auteurs (comme Dehormoy par exemple) font totalement abstraction de l'arbre $T$ ? A vrai dire ils prennent pour $T$ l'arbre total $\omega^{< \omega}$, et font tout le taf avec ça. J'aimerais bien avoir la réponse à cette question.

@Tous : pour la culture gé, en 1905 Zermelo démontre le théorème suivant : au jeu d'échecs, l'un des 3 théorèmes suivants est vrai :
Th1 : les blancs ont une stratégie gagnante.
Th2 : les noirs ont une stratégie gagnante.
Th3 : chacun des joueurs dispose d'une stratégie lui permettant au pire de faire nul.
Evidemment l'argument massif est la finitude du nombre de coups d'une partie d'échecs.
Mais ce qui est marrant c'est que la preuve de Gale-Stewart ressemble étrangement à celle de Zermelo... la finitude étant remplacée par la "fermitude".

En tous cas merci, Max.

Maxtimax · January 2021

Martial : oui pour les échecs tu as un arbre qui vérifie une propriété en plus de "localité" si tu veux (modulo la règle des 50 coups et aussi le roque) mais en principe il n'y a pas de raison de l'imposer, si tu préfères tu peux penser à un jeu où tu n'as le droit de faire certaines actions qu'un nombre fixé de fois ou je-ne-sais-quoi. Mais bon, tu as compris, c'est l'essentiel ;-)

Pour ta remarque sur Zermelo, c'est pas étonnant, c'est un corollaire de Gale-Stewart !!

Martial · January 2021

@Max : oui d'accord, c'est un corollaire de Gale-Stewart, mais quand même, historiquement, le théorème est de 48 ans plus jeune que le corollaire, lol.

Au risque d'abuser, peux-tu m'aider dans cette question :

"Mais il y a encore un truc qui me chiffonne : pourquoi certains auteurs (comme Dehormoy par exemple) font totalement abstraction de l'arbre $T$ ? A vrai dire ils prennent pour $T$ l'arbre total $\omega^{< \omega}$, et font tout le taf avec ça. J'aimerais bien avoir la réponse à cette question"

Merci d'avance.

Poirot · January 2021

@Martial : qui est $X$ dans ton premier message ? C'est $\omega^{\omega}$ j'imagine. Quant à ta traduction de payoff elle est vraiment mauvaise, celle suggérée par Max est bien meilleure (payoff voulant dire gain, récompense, etc.).

Maxtimax · January 2021

Pour ta question, je ne sais pas trop, je n'ai pas lu assez de choses à ce sujet. Notamment je ne suis plus certain de si la version avec arbre de AD est équivalente à la version sans arbre (j'avais, à l'époque, pris le parti de mettre les arbres parce que je les utilisais dans certaines preuves je crois)
(Peut-être modulo DC ou ACDén...)

Mais donc je ne sais malheureusement pas te répondre.

Martial · January 2021

@Poirot : oui, sorry, en fait $X= \omega$, donc $X^{<\omega} = \omega ^{<\omega}$, c'est toujours comme ça quand on essaye d'adapter les notations.

@Max : je crois que la version arboricole sert à contourner les problèmes quand on ne suppose plus AC (typiquement, sous AD).
A mon avis, tant que tu es sous AC il n'y a pas de problème, tu n'as pas besoin de l'arbre pour la détermination borélienne, ou analytique, ou pi-1-32, ou projective. C'est seulement quand tu es obligé de zapper AC (par exemple en faveur de AD) que tu en as besoin.
Mais je peux me tromper...

Merci à tous deux, bonne nuit, et bonne année...

Maxtimax · January 2021

Oui oui je sais que pour la détermination borélienne on peut mettre des arbres (analytique je n'avais pas osé lire la preuve :-D), je me demandais (j'ai oublié) si demander que tout jeu arboricole soit déterminé (ADarbre) était strictement plus fort que demander que tout jeu "sans règles" soit déterminé.

Bonne année à toi, et bonne nuit

Martial · January 2021

@Poirot : d'accord avec toi sur le fait que ma traduction est pourrie...

christophe c · January 2021

@Martial les versions arboricoles sont pédagogiques et pour des économies d'écriture. Elles ne servent que pour les PREUVES. De toute façon tu les obtiens en rajoutant dans les parties perdantes les suites où le joueur, pour la première fois, n'a pas respecté l'arbre. Mais ça évite de le dire à chaque fois. De mon téléphone

Martial · January 2021

@Christophe : OK, c'est un bon argument. C'est un peu comme si aux échecs tu étais déclaré perdant dès l'instant que tu joues un mouvement non autorisé par les règles. Je vais essayer de me dépatouiller avec ça.

@Max : "analytique je n'avais pas osé lire la preuve". Bizarrement la preuve de (Existe un mesurable) entraine (Détermination analytique) est conceptuellement plus simple que celle de la détermination borélienne sans hypothèse additionnelle. Il est d'ailleurs intéressant de noter l'ordre dans lequel les choses se sont passées au plan historique.
1954 : Gale-Stewart
(Je te passe les étapes intermédiaires).
1970 : Martin démontre mesurable implique $Det(\mathbf{\Pi_1^1.})$.
1974 : Harvey Friedman prouve que la détermination borélienne ne peut pas être prouvée dans ZC (elle nécessite toutes les instances du schéma de remplacement nécessaires pour construire tous les cardinaux $< \beth_{\aleph_1}$).
1975 : Martin démontre la détermination borélienne.
1980 : Martin prouve que I2 entraîne $Det(\mathbf{\Pi^1_2})$.
1984 : Woodin montre que I0 entraîne la détermination projective et $AD^{\mathbb{L}(\mathbb{R})}$.
1985/1987 : Martin-Steel prouvent la détermination projective sous l'hypothèse : "il existe une infinité de cardinaux Woodin".
1989 : Woodin prouve une pseudo-réciproque : si DP est vrai, alors il existe $\omega$ Woodin dans un modèle intérieur.

christophe c · January 2021

Exactement a écrit:

C'est un peu comme si aux échecs tu étais déclaré perdant dès l'instant que tu joues un mouvement non autorisé par les règles. Je vais essayer de me dépatouiller avec ça.

Je ne sais plus si je te l'ai souhaité. Bonne année Martial !!!