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.