Algorytm optymalizacji gry meczowej ze znaną kolejką

Próbuję napisać solver w języku C # .NET dla gry znanej jako Flowerz. W celach informacyjnych możesz grać w MSN, tutaj: http://zone.msn.com/gameplayer/gameplayer.aspx?game=flowerz . Piszę to dla zabawy, nie do żadnego rodzaju zadania ani niczego związanego z pracą. Z tego powodu jedynym ograniczeniem jest mój komputer (rdzeń Intel i7 z 8 GB pamięci RAM). Moim zdaniem nie musi działać nigdzie indziej.

Krótko mówiąc, jego zasady są takie:

• Jest kolejka wypełniona kolorowymi kwiatami. Jego długość jest dowolna
  • Nie można wpływać na kolejkę
  • Kolejka jest generowana na początku poziomu
• Kwiaty mają jeden lub dwa kolory.
  • Jeśli są dwa kolory, to jest kolor zewnętrzny i kolor wewnętrzny. W przypadku dwóch kolorów do dopasowania służy kolor zewnętrzny.
  • Jeśli istnieje dopasowanie, wówczas kolor zewnętrzny znika, a kwiat jest teraz kwiatem jednokolorowym o tym samym kolorze co kwiat wewnętrzny
• Celem gry jest stworzenie meczów trzech (lub więcej) tego samego koloru
  • Kiedy kwiat jednego koloru jest częścią dopasowania, jest usuwany z pola gry, tworząc pustą przestrzeń
  • Możesz dopasować kwiat jednokolorowy do zewnętrznego koloru kwiatu dwukolorowego. W tym przypadku kwiat jednokolorowy znika, kolor zewnętrzny kwiatu dwukolorowego znika, a kolor wewnętrzny pozostaje
• Wygrywasz rundę, gdy kolejka jest pusta i pozostało co najmniej jedno puste miejsce
• Możliwe są mecze kaskadowe. Kaskada ma miejsce, gdy znikają trzy (lub więcej) zewnętrzne kwiaty, a ich wewnętrzne kolory tworzą kolejny łańcuch 3 (lub więcej) kwiatów.
• Pole gry to zawsze 7x7
• Niektóre pola na polu są pokryte skałami
  • Nie możesz stawiać kwiatów na skałach
• Kolejka może również zawierać łopatę, której można użyć do przeniesienia dowolnego umieszczonego kwiatu na wolne miejsce
  • Musisz użyć łopaty, ale tak naprawdę nie musisz przesuwać kwiatu: umieszczenie go dokładnie tam, gdzie przyszło
• Kolejka może również zawierać kolorowy motyl. Kiedy użyjesz tego motyla na kwiatku, kwiat uzyska kolor motyla
  • Nałożenie motyla na kwiat w dwóch kolorach powoduje, że kwiat otrzymuje tylko jeden kolor, a mianowicie kolor motyla
  • Możesz zmarnować motyla na pustą przestrzeń lub kwiat, który ma już ten kolor
• Wyczyszczenie pola nie wygrywa

Cel solvera jest prosty: znaleźć sposób na opróżnienie kolejki, z możliwie jak największą ilością miejsca na boisku. Zasadniczo AI gra dla mnie. Wyjście solvera to lista ruchów, które znaleziono. Nie interesuje mnie wynik, ale przetrwanie tak długo, jak to możliwe, dlatego interesują mnie ruchy, które pozostawiają tyle otwartych przestrzeni, ile to możliwe.

Nie trzeba dodawać, że przestrzeń wyszukiwania rośnie szybko, im większa staje się kolejka, więc brutalna siła nie wchodzi w rachubę. Kolejka zaczyna się od 15 i rośnie o 5 co dwa lub trzy poziomy, jeśli dobrze pamiętam. I oczywiście umieszczenie pierwszego kwiatu na (0,0) i drugiego na (0,1) różni się od umieszczenia pierwszego kwiatu na (1,0) i drugiego kwiatu na (0,0), szczególnie gdy pole jest już wypełnione kwiatami z wcześniejszej rundy. Taka prosta decyzja może mieć znaczenie w podejmowaniu decyzji lub nie.

Mam następujące pytania:

• Co to za problem? (pomyśl wędrowny sprzedawca, plecak lub jakiś inny problem kombinatoryczny). Wiedząc o tym, mój Google-fu może być trochę lepszy.
• Jaki algorytm może dać mi dobre wyniki, szybko?

W odniesieniu do tego ostatniego: na początku próbowałem napisać własny algorytm heurystyczny (w zasadzie: jak go rozwiązać, gdybym wiedział, że jest kolejka?), Ale powoduje to wiele przypadków przewagi i dopasowywania wyników, których mogę przegapić.

Myślałem o użyciu algorytmu genetycznego (bo przynajmniej wiem, jak go użyć ...), ale mam pewne problemy z decyzją o binarnej reprezentacji tablicy. Następnie pojawia się problem crossovera, który można rozwiązać za pomocą zamówionego operatora crossovera lub podobnego rodzaju operacji.

Domyślam się, że solver musi zawsze znać konfigurację płyty i kolejkę, którą próbuje opróżnić.

Znam kilka innych algorytmów heurystycznych, takich jak sieci neuronowe i systemy logiki rozmytej, ale brakuje mi doświadczenia, aby wiedzieć, który z nich najlepiej nadaje się do zastosowania lub czy istnieją inne, które lepiej pasują do danego zadania.

Na pierwszy rzut oka wydaje mi się, że jest to problem z wyszukiwaniem jednego agenta . To znaczy: masz jednego agenta („gracza” AI). Istnieje stan gry reprezentujący stan planszy i kolejki, a masz funkcję następcy, która może generować nowe stany z danego stanu.

Istnieją również kryteria celu, które informują, kiedy stan jest „rozwiązany”. Oraz koszt ścieżki - koszt przejścia do danego stanu (w tym przypadku zawsze „1 ruch”).

Jedną z takich prototypowych łamigłówek jest 15 Układanka . Typowym sposobem rozwiązania tego problemu jest świadome wyszukiwanie - na przykład klasyczny wyszukiwanie heurystyczne A * i jego warianty.

Jest jednak problem z tym podejściem na pierwszy rzut oka. Algorytmy takie jak A * mają na celu zapewnienie najkrótszej ścieżki do celu (na przykład: najmniejszej liczby ruchów). W twoim przypadku liczba ruchów jest zawsze stała - nie ma najkrótszej ścieżki - więc wyszukiwanie heurystyczne da ci tylko się ścieżkę do zakończonego meczu.

To, czego chcesz, to sekwencja ruchów, która zapewnia najlepszy ukończony stan gry.

Musisz więc nieco rozwiązać problem. Zamiast planszy będącej „państwem”, sekwencja ruchów staje się „stanem”. (Tj .: Umieść przedmioty w kolejce na pozycjach „D2, A5, C7, B3, A3, ...”)

Oznacza to, że tak naprawdę nie obchodzi nas, w jaki sposób generowane są te stany. Sama tablica jest przypadkowa, wymagana tylko do oceny jakości danego stanu.

To zmienia problem w optymalizacji , który można rozwiązać za pomocą lokalnego algorytmu wyszukiwania (co w zasadzie oznacza tworzenie stanów wokół danego stanu i wybieranie najlepszego stanu bez dbania o ścieżkę między stanami).

Prototypowa łamigłówka tego rodzaju to Eight Queens Puzzle .

W tej klasie problemu przeszukujesz przestrzeń stanu, aby znaleźć dobre rozwiązanie, w którym „dobre” jest oceniane przez funkcję celu (zwaną także funkcją oceny lub, w przypadku algorytmów genetycznych, funkcją sprawności ).

W przypadku Twojego problemu funkcja celu może zwrócić wartość od 0 do N dla liczby elementów w kolejce, które zostały wykorzystane przed osiągnięciem stanu awarii (gdzie N jest długością kolejki). A w przeciwnym razie wartość N + M, gdzie M jest liczbą pustych miejsc pozostawionych na planszy po pustej kolejce. Jako taki - im wyższa wartość, tym „obiektywnie lepsze” rozwiązanie.

(Warto w tym miejscu zauważyć, że należy zoptymalizować bzdury z kodu uruchamiającego grę - który zamienia stan w gotową planszę, którą można wykorzystać do funkcji celu).

Jeśli chodzi o przykłady lokalnych algorytmów wyszukiwania : Podstawowym wzorem jest wspinaczka wyszukiwanie podczas które przyjmuje dany stan, mutuje go i przechodzi do następnego stanu, który daje lepszy wynik.

Oczywiście może to utknąć w lokalnych maksimach (i tym podobnych). W tej formie nazywa się to chciwym lokalnym wyszukiwaniem . Istnieje wiele odmian, aby poradzić sobie z tym i innymi problemami ( Wikipedia ma na ciebie pokrycie ). Niektóre z nich (np. Lokalne wyszukiwanie wiązki ) śledzą wiele stanów jednocześnie.

Szczególną odmianą tego jest algorytm genetyczny ( Wikipedia ). Podstawowe kroki dla algorytmu genetycznego to:

1. Określ sposób przekonwertowania stanu na ciąg znaków. W twoim przypadku może to być ciąg cyfr długości kolejki od 1 do 49 (reprezentujących wszystkie możliwe miejsca na planszy 7x7, prawdopodobnie przechowywane 1 bajt każdy). (Twój „pik” może być reprezentowany przez dwa kolejne wpisy w kolejce dla każdej fazy ruchu.)
2. Losowo wybieraj populację hodowlaną, zwiększając prawdopodobieństwo stanów o lepszej kondycji . Populacja lęgowa powinna być tej samej wielkości, co populacja pierwotna - możesz wielokrotnie wybierać stany z pierwotnej populacji.
3. Sparuj stany w populacji hodowlanej (pierwsza z drugą, trzecia z czwartą itd.)
4. Losowo wybierz punkty podziału dla każdej pary (pozycja w ciągu).
5. Utwórz dwa potomstwo dla każdej pary, zamieniając część struny za punktem podziału.
6. Losowo mutuj każdy ze stanów potomnych. Na przykład: losowo wybierz, aby zmienić losową pozycję w ciągu na losową wartość.
7. Powtarzaj ten proces z nową populacją, aż populacja zbiega się w jednym lub większej liczbie rozwiązań (lub po określonej liczbie pokoleń lub znalezieniu wystarczająco dobrego rozwiązania).

Roztwór algorytm genetyczny jest jak to może być odpowiednie dla swojego problemu - z jakiejś regulacji. Największą trudność, jaką widzę, polega na tym, że przy powyższej reprezentacji łańcucha przekonasz się, że zamiana tylnych połówek stanów z bardzo różnymi przednimi połówkami może doprowadzić do stanów „martwych” (z powodu sprzecznych ruchów między dwiema połówkami, które skutkują z niskim wynikiem fitness).

Być może uda się rozwiązać ten problem. Jednym z pomysłów, który przychodzi na myśl, jest zwiększenie prawdopodobieństwa, że ​​stany o podobnych przednich połowach staną się parami hodowlanymi. Może to być tak proste, jak posortowanie populacji lęgowej stanów przed ich połączeniem. Może to również pomóc w stopniowym przesuwaniu prawdopodobnej pozycji zwrotnicy od początku do końca łańcucha, w miarę wzrostu liczby generacji.

Może być również możliwe przedstawienie reprezentacji ruchów w stanie, który jest bardziej odporny (być może nawet całkowicie odporny) na napotkanie stanu błędu „kwadrat jest pełny”. Być może reprezentuje ruchy jako współrzędne względne z poprzedniego ruchu. Lub mając ruchy, wybierz najbliższe puste miejsce do danej pozycji.

Podobnie jak w przypadku wszystkich nietrywialnych problemów AI, będzie to wymagało znacznego majsterkowania.

I, jak wspomniałem wcześniej, innym ważnym wyzwaniem jest po prostu optymalizacja funkcji celu. Przyspieszenie tego pozwoli ci przeszukiwać dużą ilość miejsca i szukać rozwiązań dla gier z dłuższymi kolejkami.

Aby odpowiedzieć na tę odpowiedź, w szczególności aby uzyskać prawidłową terminologię, musiałem wykopać mój uniwersytecki podręcznik sztucznej inteligencji „Sztuczna inteligencja: nowoczesne podejście” Russella i Norviga. Nie jestem pewien, czy jest „dobry” (nie mam żadnych innych tekstów AI do porównania), ale nie jest źle. Przynajmniej jest dość duży;)

Kategoryzacja

Odpowiedź nie jest łatwa. Teoria gier ma pewne klasyfikacje dla gier, ale wydaje się, że nie ma wyraźnego dopasowania 1: 1 dla tej gry do specjalnej teorii. Jest to specjalna forma problemu kombinatorycznego.

To nie podróżujący sprzedawca, który decydowałby o zamówieniu, w którym odwiedzasz „węzły” z pewnym kosztem dotarcia do następnego węzła z ostatniego. Nie można zmienić kolejności kolejki ani użyć wszystkich pól na mapie.

Plecak nie pasuje, ponieważ niektóre pola stają się puste podczas umieszczania niektórych przedmiotów w „plecaku”. Być może jest to jakaś rozszerzona forma tego, ale najprawdopodobniej z tego powodu algorytmy nie będą miały zastosowania.

Wikipedia podaje kilka wskazówek na temat kategoryzacji: http://en.wikipedia.org/wiki/Game_theory#Types_of_games

Sklasyfikowałbym to jako „problem z optymalnym czasem dyskretnym” ( http://en.wikipedia.org/wiki/Optimal_control ), ale nie sądzę, żeby ci to pomogło.

Algorytmy

Jeśli naprawdę znasz całą kolejkę, możesz zastosować algorytmy wyszukiwania drzewa. Jak powiedziałeś, złożoność problemu rośnie bardzo szybko wraz z długością kolejki. Sugeruję użycie algorytmu typu „Wyszukiwanie w pierwszej kolejności (DFS)”, który nie wymaga dużej ilości pamięci. Ponieważ wynik nie ma dla ciebie znaczenia, możesz po prostu przestać po znalezieniu pierwszego rozwiązania. Aby zdecydować, którą gałąź należy najpierw przeszukać, należy zastosować heurystykę przy zamawianiu. Oznacza to, że powinieneś napisać funkcję oceny (np .: liczba pustych pól; im bardziej wyrafinowana, tym lepiej), która daje wynik do porównania, który następny ruch jest najbardziej obiecujący.

Potrzebujesz tylko następujących części:

1. model stanu gry, który przechowuje wszystkie informacje o grze (np. status planszy / mapa, kolejka, numer ruchu / pozycja w kolejce)
2. generator ruchów, który daje wszystkie ważne ruchy dla danego stanu gry
3. funkcja „wykonaj ruch” i „cofnij ruch”; które stosują / cofają dane (prawidłowe) przejście do stanu gry. Natomiast funkcja „do move” powinna przechowywać niektóre informacje „cofnąć” dla funkcji „cofnąć”. Kopiowanie stanu gry i modyfikowanie go w każdej iteracji znacznie spowalnia wyszukiwanie! Spróbuj przynajmniej zapisać stan na stosie (= zmienne lokalne, brak dynamicznej alokacji przy użyciu „nowego”).
4. funkcja oceny, która daje porównywalny wynik dla każdego stanu gry
5. funkcja wyszukiwania

Oto niepełna implementacja referencyjna dla wyszukiwania w pierwszej kolejności:

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

Ten kod nie został zweryfikowany pod kątem działania, nie można go też skompilować ani uzupełnić. Ale powinien dać ci pomysł, jak to zrobić. Najważniejszą pracą jest funkcja oceny. Im bardziej wyrafinowane, tym niewłaściwe „próby” algorytm spróbuje (i będzie musiał cofnąć) później. To niezwykle zmniejsza złożoność.

Jeśli jest to zbyt wolne, możesz również spróbować zastosować niektóre metody gier dwuosobowych jako HashTables. W tym celu musisz obliczyć (iteracyjny) klucz skrótu dla każdego ocenianego stanu gry i oznaczyć stany, które nie prowadzą do rozwiązania. Np. Za każdym razem, gdy metoda Search () zwraca „null”, należy utworzyć wpis HashTable, a wchodząc w Search () sprawdzasz, czy ten stan został już osiągnięty bez pozytywnego wyniku, a jeśli tak, zwracasz „null” bez Dalsze dochodzenie. W tym celu potrzebujesz ogromnej tabeli skrótów i musiałbyś zaakceptować „kolizje skrótów”, co może spowodować, że prawdopodobnie nie znajdziesz istniejącego rozwiązania, ale jest to bardzo mało prawdopodobne, jeśli twoje funkcje skrótu są wystarczająco dobre, a tabela jest wystarczająco duży (ryzyko ryzyka możliwego do obliczenia).

Myślę, że nie ma innego algorytmu do rozwiązania tego problemu (opisanego przez ciebie) bardziej wydajnego, zakładając, że twoja funkcja oceny jest optymalna ...