Algoritmo para optimizar un juego de partidos con cola conocida

Estoy tratando de escribir un solucionador en C # .NET para un juego conocido como Flowerz. Para su referencia, puede jugarlo en MSN, aquí: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz . Lo escribo por diversión, no para ningún tipo de tarea ni nada relacionado con el trabajo. Debido a esto, el único límite es mi computadora (un núcleo Intel i7, con 8GB de RAM). No necesita ejecutarse en ningún otro lugar, en lo que a mí respecta.

En resumen, sus reglas son así:

• Hay una cola llena de flores de colores. Su longitud es arbitraria
  • La cola no puede ser influenciada
  • La cola se genera al comienzo del nivel.
• Las flores tienen uno o dos colores.
  • Si hay dos colores, entonces hay un color externo y un color interno. En el caso de dos colores, el color exterior se usa para hacer coincidir.
  • Si hay una coincidencia, el color exterior desaparece y la flor ahora es una flor de un solo color con el mismo color que la flor interior.
• El objetivo del juego es crear combinaciones de tres (o más) del mismo color.
  • Cuando una flor de un solo color es parte de un partido, se elimina del campo de juego, creando un espacio vacío
  • Puede hacer coincidir una flor de un solo color con el color exterior de una flor de dos colores. En este caso, la flor de un solo color desaparece, el color exterior de la flor de dos colores desaparece y el color interno permanece
• Ganas la ronda cuando la cola está vacía y queda al menos un espacio vacío
• Las coincidencias en cascada son posibles. Una cascada es cuando desaparecen tres (o más) flores externas, y cuando sus colores internos forman otra cadena de 3 (o más flores).
• El campo de juego es siempre 7x7
• Algunos espacios en el campo están cubiertos por rocas.
  • No puedes colocar flores en las rocas
• La cola también puede contener una pala que puede usar para mover cualquier flor colocada a un espacio desocupado
  • Tienes que usar la pala, pero en realidad no tienes que mover la flor: es perfectamente legal volver a colocarla de donde vino
• La cola también puede contener una mariposa de color. Cuando usas esta mariposa en una flor, la flor adquiere el color de la mariposa.
  • Al aplicar una mariposa a una flor con dos colores, la flor obtiene un solo color, es decir, el de la mariposa.
  • Puedes desperdiciar la mariposa en un espacio vacío o en una flor que ya tiene este color.
• Despejar el campo no gana el juego

El objetivo del solucionador es simple: encontrar una manera de vaciar la cola, con tantos espacios sobrantes en el campo de juego como sea posible. Básicamente, la IA juega el juego para mí. La salida del solucionador es una lista con los movimientos que encontró. No estoy interesado en la puntuación, pero en sobrevivir el mayor tiempo posible, por lo tanto, estoy interesado en los movimientos que dejan tantos espacios abiertos como sea posible.

No es necesario decir que el espacio de búsqueda crece rápidamente a medida que aumenta la cola, por lo que una fuerza bruta está fuera de discusión. La cola comienza en 15 y crece con 5 cada dos o tres niveles, si no recuerdo mal. Y, por supuesto, colocar la primera flor en (0,0) y la segunda en (0,1) es diferente de colocar la primera en (1,0) y la segunda flor en (0,0), especialmente cuando el campo ya está poblado con flores de una ronda anterior. Una decisión tan simple podría marcar la diferencia al tomarla o no.

Las preguntas que tengo son las siguientes:

• ¿Qué tipo de problema es este? (piense en un vendedor ambulante, una mochila o algún otro problema combinatorio). Saber esto podría hacer que mi Google-fu sea un poco mejor.
• ¿Qué tipo de algoritmo podría darme buenos resultados, rápido?

Con respecto a lo último: al principio, traté de escribir mi propio algoritmo heurístico (básicamente: ¿cómo lo resolvería, si supiera la cola?), Pero eso resulta en muchos casos extremos y coincidencias de puntuación que podría perder.

Estaba pensando en usar un algoritmo genético (porque al menos sé cómo usar eso ...), pero tengo algunos problemas para decidir sobre una representación binaria del tablero. Luego está el problema del crossover, pero eso se puede resolver con un operador de crossover ordenado o un tipo de operación similar.

Supongo que el solucionador siempre debe conocer la configuración de la placa y la cola que intenta vaciar.

Conozco algunos otros algoritmos heurísticos como las redes neuronales y los sistemas de lógica difusa, pero me falta la experiencia para saber cuál es el mejor aplicable, o si hay otros que son más adecuados para la tarea en cuestión.

A primera vista , esto me parece un problema de búsqueda de agente único . Es decir: tienes un agente (el "jugador" de IA). Hay un estado del juego que representa el estado del tablero y la cola del juego, y tiene una función sucesora que puede generar nuevos estados a partir de un estado dado.

También hay un criterio de objetivo que le indica cuándo el estado es el estado "resuelto". Y un costo de ruta : el costo de avanzar a un estado dado (siempre "1 movimiento" en este caso).

Un rompecabezas prototípico de este tipo es el 15 Puzzle . Y la forma típica de resolverlo es con una búsqueda informada , por ejemplo, la búsqueda heurística clásica A * y sus variantes.

Sin embargo, hay un problema con este enfoque a primera vista. Algoritmos como A * están diseñados para darle el camino más corto hacia una meta (por ejemplo: el menor número de movimientos). En su caso, el número de movimientos siempre es fijo, no hay un camino más corto, por lo que una búsqueda heurística solo le dará un camino hacia un juego completado.

Lo que quieres es una secuencia de movimientos que te brinde el mejor estado de juego completado.

Entonces, lo que debe hacer es cambiar un poco el problema. En lugar de que el tablero de juego sea el "estado", la secuencia de movimientos se convierte en el "estado". (Es decir: coloque los elementos en la cola en las posiciones "D2, A5, C7, B3, A3, ...")

Esto significa que realmente no nos importa cómo se generan esos estados. El tablero en sí es incidental, solo se requiere para evaluar la calidad de un estado determinado.

Esto convierte el problema en un problema de optimización , que se puede resolver con un algoritmo de búsqueda local (que básicamente significa crear estados alrededor de un estado determinado y seleccionar el mejor estado, sin importar la ruta entre los estados).

El rompecabezas prototípico de este tipo es el Rompecabezas de las ocho reinas .

En esta clase de problema, está buscando en el espacio de estado para encontrar una buena solución, donde "bueno" es evaluado por una función objetivo (también llamada función de evaluación o, para algoritmos genéticos, una función de aptitud ).

Para su problema, una función objetivo podría devolver un valor entre 0 y N, para el número de elementos en la cola que se utilizaron antes de alcanzar un estado de falla (donde N es la longitud de la cola). Y, de lo contrario, un valor de N + M, donde M es el número de espacios en blanco que quedan en el tablero después de que la cola esté vacía. Como tal, cuanto mayor sea el valor, "objetivamente mejor" será la solución.

(Vale la pena señalar, en este punto, que debes optimizar la basura del código que ejecuta el juego, que convierte un estado en un tablero terminado que se puede usar para la función objetivo).

En cuanto a los ejemplos de algoritmos de búsqueda locales : el patrón básico es una búsqueda de escalada que toma un estado dado, lo muta y se mueve hacia el siguiente estado que da un mejor resultado.

Obviamente, esto puede atascarse en los máximos locales (y similares). En esta forma se llama una búsqueda local codiciosa . Hay un montón de variaciones para lidiar con este y otros problemas ( Wikipedia lo tiene cubierto ). Algunos de los cuales (por ejemplo: búsqueda de haz local ) realizan un seguimiento de múltiples estados a la vez.

Una variación particular de esto es el algoritmo genético ( Wikipedia ). Los pasos básicos para un algoritmo genético son:

1. Determine alguna forma de convertir un estado en una cadena de algún tipo. En su caso, esto podría ser una cadena de dígitos de longitud de cola del 1 al 49 (que representa todas las ubicaciones posibles en un tablero de 7x7, probablemente almacenado 1 byte cada uno). (Su pieza de "espada" podría estar representada por dos entradas de cola subsiguientes, para cada fase del movimiento).
2. Seleccione aleatoriamente una población reproductora, lo que da una mayor probabilidad a los estados que tienen una mejor forma física . La población reproductora debe ser del mismo tamaño que la población original: puede elegir estados de la población original varias veces.
3. Empareje estados en la población reproductora (primero va con el segundo, tercero va con el cuarto, etc.)
4. Seleccione aleatoriamente puntos de cruce para cada par (una posición en la cadena).
5. Cree dos descendientes para cada par intercambiando la porción de la cadena después del punto de cruce.
6. Muta aleatoriamente cada uno de los estados descendientes. Por ejemplo: elija aleatoriamente cambiar una posición aleatoria en la cadena a un valor aleatorio.
7. Repita el proceso con la nueva población hasta que la población converja en una o más soluciones (o después de un número determinado de generaciones, o se encuentre una solución suficientemente buena).

Parece que una solución de algoritmo genético podría ser apropiada para su problema, con algunos ajustes. La mayor dificultad que veo es que, con la representación de la cadena anterior, encontrará que cambiar las mitades de cola de estados con mitades frontales muy diferentes probablemente resulte en estados "muertos" (debido a movimientos conflictivos entre las dos mitades, ese resultado en un bajo puntaje de condición física).

Quizás sea posible superar este problema. Una idea que viene a la mente es que es más probable que los estados con mitades frontales similares se conviertan en parejas reproductoras. Esto podría ser tan simple como clasificar la población reproductora de estados, antes de emparejarlos. También puede ayudar mover gradualmente la posición probable del cruce, desde el principio hasta el final de la cadena, a medida que aumenta el número de generación.

También es posible llegar a una representación de movimientos dentro de un estado que sea más resistente (tal vez incluso completamente inmune) a encontrar el estado de falla "cuadrado está lleno". Quizás representando movimientos como coordenadas relativas del movimiento anterior. O haciendo que los movimientos seleccionen el espacio vacío más cercano a la posición dada.

Al igual que con todos los problemas de IA no triviales como este, requerirá algunos ajustes significativos.

Y, como mencioné antes, el otro gran desafío es simplemente optimizar su función objetivo. Hacer esto más rápido le permitirá buscar una gran cantidad de espacio y buscar soluciones para juegos con colas más largas.

Para esta respuesta, particularmente para tener toda la terminología correcta, tuve que desenterrar el libro de texto de IA de mi universidad, "Inteligencia artificial: un enfoque moderno" de Russell y Norvig. No estoy seguro de si es "bueno" (no tengo ningún otro texto de IA para compararlo), pero no está mal. Al menos es bastante grande;)

Categorización

La respuesta no es fácil. La teoría del juego tiene algunas clasificaciones para los juegos, pero parece que no hay una coincidencia 1: 1 clara para ese juego con una teoría especial. Es una forma especial de problema combinatorio.

No es un vendedor ambulante, que estaría decidiendo un pedido en el que visita "nodos" con algún costo para llegar al siguiente nodo desde el último. No puede reordenar la cola, ni tiene que usar todos los campos en el mapa.

La mochila no coincide porque algunos campos se vacían al colocar algunos elementos en la "mochila". Entonces, tal vez sea una forma extendida de eso, pero lo más probable es que los algoritmos no sean aplicables debido a esto.

Wikipedia da algunos consejos sobre la categorización aquí: http://en.wikipedia.org/wiki/Game_theory#Types_of_games

Lo clasificaría como "problema de control óptimo en tiempo discreto" ( http://en.wikipedia.org/wiki/Optimal_control ), pero no creo que esto lo ayude.

Algoritmos

En caso de que realmente conozca la cola completa, puede aplicar algoritmos de búsqueda de árbol. Como dijiste, la complejidad del problema crece muy rápido con la longitud de la cola. Sugiero usar un algoritmo como "Búsqueda de profundidad primero (DFS)", que no requiere mucha memoria. Como el puntaje no le importa, puede detenerse después de haber encontrado la primera solución. Para decidir qué sub-rama buscar primero, debe aplicar una heurística para ordenar. Eso significa que debe escribir una función de evaluación (p. Ej .: número de campos vacíos; cuanto más sofisticado sea este, mejor), que otorgue una puntuación para comparar qué próximo movimiento es el más prometedor.

Entonces solo necesita las siguientes partes:

1. modelo del estado del juego, que almacena toda la información del juego (por ejemplo, estado / mapa del tablero, cola, número de movimiento / posición en la cola)
2. un generador de movimientos, que te ofrece todos los movimientos válidos para un estado de juego determinado
3. una función "mover" y "deshacer mover"; que aplican / deshacen un movimiento (válido) dado a un estado de juego. Mientras que la función "do move" debe almacenar alguna "información de deshacer" para la función "deshacer". ¡Copiar el estado del juego y modificarlo en cada iteración ralentiza significativamente la búsqueda! Intente al menos almacenar el estado en la pila (= variables locales, sin asignación dinámica usando "nuevo").
4. una función de evaluación, que proporciona una puntuación comparable para cada estado del juego
5. buscando función

Aquí hay una implementación de referencia incompleta para la búsqueda en profundidad:

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;
    }
}

No se verifica que este código funcione, ni es compilable ni completo. Pero debería darte una idea de cómo hacerlo. El trabajo más importante es la función de evaluación. Cuanto más sofisticado es, los "intentos" incorrectos que el algoritmo intentará (y tendrá que deshacer) más tarde. Esto reduce extremadamente la complejidad.

Si esto es demasiado lento, también puede intentar aplicar algunos métodos de juegos para dos personas como HashTables. Para eso, tendrás que calcular una clave hash (iterativa) para cada estado del juego que evalúes y marcar los estados que no conducen a una solución. Por ejemplo, cada vez antes de que el método Search () devuelva "nulo", debe crearse una entrada HashTable y, al ingresar Buscar (), verificaría si este estado ya se ha alcanzado hasta ahora sin resultado positivo y, de ser así, devolverá "nulo" sin investigación exahustiva. Para esto, necesitará una gran tabla hash y tendrá que aceptar "colisiones hash", lo que podría causar que probablemente no encuentre una solución existente, pero que es muy poco probable si sus funciones hash son lo suficientemente buenas y su tabla es suficientemente grande (es un riesgo de riesgo calculable).

Creo que no hay otro algoritmo para resolver este problema (según lo descrito por usted) más eficiente, asumió que su función de evaluación es óptima ...