Sokoban
Free and Social Puzzle Game

Jeu de Sokoban
Recherche de solutions optimales

Chapitre 1 Remerciements

Table des matières

Chapitre 2 Introduction

Chapitre 3 Le Sokoban

Historique

Sokoban, gardien d'entrepôt en français, est un jeu vidéo de réflexion originaire du Japon et datant du début des années 80. Selon des sources diversesSoHistory (Pas d'année); WikiSokoban (Pas d'année), il a été créé par Hiroyuki Imabayashi et édité par Thinking Rabbit qui en détient aujourd'hui tous les droits. Le jeu doit sa popularité à des règles très simples mais qui permettent néanmoins une très grande complexité. De fait, certains niveaux sont très difficiles à résoudre par l'homme et même par la machine.

Règles

La Figure 3.2 correspond à la représentation d'un niveau de Sokoban.

Exemple de solution optimale

Etant donné le niveau représenté sur la Figure 3.3, la liste des états intermédiaires qui mènent à la solution optimale, en terme de mouvements et de poussées, est visible sur la Figure 3.4. Il y a plusieurs façons de représenter une solution. Celle adoptée dans ce document consiste à se placer du point de vue du pousseur et d'indiquer ses directions successives par des lettres minuscules s'il ne pousse pas de caisse ou majuscules s'il en pousse une. Si plusieurs mouvements ont lieu dans la même direction. La lettre est préfixée par son nombre d'occurences. Dans notre exemple, la solution est Ld2l2urDldR et s'établit en 11 mouvements et 3 poussées.

Complexité

Il a été démontré en 1995 par Dorit Dor et Uri ZwickDor et Zwick (Pas d'année) que le problème de décision correspondant au Sokoban était NP-difficile. C'est-à-dire que Sokoban fait partie de la classe des problèmes décidables par une machine de Turing non déterministe en temps polynomial.
Deux ans plus tard, en 1997, des travaux réalisés par Joseph CulbersonCulberson (Pas d'année) ont démontré que le problème de décision était PSPACE-complet. Il appartient donc à la classe PSPACE et est PSPACE-difficile. C'est-à-dire qu'il est au moins aussi difficile que tous les problèmes de la classe PSPACE qui représente les problèmes décidables par une machine de Turing déterministe en espace polynomial par rapport à la taille de sa donnée.

Chapitre 4 Résolution

Arbre de recherche

Afin de limiter la taille de l'arbre de recherche, ce ne sont pas les mouvements du pousseur qui sont pris en compte mais les poussées des caisses. Les transitions entre un état et ses fils correspondent donc chaque fois à une succession de mouvements suivie d'une poussée comme indiqué sur la Figure 4.1. Cette couche d'abstraction nous permet d'arriver plus vite à un état solution mais ne nous garantit pas l'obtention de la solution optimale en terme de mouvements, seulement celle en terme de poussées.

État de l'art

Rolling Stone

Le solveur Rolling Stone est certainement celui qui est le plus documenté à ce jour. Il provient de l'Université d'Alberta, Canada. Des recherches y ont été faites entre 1997 et 2001 et il en résulte une Thèse écrite par Andreas JunghannsJunghanns (1999) et de nombreuses publications d'articles sur des méthodes testées et plus ou moins efficaces. L'utilisation d'une méthode intelligente de parcours de l'arbre de recherche (IDA*) permet d'assurer l'optimalité de la solution en terme de poussées d'un niveau. De plus, de nombreuses méthodes de détection de deadlocks et de pénalités sont utilisées et réduisent considérablement la taille de l'arbre de recherche.

Talking Stone

Le solveur Talking Stone est plus récent et date de 2006. Il a été créé par François Van Lishout à l'Université de Liège, Belgique, dans le cadre d'un DEA en Sciences AppliquéesVan Lishout (2006). Une nouvelle approche Multi-Agent est utilisée dans le but de faire interagir les éléments principaux du jeu – les caisses – entre-eux avec un objectif commun. F. Van Lishout est parvenu à trouver un algorithme permettant de résoudre les niveaux lorsque ceux-ci appartiennent à une certaine sous-classe prédéfinie. L'idée principale est qu'un niveau appartient à cette sous-classe si on peut trouver une association caisses-goals permettant de mettre, tour à tour, chaque caisse sur son goal. Cette méthode a cependant très vite montré ses limites car un seul niveau a ainsi pu être résolu.

Talking Stone (2)

Un autre solveur est apparu l'année suivante à Liège, toujours en Scheme et reprenant les principes de base de Talking Stone. Il a été créé par Jean-Noël Demaret dans le cadre de sa Deuxième LicenceDemaret (2007) et reprend l'approche Multi-Agent en l'améliorant et en insérant des optimisations propres au Sokoban. Il concrétise l'intérêt de l'approche de Talking Stone en résolvant 54 niveaux tout en laissant une légère marge de progression.

Sokoban Automatic Solver

Le solveur Sokoban Automatic Solver est certainement celui qui est le plus puissant à ce jour. Il est toujours en développement et sa première version semble dater de 2003. Malheureusement, il est non documenté et son code n'est pas disponible. Il est créé par le Japonais Ken'ichiro Takahashi et la version 7.2.2 de janvier 2008Takahashi (Pas d'année) permet de résoudre 86 des 90 problèmes proposés, ce qui est réellement impressionnant. Les solutions trouvées ne sont pas optimales ce qui laisse supposer qu'il utilise des heuristiques très précises pour réduire la taille de l'arbre de recherche.

Contributions

Optimalité des solutions

Zone

Deadlock

Concrètement, un deadlock est un état dont on peut affirmer, par l'une ou l'autre méthode (cf. Chapitre 8), qu'il ne mènera pas à une solution. En d'autres mots, cet état est la racine d'un sous-arbre de l'arbre de recherche qu'il faut éviter de créer, au risque de faire croître inutilement la taille de l'arbre et augmenter le temps de résolution du problème.
Un certain nombre de techniques efficaces ont été implémentées à partir de méthodes décrites dans la Section 4.2. Nous avons ajouté à celles-ci une nouvelle méthode permettant d'étendre la notion de deadlock à celle de deadlock zone. Cette méthode découle d'observations effectuées lors de l'utilisation du solveur sur certains niveaux et est décrite dans la Section 8.2.2.

Tables de coût et pénalités

Pré-traitement / Post-traitement

Dans les précédentes recherches de la Section 4.2, il semble n'y avoir eu que quelques cas de pré-traitement, notamment dans le cadre de l'utilisation de Deadlock Tables dans Junghanns (1999). Peut-être étaient-ils passés sous silence mais utilisés dans la pratique. Peut-être également que l'une des contraintes était de pouvoir recalculer les informations utiles à la volée. Quoi qu'il en soit, nous pensons que ces techniques sont intéressantes car facultatives et persistantes. Facultatives car il est possible d'utiliser le solveur sans utiliser de pré-traitement ni de post-traitement. Persistantes car une fois un traitement effectué, il peut être chargé instantanément lors d'une prochaine utilisation du solveur et être utilisé tel quel ou complété.

Langage de programmation

Chapitre 5 Prérequis

Algorithme principal

État

Comme nous l'avons signalé dans la Section 4.1, la structure d'un état ne doit pas contenir d'information relative aux positions des goals et des murs. Celles-ci sont stockées au début de la résolution d'un niveau et ne sont plus recalculées par la suite.
La Figure 5.1 représente la structure d'un état tel qu'il est stocké en mémoire. Les croix représentent les positions qui sont utilisées respectivement par les caisses et par le pousseur. La zone du pousseur comprend également les caisses voisines de son champ d'action. Nous verrons dans la section 5.5 pourquoi nous procédons de la sorte.

Nœud

Liste d'attente

Zone

5.5.1 Objectif

Les zones ne peuvent représenter que les positions qui se situent à l'intérieur d'un niveau par rapport aux murs. En d'autres mots, les positions sur lesquelles le pousseur et les caisses peuvent évoluer. La Figure 5.3 représente l'ensemble des positions { w 1 , w 2 , , w 23 } qui sont représentées par une zone sur ce niveau. Comme illustré, les positions sont numérotées ligne par ligne, en partant du coin supérieur gauche.

5.5.2 Implémentation

Tout l'intérêt d'une zone est de pouvoir être représentée par un nombre binaire. Dans l'exemple de la Figure 5.3, nous voyons qu'une zone est définie par 23 positions. Ces positions peuvent toutes être représentées par un bit. Le bit i vaudra 1 si la position w i est comprise dans l'ensemble et 0 si elle ne l'est pas.

5.5.3 Tables de traduction

  1. Le positionnement absolu : il permet de couvrir toutes les positions d'un niveau sans exception. Chaque position est référencée par l'intersection entre une ligne (lettre) et une colonne (nombre). Cette méthode permet de situer les éléments fixes d'un niveau comme le murs ou les positions extérieures.
  2. Le positionnement relatif à la zone : il permet de couvrir les positions comprises dans la zone. Il sera utilisé pour situer les éléments dans une zone tels que les caisses ou les positions du pousseur. Cette méthode est essentiellement utilisée dans les interactions avec un état.
Pour éviter ce problème, deux tables de traduction Tra d ar et Tra d ra sont créées. Celles-ci ont la propriété d'associer une position relative à chaque position absolue et vice versa tel qu'illustré sur la Figure 5.4. Dans le cas où aucune position relative ne correspond à une position absolue, la table de traduction retournera -1 pour bien indiquer l'impossibilité. C'est le cas de Tra d ar [ A1 ] qui retournera -1 pour bien montrer l'impossibilité de représenter cette position par la méthode relative.

5.5.4 Opérations

Tester si un état est solution

Trouver les poussées potentielles

Il suffit, comme la Figure 5.5 le montre, de rechercher l'intersection entre les deux zones. Concrètement, cela consiste à appliquer une opération binaire ET entre les représentations de la zone du pousseur et de la zone des caisses. On obtient ainsi une nouvelle zone contenant la position des caisses que le pousseur peut atteindre. On pourra ainsi travailler directement sur un sous-ensemble de caisses, ce qui diminuera la quantité de calculs nécessaires lors de la création des états fils d'un nœud de l'arbre de recherche.

Tester l'inclusion

  1. e A zoneCaisses e B zoneCaisses : toutes les positions de la zone des caisses de l'état e A doivent appartenir à la zone des caisses de l'état e B .
  2. e A zonePousseur e B zonePousseur : toutes les positions de la zone du pousseur de l'état e B doivent appartenir à la zone du pousseur de l'état e A .
Le fait que ce soit la zone du pousseur de l'état B qui doit être contenue dans celle de l'état A va à l'encontre d'une première intuition. Il faut cependant prendre en compte, comme représenté sur la Figure 5.6, que moins un état possède de caisses, plus la zone du pousseur sera grande. Dans un état sans caisses, la zone du pousseur représenterait toutes les positions de celui-ci.
À l'aide des zones, tester si z A z B , où z A et z B sont des zones d'un même niveau, est assez simple. Il suffit d'appliquer z C = z A z B à la manière de la Figure 5.5 et ensuite de tester la condition z C =? z A . Si la condition est vérifiée, alors z A z B , sinon z A z B . Un tel test est donc très rapide car il ne concerne que des opérations élémentaires portant sur des entiers. À chaque opération sur un entier, ce sont 32 positions qui sont testées à la fois.

Tester l'intersection

Doublons

Ces problèmes de duplications de sous-arbres et de situations redondantes (cf. Figure 5.7) sont très préoccupants dans un contexte où nous essayons justement de limiter les calculs nécessaires, et donc la taille de l'arbre de recherche, pour trouver une solution.

Implémentation

La table de hachage a été testée de manière intensive (cf. Tableau 5.1 et Figure 5.9) avec la création d'un arbre de recherche contenant environ 4250000 nœuds. Les résultats attendus correspondent à une moyenne de 5 éléments par liste chaînée. Les résultats obtenus sont assez concluants car 65% des listes contiennent jusqu'à 5 éléments, 90% des listes contiennent jusqu'à 10 éléments et 99% des listes possèdent 20 éléments ou moins. Sans être exceptionnels, ces résultats ne justifient pas la recherche d'une meilleure fonction de hachage.

Chapitre 6 Parcours

Nous avons vu dans la Section 4.1 que la résolution d'un problème de Sokoban nécessitait la construction d'un arbre de recherche. Le moment est venu de décrire les différentes façons de construire cet arbre. Chacune des méthodes proposées possède ses avantages et inconvénients et diffère essentiellement des autres par l'ordre dans lequel les nœuds dans la liste d'attente seront placés dans l'arbre de recherche.

Parcours en largeur

Le parcours en largeur explore en priorité les nœuds les plus hauts de l'arbre de recherche. Du fait que dans notre solveur, chaque saut d'un nœud à un autre corresponde à une seule poussée, nous pouvons en déduire que l'optimalité en terme de poussées de la solution sera atteinte. Sur la Figure 6.1, nous pouvons voir deux nœuds qui contiennent des états solutions. L'une des deux solutions est optimale avec 2 poussées (nœud 8) et l'autre ne l'est pas avec 3 poussées (nœud 12). Avec le parcours en largeur, la solution qui sera trouvée la première sera bien celle qui est optimale.

Parcours en profondeur

Parcours informé

6.3.1 Tas

Fonctionnement

Si l'arbre binaire contient p niveaux, alors celui-ci doit être complet sur ses p-1 premiers niveaux et le dernier doit être rempli de gauche à droite. Un des aspects les plus pratiques d'un tas est qu'il peut être stocké dans un tableau T tel qu'illustré sur la Figure 6.4. L'arbre binaire correspondant au tas doit respecter un certain ordre dans ses éléments : si A et B sont deux nœuds de l'arbre binaire tels que A est le père de B, alors cout(A) cout(B) .

Implémentation

Parcours A*

6.4.1 Fonctionnement

  1. δ contient un nœud solution.
  2. Le nombre de fils d'un nœud quelconque est fini.
  3. Il existe un minorant strictement positif de l'ensemble des coûts des arcs.
  1. Les algorithmes de types A* appliqués à δ se terminent.
  2. Un chemin joignant la racine à un nœud solution est trouvé.
  3. Le chemin découvert est un chemin de coût minimal dans l'arbre de recherche, entre la racine et l'ensemble des nœuds solutions.

6.4.2 Implémentation

Lors du parcours, il a été prévu dans la Section 5.6 de rejeter un état si celui-ci est déjà présent dans l'arbre de recherche. Dans le cas du parcours A*, afin de garder l'optimalité des solutions, il ne suffit plus de rejeter tous les doublons. En effet, deux états identiques peuvent se trouver à deux profondeurs différentes de l'arbre de recherche et possèder deux valeurs différentes pour g(n) n est le nœud contenant l'état. Si le nœud dont la valeur est la plus petite, et donc la meilleure, est traité en deuxième lors du parcours, il sera considéré comme doublon et rejeté à tort. Le risque est que ce nœud mène justement à la solution optimale, qui sera alors perdue.

Le nouveau nœud est déjà présent dans l'arbre de recherche et noeudPresent T ferme

Le nouveau nœud est déjà présent dans l'arbre de recherche et noeudPresent T ouvert

6.4.3 Priorité de la liste d'attente

6.4.4 Exemple

La Figure 6.5 représente les différentes structures qui interviennent lors d'un parcours A*. Pour une lecture plus facile, la liste d'attente n'est pas représentée sous la forme d'un tas mais sous celle d'une liste chaînée triée. On voit que le parcours se dirige assez facilement vers le nœud solution 15 en évitant les autres nœuds dont le coût f(n) est plus élevé. Si aucune solution en 5 poussées n'était possible, le prochain nœud traité serait le premier de la liste d'attente et donc celui qui est le plus prometteur en 6 poussées.

Parcours IDA*

6.5.1 Fonctionnement

La Figure 6.6 montre différentes itérations du parcours A*. Nous pouvons y voir que la solution optimale sera toujours trouvée la première (lors de l'itération pour laquelle f max =10 ). Des solutions moins bonnes pourraient être trouvées lors d'itérations suivantes.

6.5.2 Avantages

6.5.3 Inconvénients

6.5.4 Optimisations

Valeur initiale de f max

Incrémentation de f max

Nous avons remarqué que l'évolution du coût a tendance à évoluer par pas de 2. En effet, si le pousseur est placé du mauvais côté pour pousser une caisse, il va d'abord devoir la pousser une première fois, la contourner, puis la repousser une deuxième fois (cf. Figure 6.7). L'estimation du coût est ainsi faussée de 2 poussées. Pour ne pas inutilement incrémenter la limite par pas de 1 si on peut progresser plus rapidement, nous allons garder en mémoire le nœud rejeté dont le coût est le plus petit. Par exemple si la limite actuelle est de 10 et qu'à la fin de l'itération, le coût le plus petit qui a été rejeté est 12, nous pourrons commencer l'itération suivante à 12.

6.5.5 Priorité de la liste d'attente

Chapitre 7 Estimation

  1. Calculer le plus précisément possible le nombre de poussées requises pour placer une caisse sur chacun des goals. Nous appellerons cela l' estimation d'une caisse.
  2. Diriger les caisses présentes dans un état vers les goals de manière à trouver l' estimation totale de l'état la plus juste possible. Il faut s'aider des estimations des caisses et il est important de continuer à minorer h * (n) .

Estimation d'une caisse

Comme nous le verrons dans le Chapitre 10, le temps de calcul de l'estimation des caisses n'est pas un problème majeur. Ceci est lié au fait que le calcul n'est réalisé qu'une seule fois par niveau. Par la suite, les résultats seront réutilisables à l'infini. Il est donc préférable d'utiliser les méthodes les plus précises même si elles s'avèrent souvent plus lentes.
Chaque état contient des caisses sur des emplacements différents. Celles-ci peuvent potentiellement occuper toutes les positions internes d'un niveau (cf. Figure 5.3). Nous allons construire une matrice M carrée N × N , où N est le nombre de positions internes, et dans laquelle la cellule M i,j 1i,jN contiendra le nombre de poussées requises pour déplacer une caisse située sur la position i vers la position j . Cette matrice M sera aussi appelée la table des estimations.

7.1.1 Taxi-distance

La Figure 7.2 représente la taxi-distance entre la caisse se situant sur la position F5 et l'ensemble des autres positions joignables.

7.1.2 Distance réelle

  1. La position p 1 ne doit être ni un mur, ni une caisse. Elle correspond à l'emplacement du pousseur avant la poussée.
  2. La position p 3 ne doit être ni un mur, ni une caisse. Elle correspond à l'emplacement de la caisse après la poussée.
La Figure 7.3 représente le graphe connexe utilisé pour calculer l'estimation de la caisse F5 ainsi que le niveau qui comprend les estimations obtenues de la sorte. Sachant que chaque arc du graphe possède un poids unitaire, il est facile d'y appliquer directement l'algorithme de Dijkstra. L'objectif est de trouver le chemin minimal permettant de pousser la caisse s 0 vers les trois goals s 1 , s 2 et s 3 , et par la même occasion, les chemins minimaux de la caisse vers toutes les autres positions.

7.1.3 Distance réelle avec gestion du pousseur

À titre d'exemple, sur la Figure 7.3, après une poussée de E4 vers D4, le pousseur se trouvera sur la position E4. Par la suite, il n'aura pas la possibilité de déplacer la caisse sur la position D5, contrairement à ce qui est indiqué dans le graphe.

Parcours en largeur

Dans le but de réutiliser des fonctionnalités qui ont déjà été implémentées, cette méthode passe par la création d'un niveau temporaire comprenant une seule caisse et un seul goal. Sur ce niveau, un parcours en largeur sera appliqué tel qu'il a été décrit dans la Section 6.1. Celui-ci permet de trouver la solution optimale d'un niveau. Le nombre de poussées de la solution optimale servira donc d'estimation pour déplacer une caisse de la position i vers la position j .

Création améliorée du graphe connexe

La Figure 7.4 représente le graphe connexe amélioré obtenu en procédant comme indiqué. Pour une meilleure lisibilité, les sommets qui correspondent à une même position sont entourés par des cercles plus clairs. Ceux-ci ne sont pas à prendre en considération dans le graphe connexe. Même si le graphe connexe semble peu lisible à première vue, il est possible de transiter d'un sommet à l'autre en partant de s 0 pour arriver à l'un des goals. L'important est de remarquer que le chemin emprunté sera plus long que sur la Figure 7.3 car les contraintes imposées par la position du pousseur ne permettent pas toujours le déplacement voulu.

Implémentation

Complexité

Conclusion

Estimation totale

La Figure 7.5 représente un nœud ainsi que la matrice O correspondante. Pour être fidèle à la réalité, la matrice M utilisée pour créer la matrice O a été générée à l'aide de la méthode de la Section 7.1.3 impliquant Dijkstra et le graphe amélioré. L'intersection entre la ligne c 2 et la colonne g 3 contient l'estimation requise pour positionner la caisse c 2 sur le goal g 3 .

7.2.1 Goal le plus proche

7.2.2 Goal le plus proche avec réservation

Cette méthode ne conserve pas la propriété d'admissibilité car il existe des états pour lesquels h(n)> h * (n) . L'un de ces états est illustré sur la Figure 7.6. Dans celui-ci, h * (n)=9 et h(n)=11 . Ceci est dû au fait que, pour minimiser l'estimation totale, il est plus intéressant de déplacer la caisse c 1 vers le goal le plus éloigné ( g 2 ) que vers le goal le plus proche ( g 1 ).

7.2.3 Association caisses-goals minimisant l'estimation totale

Implémentation

Pour ne pas devoir réimplémenter la méthode Hongroise à partir de rien, une version C++ existanteWeaver (Pas d'année), déjà déboguée et optimisée, a été intégrée à notre solveur. Nos données ont été adaptées pour correspondre aux contraintes des fonctions existantes.

Méthodes utilisées

Trois méthodes ont été présentées pour calculer l'estimation d'une caisse et trois méthodes ont été présentées pour calculer l'estimation totale. En théorie il y a donc neuf possibilités d'associations entre ces méthodes comme illustré sur la Figure 7.8. Dans la pratique, on peut directement éliminer la méthode de la Section 7.2.2 du goal le plus proche avec réservation car elle ne respecte pas la propriété d'admissibilité du parcours A*. Si une solution est trouvée, il ne sera donc pas possible d'affirmer que celle-ci est optimale.
Des six associations restantes possibles et qui sont admissibles, il est préférable de prendre celle qui maximise l'estimation de manière à être le plus proche de la valeur h * (n) . Comme le démontre la Figure 7.9, c'est l'algorithme de Dijkstra avec graphe amélioré qui majore le plus l'estimation d'une caisse vers chacune des positions. C'est donc la méthode qui s'avère la plus efficace. Rien d'étonnant à cela, c'est la méthode qui prend en compte le plus de contraintes, dont la position du pousseur.

Chapitre 8 Deadlock

Deadlock à une caisse

8.1.1 Deadlock en coin

Un exemple de deadlock en coin est illustré sur la Figure 8.2. Selon les règles du jeu, il parait clair que la caisse située sur la position absolue D2 ne pourra pas rejoindre l'un des goals.

8.1.2 Deadlock en ligne

Un exemple de deadlock en ligne est illustré sur la Figure 8.3. Selon les règles du jeu, il parait clair que la caisse située sur la position absolue C2 ne pourra pas s'écarter du mur pour rejoindre l'un des goals.
Une fois tous les deadlocks en ligne trouvés, nous enregistrons une zone ne comprenant que les positions concernées comme illustré à l'aide de croix sur la Figure 8.4. La zone sera utilisée par la suite afin de rejeter de l'arbre de recherche tous les états qui ont une caisse sur l'une des croix.

8.1.3 Implémentation

Deadlock à plusieurs caisses

8.2.1 Dernière poussée

Deadlock en carré

La caisse qui vient d'être poussée sur la position absolue H9 de la Figure 8.6 provoque un deadlock en carré avec les trois autres positions G8, G9 et H8.

Deadlock en Z

8.2.2 Deadlock Zone

De manière générale, la méthode de la deadlock zone est assez coûteuse mais permet de détecter des situations de deadlock éventuellement provoquées par un grand nombre de caisses (cf. Figure 8.10). Cette méthode vérifie, pour chaque état, que celui-ci ne contient pas une deadlock zone. Si un état en contient une, alors il est rejeté de l'arbre de recherche.

8.2.3 Deadlock méthodique

Recherche passive

Nous verrons que la recherche passive de deadlocks est un cas particulier de la recherche passive de pénalités. La Section 9.2.1 décrit plus en profondeur la technique employée pour créer les états à 1, 2 ou 3 caisses.

Recherche active

Comme la recherche passive, la recherche active de deadlocks est un cas particulier de la recherche active de pénalités. La Section 9.2.2 explique comment créer des sous-états à tester à partir d'un état de l'arbre de recherche.

Chapitre 9 Pénalité

Les techniques développées dans le Chapitre 7 permettent d'obtenir une estimation h(n) en fonction des positions des caisses et des goals dans le nœud. Rien dans ces techniques ne permet de mettre en évidence le surcoût occasionné lorsque plusieurs caisses se gênent mutuellement.
Le cas d'un sous-état contenant des caisses qui se gênent mutuellement, illustré sur la Figure 9.1, n'est pourtant pas rare. À partir des méthodes d'estimation décrites précédemment, on obtient pour ce sous-état h(n)=20 . Dans les faits cependant, on voit directement que la caisse située sur la position absolue H9 ne pourra pas être atteinte par le pousseur sans qu'il ne commence par pousser la caisse située en H6 vers le bas. Ce mouvement supplémentaire donnera au final h * (n)=22 . La différence entre l'estimation et le coût réel est donc de 2.
Cette différence entre coût estimé et coût réel du sous-état, que nous appellerons pénalité d'un sous-état, devra s'appliquer dans tous les états dans lesquels ce sous-état est inclus. La pénalité déduite d'un état e comprend l'application des pénalités (cf. Section 9.4) de tous les sous-états s 1 ,s 2 , ,s n tels que s 1 e,s 2 e, ,s n e . Contrairement à la pénalité d'un sous-état, la pénalité déduite d'un état n'est pas toujours la différence exacte entre le coût estimé et le coût réel, ce n'est qu'une meilleure approche de la valeur h * (n)

Définition

Cette technique est une généralisation de celle des deadlocks méthodiques (cf. Section 8.2.3). En effet, un sous-état qui provoque un deadlock peut être considéré comme un sous-état dont la pénalité est infinie. L'état qui comprend ce sous-état aura alors une pénalité déduite infinie et une valeur h(n)= . Le coût du nœud contenant l'état va alors provoquer son rejet de l'arbre de recherche.

Recherche

  1. Une solution est trouvée : la limite f max introduite correspond à la distance exacte entre le nœud initial et le nœud solution. L'estimation actuelle du sous-état correspond donc à la distance réelle. Aucune pénalité ne doit être assignée au sous-état.
  2. Aucune solution n'est trouvée : la limite f max introduite est plus petite que la distance exacte entre l'état initial et le nœud solution. Cela signifie que l'estimation actuelle du sous-état ne correspond pas à la distance réelle. Selon le résultat de la validation (cf. Section 9.3), le sous-état va alors être pénalisé.

9.2.1 Recherche passive

La zone des caisses de chaque état sera ainsi créée à partir des positions des caisses obtenues par ce procédé. Il faut ensuite chercher toutes les zones du pousseur possibles à partir de chaque zone des caisses. Pour chaque couple possible ( z caisses , z pousseur ) tel qu'illustré sur la Figure 9.2, un état sera créé et testé. La position du pousseur dans le niveau transmis au solveur bestPushes n'a que peu d'importance tant qu'elle se situe bien dans la zone du pousseur trouvée. Dans notre exemple, le pousseur se situe chaque fois sur la première position relative à la zone du pousseur à tester.

9.2.2 Recherche active

  1. Une pénalité est trouvée et enregistrée.
  2. Toutes les caisses de l'état qui se trouvent sur l'un des chemins ont été ajoutées.
  3. La recherche active des sous-états pénalisés d'un état est limitée par une certaine quantité de nœuds. Si cette quantité est dépassée pour un certain état, on arrête la recherche de sous-états pénalisés.
Pour illustrer cette méthode, nous avons repris l'exemple présenté dansJunghanns (1999) La Figure 9.3 correspond à une poussée. La recherche active va s'appliquer sur la caisse qui vient d'être poussée en créant plusieurs sous-états qui sont susceptibles de provoquer des pénalités comme illustré sur la Figure 9.4.
Le chemin des caisses récupéré à partir de la solution du sous-état représenté en haut à gauche de la Figure 9.4 passe par les positions absolues C6, C5, C4, C3. On ajoute donc la caisse située sur la position C5 dans le sous-état suivant. Pour le troisième sous-état représenté, on utilise le chemin du pousseur car aucune caisse ne se trouve plus sur le chemin des caisses.

Validation

Sur l'exemple de la Figure 9.5, on remarque que la différence entre le coût réel et le coût estimé est de 1. Une pénalité de 1 devrait donc être assignée à ce sous-état. Cependant, il existe un sous-ensemble de goals pour lequel l'estimation correspond bien au coût réel. Dans ce cas, la pénalité n'est pas validée car elle va majorer h * (n) si la solution comprend les trois caisses positionnées sur les goals F14, F15 et K14.

9.3.1 Sous-état pénalisé minimum

Il peut arriver qu'un sous-état pénalisé contienne plus de caisses que nécessaire pour que la pénalité s'applique (cf. 4ème état de la Figure 9.4). Il faut donc trouver le sous-état pénalisé minimum, c'est-à-dire le sous-état qui comprend le moins de caisses tout en provoquant la même pénalité. Pour y arriver, pour chaque état de c caisses qui est validé, nous allons tester les pénalités de tous les sous-états de n-1 caisses. Par récursivité, tous les sous-états qui provoquent une pénalité seront trouvés.

Application

Un exemple de pénalité déduite est illustré sur la Figure 9.7. Celle-ci représente la copie e temp de l'état en cours (en haut à gauche) qui possède une estimation de 189. Chaque fois qu'une pénalité est appliquée sur l'état en cours, les caisses correspondantes sont supprimées de e temp et d'autres pénalités qui correspondent aux caisses restantes peuvent ensuite être appliquées. Au total, la pénalité déduite de l'état est de 10+6+4=20. L'estimation de la distance restante de l'état est donc de h(n)=estimation+penalitededuite=189+20=209 .

Chapitre 10 Pré-traitement

Table des estimations

La table des estimations correspond à la matrice M que nous avons construite lors du Chapitre 7. Celle-ci nous permet de connaître l'estimation du coût nécessaire pour pousser une caisse de la position relative i vers la position relative j d'un niveau.

Pénalités

Les pénalités correspondent aux sous-états pénalisés du Chapitre 9. En général, plus le solveur connait de pénalités avant de commencer à résoudre un niveau et moins l'arbre de recherche sera grand. La recherche passive de pénalités que nous avons vue dans la Section 9.2.1 permet de détecter des pénalités avant même de construire l'arbre de recherche.

Chapitre 11 Post-traitement

Itération du parcours IDA*

Nous avons vu dans la Section 6.5 que le parcours IDA* procédait à plusieurs itérations du parcours A*, avec une valeur f max progressive, dans le but de limiter au mieux les efforts de chaque itération. Il arrive parfois que des millions de nœuds soient nécessaires pour qu'une itération de A* se termine entièrement sans trouver de solution pour un certain f max . Celui-ci va alors être incrémenté pour l'itération suivante du parcours A*.

Pénalités probables

11.2.1 Positions fréquentes

  1. Les 15 positions les plus utilisées, excepté les positions qui correspondent aux goals.
  2. Les 15 positions les plus utilisées, toutes positions confondues.

11.2.2 Sous-états probablement pénalisés

Chapitre 12 Optimisations

Macro-poussées

Dans la Section 7.1.3, le graphe connexe calculait la distance d'une caisse vers chacun des goals sans prendre en compte les autres caisses. Cette fois-ci, toutes les autres caisses devront être considérées comme des obstacles. Le graphe connexe amélioré sera donc créé à partir de l'état courant en considérant toutes les autres caisses comme si elles étaient des murs.
Contrairement à ce que l'on pourrait croire, on n'ajoute pas toutes les macro-poussées détectées dans un état. On ajoute uniquement celles qui ont l'air les plus prometteuses. Inspirée de l'ordonnancement des goals deDemaret (2007), cette méthode n'autorise que les macro-poussées des caisses vers les goals qui sont cernés, sur les 4 positions directement voisines, par le plus de caisses et de murs.

Élagage

Chapitre 13 Résultats

Généralités

Tableau des résultats

  1. Le nombre de poussées de la meilleure solution existante provient deOriginalHighScore (Pas d'année) etExtraHighScore (Pas d'année). Son optimalité n'est pas garantie mais elle a de grandes chances de l'être.
  2. Le pré-processing représente le nombre de caisses utilisées lors de la recherche des sous-états pénalisés. Si le chiffre est 3, cela signifie que tous les sous-états pénalisés de 3 caisses et moins ont été trouvés avant de résoudre le niveau.
  3. L'itération IDA* en cours ( f max ) contient la dernière itération du parcours IDA* atteinte par le solveur.
  4. Le nombre de poussées/mouvements de la solution trouvée. Les solveurs bestPushes et Rolling Stone trouvent la solution optimale. Le solveur Talking Stone (2) créé par Jean-Noël Demaret trouve une bonne solution qui sera rarement optimale.
  5. Les nœuds explorés correspondent aux nombres de nœuds de l'arbre de recherche qui ont été explorés, lors de la dernière itération d'IDA*, avant de trouver une solution.

Le parcours lent

Le parcours rapide

Chapitre 14 Perspectives

Pénalités probables : améliorations

14.1.1 Détection d'ensembles de positions occupées simultanément

Nous avons parlé du post-traitement dans le Chapitre 11. L'une des méthodes proposée consistait à analyser l'arbre de recherche après l'exécution du solveur pour en déduire les sous-états dont la probabilité d'être pénalisés était forte.

14.1.2 Détection dynamique des pénalités probables

Pénalités restrictives

Une raison pour laquelle ces niveaux sont plus difficiles est qu'il arrive souvent que la pénalité d'un sous-état n'affecte qu'un certain sous-ensemble de goals (cf. Figure 9.5). Nous appellerons ces pénalités particulières des pénalités restrictives. Selon les méthodes utilisées, ces pénalités ne peuvent pas être gardées. Le but de la validation de pénalité est justement de ne garder que celles qui s'appliquent indépendamment de la destination des caisses.

Macro-Tunnels

La méthode des Macro-Tunnels provient deJunghanns (1999) et consiste à détecter des tunnels dans les niveaux. Un tunnel est une succession de positions qui forment une ligne bornée sur deux côtés par des murs tel qu'illustré sur la Figure 14.3. Si deux caisses s'engagent en même temps dans un tunnel, elles y resteront bloquées et formeront un deadlock.

Chapitre 15 Conclusion

Les évolutions de notre solveur sont possibles dans deux directions différentes. La première consiste à ajouter et améliorer les méthodes qui conservent l'optimalité des solutions. La deuxième consiste à ajouter des heuristiques très puissantes, telles que celles présentées par Jean-Noël Demaret dans Talking Stone (2)Demaret (2007), sur chaque état exploré de notre arbre de recherche. En ajoutant de bonnes heuristiques à l'efficacité du parcours décrit dans ce mémoire, il est fort probable que le nombre de solutions non-optimales trouvées soit assez important.