Algorithme pour optimiser un jeu de correspondance avec une file d'attente connue

J'essaie d'écrire un solveur en C # .NET pour un jeu appelé Flowerz. Pour votre référence, vous pouvez le jouer sur MSN, ici: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz . Je l'écris pour le plaisir, pas pour tout type de mission ou quoi que ce soit lié au travail. Pour cette raison, la seule limite est mon ordinateur (un noyau Intel i7, avec 8 Go de RAM). Il n'a pas besoin de fonctionner ailleurs, en ce qui me concerne.

En bref, ses règles sont comme ceci:

• Il y a une file d'attente remplie de fleurs colorées. Sa longueur est arbitraire
  • La file d'attente ne peut pas être influencée
  • La file d'attente est générée au début du niveau
• Les fleurs ont une ou deux couleurs.
  • S'il y a deux couleurs, alors il y a une couleur extérieure et une couleur intérieure. Dans le cas de deux couleurs, la couleur extérieure est utilisée pour l'appariement.
  • S'il y a une correspondance, la couleur extérieure disparaît et la fleur est maintenant une fleur de couleur unique avec la même couleur que la fleur intérieure
• Le but du jeu est de créer des matchs de trois (ou plus) de la même couleur
  • Lorsqu'une fleur d'une seule couleur fait partie d'un match, elle est supprimée du terrain de jeu, créant un espace vide
  • Vous pouvez faire correspondre une fleur d'une seule couleur avec la couleur extérieure d'une fleur bicolore. Dans ce cas, la fleur unicolore disparaît, la couleur extérieure de la fleur bicolore disparaît et la couleur intérieure reste
• Vous gagnez la manche lorsque la file d'attente est vide et qu'il reste au moins un espace vide
• Des correspondances en cascade sont possibles. Une cascade se produit lorsque trois (ou plus) fleurs extérieures disparaissent, et lorsque leurs couleurs intérieures forment une autre chaîne de 3 (ou plus de fleurs).
• Le terrain de jeu est toujours 7x7
• Certains espaces sur le terrain sont couverts de roches
  • Vous ne pouvez pas placer des fleurs sur des rochers
• La file d'attente peut également contenir une pelle que vous pouvez utiliser pour déplacer n'importe quelle fleur placée vers un espace inoccupé
  • Vous devez utiliser la pelle, mais vous n'avez pas vraiment à déplacer la fleur: il est parfaitement légal de la replacer d'où elle est venue
• La file d'attente peut également contenir un papillon coloré. Lorsque vous utilisez ce papillon sur une fleur, la fleur prend la couleur du papillon
  • L'application d'un papillon sur une fleur à deux couleurs fait que la fleur n'a qu'une seule couleur, à savoir celle du papillon
  • Vous pouvez gaspiller le papillon sur un espace vide ou une fleur qui a déjà cette couleur
• Vider le terrain ne gagne pas la partie

Le but du solveur est simple: trouver un moyen de vider la file d'attente, avec autant d'espaces restants sur le terrain que possible. Fondamentalement, l'IA joue le jeu pour moi. La sortie du solveur est une liste des mouvements qu'il a trouvés. Je ne m'intéresse pas au score, mais à survivre le plus longtemps possible, donc je m'intéresse aux mouvements qui laissent autant d'espaces ouverts que possible.

Inutile de dire que l'espace de recherche augmente rapidement plus la file d'attente est grande, il est donc hors de question d'avoir recours à une force brute. La file d'attente commence à 15 et augmente avec 5 tous les deux ou trois niveaux, si je me souviens bien. Et, bien sûr, placer la première fleur sur (0,0) et la seconde sur (0,1) est différent de placer la première sur (1,0) et la deuxième fleur sur (0,0), surtout lorsque le champ est déjà peuplé de fleurs d'un cycle précédent. Une décision aussi simple pourrait faire la différence en la rendant ou non.

Mes questions sont les suivantes:

• Quel genre de problème est-ce? (pensez vendeur ambulant, sac à dos ou autre problème combinatoire). Le savoir pourrait rendre mon Google-fu un peu meilleur.
• Quel type d'algorithme pourrait me donner de bons résultats, rapidement?

En ce qui concerne ce dernier: au début, j'ai essayé d'écrire mon propre algorithme heuristique (essentiellement: comment pourrais-je le résoudre, si je connaissais la file d'attente?), Mais cela se traduit par de nombreux cas marginaux et des correspondances de score que je pourrais manquer.

Je pensais utiliser un algorithme génétique (parce que je sais au moins comment l'utiliser ...), mais j'ai du mal à décider d'une représentation binaire de la carte. Ensuite, il y a le problème du croisement, mais cela peut être résolu avec un opérateur de croisement ordonné ou un type d'opération similaire.

Je suppose que le solveur doit toujours connaître la configuration de la carte et la file d'attente qu'il essaie de vider.

Je connais quelques autres algorithmes heuristiques tels que les réseaux de neurones et les systèmes de logique floue, mais je n'ai pas l'expérience pour savoir lequel est le mieux applicable, ou s'il y en a d'autres qui sont mieux adaptés à la tâche à accomplir.

À première vue , cela me semble être un problème de recherche d'agent unique . C'est-à-dire: vous avez un agent (le "joueur" IA). Il y a un état de jeu représentant l'état du plateau de jeu et de la file d'attente, et vous avez une fonction successeur qui peut générer de nouveaux états à partir d'un état donné.

Il existe également un critère d'objectif qui vous indique quand l'état est l'état "résolu". Et un coût de chemin - le coût de l'avancement vers un état donné (toujours "1 mouvement" dans ce cas).

Un casse-tête prototype de ce genre est le 15 Puzzle . Et la manière typique de le résoudre est avec une recherche éclairée - par exemple, la recherche heuristique classique A * et ses variantes.

Cependant, il y a un problème avec cette approche à première vue. Des algorithmes comme A * sont conçus pour vous donner le chemin le plus court vers un objectif (par exemple: le plus petit nombre de mouvements). Dans votre cas, le nombre de coups est toujours fixe - il n'y a pas de chemin le plus court - donc une recherche heuristique vous donnera juste un chemin vers une partie terminée.

Ce que vous voulez, c'est une séquence de mouvements qui vous donne le meilleur état de jeu terminé.

Donc, ce que vous devez faire, c'est tourner un peu le problème. Au lieu que le plateau de jeu soit "l'état", la séquence de mouvements devient "l'état". (C'est-à-dire: placer les articles dans la file d'attente aux positions "D2, A5, C7, B3, A3, ...")

Cela signifie que nous ne nous soucions pas vraiment de la façon dont ces états sont générés. La carte elle-même est accessoire, requise uniquement pour évaluer la qualité d'un état donné.

Cela transforme le problème en un problème d'optimisation , qui peut être résolu avec un algorithme de recherche local (ce qui signifie essentiellement créer des états autour d'un état donné et sélectionner le meilleur état, sans se soucier du chemin entre les états.)

Le casse-tête prototype de ce genre est le casse-tête des huit reines .

Dans cette classe de problème, vous recherchez l'espace d'état pour trouver une bonne solution, où "bon" est évalué par une fonction objective (également appelée fonction d'évaluation ou, pour les algorithmes génétiques, une fonction de fitness ).

Pour votre problème, une fonction objective peut renvoyer une valeur comprise entre 0 et N, pour le nombre d'éléments de la file d'attente qui ont été utilisés avant d'atteindre un état d'échec (où N est la longueur de la file d'attente). Et, sinon, une valeur de N + M, où M est le nombre d'espaces vides laissés sur la carte après que la file d'attente est vide. Ainsi, plus la valeur est élevée, plus la solution est «objectivement meilleure».

(Il convient de noter, à ce stade, que vous devez optimiser la merde du code qui exécute le jeu - qui transforme un état en un tableau fini pouvant être utilisé pour la fonction objectif.)

En ce qui concerne les exemples d' algorithmes de recherche locaux : Le modèle de base est une recherche en escalade qui prend un état donné, le mute et se déplace vers l'état suivant qui donne un meilleur résultat.

Évidemment, cela peut rester bloqué dans les maximums locaux (et similaires). Dans cette forme, cela s'appelle une recherche locale gourmande . Il existe un tas de variantes pour faire face à ce problème et à d'autres ( Wikipédia vous a couvert ). Certains d'entre eux (par exemple, la recherche locale de faisceaux ) assurent le suivi de plusieurs états à la fois.

Une variation particulière à ce sujet est l' algorithme génétique ( Wikipedia ). Les étapes de base d'un algorithme génétique sont les suivantes:

1. Déterminez un moyen de convertir un état en une chaîne quelconque. Dans votre cas, cela peut être une chaîne de chiffres de longueur de file d'attente de 1 à 49 (représentant tous les emplacements possibles sur une carte 7x7, probablement stockés 1 octet chacun). (Votre pièce "pique" pourrait être représentée par deux entrées de file d'attente ultérieures, pour chaque phase du déplacement.)
2. Sélectionnez au hasard une population reproductrice, ce qui donne une probabilité plus élevée aux États qui ont une meilleure forme physique . La population reproductrice doit avoir la même taille que la population d'origine - vous pouvez choisir plusieurs fois les états de la population d'origine.
3. Jumeler les états de la population reproductrice (le premier va avec le deuxième, le troisième va avec le quatrième, etc.)
4. Sélectionnez au hasard des points de croisement pour chaque paire (une position dans la chaîne).
5. Créez deux descendants pour chaque paire en échangeant la partie de la chaîne après le point de croisement.
6. Mute aléatoirement chacun des états de la progéniture. Par exemple: choisissez au hasard de changer une position aléatoire dans la chaîne en une valeur aléatoire.
7. Répétez le processus avec la nouvelle population jusqu'à ce que la population converge vers une ou plusieurs solutions (ou après un nombre donné de générations, ou qu'une solution suffisamment bonne soit trouvée).

Une solution d'algorithme génétique se sent comme il pourrait être approprié pour votre problème - avec un certain ajustement. La plus grande difficulté que je vois est que, avec la représentation de chaîne ci-dessus, vous constaterez que la commutation des moitiés de queue d'états avec des moitiés avant très différentes entraînera probablement des états "morts" (en raison de mouvements conflictuels entre les deux moitiés, ce résultat dans un faible score de fitness).

Il est peut-être possible de surmonter ce problème. Une idée qui vient à l'esprit est qu'il est plus probable que les États ayant des moitiés avant similaires deviennent des couples reproducteurs. Cela pourrait être aussi simple que de trier la population reproductrice des États, avant de les jumeler. Cela peut également aider à déplacer progressivement la position probable du croisement, du début à la fin de la chaîne, à mesure que le nombre de générations augmente.

Il peut également être possible de proposer une représentation des mouvements dans un état qui soit plus résistant (peut-être même entièrement immunisé) à rencontrer l'état d'échec «le carré est plein». Représentant peut-être les mouvements sous forme de coordonnées relatives par rapport au mouvement précédent. Ou en ayant des mouvements, sélectionnez l'espace vide le plus proche de la position donnée.

Comme pour tous les problèmes d'IA non triviaux comme celui-ci, cela nécessitera un bricolage important.

Et, comme je l'ai mentionné précédemment, l'autre défi majeur consiste simplement à optimiser votre fonction objective. Rendre cela plus rapide vous permettra de rechercher une grande quantité d'espace et de rechercher des solutions aux jeux avec des files d'attente plus longues.

Pour cette réponse, en particulier pour obtenir toute la terminologie, j'ai dû creuser mon manuel universitaire d'IA, "Intelligence artificielle: une approche moderne" par Russell et Norvig. Je ne sais pas si c'est "bon" (je n'ai pas d'autre texte d'IA pour le comparer), mais ce n'est pas mauvais. Au moins c'est assez gros;)

Catégorisation

La réponse n'est pas facile. La théorie des jeux a certaines classifications pour les jeux, mais il ne semble pas y avoir de correspondance claire de 1: 1 pour ce jeu avec une théorie spéciale. C'est une forme spéciale de problème combinatoire.

Ce n'est pas un vendeur itinérant, qui déciderait d'une commande dans laquelle vous visitez des «nœuds» avec un certain coût pour atteindre le nœud suivant à partir du dernier. Vous ne pouvez pas réorganiser la file d'attente, ni utiliser tous les champs de la carte.

Le sac à dos ne correspond pas car certains champs deviennent vides lors de la mise en place de certains éléments dans le "sac à dos". C'est peut-être une forme étendue de cela, mais très probablement les algorithmes ne seront pas applicables à cause de cela.

Wikipedia donne quelques conseils sur la catégorisation ici: http://en.wikipedia.org/wiki/Game_theory#Types_of_games

Je le classerais comme «problème de contrôle optimal en temps discret» ( http://en.wikipedia.org/wiki/Optimal_control ), mais je ne pense pas que cela vous aidera.

Des algorithmes

Si vous connaissez vraiment la file d'attente complète, vous pouvez appliquer des algorithmes de recherche d'arborescence. Comme vous l'avez dit, la complexité du problème augmente très rapidement avec la longueur de la file d'attente. Je suggère d'utiliser un algorithme comme "la recherche en profondeur d'abord (DFS)", qui ne nécessite pas beaucoup de mémoire. Comme le score n'a pas d'importance pour vous, vous pouvez simplement vous arrêter après avoir trouvé la première solution. Pour décider quelle sous-branche rechercher en premier, vous devez appliquer une heuristique pour la commande. Cela signifie que vous devez écrire une fonction d'évaluation (par exemple: nombre de champs vides; plus celle-ci est sophistiquée, mieux c'est), qui donne un score pour comparer le prochain mouvement le plus prometteur.

Vous n'avez alors besoin que des pièces suivantes:

1. modèle de l'état du jeu, qui stocke toutes les informations du jeu (par exemple, état / carte du plateau, file d'attente, numéro / position du mouvement dans la file d'attente)
2. un générateur de coups, qui vous donne tous les coups valides pour un état de jeu donné
3. une fonction "faire bouger" et une fonction "annuler bouger"; qui appliquent / annulent un mouvement donné (valide) à un état de jeu. Alors que la fonction "do move" devrait stocker des "informations d'annulation" pour la fonction "undo". Copier l'état du jeu et le modifier à chaque itération ralentit considérablement la recherche! Essayez au moins de stocker l'état sur la pile (= variables locales, pas d'allocation dynamique en utilisant "nouveau").
4. une fonction d'évaluation, qui donne un score comparable pour chaque état du jeu
5. fonction de recherche

Voici une implémentation de référence incomplète pour une recherche en profondeur d'abord:

public class Item
{
    // TODO... represents queue items (FLOWER, SHOVEL, BUTTERFLY)
}

public class Field
{
    // TODO... represents field on the board (EMPTY or FLOWER)
}

public class Modification {
    int x, y;
    Field originalValue, newValue;

    public Modification(int x, int y, Field originalValue, newValue) {
        this.x = x;
        this.y = y;
        this.originalValue = originalValue;
        this.newValue = newValue;
    }

    public void Do(GameState state) {
        state.board[x,y] = newValue;
    }

    public void Undo(GameState state) {
        state.board[x,y] = originalValue;
    }
}

class Move : ICompareable {

    // score; from evaluation function
    public int score; 

    // List of modifications to do/undo to execute the move or to undo it
    Modification[] modifications;

    // Information for later knowing, what "control" action has been chosen
    public int x, y;   // target field chosen
    public int x2, y2; // secondary target field chosen (e.g. if moving a field)


    public Move(GameState state, Modification[] modifications, int score, int x, int y, int x2 = -1, int y2 = -1) {
        this.modifications = modifications;
        this.score = score;
        this.x = x;
        this.y = y;
        this.x2 = x2;
        this.y2 = y2;
    }

    public int CompareTo(Move other)
    {
        return other.score - this.score; // less than 0, if "this" precededs "other"...
    }

    public virtual void Do(GameState state)
    {
        foreach(Modification m in modifications) m.Do(state);
        state.queueindex++;
    }

    public virtual void Undo(GameState state)
    {
        --state.queueindex;
        for (int i = m.length - 1; i >= 0; --i) m.Undo(state); // undo modification in reversed order
    }
}

class GameState {
    public Item[] queue;
    public Field[][] board;
    public int queueindex;

    public GameState(Field[][] board, Item[] queue) {
        this.board = board;
        this.queue = queue;
        this.queueindex = 0;
    }

    private int Evaluate()
    {
        int value = 0;
        // TODO: Calculate some reasonable value for the game state...

        return value;
    }

    private List<Modification> SimulateAutomaticChanges(ref int score) {
        List<Modification> modifications = new List<Modification>();
        // TODO: estimate all "remove" flowers or recoler them according to game rules 
        // and store all changes into modifications...
        if (modifications.Count() > 0) {
            foreach(Modification modification in modifications) modification.Do(this);

            // Recursively call this function, for cases of chain reactions...
            List<Modification> moreModifications = SimulateAutomaticChanges();

            foreach(Modification modification in modifications) modification.Undo(this);

            // Add recursively generated moves...
            modifications.AddRange(moreModifications);
        } else {
            score = Evaluate();
        }

        return modifications;
    }

    // Helper function for move generator...
    private void MoveListAdd(List<Move> movelist, List<Modifications> modifications, int x, int y, int x2 = -1, int y2 = -1) {
        foreach(Modification modification in modifications) modification.Do(this);

        int score;
        List<Modification> autoChanges = SimulateAutomaticChanges(score);

        foreach(Modification modification in modifications) modification.Undo(this);

        modifications.AddRange(autoChanges);

        movelist.Add(new Move(this, modifications, score, x, y, x2, y2));
    }


    private List<Move> getValidMoves() {
        List<Move> movelist = new List<Move>();
        Item nextItem = queue[queueindex];
        const int MAX = board.length * board[0].length + 2;

        if (nextItem.ItemType == Item.SHOVEL)
        {

            for (int x = 0; x < board.length; ++x)
            {
                for (int y = 0; y < board[x].length; ++y)
                {
                    // TODO: Check if valid, else "continue;"

                    for (int x2 = 0; x2 < board.length; ++x2)
                    {
                        for(int y2 = 0; y2 < board[x].length; ++y2) {
                            List<Modifications> modifications = new List<Modifications>();

                            Item fromItem = board[x][y];
                            Item toItem = board[x2][y2];
                            modifications.Add(new Modification(x, y, fromItem, Item.NONE));
                            modifications.Add(new Modification(x2, y2, toItem, fromItem));

                            MoveListAdd(movelist, modifications, x, y, x2, y2);
                        }
                    }
                }
            }

        } else {

            for (int x = 0; x < board.length; ++x)
            {
                for (int y = 0; y < board[x].length; ++y)
                {
                    // TODO: check if nextItem may be applied here... if not "continue;"

                    List<Modifications> modifications = new List<Modifications>();
                    if (nextItem.ItemType == Item.FLOWER) {
                        // TODO: generate modifications for putting flower at x,y
                    } else {
                        // TODO: generate modifications for putting butterfly "nextItem" at x,y
                    }

                    MoveListAdd(movelist, modifications, x, y);
                }
            }
        }

        // Sort movelist...
        movelist.Sort();

        return movelist;
    }


    public List<Move> Search()
    {
        List<Move> validmoves = getValidMoves();

        foreach(Move move in validmoves) {
            move.Do(this);
            List<Move> solution = Search();
            if (solution != null)
            {
                solution.Prepend(move);
                return solution;
            }
            move.Undo(this);
        }

        // return "null" as no solution was found in this branch...
        // this will also happen if validmoves == empty (e.g. lost game)
        return null;
    }
}

Ce code n'est pas vérifié pour fonctionner, ni compilable ni complet. Mais cela devrait vous donner une idée de la façon de procéder. Le travail le plus important est la fonction d'évaluation. Plus il est sophistiqué, plus les mauvais "essais" que l'algorithme tentera (et devront annuler) plus tard. Cela réduit considérablement la complexité.

Si cela est trop lent, vous pouvez également essayer d'appliquer certaines méthodes de jeux à deux comme HashTables. Pour cela, vous devrez calculer une clé de hachage (itérative) pour chaque état de jeu que vous évaluez et marquer les états qui ne conduisent pas à une solution. Par exemple, chaque fois que la méthode Search () retourne "null", une entrée HashTable doit être créée et lorsque vous entrez Search (), vous vérifierez si cet état a déjà été atteint jusqu'à présent sans résultat positif et si tel est le cas, renvoyez "null" sans complément d'enquête. Pour cela, vous aurez besoin d'une énorme table de hachage et vous devrez accepter les "collisions de hachage" qui pourraient faire en sorte que vous ne trouviez probablement pas de solution existante, mais ce qui est très peu probable, si vos fonctions de hachage sont assez bonnes et votre table est assez grand (c'est un risque de risque calculable).

Je pense qu'il n'y a pas d'autre algorithme pour résoudre ce problème (tel que décrit par vous) plus efficace, en supposant que votre fonction d'évaluation est optimale ...