Struktura danych dla dwuwymiarowych gier planszowych w językach funkcjonalnych

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, ykrotkami, 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.

A Mapjest tutaj dokładnie właściwą bazą danych. Nie jestem pewien, dlaczego to sprawiało, że czułeś się niespokojny. Ma dobre czasy wyszukiwania i aktualizacji, ma dynamiczny rozmiar i bardzo łatwo jest tworzyć pochodne struktury danych. Na przykład (w haskell):

filterWithKey (\k _ -> (snd k) == column) -- All pieces in given column
filterWithKey (\k _ -> (fst k) == row)    -- All pieces in given row
mapKeys (\(x, y) -> (-x, y))              -- Mirror

Inną rzeczą, która często jest trudna do zrozumienia dla programistów, gdy zaczynają programowanie z pełną niezmiennością, jest to, że nie trzeba trzymać się tylko jednej struktury danych. Zazwyczaj wybierasz jedną strukturę danych jako „źródło prawdy”, ale możesz tworzyć dowolną liczbę pochodnych, nawet pochodnych pochodnych, i wiesz, że będą one zsynchronizowane tak długo, jak tego potrzebujesz.

Oznacza to, że możesz użyć Mapnajwyższego poziomu, a następnie przełączyć się na Listslub Arraysdo analizy wierszy, a następnie Arrayszindeksować w inny sposób do analizy kolumn, a następnie maski bitów do analizy wzorców, a następnie Stringsdo wyświetlania. Dobrze zaprojektowane programy funkcjonalne nie przekazują żadnej struktury danych. Są to serie kroków, które uwzględniają jedną strukturę danych i emitują nową, która nadaje się do następnego kroku.

Tak długo, jak możesz wyjść z drugiej strony, wykonując ruch w formacie zrozumiałym dla najwyższego poziomu, nie musisz się martwić, jak bardzo zrestrukturyzujesz dane pomiędzy nimi. Jest niezmienny, więc możliwe jest prześledzenie ścieżki z powrotem do źródła prawdy na najwyższym poziomie.

Zrobiłem to niedawno w F # i skończyło się na jednowymiarowej liście (w F # to lista z pojedynczym połączeniem). W praktyce szybkość indeksatora listy O (n) nie stanowi wąskiego gardła dla rozmiarów tablic użytecznych dla ludzi. Eksperymentowałem z innymi typami, takimi jak tablica 2d, ale ostatecznie był to kompromis albo pisania własnego kodu sprawdzającego równość wartości, albo tłumaczenia rangi i pliku na indeks i z powrotem. To drugie było prostsze. Powiedziałbym, aby najpierw działał, a następnie zoptymalizować typ danych w razie potrzeby. Prawdopodobnie nie zrobi to wystarczająco dużej różnicy, aby miało znaczenie.

W końcu twoja implementacja nie powinna mieć tak dużego znaczenia, o ile operacje twojej tablicy są odpowiednio obudowane według typu tablicy i operacji. Oto na przykład, jak niektóre z moich testów mogą wyglądać, aby skonfigurować tablicę:

let pos r f = {Rank = r; File = f} // immutable record type
// or
let pos r f = OnBoard (r, f) // algebraic type
...
let testBoard =
    Board.createEmpty ()
    |> Board.setPiece p (pos 1 2)
    |> ...

W przypadku tego kodu (lub dowolnego kodu wywołującego) nie ma znaczenia, w jaki sposób tablica była reprezentowana. Tablica jest reprezentowana przez operacje na niej bardziej niż jej podstawową strukturę.