Le taquin est un problème assez classique en intelligence artificielle. D’une part parce qu’il est très facile à modéliser, d’autre part parce que sa résolution est un problème NP-Complet. Pour rappel, le jeu du taquin est constitué d’un ensemble de palets et d’un trou appelé “blanc” qu’il faut remettre dans le bon ordre. Le seul déplacement légal consiste à déplacer un palet adjacent au blanc vers le blanc.
Une approche naïve consiste à faire une recherche en profondeur de la solution, jusqu’à atteindre la position souhaitée. Cela pose évidemment des problèmes divers… Comment éviter les boucles, etc. Je ne parlerais pas trop ici de cette solution, parce qu’elle est très loin d’être satisfaisante. Pour donner une idée de son inefficacité, il faut s’imaginer que cela correspond à lister toutes les successions de déplacements possibles (en évitant les boucles) et tester à chaque fois si cette succession de déplacements aboutit à la solution.
Intelligence Artificielle Distribuée
L’approche que je vais présenter ici est davantage basée sur la réactivité que l’analyse en profondeur d’un problème. Vous pouvez trouver le code source ici. Il n’est pas commenté, mais ce billet fait office de commentaire.
Nous allons essayer d’agir le plus vite possible, en essayant de faire en sorte que cette activité va diminuer l’entropie du système, c’est à dire nous approcher de la solution. L’entropie dont je parle peut-être vue ici comme une mesure du chaos qui règne dans la situation actuelle du taquin. Cela peut s’approcher de l’entropie de Shannon ou encore dans une certaine mesure à la complexité de Kolmogorov. En effet, on peut considérer qu’un taquin résolu possède une entropie minimale : la quantité minimale d’information nécessaire pour décrire sa situation est minimale ; chaque palet étant dans la bonne case, il suffit de dire “taquin de taille N”, ou de façon encore plus compacte : “N”. Inversement, un taquin très mélangé, chaque palet est dans une mauvaise case, il va falloir préciser la position de chaque palet : “{4,5,2,6,8,…}”.
L’entropie d’un taquin telle qu’elle est vue ici peut s’approcher comme la somme des distances de Manhattan de chaque palet à son but :
Si on déplace n’importe quel palet en s’arrangeant pour l’approcher de son but, alors l’entropie du palet diminue. Si on s’arrange, dans la foulée pour déplacer tous les palets de cette manière, l’entropie globale diminue, et on s’approche donc de la solution.
Pour mettre cette idée en pratique, on va utiliser une méthode de résolution introduite par Jacques Ferber en 1988 : l’éco-résolution. “Système multi-agents” est un nom plus connu, mais il ne s’agit pas tout à fait de la même chose. En fait, les systèmes multi-agents sont plus généraux que l’éco-résolution. Avec l’éco-résolution, on cherche à faire émerger le maximum de comportements de façon implicite, c’est à dire que la résolution d’un problème ou l’intelligence, complexe, qui se dégage d’un système (d’un jeu…) ne sera même pas explicitement décrite dans le code.
On parle de système multi-agents, parce qu’o va chercher à décomposer notre problème global (ici, résoudre le taquin) en un ensemble de sous-problèmes qui seront modélisés comme des entités dotées d’une perception (partielle ou complète) de leur environnement et de la capacité d’agir sur celui-ci. On appelle ces entités des agents. Ces agents ont donc un but qu’ils vont chercher à satisfaire par le biais d’un ensemble de moyens mit à leur disposition leur permettant d’analyser rapidement leur situation et d’adopter un comportement localement approprié. “Localement approprié”, ça veut dire qu’un agent est en fait très égoïste : il n’agit que pour se faire plaisir, se satisfaire. Il n’a aucune activité altruiste où il va soudainement adopter un comportement pour faire plaisir à un autre agent. Cela signifie d’un point de vue plus formel que l’activité de recherche de satisfaction des agents, prise individuellement, est une fonction de recherche d’optimum local.
Dans le cas du taquin, on crée un agent pour chaque palet. Ces agents ont pour but de se déplacer sur leur case-but. Cela pose néanmoins quelques question. Quel palet déplacer en premier ? Quel direction lui faire prendre ? Que se passe-t-il si on veut déplacer un palet qui n’est pas adjacent au blanc ?
Le choix du palet
Cela pose directement la question de la possibilité – ou non – de déplacer un palet qui n’est pas adjacent au blanc. Comment faire ? Ou plus précisément : peut-on essayer de satisfaire un palet qui n’est pas adjacent au blanc ? La réponse est oui. Dans le cas où un palet n’est pas adjacent au blanc et où on souhaite satisfaire ce palet, ce dernier va essayer de se déplacer sur l’une de ses cases adjacentes, quitte à agresser, si besoin, un autre palet qui s’y trouverait.
Ensuite, le choix du palet à déplacer pose la question de l’ordonnancement de la satisfaction des palets. En effet, pourquoi essayer de satisfaire un palet plutôt qu’un autre ? En fait, la raison principale qui pourrait nous pousser à vouloir ordonnancer la satisfaction des palets est une question d’optimisation… Autrement dit, on peut chercher à satisfaire les palets dans un certain ordre, afin de réduire, progressivement, la taille du taquin. Typiquement, on va chercher à satisfaire les palets dans l’ordre suivant :
Cependant, cela n’est absolument pas indispensable, et cela peut même s’avérer contre-productif. Je rappelle qu’avec l’éco-résolution, on cherche à obtenir un maximum de comportements émergeants. Si on ordonnance explicitement la satisfaction des palets, alors cela fait un comportement émergeant de moins. Or, intuitivement, dans la mesure où les palets ne peuvent se déplacer que vers le blanc et que la position finale du blanc est en bas à droite (dans notre exemple), on comprend bien que les derniers palets à être satisfaits seront les palets du coin inférieur droit, et que par conséquent, la taille du taquin va se réduire naturellement, sans que l’on ait eu besoin de le préciser explicitement.
En outre, ordonnancer les palets demande, contrairement à ce qu’on peut penser, beaucoup plus de code explicite. En effet, il ne suffit pas de dire “on satisfait les palets dans l’ordre A, B, C, D…”, car imposer un ordre, sans apporter de comportements explicites supplémentaires va générer des boucles. Typiquement : si un palet A se satisfait juste avant le palet B, mais que lors de la satisfaction du palet B, le palet A retrouve sa précédente position, et inversement, alors, il n’y a aucune raison que lors de la satisfaction suivante, les choses se passent autrement. Et ainsi, on aura obtenu une boucle dans laquelle les palets A et B se passent le relai de la satisfaction indéfiniment. Il faudra donc implémenter explicitement des comportements supplémentaires pour éviter ce genre d’écueils, et cela peut s’avérer très complexe (c’est à dire : demander beaucoup de code), ce qui est contre-productif dans notre optique.
Est-il nécessaire de choisir un ordre particulier pour satisfaire les palets ? La réponse est non. Comme je l’ai expliqué plus haut, dès lors qu’on essaie de satisfaire un palet, n’importe lequel, en s’arrangeant pour que les déplacements provoqués par la fuite des palets agressés les approchent le plus possible de leur case-but, alors, l’entropie globale du problème va avoir tendance à diminuer, jusqu’à atteindre zéro, c’est à dire la solution.
Voilà donc déjà un problème de résolu : quel palet satisfaire en premier ? N’importe lequel. Attention néanmoins, quand je dis “n’importe lequel”, cela signifie vraiment “choisir un palet aléatoirement”. Par exemple choisir toujours le 1er palet dans une liste de palets non-satisfaits implique de créer un ordre précis, et on retombe dans les problèmes d’ordonnancement présentés plus haut.
Le choix du déplacement
Où déplacer notre palet ?
Comme dit précédemment, il faut essayer de réduire l’entropie du système. Pour ce faire, il faut calculer la distance de Manhattan entre la position actuelle du palet qui cherche à se satisfaire et sa destination. On choisira alors la case adjacente au palet qui est la plus proche de sa destination. Dans le cas où plusieurs cases sont à la même distance de la case de destination, alors on choisira la case la plus proche du blanc. Et dans le cas où plusieurs cases sont à la fois à équidistance de la case-but et du blanc, alors, on choisira n’importe laquelle (encore une fois : choix “réellement” aléatoire).
Ces choix “réellement” aléatoires ont une importance, car ils permettent d’assurer la robustesse du système. D’un point de vue général, un agent, face à un choix, doit choisir l’option qui lui est la plus favorable. Or comment reconnaître qu’une option lui est plus favorable qu’une autre ? Par le calcul. Dans le cas du taquin, on reconnaît le meilleur déplacement grâce à la distance de Manhattan calculée et propagée à travers l’environnement (les variables gradient et gradientblanc). Or, il peut arriver que le calcul réalisé n’est pas suffisant pour reconnaître quel est le meilleur choix. Pour donner un exemple simple, imaginez que vous allez au marché aux fruits pour acheter de belles pommes. Vous n’avez évidemment pas le droit de les goûter (ce qui reviendrait à réaliser résoudre le problème). Il vous faut donc deviner quelles sont les meilleures pommes. Pour ce faire, vous avez leur odeur, leur couleur, leur forme. Ce sont des appréciations faciles à obtenir. En revanche, si vous voulez calculer leur pH, leur poids, etc… Là, c’est beaucoup plus long et difficile. Dans notre histoire, c’est la même chose : certains calculs sont trop longs pour ce qu’ils apportent, dans ces cas là, on préfèrera choisir aléatoirement une des options, quitte à revenir en arrière plus tard. De toute façon, l’éco-résolution est robuste face aux intempéries.
Nous avons aussi des palets cherchant à fuir. Ceux-là vont globalement avoir le comportement inverse des palets cherchant à se satisfaire, c’est à dire qu’ils vont avant tout essayer de s’approcher du blanc puis de leur case-but. Le palet directement agressé par le palet cherchant à se satisfaire va également éviter la case-but de ce dernier. Il s’agit de simple bon sens : si vous voulez vous asseoir quelque part et demandez à quelqu’un de se déplacer parce qu’il est sur votre passage, il ne faut pas qu’il aille s’asseoir là où vous voulez vous mettre. Sinon, il faudra lui redemander.
Une dernière chose…
Avec ça, vous avez presque toute la théorie de base pour le taquin. Il ne reste qu’un détail : on a créé des boucles d’agression. C’est à dire qu’on a divers palets qui vont se satisfaire en “poussant”, en agressant les palets qui se trouvent sur leur passage. Il ne faut pas qu’un palet déjà agressé le soit de nouveau. Simplement, parce qu’à force, il aurait une dépression nerveuse qui conduirait à une boucle infinie. En effet : un palet déjà agressé n’a aucune raison de réagir autrement à une nouvelle agression : il agressera le palet qu’il a déjà agressé avant. Et ainsi de suite, créant une boucle.
Aussi, il convient de mettre en place un système “bloquant” les cases faisant partie d’une boucle d’agression. Un simple booléen “locked” suffit à provoquer cet effet. Les cases bloquées agiront comme des obstacles, des “montagnes” infranchissables et la propagation de l’agression suivra naturellement la pente décrite par les gradients des distances au blanc et aux différentes case-but.
