Czy sztuczna inteligencja przypominająca szachy naprawdę nie ma zastosowania w turowych grach strategicznych?

Oczywiście, próba zastosowania algorytmu min-max na pełnym drzewie ruchów działa tylko w przypadku małych gier (przepraszam wszystkich entuzjastów szachów, przez „małe” nie mam na myśli „uproszczonego”). W typowych strategicznych grach turowych, w których plansza jest często szersza niż 100 płytek, a wszystkie elementy na boku mogą się poruszać jednocześnie, algorytm min-max nie ma zastosowania.

Zastanawiałem się, czy częściowy algorytm min-max, który ogranicza się do konfiguracji płyty N na każdej głębokości, nie może być wystarczająco dobry? Za pomocą algorytmu genetycznego może być możliwe znalezienie wielu konfiguracji płytki, które są dobre dla funkcji oceny. Mamy nadzieję, że te konfiguracje mogą być również dobre dla celów długoterminowych.

Byłbym zaskoczony, gdyby o tym wcześniej nie pomyślano i nie próbowano. Ma to? Jak to działa?

To zależy od mechaniki gry. Drzewo gry min-max może być ogólnie nie do zastosowania, ale może ma zastosowanie w niektórych obszarach. Często lokalizacje na mapie są strategicznie ważne. Min-max może obowiązywać na poziomie strategicznym, dla której z tych lokalizacji należy kontrolować. Na poziomie taktycznym, dla x kwadratów wokół każdej strategicznej lokalizacji, można użyć wartości min-max, aby zdecydować, w jaki sposób jednostki rozmieszczą się, aby je przejąć i obronić.

To nie jest algorytm minimax, jednak faceci odpowiedzialni za AI Killzone opublikowali artykuł oparty na funkcjach oceny pozycji, z których korzysta także niektóre szachy AI.

To bardzo proste, ponieważ wszystko, co robi, to wybiera pozycję na planszy w oparciu o aktualną wiedzę agenta. Jeśli więc niski poziom zdrowia agenta, pozycje znajdujące się dalej od wroga otrzymają wyższy wynik, ponieważ bardziej pożądane jest przebywanie poza zasięgiem wroga.

Artykuł można znaleźć w AI Game Programming Wisdom 3 i ma on tytuł Dynamic Tactical Position Assessment.

Szkic artykułu można znaleźć w Internecie tutaj:
http://www.cgf-ai.com/docs/straatman_remco_killzone_ai.pdf

Mam nadzieję, że to pomaga.

Nie sądzę, żeby to wystarczyło. Wybór konkretnych konfiguracji N, ile i które konfiguracje byłyby praktycznie niemożliwe w czymś tak złożonym. Pamiętaj, że jeśli twoja gra ma nieskończone zasoby lub coś podobnego, mogą istnieć kręgi w jej sposobie grania, co sprawia, że ​​wykorzystywanie takiej AI jest stosunkowo łatwe.

Sugerowałbym przynajmniej wdrożenie min-max z przycinaniem alfa-beta.

Bez wypróbowania go i stwierdzenia, że ​​jest to niepraktyczne (tj. Straszna wydajność) i bez większego doświadczenia w mechanice gry, nie rozumiem, dlaczego uważasz, że min-max nie ma zastosowania.

Rozmiar planszy jest potencjalnie problemem, ale w przypadku przycinania, odrzucanie ścieżek utraty umożliwia głębsze wyszukiwanie z taką samą ilością obliczeń, więc może większe obszary planszy nie będą stanowić problemu po przycięciu? Dodatkowo, zakładając, że sam rozmiar planszy jest problemem, może być przedwczesny, to nie tyle wielkość planszy, co złożoność mechaniki i liczba możliwych ruchów z każdej pozycji planszy. Jeśli twoja gra ma duży, ale słabo zaludniony obszar, liczba możliwych ruchów z każdego stanu planszy może się nieznacznie różnić, niż gdyby plansza była wystarczająco duża, aby pomieścić wszystkie elementy. Oczywiście, jeśli masz gigantyczną planszę, która jest wypełniona w 90% i wszystko może się poruszać w dowolnym miejscu za każdym razem, będzie to wymagało wielu poszukiwań.

Nie jestem również pewien, dlaczego jednoczesny ruch jest z natury problemem. Tak długo, jak przejdziesz z jednego dyskretnego stanu płyty do drugiego i będziesz mieć funkcję oceny, algorytm powinien być stosowany.

Zakładam, że i tak potrzebujesz funkcji oceny i bez względu na to, jakiego wyszukiwania używasz, funkcja oceny jest tam, gdzie prawdopodobnie zajmie się większość pracy. Algorytm min-max z przycinaniem sam w sobie jest bardzo prosty do wdrożenia, coś, co prawdopodobnie można zrobić za godzinę lub dwie, a znaczna część infrastruktury działa jak przechowywanie stanu płyty, ocena, generowanie ruchów, prawdopodobnie będzie taka sama, niezależnie od szukaj, na którym się zdecydujesz.

Zwycięzca wyzwania Google AI 2011 wykorzystał min-max (głębokość 1). Inny najlepszy zawodnik zastosował losowe próbkowanie . Ten zawodnik wspomniał, że połączenie minimalnego i losowego próbkowania, które jest zasadniczo tym, co opisałem w moim pytaniu, wypadło źle. To chyba załatwia sprawę.

Z drugiej strony pokazuje, że można używać min-max w dużych grach. Wydaje się jednak, że konieczne było ograniczenie go do małych grup mrówek, praca z pełnym zestawem wszystkich mrówek byłaby prawdopodobnie zbyt wolna. Innym interesującym spostrzeżeniem jest to, że wystarczyła głębokość 1. My (ludzie) jesteśmy całkiem dobrzy w grze w szachy, a sztuczna inteligencja w tej grze wymaga o wiele głębszych drzew wyszukiwania, aby stanowić wyzwanie. Nowe, bardziej złożone gry nie były odtwarzane i badane przez tak długi czas, a głupsze AI mogą mieć wystarczającą wartość rozrywkową.

Podstawową ideą szachowej sztucznej inteligencji jest zrobienie listy wszystkich możliwych ruchów z aktualnie szacowanego najlepszego ruchu, a następnie ich ocena i powtórzenie procesu. Powoduje to, że mają zbyt małą szansę, ponieważ nie zostaną zabrani (lub można założyć, że nie zostaną zabrani, ponieważ nie dają przewagi).

Podstawowy pomysł wymaga sporządzenia listy wszystkich możliwych ruchów i powtórzenia tego procesu dla wszystkich tych ruchów itp. Jest to możliwe w szachach (gdzie lista prawdopodobnych następnych ruchów jest efektywnie wyliczalna; początkowa szachownica ma 20 możliwych ruchów ) i do pewnego stopnia za inne rzeczy, takie jak trik-trak, warcaby i rozwiązywanie kostki Rubika.

Jeśli wezmę na przykład prostą grę turową (Civilization 2), każdy z was może przejść do 8 pól (lub 24) w jednej turze. Jeśli masz 10 facetów (co nie jest dużo, zwykle masz ich więcej, zanim zacznie się to nieco interesować), całkowita liczba możliwych „ruchów” z obecnego stanu (czyli jednego poziomu) wynosi już 8 ^ 10 lub około 4 miliardów. Nawet jeśli przycinasz 99,99%, nadal nie możesz wejść głęboko w drzewo, ponieważ liczba możliwych ruchów eksploduje naprawdę szybko.

Dodaj do tego, że gra jest trochę jak problem z kostką Rubika, w którym widać postęp dopiero po około 10 lub 12 ruchach, problem eksploduje do tego stopnia, że ​​zalety standardowej wartości min / max występują tylko przy pojemności pamięci wynoszącej więcej niż typowy komputer.

Innymi słowy, strategie, które znajdzie, będą powtarzalne, ale złe.

Jeśli chodzi o rzeczywisty problem, jak stworzyć przyzwoitą sztuczną inteligencję, pójdę w kierunku w zasadzie sterowanego losowego ruchu (poruszaj każdego faceta odrobiną podstawowej inteligencji), oceny i strojenia. Zrób to równolegle dla 100 lub 1000 różnych i wybierz ten, który ostatecznie będzie najlepszy. Możesz przekazać wyniki z tego do oryginalnego inteligentnego układu kierowniczego, aby ponownie go dostroić. Trochę jak symulacja Monte Carlo.

Aby skutecznie zastosować min / max do turowej gry strategicznej, musisz poprawnie zastosować wszystkie dostępne techniki szachowe ...

Funkcja oceny

Nawet silniki szachowe mają bardzo słabą siłę, jeśli twoje funkcje oceny są złe. Najprostsza wersja funkcji oceny to: 1 = gra wygrana przez kolor biały, -1 = gra wygrana przez kolor czarny, 0 = wszystkie pozostałe przypadki; Ale dałoby to bardzo słabą wydajność. To samo dzieje się z twoją grą turową! Jeśli chcesz używać min / max (z przycinaniem alfa / beta i tak dalej) jak w szachach, musisz także wdrożyć rozsądną funkcję oceny! Poza tym nie można porównywać wydajności tych algorytmów w grze strategicznej z przypadkiem, w którym stosuje się ją w szachach.

Funkcje funkcji silników szachowych polegają na ocenie rzeczy takich jak:

• Jak dobrze jest pozycja pionka na planszy?
• Ile razy atakowany jest kawałek?
• Ile razy element jest chroniony?
• Jak dobrze każdy element może swobodnie „poruszać się” na planszy? (lub: Ile płytek „kontroluje”)

Te części funkcji oceny muszą najpierw zostać „przetłumaczone” na twoją grę:

• Pozycja elementu: czy znajduje się np. Na wzgórzu, które zwiększa zasięg strzelania?
• Zaatakowany: Ile kosztuje każda sztuka? (np. suma wartości ataku jednostek zdolnych do ataku na jednostkę specjalną pomnożona przez pewne prawdopodobieństwo jej zaatakowania; prawdopodobieństwo wzrasta, jeśli jednostka jest już uszkodzona; zmniejsza się, jeśli wiele innych jednostek znajduje się w zasięgu jednostki atakującej)
• Własny atak: ile jednostek może zostać zaatakowanych przez tę jednostkę?
• Ochrona: ile własnych elementów jest obok (aby pomóc)? Być może jednostka nie może atakować jednostek w minimalnej odległości i lepiej jest chronić ją przez jednostkę mającą możliwość atakowania pobliskich jednostek.
• Mobilność: jak mobilna jest twoja jednostka? (czy może uciec?)

Różne oceny należy zsumować za pomocą funkcji ważenia (współczynnik_a * ocena_a + współczynnik_b * ranting_b + ...) dla wszystkich jednostek ...

W grach strategicznych należy również wziąć pod uwagę pozostałe zasoby (złoto, drewno, ...).

Jeśli funkcja oceny jest wystarczająca, w większości przypadków nie trzeba tak naprawdę szukać „głęboko” w drzewie. Prawdopodobnie musisz tylko przyjrzeć się 3 lub 10 najbardziej obiecującym wyborom. Zobacz następny rozdział ...

Możliwe ruchy w każdej pozycji

Najbardziej problematyczną rzeczą w używaniu min / max w grach strategicznych jest to, że możesz dowodzić wieloma jednostkami w jednej turze, podczas gdy w szachach możesz dowodzić tylko jedną jednostką (z wyjątkiem roszady, ale jest to wyraźnie zdefiniowana kombinacja ruchów). Powoduje to 5 ^ N możliwych ruchów dla N jednostek dla każdej „pozycji” (termin szachowy), jeśli zdecydujesz się tylko na „ruch na północ, południe, zachód, wschód lub zatrzymanie OR” dla każdej jednostki. Możesz rozwiązać ten problem, dzieląc złożone polecenie na polecenia niskiego poziomu: np. Wybierz akcję dla jednostki A, idź w głąb i wybierz jednostkę B .... wybierz jednostkę N ..., a następnie zakończ tę turę. Ale to samo nie zmienia złożoności! Musisz zoptymalizować kolejność przypisywania akcji do jednostek (np. Pierwsza jednostka B, C, D, a następnie jednostka A). Możesz zapisać wpływ decyzji dla każdej jednostki podczas ostatniego obliczenia, a następnie posortować według ważności. W ten sposób przycinanie alfa-beta można bardzo wcześnie wyciąć złą kombinację z drzewa wyszukiwania. Najwyższym priorytetem zawsze powinno być „nie rób nic więcej i kończ swoją turę” (przycinanie ruchu zerowego) w każdej iteracji. W ten sposób możesz „pominąć” przypisywanie większości zadań do większości jednostek i pozwolić im po prostu kontynuować to, co zrobili wcześniej. W ten sposób wyszukiwanie szybko się pogłębi, po prostu patrząc na „krytyczne” jednostki (np. Te, które naprawdę są teraz w walce). Upewnij się, że dowodzisz każdą jednostką tylko raz ... Możesz także użyć pewnej losowości, aby mieć pewność, że „ważne” jednostki również otrzymują od czasu do czasu polecenie. Szczególnie jednostki kończące jakąś pracę (np

Iteracyjne pogłębianie + buforowanie / tablica skrótu

Następnie możesz „pogłębiać interwencyjnie”, aby pogłębiać się coraz głębiej, aż do osiągnięcia określonego limitu czasu. Będziesz więc szukać głębiej, jeśli będzie mniej jednostek, i zawsze będziesz mieć „wynik”, jeśli przestaniesz szukać lepszego rozwiązania. Pogłębianie iteracyjne wymagałoby użycia tabeli skrótów do buforowania wcześniejszych wyników wyszukiwania. Umożliwia to także ponowne wykorzystanie niektórych wyników z wyszukiwania w ostatnich turach (gałąź drzewa wyszukiwania, która obejmuje polecenia faktycznie wykonane w ostatniej turze). Aby to zaimplementować, potrzebujesz bardzo dobrej funkcji skrótu (spójrz na „klucz zobrista”), którą można iteracyjnie aktualizować. Aktualizacja klucza skrótu oznacza, że ​​możesz po prostu wziąć klucz skrótu ze starej „pozycji” i po prostu wprowadzić zmianę pozycji (np. wyjmij jednostkę w pozycji x i ustaw ją w pozycji y). W ten sposób obliczenie klucza skrótu jest szybkie i nie trzeba przetwarzać całej sytuacji na tablicach, aby go obliczyć, wystarczy sprawdzić, czy skrót zawiera poprzedni wpis dla tej pozycji. W pewien sposób musisz upewnić się, że nie dojdzie do kolizji skrótu.

Zachowanie niedeterministyczne

Zachowanie niedeterministyczne jest problemem dla wyszukiwań min / maks. Oznacza to, że nie jest pewne, czy trafisz zaatakowany cel (np. Prawdopodobieństwo wynosi 10%). Wtedy nie możesz tak po prostu zaplanować. W takim przypadku musisz zmodyfikować algorytm i umieścić warstwę „prawdopodobieństwa” pomiędzy nimi. To trochę tak, jakby „zmienił się prawdopodobieństwo”. Każdy niezależny wynik należy rozpatrywać osobno. Następnie należy pobrać próbkę oceny przez tę „warstwę” głębokości (próbkowanie Monte Carlo), a wynik szczegółowej oceny musi być ważony prawdopodobieństwem wystąpienia. Różne wyniki warstwy prawdopodobieństwa należy traktować jak różne ruchy przeciwne (ale zamiast min / max należy obliczyć „średnią”). To oczywiście zwiększy złożoność drzewa wyszukiwania.

streszczenie

Stosując wszystkie te techniki (wszystkie stosowane w obecnych silnikach szachowych) w deterministycznej grze, z pewnością będziesz w stanie osiągnąć rozsądne wyniki również w grze. W przypadku gier niedeterministycznych będzie to prawdopodobnie bardziej skomplikowane, ale myślę, że nadal jest to możliwe.

Dobrym źródłem informacji na temat tych technik (w szachach) jest http://chessprogramming.wikispaces.com/

Możesz nawet wdrożyć ukierunkowaną losowość w wyszukiwaniu min / maks. Zamiast deterministycznie badać najlepsze wyniki na początku każdej iteracji, możesz po prostu randomizować to i pozwolić na ustalenie jego kolejności na podstawie rozkładu prawdopodobieństwa opartego na bieżących ocenach ...