Comment résoudre de manière optimale l'énigme du comblement des crues ?

Question

J'aime jouer au jeu de puzzle Flood-It, qui peut être joué en ligne sur le site :

https://www.lemoda.net/javascript/flood-it/game.html

Il est également disponible sous forme de gadget iGoogle. Le but est de remplir l'ensemble du tableau avec le moins de remplissages successifs.

J'essaie d'écrire un programme qui puisse résoudre ce puzzle de manière optimale. Quelle est la meilleure façon d'aborder ce problème ? Idéalement, je veux utiliser le A* mais je n'ai aucune idée de ce que devrait être la fonction estimant le nombre d'étapes restantes. J'ai écrit un programme qui a effectué une recherche par force brute en profondeur 4 pour maximiser la surface remplie. Il a raisonnablement bien fonctionné et m'a battu dans la résolution du puzzle, mais je ne suis pas complètement satisfait de cet algorithme.

Des suggestions ? Merci d'avance.

Answer 1

À titre heuristique, vous pourriez construire un graphe où chaque nœud représente un ensemble de carrés contigus de même couleur, et où chaque nœud est relié à ceux qu'il touche. (Chaque arête est pondérée à 1). Vous pourriez ensuite utiliser un algorithme de recherche de chemin pour calculer la "distance" entre le nœud supérieur gauche et tous les autres nœuds. Ensuite, en examinant les résultats du remplissage en utilisant chacune des 5 autres couleurs, déterminez celle qui minimise la distance jusqu'au nœud le plus "éloigné", puisque ce sera probablement votre goulot d'étranglement.

Ajoutez le résultat de ce calcul au nombre de remplissages effectués jusqu'à présent, et utilisez-le comme heuristique A*.

Answer 2

Après avoir joué plusieurs fois au jeu, j'ai remarqué qu'une bonne stratégie consiste à toujours aller "en profondeur", à choisir la couleur qui va le plus loin dans le territoire non inondé.

Answer 3

Un algorithme naïf "avide" consiste à choisir l'étape suivante qui maximise le périmètre global de la région principale.

(Deux de mes amis intelligents y réfléchissaient l'autre jour et ont décidé que l'optimium pourrait être NP-hard (c'est-à-dire que vous devez le forcer brutalement) - je ne sais pas s'ils ont raison (je n'étais pas là pour entendre le raisonnement et je n'y ai pas réfléchi moi-même).

Notez que pour le calcul des étapes, je présume que l'algorithme union-find est votre ami, il rend le calcul d'une étape très rapide (voir par exemple cet article de blog ).

Answer 4

A* est juste une recherche de graphe hiérarchisé. Chaque nœud est un état du jeu, vous classez les nœuds en fonction d'une heuristique, et vous développez toujours le nœud au coût final le plus bas. Tant que votre heuristique ne sous-estime pas les coûts, la première solution que vous trouvez est garantie comme étant optimale.

Après avoir joué plusieurs fois à ces jeux, j'ai constaté qu'essayer de percer jusqu'au coin opposé puis tous les coins avait tendance à aboutir à une victoire. Donc une bonne estimation du coût de départ serait (coût jusqu'à présent) + un nombre suffisant de remplissages pour atteindre le coin opposé [note : pas minimum, juste suffisant. Il suffit de remplir avidement vers le coin pour calculer l'heuristique].

Answer 5

J'ai travaillé sur ce sujet, et après avoir fait fonctionner mon solveur, j'ai jeté un coup d'œil aux approches adoptées par les autres.

La plupart des solveurs existants sont heuristiques et ne garantissent pas l'optimalité. Les heuristiques s'intéressent au nombre de cases et à la distribution des couleurs non choisies, ou à la distance jusqu'à la case la plus éloignée. La combinaison d'une bonne heuristique avec la DFS bornée (ou la BFS avec lookahead) permet d'obtenir des solutions assez rapides pour la grille standard de 14x14.

J'ai adopté une approche légèrement différente car je souhaitais trouver le chemin optimal prouvé, et pas seulement un "bon" chemin. J'ai observé que l'espace de recherche croît en fait beaucoup plus lentement que le facteur de branchement de l'arbre de recherche, car il y a beaucoup de positions en double. (Avec une stratégie de recherche en profondeur, il est donc important de maintenir un historique pour éviter un travail redondant). Le facteur de branchement effectif semble plus proche de 3 que de 5.

La stratégie de recherche que j'ai adoptée consiste à effectuer une BFS jusqu'à une profondeur "médiane" où le nombre d'états devient infaisable, quelque part entre 11 et 13 mouvements. Ensuite, j'examine chaque état à la profondeur du point médian et j'effectue une nouvelle BFS en commençant par cet état comme racine. Ces deux recherches BFS peuvent être élaguées en éliminant les états trouvés dans les profondeurs précédentes, et la dernière recherche peut être limitée par la profondeur de la solution la mieux connue. (Une heuristique appliquée à l'ordre des sous-arbres examinés dans la deuxième étape serait probablement utile, elle aussi).

L'autre technique d'élagage qui s'est avérée être la clé d'un solveur rapide consiste simplement à vérifier s'il reste plus de N couleurs, si vous êtes à N pas ou moins de la meilleure solution actuelle.

Une fois que nous connaissons l'état du point médian qui se trouve sur le chemin d'une solution optimale, le programme peut effectuer une DFS en utilisant cet état médian comme objectif (et en élaguant tout chemin qui sélectionne un carré qui n'est pas dans le point médian.) Ou, il pourrait être possible de simplement construire les chemins dans les étapes de la BFS, au prix d'un peu de mémoire supplémentaire.

Mon solveur n'est pas super rapide, mais il peut trouver une solution optimale garantie en quelques minutes au maximum. (Voir http://markgritter.livejournal.com/673948.html ou le code à http://pastebin.com/ZcrS286b .)