Minimax dla Bomberman

Rozwijam klon gry Bomberman i eksperymentuję z różnymi rodzajami sztucznej inteligencji. Najpierw przeszukiwałem przestrzeń stanu za pomocą A *, a teraz chcę wypróbować inne podejście z algorytmem Minimax. Mój problem polega na tym, że każdy artykuł minimax, który znalazłem, zakładał, że gracze się zmieniają. Ale w Bomberman każdy gracz wykonuje jakąś akcję jednocześnie. Myślę, że mógłbym wygenerować wszystkie możliwe stany dla jednego tyknięcia w grze, ale przy czterech graczach i 5 podstawowych akcjach (4 ruchy i miejsce bomby) daje to 5 ^ 4 stanów na pierwszym poziomie drzewa gry. Wartość ta będzie rosła wykładniczo z każdym kolejnym poziomem. Czy coś brakuje? Czy są jakieś sposoby na jego wdrożenie, czy powinienem używać zupełnie innego algorytmu? Dziękuję za wszelkie sugestie

Gry strategiczne w czasie rzeczywistym, takie jak bombowiec, mają trudności z AI. Chcesz, żeby był inteligentny, ale jednocześnie nie może być doskonały.

Jeśli AI jest idealna, twoi gracze będą sfrustrowani. Albo dlatego, że zawsze tracą, albo dostajesz .3 klatki na sekundę.

Jeśli nie jest wystarczająco inteligentny, twoi gracze się nudzą.

Moje zalecenie to mieć dwie funkcje AI, jedna, która określa, dokąd idzie AI, druga, która określa, kiedy najlepiej zrzucić bombę. Możesz użyć takich rzeczy, jak przewidywanie ruchu, aby ustalić, czy wróg zbliża się do miejsca, które będzie niebezpieczne, jeśli bomba zostanie upuszczona w bieżącym miejscu.

W zależności od trudności możesz zmodyfikować te funkcje, aby poprawić lub zmniejszyć trudność.

Jak zauważyłeś, Bomberman jest zbyt skomplikowany, aby można go było symulować jako grę turową. Ekstrapolacja każdej możliwej własnej decyzji oraz każdej możliwej decyzji każdego innego gracza po prostu nie działa.

Zamiast tego powinieneś raczej zastosować bardziej strategiczne podejście.

Powinieneś zadać sobie pytanie: W jaki sposób ludzki gracz podejmuje decyzje podczas gry w bombowiec? Zwykle gracz powinien przestrzegać czterech podstawowych priorytetów:

1. unikać obszarów wybuchowych bomb
2. umieszczać bomby, aby inni nie mogli uniknąć obszarów wybuchu
3. zbierać bonusy
4. umieszczać bomby, aby wysadzić skały

Pierwszy priorytet można spełnić, tworząc „mapę zagrożeń”. Po umieszczeniu bomby wszystkie pokryte nią płytki należy oznaczyć jako „niebezpieczne”. Im wcześniej bomba wybuchnie (pamiętaj o reakcjach łańcuchowych!), Tym wyższy poziom zagrożenia. Ilekroć AI zauważy, że znajduje się na polu o wysokim niebezpieczeństwie, powinna się odsunąć. Podczas rysowania ścieżki (z dowolnego powodu) należy unikać pól o wysokim poziomie niebezpieczeństwa (można to zrealizować poprzez sztuczne dodanie do nich wyższych kosztów ścieżki).

Obliczenia mapy niebezpieczeństw można dodatkowo ulepszyć, aby chronić AI przed głupimi decyzjami (takimi jak wchodzenie w obszary, z których trudno jest uciec, gdy w pobliżu znajduje się inny gracz).

To powinno już stworzyć rozsądną obronną AI. A co z przestępstwem?

Kiedy AI zdaje sobie sprawę, że jest w tej chwili dość bezpieczna, powinna zaplanować ofensywne manewry: powinna rozważyć, w jaki sposób może zwiększyć mapę niebezpieczeństwa wokół innych graczy, umieszczając bomby. Wybierając lokalizację do podłożenia bomby, powinna preferować bliskie lokalizacje, aby nie musiała się jak dotąd przemieszczać. Powinien także ignorować lokalizacje bomb, gdy wynikowa mapa niebezpieczeństwa nie pozwala na rozsądną drogę ucieczki.

Myślę, że mógłbym wygenerować wszystkie możliwe stany dla jednego tyknięcia w grze, ale przy czterech graczach i 5 podstawowych akcjach (4 ruchy i miejsce bomby) daje to 5 ^ 4 stanów na pierwszym poziomie drzewa gry.

Poprawny! Musisz przeszukać wszystkie akcje 5 ^ 4 (a nawet 6 ^ 4, ponieważ możesz chodzić w 4 kierunkach, zatrzymać się i „postawić bombę”?) Dla każdego tiku gry. ALE, gdy gracz już zdecydował się na ruch, wykonanie go zajmuje trochę czasu (np. 10 tyknięć w grze). W tym okresie liczba możliwości zmniejsza się.

Wartość ta będzie rosła wykładniczo z każdym kolejnym poziomem. Czy coś brakuje? Czy są jakieś sposoby na jego wdrożenie, czy powinienem używać zupełnie innego algorytmu?

Za pomocą tabeli skrótów można tylko raz obliczyć „poddrzewo” tego samego stanu gry. Wyobraź sobie, że gracz A chodzi w górę i w dół, podczas gdy wszyscy inni gracze „czekają”, kończysz w tym samym stanie gry. Jest to to samo, co dla „lewo-prawo” lub „prawo-lewo”. Przesunięcie „w górę, a potem w lewo” i „w lewo, a potem w górę” powoduje ten sam stan. Za pomocą tabeli skrótów możesz „ponownie wykorzystać” obliczony wynik dla stanu gry, który został już oceniony. To znacznie zmniejsza szybkość wzrostu. Matematycznie zmniejsza podstawę funkcji wzrostu wykładniczego. Aby dowiedzieć się, o ile zmniejsza to złożoność, spójrzmy na ruchy możliwe tylko dla jednego gracza w porównaniu z dostępnymi pozycjami na mapie (= różne stany gry), jeśli gracz może po prostu poruszać się w górę / w dół / w lewo / w prawo / stop .

głębokość 1: 5 ruchów, 5 różnych stanów, 5 dodatkowych stanów dla tej rekurencji

głębokość 2: 25 ruchów, 13 różnych stanów, 8 dodatkowych stanów dla tej rekurencji

głębokość 3: 6125 ruchów, 25 różnych stanów, 12 dodatkowych stanów dla tej rekurencji

Aby to sobie wyobrazić, odpowiedz sobie: do których pól na mapie można dotrzeć jednym ruchem, dwoma ruchami, trzema ruchami. Odpowiedź brzmi: wszystkie pola o maksymalnej odległości = 1, 2 lub 3 od pozycji początkowej.

Korzystając z HashTable, musisz ocenić każdy osiągalny stan gry (w naszym przykładzie 25 na głębokości 3) tylko raz. Podczas gdy bez HashTable musisz je oceniać wiele razy, co oznaczałoby 6125 ocen zamiast 25 na poziomie głębokości 3. Najlepsze: Po obliczeniu wpisu HashTable możesz go ponownie użyć w późniejszych krokach czasowych ...

Możesz także użyć poddrzewa „przycinania” stopniowego pogłębiania i przycinania alfa-beta, których nie warto szukać głębiej. W przypadku szachów zmniejsza to liczbę wyszukiwanych węzłów do około 1%. Krótkie wprowadzenie do przycinania alfa-beta można znaleźć jako film tutaj: http://www.teachingtree.co/cs/watch?concept_name=Alpha-beta+Pruning

Dobrym początkiem do dalszych badań jest http://chessprogramming.wikispaces.com/Search . Strona jest związana z szachami, ale algorytmy wyszukiwania i optymalizacji są takie same.

Kolejnym (ale złożonym) algorytmem AI - który byłby bardziej odpowiedni dla gry - jest „Uczenie się różnic w czasie”.

pozdrowienia

Stefan

PS: Jeśli zmniejszysz liczbę możliwych stanów gry (np. Bardzo mały rozmiar mapy, tylko jedna bomba na gracza, nic więcej), istnieje szansa na wstępne obliczenie oceny dla wszystkich stanów gry.

--edytować--

Możesz także użyć obliczonych offline wyników obliczeń minimax do wyszkolenia sieci neuronowej. Możesz też użyć ich do oceny / porównania ręcznie wdrożonych strategii. Na przykład możesz wdrożyć niektóre z sugerowanych „osobowości” i niektóre heurystyki, które wykrywają, w których sytuacjach strategia jest dobra. Dlatego powinieneś „klasyfikować” sytuacje (np. Stany gry). Można to również rozwiązać za pomocą sieci neuronowej: Trenuj sieć neuronową, aby przewidzieć, która ze strategii kodowanych ręcznie gra najlepiej w obecnej sytuacji i ją wykonać. To powinno przynieść niezwykle dobre decyzje w czasie rzeczywistym dla prawdziwej gry. Znacznie lepiej niż wyszukiwanie z ograniczeniem głębokości, które można osiągnąć inaczej, ponieważ nie ma znaczenia, ile czasu zajmują obliczenia offline (są przed grą).

- edytuj # 2 -

Jeśli przeliczysz tylko najlepsze ruchy co 1 sekundę, możesz także spróbować wykonać więcej planowania na wyższym poziomie. Co mam przez to na myśli? Wiesz, ile ruchów możesz wykonać w ciągu 1 sekundy. Możesz więc stworzyć listę dostępnych pozycji (np. Jeśli byłyby to 3 ruchy w ciągu 1 sekundy, miałbyś 25 dostępnych pozycji). Następnie możesz zaplanować: przejdź do „pozycji x i umieść bombę”. Jak sugerują niektórzy inni, możesz stworzyć mapę „niebezpieczeństwa”, która będzie używana dla algorytmu routingu (jak przejść do pozycji x? Która ścieżka powinna być preferowana [w większości przypadków możliwe są pewne warianty]). To mniej zużywa pamięć w porównaniu do ogromnej tabeli HashTable, ale daje mniej optymalne wyniki. Ponieważ jednak zużywa mniej pamięci, może być szybszy z powodu efektów buforowania (lepsze wykorzystanie pamięci podręcznych L1 / L2).

DODATKOWO: Możesz przeprowadzić wstępne wyszukiwania, które zawierają tylko ruchy dla jednego gracza, aby uporządkować warianty, które powodują utratę. Dlatego wyklucz wszystkich graczy z gry ... Przechowuj kombinacje, które każdy gracz może wybrać, nie tracąc. Jeśli są tylko przegrane ruchy, poszukaj kombinacji ruchów, w których gracz pozostaje przy życiu najdłużej. Aby przechowywać / przetwarzać tego rodzaju struktury drzewne, powinieneś użyć tablicy z wskaźnikami indeksu takimi jak to:

class Gamestate {
  int value;
  int bestmove;
  int moves[5];
};

#define MAX 1000000
Gamestate[MAX] tree;

int rootindex = 0;
int nextfree = 1;

Każdy stan ma „wartość” ewaluacyjną i łączy się z następnymi Gamestatami podczas ruchu (0 = stop, 1 = góra, 2 = prawo, 3 = dół, 4 = lewo), przechowując indeks tablicy w „drzewie” w ruchach [0 ] do ruchów [4]. Aby rekurencyjnie budować drzewo, mogłoby to wyglądać następująco:

const int dx[5] = { 0,  0, 1, 0, -1 };
const int dy[5] = { 0, -1, 0, 1,  0 };

int search(int x, int y, int current_state, int depth_left) {
  // TODO: simulate bombs here...
  if (died) return RESULT_DEAD;

  if (depth_left == 0) {
    return estimate_result();
  }

  int bestresult = RESULT_DEAD;

  for(int m=0; m<5; ++m) {
    int nx = x + dx[m];
    int ny = y + dy[m];
    if (m == 0 || is_map_free(nx,ny)) {
      int newstateindex = nextfree;
      tree[current_state].move[m] = newstateindex ;
      ++nextfree;

      if (newstateindex >= MAX) { 
        // ERROR-MESSAGE!!!
      }

      do_move(m, &undodata);
      int result = search(nx, ny, newstateindex, depth_left-1);
      undo_move(undodata);

      if (result == RESULT_DEAD) {
        tree[current_state].move[m] = -1; // cut subtree...
      }

      if (result > bestresult) {
        bestresult = result;
        tree[current_state].bestmove = m;
      }
    }
  }

  return bestresult;
}

Ten rodzaj struktury drzewa jest znacznie szybszy, ponieważ dynamiczne przydzielanie pamięci jest naprawdę bardzo wolne! Ale przechowywanie drzewa wyszukiwania jest również dość powolne ... Więc to jest bardziej inspiracja.

Czy pomogłoby to sobie wyobrazić, że wszyscy na zmianę?

Technicznie rzecz biorąc, faktycznie działają w systemie bazowym, ale ponieważ rzeczy są przeplatane i nakładają się, wydają się działać jednocześnie.

Pamiętaj również, że nie musisz uruchamiać AI po każdej klatce animacji. Wiele udanych gier casualowych uruchamia algorytm sztucznej inteligencji tylko co sekundę, dostarczając postaciom kontrolowanym przez AI informacje o tym, dokąd mają się udać lub co mają zrobić, a następnie informacje te są wykorzystywane do kontrolowania postaci AI na pozostałych ramkach.