Tworzę prostą implementację MiniMax w funkcjonalnym języku programowania Elixir. Ponieważ istnieje wiele gier o doskonałej wiedzy (kółko i krzyżyk, connect-four, warcaby, szachy itp.), Ta implementacja może stanowić podstawę do tworzenia gier AI dla każdej z tych gier.
Jednym z problemów, przed którymi stoję, jest jednak prawidłowe przechowywanie stanu gry w funkcjonalnym języku. Te gry dotyczą głównie dwuwymiarowych plansz, na których często występują następujące operacje:
- Przeczytaj zawartość określonego miejsca na planszy
- Zaktualizuj zawartość określonego miejsca na planszy (przy zwrocie nowej możliwości ruchu)
- Biorąc pod uwagę zawartość jednej lub więcej lokalizacji, które są połączone z bieżącą lokalizacją (tj. Następną lub poprzednią lokalizacją poziomą, pionową lub ukośną)
- Biorąc pod uwagę zawartość wielu połączonych lokalizacji w dowolnym kierunku.
- Biorąc pod uwagę zawartość całych plików, szeregów i przekątnych.
- Obracanie lub odbicie lustrzane tablicy (aby sprawdzić symetrie, które dają taki sam wynik jak coś już obliczonego).
Większość języków funkcjonalnych wykorzystuje Listy Połączone i Krotki jako podstawowe elementy składowe wieloelementowych struktur danych. Wydają się jednak bardzo źle wykonane do tej pracy:
- Listy połączone mają czas wyszukiwania O (n) (liniowy). Ponadto, ponieważ nie możemy „skanować i aktualizować tablicy” jednym ruchem po tablicy, używanie list wydaje się bardzo niepraktyczne.
- Krotki mają czas wyszukiwania O (1) (stały). Jednak reprezentowanie planszy jako krotki o stałym rozmiarze sprawia, że bardzo trudno jest iterować po szeregach, plikach, przekątnych lub innych rodzajach kolejnych kwadratów. Ponadto, zarówno Elixir, jak i Haskell (które są dwoma znanymi mi językami funkcjonalnymi) nie mają składni do odczytania n- tego elementu krotki. Uniemożliwiłoby to napisanie dynamicznego rozwiązania, które działałoby dla tablic o dowolnej wielkości.
Elixir ma wbudowaną strukturę danych Map (a Haskell ma Data.Map
), która umożliwia O (log n) (logarytmiczny) dostęp do elementów. Teraz używam mapy z x, y
krotkami, które przedstawiają pozycję jako klucze.
To „działa”, ale niewłaściwe jest nadużywanie map w ten sposób, chociaż nie wiem dokładnie, dlaczego. Szukam lepszego sposobu na przechowywanie dwuwymiarowej planszy w funkcjonalnym języku programowania.