Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
296 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Arbre de positions

Envoyé par Martial 
Arbre de positions
il y a quatre mois
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



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Martial.
Re: Arbre de positions
il y a quatre mois
Avant d'avoir tout lu j'allais te corriger, et je pense que ma correction (erronée grinning smiley) 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

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Arbre de positions
il y a quatre mois
@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.



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Martial.
Re: Arbre de positions
il y a quatre mois
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 winking smiley

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

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Arbre de positions
il y a quatre mois
@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.



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par Martial.
Re: Arbre de positions
il y a quatre mois
@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.).
Re: Arbre de positions
il y a quatre mois
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.

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell



Edité 1 fois. La dernière correction date de il y a quatre mois et a été effectuée par AD.
Re: Arbre de positions
il y a quatre mois
@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...
Re: Arbre de positions
il y a quatre mois
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 grinning smiley), 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

"Mathematics, rightly viewed, possesses not only truth, but supreme beauty"-Russell
Re: Arbre de positions
il y a quatre mois
@Poirot : d'accord avec toi sur le fait que ma traduction est pourrie...
Re: Arbre de positions
il y a quatre mois
@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

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Arbre de positions
il y a quatre mois
@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.
Re: Arbre de positions
il y a quatre mois
Citation
Exactement
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 !!!

Signature: aide les autres comme toi-même car ils SONT toi, ils SONT VRAIMENT toi
Re: Arbre de positions
il y a quatre mois
Bonne année Christophe !!!
Et bonne année à tous !!!
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 149 224, Messages: 1 506 885, Utilisateurs: 27 661.
Notre dernier utilisateur inscrit ibra.


Ce forum
Discussions: 2 516, Messages: 51 071.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page