STRUCTURES DES DONNEES ---------------------- Un GRAPHE est représenté par soit une liste d'adjacence soit une matrice d'adjacence. Une matrice d'adjacence est un tableau à 2 dimension contenant des booléens tandis qu'une liste d'adjacence est un tableau de hash dont chacun contenant comme clés les sommets atteints. Un CHOCOBAR est représenté par plusieurs façons différentes afin de pouvoir comparer les méthodes plus efficaces d'une implémentation aux autres. a/ Par une liste des "points de ruptures". b/ Par un tableau d'entiers de 8 bits. c/ Par un entier de 64-bit. Une STRATEGIE est un tableau d'entiers, un entier x indexé à la position i du tableau signifie que si le joueur concerné se trouve à la configuration i alors il doit choisir la configuration x comme son coup. Une STRATEGIE GAGNANTE est une stratégie d'un joueur qui effectue le PREMIER coup et celle-ci garantit que quel que soit les états choisis par l'adversaire alors l'adversaire perdra. REMARQUE SUR LES DIFFERENTES IMPLEMENTATIONS DE CHOCHOBAR --------------------------------------------------------- Il est évident que ces trois différentes implémentations ne distinguent que la manière de générer le graphe de jeu : vitesse de construction du graphe et espace occupé pour cette génération. a/ Un POINT DE RUPTURE est une paire d'entiers représentant un point à partir du duquel tous les carrés à droite et en bas de ceci sont déjà mangés. Un état de jeu peut en effet contenir plusieurs point de ruptures. L'espace occupé par un état de jeu est alors au pire = taille 2 entiers X nombre de colonnes de la barre de chocolat car une barre de chocolat ne peut pas avoir plus que (nombre de colonnes) point de ruptures. Cette implémentation est réalisée par Glenn ROLLAND. b/ Un TABLEAU DE CHAR. Un état de jeu est alors représenté par une liste d'entiers marquant les carrés mangés de chaque colonne de la barre de chocolat. Afin d'avoir un entier de 8 bits on utiliser le type char de Java. Ceci dit, l'espace occupé par un état de jeu = nombre de colonnes de la barre de chocolat X taille d'un entier. Cette approche est réalisée par INDRAWATI. c/ Un ENTIER DE 64-BIT. De même principe qu'en (b) on stocke toujours le nombre de carrés mangés de chaque colonne mais au lieu d'utiliser un tableau alors on utilise un entier de 64 bits pour "cartographier" ces colonnes. Cette approche est réalisée par INDRAWATI. Dans ce cas, un état de jeu prend un espace de taille un entier de 64 bits. Cette dernière implémentation a rendu possible la génération de configuration de jeu de taille assez grande puisque l'on a aucun espace perdu pour créer les états : pour une barre de taille (mxn) alors un "cartographie" un état par un tableau de n entiers en base(m+1). Ceci dit, la taille maximale de barre de chocolat que l'on peut calculer est de (mxn) telle que (m+1)^n <= 2^64. On estime que cette taille est suffisante puisque lors des tests on a trouvé que de toute façon sans dépasser cette limitation on n'a pas assez d'espace de mémoire pour stocker notre graphe (avec liste d'adjacence ni matrice d'adjacence), on ne risque donc en aucun cas d'être bloqué à cause de la structure de données de ChocoBar. GENERATION DE GRAPHE -------------------- Afin d'économiser l'espace de mémoire utilisé au cours du déroulement de programme, on supprime la liste des états une fois que le graphe du jeu aura été généré. a/ Avec une liste de POINTS DE RUPTURES L'algorithme a été implémenté par Glenn ROLLAND. Il s'agit d'un algorithme récursif dans lequel on génère en une seule passe les états et le graphe. On commence par une ChocoBar vide, et on "mange" récursivement les points inférieurs droits jusqu'à atteindre le sommet supérieur gauche. On définit dans la suite de cette section le type ChocoBar comme une liste de couples d'entiers. On considèrera de plus que les variables E et V sont globales. D'autre part, dans le pseudo-code suivant, le chocobar et son index seront confondus, mais dans notre implémentation, le temps de calcul de l'index d'un chocobar donné est en O(min(m,n)). La récupération du chocobar correpondant à un index se fait en temps constant. Chaque ajout d'élément à l'ensemble V du graphe nécessite le calcul de l'index du chocobar. De même, chaque vérification d'existance d'un élément dans V nécessite ce calcul. Cette implémentation nécessite de maintenir aussi bien une liste des sommets incidents que des sommets adjactents à un sommet donné pour avoir une complexité en temps petite. Pour commencer, voici quelques fonctions simples dont le détail ne sera pas donné: chocobar.addBreakPoint(m,n) // fonction qui ajoute le breakpoint (m,n) à la liste des points (triés) du // chocobar en un temps O(min(m,n)), soit O(n) chocobar.getBreakLine() // fonction qui renvoie la ligne frontiere entre la partie mangée et la // partie non-mangée de la tablette de chocolat. Les points de la liste // sont des carrés non-mangés et incluent les bordures inférieure et droite // de la tablette lorsque celle-ci est pleine. Elle se calcule // en O(m+n), ce qui est équivalent à O(n) chocobar.equals(c) // fonction qui compare les deux listes de points de chocobar et c // Sa temps de calcul est min(m,n), soit une complexité de O(n) Et ensuite les fonctions permettant la génération du graphe et des états: global (V,E) <- (vide,vide) global etatInitial <- vide global etatFinal <- vide //fonction d'initialisation de la génération du graphe debut genChoco(m: entier, n:entier) etatInitial <- ChocoBar(m, n) V <- etatInitial genChocoFromPoint(etatInitial,m-1,n-1) renvoyer configGraph fin genChoco Comme on le constate, genChoco ne fait que l'initialisation du graphe avec l'état initial et aucun arc, suivi d'un appel à la fonction récursive genChocoFromPoint. La complexité de genChoco est donc égale à celle de O(genChocoFromPoint) plus une constante. //fonction qui construit une configuration de jeu à partir d'un état donné //en mangeant le carré de coordonnées (m, n) debut genChocoFromPoint(oldCBar: ChocoBar, m: entier, n: entier) currentCBar <- oldCBar currentCBar.addBreakPoint(m, n) //on mange le carré (m, n) si currentCBar = Exception "déja mangé" alors sortir fin si si currentCBar = Exception "invalide" alors sortir fin si si V inclus currentCBar alors E <- E U {(oldCBar,currentCBar)} retourner sinon V <- V U {currentCBar} si isFinalConfig(currentCBar) alors etatFinal <- currentCBar fin si constructArcsFromAncestorsTo(oldCBar,currentCBar) ***** expliquer ***** frontline <- chocobar.getBreakLine() pour chaque p=(x,y) dans frontline, faire genChocoFromPoint(currentCBar,x,y) fin pour fin si fin genChocoFromPoint Cette fonction va s'appeller récursivement |V| fois (pour chaque chocobar possible) au total. Chaque appel de la fonction coûte O(addBreakpoint)+ O(V inclus currentCBar) + O(isFinalConfig) + O(constructArcsFromAncestorsTo) + O(breakline). Or isFinalConfig est une fonction qui teste en temps constant si la configuration est la chocobar à 1 élément dans le coin supérieur gauche. // fonction qui dit si sonCB est une configuration accessible à // partir de fatherCB debut isNextOf(fatherCB,sonCB) : booleen pour chaque p=(i,j) appartenant à la liste de breakpoint de sonCB fatherCopy <- fatherCB fatherCopy.addBreakPoint(i,j) si fatherCopy = father alors retourner vrai sinon retourner faux fin si fin isNextOf La vérification de l'accessibilité d'un état à partir d'un autre nécessite |sonCB| ajouts de breakpoints suivi de comparaisons de listes. Or |sonCB| = min(m,n), O(addBreakPoint)=O(n) et O(equals)=O(n). On a donc O(isNextOf) = O(n^3) // fonction qui remplit le graphe à partir d'une configuration vers // tous ses ancetres possibles... debut constructArcsFromAncestorsTo(fatherCB: ChocoBar, sonCB:ChocoBar) si isNextOf(fatherCB,sonCB) alors E <- E U {(fatherCB,sonCB)} pour tout ancetreCB appartenant à incident fatherCB dans V, faire constructArcsFromAncestorsTo(ancetreCB,sonCB) fin pour sinon retourner fin si fin constructArcsFromAncestorsTo La somme du nombre d'ancetreCB trouvés sur tous les appels de constructArcsFromAncestorsTo est |V|, et pour chacun d'eux on appelle isNextOf. La complexité d'un appel (récursif) à cette fonction est donc de |V|*O(isNextOf), soit O( |V| * n^3 ). La complexité totale de la construction du graphe et des états est donc égale à O(genChocoFromPoint) = |V| * ( O(addBreakpoint)+ O(V inclus currentCBar) + O(isFinalConfig) + O(constructArcsFromAncestorsTo) + O(breakline) ) = O( |V| * ( n + |V|*n^3 + n)) = O( (n^3) * (|V|^2) + (|V|*n) ) b/ Avec un tableau de ENTIER de 8BIT L'algorithme a été implémenté par INDRAWATI. On génère d'abord toutes les configurations possibles du jeu de ChocoBar de taille (m x n) avec m le nombre de lignes et n lenombre de colonnes : c'est une génération d'une suite d'entiers de longueur n en ordre lexicographique particulier. genChoco(m: entier, n: entier) V <- genEtat(m, n) E <- vide pour i de 0 à longeur(V) faire pour j de i+1 à longeur(V) faire si estFils(V[j], V[i]) alors E <- E U {(i, j)} fin si fin pour fin pour renvoyer (V, E) //c'est notre graphe genEtat(m: entier, n: entier) pour i de 0 à (n-1) faire init[i] <- 0 final[i] <- m fin pour etatCourant <- init tabEtat[0] <- init i <- 1 etatFinal <- final tant que etatCourant != etatFinal faire pour j de 0 à (n-1) faire gen[j] <- etatCourant[j] fin pour gen[n-1] <- gen[n-1] + 1 si gen[n-1] > m alors retenue <- vrai fin si j <- (n-1) tant que (gen[j] > m) faire si j=0 alors arreter tant que fin si gen[j-1] <- gen[j-1] + 1 j <- (j - 1) fin tant que si retenue est vrai alors pour cpt de j à (n-1) faire gen[cpt] <- gen[j] fin pour fin si etatCourant <- gen tabEtat[i] <- gen i <- i+1 fin tant que tabEtat[i] <- etatFinal renvoyer tabEtat estFils(fils: tableau d'entiers, pere: tableau d'entiers) eaten <- -1 pour i de 0 à longeur(fils) faire si fils[i] < pere[i] alors renvoyer faux fin si si eaten = -1 alors si fils[i] = pere[i] alors continuer sinon eaten <- i fin si sinon si pere[i] != fils[i] et fils[i] != eaten alors renvoyer faux fin si fin pour si eaten != -1 alors renvoyer vrai // fils est bien un etat suivant du pere sinon renvoyer faux // pere identique au fils fin si Soit la taille de la barre de chocolat du jeu est de m lignes et n colonnes et on souhaite générer tous les états possibles dont chacun nous coûte O(n) en temps. Ceci fera un total de O(n*|V|). De même pour la complexité en espace puisqu'un état est décrit par n entiers. Pour vérifier si un état peut être atteint à partir d'un autre état donné alors on doit comparer les 2n entiers décrivant ces deux états. Une comparaison coûte donc O(n). Etant donné que les états sont générés en ordre lexicographique alors on est sûr que les candidats des états adjacents à un état indexé par i sont ceux indexé par des entiers supérieur i. Le nombre de vérifications qu'il faut effectuer sont alors = somme des entiers de 1 à |V| = 1/2 * |V| * (|V|+1). Chacune de ces vérifications coûte O(n), la construction des arêtes coûte en total O(n*(|V|^2)). Tout cela conduit à un coût total en temps de génération de graphe en O(n*(|V|^2))+O(n*|V|). ATTENTION: A la fin de génération de graphe on supprime la liste des configurations, il nous reste que l'espace occupé par la matrice d'adjacence ou la liste d'adjacence du graphe. c/ Avec un ENTIER de 64BIT C'est le même algo que pour le b/. PARTIE DE JEU ------------- Cet algorithme a été concu par INDRAWATI. // C'est une fonction de simulation qui affiche le déroulement de jeu // selon stratégie des deux joueurs simulation(G: graphe, SA: strategie de A, SB: strategie de B) courant <- etat initial de G final <- etat final de G tant que courant != final faire coupA <- SA[courant] afficher "A a bougé vers coupA" si coupA == final alors afficher "A a perdu" quitter fin si courant <- SB[coupA] afficher "B a bougé vers courant" fin tant que afficher "B a perdu" En terme de complexité, ici on considère plutôt en temps puisque l'espace utilisé est statique : par définition de STRATEGIE il est égal au nombre des sommets du graphe, donc O(|V|). En ce qui concerne de temps, au pire des cas on parcourt le chemin de longueur maximale de l'état intial vers l'état final. Ce chemin dépendra, à son tour, du graphe de jeu (peut-être donné par l'utilisateur, ce n'est donc pas déterministe), tout ce que l'on sait c'est que ce chemin < |V|. TEST DE STRATEGIE ----------------- Cet algorithme a été écrit par INDRAWATI. // C'est une fonction qui teste si S est une stratégie gagnante ou non isWinningStrategy(G: graphe, S: strategie) courant <- etat initial de G final <- etat final de G etatsATraiter <- {courant} etatsTraites <- vide tant que etatsATraiter != vide faire etat <- enfiler etatsATraiter si etat == final alors continuer fin si etatsTraites <- etatsTraites U {etat} coup <- S[etat] si coup == final renvoyer faux fin si advers <- les sommets adjacents à coup pour les sommets i contenus dans advers faire si i n'est pas contenu dans etatsTraites alors etatsATraiter <- etatsATraiter U {i} fin si fin pour fin tant que renvoyer vraie En espace on sait qu'à tout moment un sommet est contenu soit dans l'ensemble etatsATraiter soit dans l'ensemble etatsTraites, l'espace occupé est alors egal au nombre des sommets du graphe. L'espace occupé est alors O(|E|). En temps, on sait que l'on visite tous les coups possibles de l'adversaire et on ne visite qu'un coup quand c'est notre tour. Ceci dit, on ne visite qu'une partie des sommets du graphe. La complexité est alors inférieure à O(|V|). REMARQUE : x->y x->z x->t On ne peut prédire combien d'arrêtes que l'on a à chaque sommet puisque le graphe peut être donné par l'utilisateur et le sommet choisi est également décidé par l'utilisateur. CONSTRUCTION DE STRATEGIE GAGNANTE ---------------------------------- Cet algorithme a été écrit par INDRAWATI. L'approche choisie est de trouver le chemin gagnant le PLUS COURT partant de l'état initial vers l'état final. Ceci dit que la stratégie ne peut pas être appliquée à une simulation si le joueur qui lui est associée ne fait pas le PREMIER coup. // C'est une fonction qui renvoie un tableau d'entiers (une stratégie gagnante) constructWinningStrategy(G: graphe) final <- etat final de G start <- etat initial de G sommetsATraiter <- vide pour i de 1 au ((nombre de sommets de G) - 1) faire S[i]=0 sommetsATraiter <- sommetsATraiter U {sommet i} fin pour etatsGagnants <- {final} etatsPerdants <- vide tant que (S[start]==0) faire sommet <- tete de sommetsATraiter test_perdant <- withOnlyEdges(sommet, etatsGagnants, g) si test_perdant != -1 alors enfiler sommet de sommetsATraiter etatsPerdants <- etatsPerdants U {sommet} S[sommet] <- test_perdant nuvo <- les sommets ayant un arc vers le sommet sommet pour tout sommet i dans nuvo etatsGagnants <- etatsGagnants U {i} S[i] <- sommet fin pour pour tout sommet i dans sommetsATraiter faire si i est contenu dans nuvo enlever i de sommetsATraiter fin si fin pour fin si fin tant que renvoyer S // C'est une fonction qui renvoie -1 si sommet src a au moins un sommet adjacent // qui n'est pas contenu dans dest withOnlyEdges(src: entier, dest: liste d'entiers, G: graphe) //si graphe est représenté par une matrice alors il faut parcourir //toute la ligne de src //si c'est une liste d'adjacence suffit de prendre la liste indexée par src adjacents <- {sommets adjacents à src} ret <- -1 pour tout sommet i contenu dans adjacents faire si i n'est pas contenu dans dest alors renvoyer -1 sinon si ret == -1 alors ret <- i fin si fin pour renvoyer ret Par hypothèse du jeu de ChocoBar, on sait que le joueur qui commence est le gagnant et que l'on peut lui trouver une stratégie gagnante. Ceci veut dire que l'on arrivera à décider une suite des coups à partir de l'état initial vers l'état final en gagnant le jeu. ATTENTION: Cet algo ne marche donc pas pour les graphes qui ne respectent pas les règles de ChocoBar. On définit alors ETAT GAGNANT comme étant un état qui peut méner à un état perdant. En effet, si un joueur se trouve dans cet état alors il peut choisir son coup et logiquement il va choisir un état perdant pour le passer à son adversaire. Un ETAT PERDANT, par contre, est l'état qui ne peut que mener aux états gagnants. C'est l'état dans lequel on souhaite placer l'adversaire afin de bloquer ses choix. Donc, partant de l'état final de jeu, on sait que celui qui trouve cet état avant de décider de jouer est le gagnant, l'état final est donc un sommet gagnant. A chaque itération on essaie de trouver un ou plusieurs états perdants. Au pire des cas on ne trouve qu'un état perdant que l'on enlèvera de l'ensemble des états à traiter. On en enlèvera également les états gagnants obtenus à partir de cet état perdant. Ce "backtracking" est effectué jusqu'au début du graphe (état initial). Naïvement on peut dire que l'on a, à chaque étape d'itération, au moins un état perdant et un état gagnant (car cet état perdant provient surement d'un autre coup) et d'un coup on enlève ces deux états (au pire) de l'ensemble restant à traiter et on doit faire donc 1/2 * (|V|) itérations dans le pire des cas. A chaque itération on visite tous les états non traités jusqu'à ce que l'on trouve un état perdant. Ceci dit qu'au maximal on effectue O(|V|^2 + |V|) visites. Or, en réalité on s'arrête beaucoup plus tôt car dès que l'on puisse décider quel coup à choisir à partir de l'état intial alors on s'arrête car on a déjà trouvé le chemin gagnant le plus court partant du début de jeu. Ce chemin se composera uniquement par un ensemble d'arrêtes de la forme (etat_gagnant -> etat perdant). Il existe des états non traités à la sortie de cet algo. Ce sont des états par lesquels on ne passera jamais car quand on a plusieurs choix (tous perdants) à partir d'un sommet gagnant alors on doit quand même en choisir qu'un seul (par définition de STRATEGIE). En terme de l'espace occupé on en a besoin de O(|V|) : |V| pour stocker la stratégie sous forme d'un tableau et |V| pour stocker les états non-traités + les états traités (états perdants + états gagnants = tous les etats).