Remarques sur les liens entre AJM et HO --------------------------------------- Hugo Herbelin Résumé ------ On définit parallèlement des parties "brutes" de style HO et style AJM en faisant apparaître qu'une partie style AJM n'est rien d'autre qu'une partie style HO avec en plus un entier associé à chaque coup (on y gagnera la possibilité d'être history-free pour les stratégies). 1- Étude de la libéralité de jeu ----------------------------- [Cette section est une contribution commune de Vincent Danos et Hugo Herbelin] On définit des conditions d'alternance, de projection, de visibilité et d'innocence applicables indifféremment aux deux styles de parties. Les "vraies" HO-parties sont les HO-parties ci-dessous définies + la condition de visibilité. Les "vraies" AJM-parties sont les AJM-parties ci-dessous définies + la condition de projection. On montre que "Innocence => Visibilité => Projection => Alternance" et que toutes les implications sont strictes. On en déduit en particulier que HO-parties INCLUS AJM-parties INCLUS HO-parties sans condition de visibilité et que les inclusions sont strictes. En particulier, encore, qu'on garde ou qu'on enlève la condition de visibilité, on sera soit trop restrictif, soit trop large pour obtenir les "vraies" AJM-parties. 2- Caractérisation des AJM-stratégies history-free en terme de HO-stratégie innocente et de P-numérisation (la P-numérisation doit vérifier une certaine contrainte de vue). Au passage une définition simple de ce qu'est l'"histoire" d'une AJM-stratégies history-free 3- Exemple de P-numérisation: la GOI et celle codant toute la vue O PRÉ-PARTIES ------------- pré-HO-parties -------------- Def : HO-coup initial = C,* Def : HO-coups = C,r Une pré-HO-partie sur C est une suite d0,d1,...,dn de HO-coups telle que d0=C,* et si dn=C,r alors r N tq l'une s'obtient de l'autre en appliquant la substitution s_n aux indices de tous les coups justifies par n. Dém : (=>) parce que des coups C,r,i et C,r,i' distincts ont des i,i' distincts (<=) trivial Projection ---------- Soit pi une HO- ou AJM'-partie et p l'indice d'un coup de pi. Def : La projection de pi par rapport à p est la pré-partie constituée de tous les coups de pi dont la chaine de pointage passe par p et pour laquelle on renumérote les pointeurs en conséquence (en particulier, le coup p reçoit le pointeur *). Condition de projection ----------------------- Def: Une HO- (resp AJM'-) partie satisfait la condition de projection si toutes ses projections sont des HO- (resp AJM'-) parties (i.e. si elles commencent par un coup avec pointeur * et si elles alternent les P-coups et O-coups) Vue --- La vue d'une AJM'-partie est definie par : Vue(vide) = vide Vue(B0,*) = B0,* Vue(d0,...,(A,p,i)) = Vue(d0,...,d(p-1)),dp,(A,p,i) Vue(d0,...,(B,q,j)) = Vue(d0,...,d(q-1)),dq,(B,q,j) Idem pour HO sans les indices. Correction de vue ----------------- La vue de pi=d0,...,dn est une sous-suite de pi. Elle a la forme V=d(v(0),...,d(v(r)). Si d(p) est dans la vue sous la forme d(v(r)) alors alors, r=v-1(p) est appelé correction de p dans la vue V. La fonction v est appelée fonction de correction de la vue. Condition de visibilité pour un coup ------------------------------------ Si la justification du coup d(p+1) dans une partie d0,d1,...,dn,... est dans la vue de d0,...,dp (i.e. a la forme v(q), v étant la fonction de correction) on dit que le coup d(p+1) satisfait la condition de visibilité. Condition de visibilité pour une partie --------------------------------------- Une partie satisfait la condition de visibilité si tous ses coups satisfont la condition de visibilité. Théorème: Visibilité => Projection => Alternance et toutes les implications sont strictes. Dém: 1) cf HO 2) trivialement par la projection en 0 Contre-exemples: L'AJM-partie O: * P: *0 O: *00 P: *1 O: *01 est alternée mais ne vérifie pas la condition de projection L'AJM-partie O: * P: *0 O: *00 P: *000 O: *01 P: *1 O: *0000 vérifie la condition de projection mais pas la condition de visibilité Idem en traduisant ces exemples en AJM'- ou HO-parties. Condition de visibilité pour un joueur -------------------------------------- Un joueur satisfait la condition de visibilité dans une partie pi si tous les coups qu'il joue dans la partie satisfont la condition de visibilité. On parle alors de P-visibilité ou de O-visibilité. Arches ------ Soit d0,d1,...,dn, une partie de vue V=d(v(0)),...,d(v(r)). Soit v(j) de même parité que v(r). L'arche de V en v(j) est défini comme étant la suite de coups Arche(v(j),V)= d(v(j+1)),...,d(v(r)) Lemme: Soit d0,d1,...,d(n+1) une AJM'-partie avec d(n+1)=A,p,i joué par P et satisfiant la condition de P-visibilité. Soit d(v(0)),...,d(v(r))=Vue(d0,...,d(n)). Puisque d(n+1) satisfait la condition de visibilité, on a p=v(j(k)) pour un certain j(k). Et on a V=d(v(0)),Arche(i(j1),V|(j2-2)),d(v(j2-1)), d(v(j2)),Arche(i(j2),V|(j3-2)),d(v(j3-1)), ... d(v(j(k-1))),Arche(v(j(k-1)),V|(j(k-1))),d(v(j(k)-1)), d(v(j(k))),Arche(v(j(k)),V) avec V|(j(l))=d(v(0)),...,d(j(l)) et quand p' est la justification du coup d(v(j(l+1)-1)) alors, par condition de visibilité, p' a la forme v(j(l)). II Stratégies (cf VD) ------------- P-stratégies --------------- Ensemble de parties ne branchant pas aux coups de P et branchant exhaustivement aux coups de O. AJM'-P-stratégies auto-équivalentes ---------------------------------- Une AJM- ou AJM'-P-stratégie est auto-équivalente si l'ensemble de la canonisation de ses parties forme une P-stratégie. P-relèvement de P-HO-stratégies ------------------------------- Soit sigma une P-HO-stratégie et d_P une P-numérisation définie sur la O-saturation du domaine de sigma. Le P-relèvement de sigma par d_P est l'ensemble des relèvements par d_P des O-saturations des parties de sigma. Prop : Une AJM'-stratégie est auto-équivalente ssi elle est le P-relèvement d'une unique HO-stratégie par une unique P-numérisation (définie sur la O-saturation des parties de la HO-stratégie) Dém : Soit psi une AJM'-stratégie (=>) On prend PI(psi) comme HO-stratégie et si psi(pi)=A,p,i la P-numérisation à considérer sera définie par d_P(pi,(A,p))=i Par exhaustivité du branchement dans psi, l'ensemble des O-numérisations est parcouru + unicité à montrer (<=) car la canonisation d'un relèvement donne l'identité On peut donc identifier les AJM'-stratégies auto-équivalentes avec les couples (HO-stratégie,P-numérisation) Innocence --------- Une HO-stratégie est innocente si ses coups sont déterminés par la vue au moment de jouer (en particulier ses coups vérifient la condition de visibilité) AJM'-innocence -------------- Une AJM'-stratégie est innocente si la HO-stratégie sous-jacente est innocente Coup maximal ------------ Soit D un ensemble de HO-parties et dn=A,p un P-coup d'une partie pi de D. S'il n'existe pas de partie pi' dans D, étendant pi, dont un des coups est justifié par n, alors, le coup A,p est dit maximal. Coup de retour -------------- Soit D un ensemble de HO-parties, dn=A,p un P-coup d'une partie pi de D. Un O-coup d(n')=B',q' de Arche(p,V) est dit coup de retour s'il existe une partie pi' étendant pi dont un des P-coups est justifié par n'. Projection futur-dépendante d'une arche --------------------------------------- Soit D un ensemble de HO-parties, dn=A,p un P-coup d'une partie pi de D. La projection futur-dépendante de Arche(p,V), que l'on note PI_D, est la suite des coups de Arche(p,V) ou l'indice des O-coups est oublié si et seulement si le O-coup n'est pas un coup de retour. P-numérisation arche-codante -------------------------- Soit d_P une P-numérisation de domaine D. Soient pi,pi' AJM'-parties dont le dernier coup est de O. Soient V et V' les vues respectives de pi et pi'. Soit p et p' deux indices dans V et V' tel que p=v(k) et p'=v(k) pour le même k. Les vues s'écrivent respectivement V=V0,arche(p,V) V'=V0',arche(p',V') et on suppose His(V0)=His(V0'). La numérisation d_P est arche-codante si 1) arche(p,V)=arche(p',V') => d_P(pi,(A,p))=d_P(pi',(A,p')) 2) si A,p est maximal pour pi dans D, alors, on a, réciproquement, d_P(pi,(A,p))=d_P(pi,(A',p')) => PI_D(arche(p,V))=PI_D(arche(p,V')) Bref: une P-numérisation est arche-codante si le numéro qu'elle assigne à un P-coup ne dépend que de l'arche courant. Plus précisément: si elle ne dépend que des indices ``utiles pour la suite'' de cette arche courante. P-numérisation arche-codante réversible --------------------------------------- Soit d_P une P-numérisation de domaine D. Soient pi,pi' AJM'-parties dont le dernier coup est de O. Soient V et V' les vues respectives de pi et pi'. Soit p et p' deux indices dans V et V' tel que p=v(k) et p'=v(k) pour le même k. Les vues s'écrivent respectivement V=V0,arche(p,V) V'=V0',arche(p',V') et on suppose V0=V0'. La numérisation d_P est arche-codante réversible si arche(p,V)=arche(p',V') <=> d_P(pi,(A,p))=d_P(pi',(A,p')) AJM'-stratégie uniformément innocente ------------------------------------- Une AJM'-stratégie est uniformément innocente si elle est innocente et si la P-numérisation sous-jacente est arche-codante AJM'-stratégie uniformément innocente réversible ------------------------------------------------ Une AJM'-stratégie est uniformément innocente si elle est innocente et si la P-numérisation sous-jacente est arche-codante réversible AJM'-stratégie history-free -------------------------- Une AJM'-stratégie est history-free (!) si ses coups sont déterminés par l'histoire au moment de jouer Mais l'honneur est sauf : Lemme : une AJM'-stratégie est history-free si la AJM-stratégie correspondante ne fait dépendre ses coups que du dernier coup de l'opposant AJM'-stratégie history-free réversible -------------------------------------- Une AJM'-stratégie est history-free réversible si elle est history-free et si la fonction qui associe les coups à jouer en fonction de l'histoire est injective. Lemme clé : si pi, AJM'-partie, satisfait la condition de visibilité pour le joueur à jouer, alors His(Vue(pi))=His(pi) Dém : Soit pi=d0,...,dn. On pose dn=C,r,k et dr=D,s,l. Puisque la condition de visibilité est satisfaite pour le joueur à jouer, on a ds qui appartient à Vue(d0,...,d(r-1)) qui donc s'écrit Vue(d0,...,ds),d(f(0)),...,d(f(m)),d(r-1). On raisonne alors par induction sur la longueur de His(pi) His(Vue(pi))=His(Vue(d0,...,d(r-1)),dr,dn) =His(Vue(d0,...,d(r-1)),dr),k =His(Vue(d0,...,ds)),l,k =His(d0,...,ds,dr),l,k (par induction) =His(pi) Lemme (innocence numérique -- VD) : pi dans sigma h.f. => Vue(pi) dans sigma Lemme : pi partie d'une AJM'-stratégie history-free => P satisfait la condition de visibilité dans pi Théorème (Pointifiction 1 -- VD) : history-free => innocence Dém : Soit sigma=(phi,d_P) une AJM'-stratégie history-free Soit pi et pi' dans sigma et supposons que Vue(PI(pi))=Vue(PI(pi')). Le lemme d'innocence numérique de VD montre que Vue(pi) est dans sigma. Mais la condition de visibilité et le lemme clé donnent His(Vue(pi))=His(pi), d'où on a sigma(pi)=sigma(Vue(pi)). Puis phi(PI(pi))=PI(sigma(pi)) =PI(sigma(Vue(pi))) =phi(PI(Vue(pi)) =phi(PI(Vue(pi')) =phi(PI(pi) et donc, phi est innocente Théorème : (phi,d_P) history-free => d_P arche-codante Dém : A refaire avec la nouvelle définition. Soit pi et pi' dans sigma=(phi,d_P) et supposons que Vue(pi)=Vue(pi'). Par le lemme clé et la condition de visibilité, on en déduit His(pi)=His(pi') puis que sigma(pi)=sigma(pi')=A,p,i et donc d_P(pi,(A,p))=d_P(pi',(A,p)), par définition de d_P (puisqu'aussi, le seul (A,p) pour lesquel d_P est défini, c'est (A,p)=PI(sigma(pi))) Théorème : history-free <=> innocence uniforme Dém: (=>) Par les deux précédents théorèmes (<=) Soit pi et pi' avec O à jouer dans sigma=(phi,d_P) AJM'-stratégie Supposons His(pi)=His(pi') Par induction sur la longueur de His(pi) on en déduit par l'arche-codage que les PI_D des arches successives sont identiques et en particulier que les PI des arches successives sont identiques. D'où PI(Vue(pi))=PI(Vue(pi')). D'où, par innocence, phi(pi)=phi(pi'). Ensuite, par codage de l'arche ......... ?? d_P(pi,phi(pi))=d_P(pi',phi(pi')) d'où, enfin, sigma(pi)=sigma(pi') Note: ci-dessus, pi et pi' sont toujours avec O qui doit jouer Théorème : history-free réversible <=> innocence uniforme réversible Dém : il reste à montrer (phi,d_P) history-free réversible entraine d_P arche-codante réversible et innocence uniforme réversible entraine history-free réversible. Equivalence faible entre AJM'-stratégies --------------------------------------- sigma et sigma' AJM'-stratégies sont faiblement équivalentes si PI(sigma)=PI(sigma') Lemme: sigma et sigma' sont faiblement équivalentes ssi une bijection f de sigma dans sigma' telle pour tout pi dans sigma, pi est equivalent à f(pi) Equivalence forte entre AJM'-stratégies -------------------------------------- sigma et sigma' AJM'-stratégies sont fortement équivalentes s'il existe phi HO-strategie et d_P et d'_P telles que sigma=d_P(phi) et sigma'=d'_P(phi) Lemme: sigma et sigma' sont fortement équivalentes ssi une famille une bijection f de sigma dans sigma' telle pour tout pi dans sigma, pi est equivalent à f(pi) Théorème : - arbres de Bohm <--> HO-P-stratégies innocentes <--> AJM'-P-stratégies innocentes à P-numérisation près <--> AJM'-P-stratégies uniformément innocentes à P-numérisation arche-codante près <--> AJM'-P-stratégies history-free à P-numérisation arche-codante près <--> AJM-P-stratégies history-free <--> AJM'-P-stratégies history-free réversible à P-numérisation arche-codante près Rem: Reste à bien caractériser les classes d'équivalence de AJM'-P-stratégies uniformément innocentes et de AJM'-P-stratégies innocentes. Qu'est-ce qu'une classe d'équivalence de P-numérisation ? III Exemples de P-numérisations ------------------------------- P-numérisation chronologique ---------------------------- On prend pour d_P(pi,(A,p)) le plus petit entier non déjà pris pour un autre coup (A,p) de pi Prop: La P-numérisation chronologique n'est pas arche-codante Contre-exemple:... La P-numérisation HH -------------------- (ne s'applique qu'aux parties satisfaisant la condition de visibilité pour P) Elle est definie par d_P(d0',...,dn',(A,v(p')))= [D(p'+1)',...,D(r)'] avec [ ... ] qui est un codage des listes vers N et où la vue de d0',...,dn' est D(0)',...,D(r)' Un décodage de la P-numérisation HH ----------------------------------- Soit pi=d0,d1,...,dn une partie. Le décodage de pi est défini par: Décodage(d0)=d0 Décodage(d0,...,dp,...,dq,...,dn)=Décodage(d0,...,dq)(A,p',i)D1,...,Dr(B,q',j) lorsque dq=(A,p,i) et dn=(B,q,j) et que i est le décodage de [D1,...,Dr] et p',q' sont v-1(p) et v-1(q) dans la suite de coup résultante. Prop: Si pi est obtenu d'une HO-partie satisfaisant la condition de visibilité pour P par la P-numérisation HH et par une O-numérisation quelconque, alors Décodage(pi)=Vue(pi) quand c'est le tour de P Dém: par induction sur la longueur de pi si |pi|=1 OK si |pi|>1 et dn=(B,q,j) et dq=(A,p,i) Par condition de visibilité pour P, dp est dans la vue de d0,...,d(q-1). Donc, Vue(pi) a la forme d0,...,dp,D1,...,Dr,dq,dn pour certains D1,...,Dr Or par hypothese d'induction, Décodage(d0,...,dp)=Vue(d0,...,dp) et l'indice i est précisément le codage des éléments de Vue(d0,...,d(q-1)) qui sont au-delà de dp. Schématiquement: /------------------------------------\ (pointage de P) d0,...,dp,...,D1-1,D1,...,D2-1,D2,...,d(q-1),dq,...,dn \-----/ \_____/ \_____/ \_____/ (pointage de O) La P-numérisation GOI --------------------- (ne s'applique aussi qu'aux parties satisfaisant la condition de visibilité pour P) C'est la même que la P-numérisation HH mais avec plus d'information oubliée. Fait: Un atome A de T est defini par une occurrence n1,n2,...,np de T. Pour la P-numérisation GOI, on ne garde de la vue que les O-coups, et encore, on ne garde des occurrences d'atomes que le dernier np (celui qui est significatif). Autrement dit: d_P(d0',...,dn',(A,v(2*p')))= ...>)> où la vue de d0',...,dn' est D(0)',...,D(2*r)' et où plus particulièrement, les D(2*(p'+1))',...,D(2*r)' ont la forme (B(s),q(s),j(s)) pour p' <= s <= r et où chaque B(s) se termine par n(s) et où < , > et CONT( , ) sont des codages de N * N -> N Rem: l'information oubliee peut-être retrouvée de manière externe car chaque segment initial d'info des O-coups suffit pour retrouver les P-coups supprimés. Prop: Les P-numérisations HH et GOI sont arche-codantes Dém: Direct Rem: Les P-numérisations GOI et HH sont définies MEME pour les parties non jouées par un terme (à condition que la visibilité soit respectée).