Podejście punktowe do komputerowych przeciwników, którzy potrzebują równowagi

To pytanie dotyczy podejścia do przeciwników komputerowych, które stworzyłem i albo są obecnie używane, albo planuje się ich użycie w kilku grach komputerowych.

tło

W ubiegłym roku, kiedy próbowałem ulepszyć komputerowego przeciwnika w grze o nazwie „Saper Flagi” (krótki opis: Turowa wersja Saper dla wielu graczy, w której musisz wziąć więcej min niż przeciwnik) , mocno zmieniłem sposób działania moich algorytmów . Zamiast stosować podejście takie jak if-else-if-else, używam zestawu „strzelców” o określonych wagach, aby określić najlepszy ruch.

Można by pomyśleć, że w przypadku gry takiej jak Saper, tylko wykonywanie ruchów daje największe prawdopodobieństwo zabrania miny, ale nie jest to takie proste. To, jaki ruch wykona komputer, zwykle zależy od kilku funkcji tego konkretnego ruchu w bieżącym stanie gry. Przykłady funkcji:

• Jakie jest prawdopodobieństwo, że ten ruch zdobędzie minę?
• Jakie jest prawdopodobieństwo ujawnienia czegokolwiek mojemu przeciwnikowi tutaj?

Opis systemu

System działa w następujący sposób:

1. „Strzelcy wstępni”: Trwa wstępna analiza bieżącego stanu gry (w odniesieniu do flag Saperów, jest to zwykle: Obliczanie wszystkich prawdopodobieństw)
2. „Strzelcy”: zestaw zwykłych strzelców jest proszony o określenie wyniku dla każdego możliwego ruchu, każdy strzelec stosuje wyniki według własnych kryteriów. Sekretarze mogą sprawdzić wyniki dokonanej analizy wstępnej.
3. Wyniki obliczone w powyższym kroku są sumowane i ustalane jako wynik za ruch.
4. Ruchy są sortowane według ich wyniku i uszeregowane w taki sposób, aby wszystkie ruchy z tym samym wynikiem uzyskały tę samą pozycję.
5. „Po sekretarzach”: Wynik powyższego można wysłać do „Po sekretarzów”, którzy mają możliwość modyfikowania wyników dowolnych pól w dowolny sposób, zgodnie z własnymi regułami sekretarza.

Łącząc grupę strzelców, strzelców (wraz z ich wagami) i strzelców, staje się to, co nazywam konfiguracją wyników .

Przykładowy wynik

Jest to przykład wyników zastosowanych do flag Saperów. Oto mapa, która została oceniona:

I to jest wynik rzeczywistej konfiguracji partytury. Pokazuje rangę możliwych ruchów, gdzie 1 to najlepsza ranga i została podświetlona na biało:

Dzięki napisaniu wysoce elastycznego kodu, to podejście do sztucznej inteligencji można również wprowadzić do innych gier.

Zalety i wady

Poniżej wymieniono niektóre zalety i wady tego systemu, które mogę sobie wyobrazić

Zalety

• Bardzo łatwo jest stworzyć wiele różnych konfiguracji dla AI.
• Możliwe jest stosowanie z algorytmami genetycznymi: Każdy strzelec ma powiązaną wagę, waga może stać się genem.
• Za pomocą niektórych narzędzi można sprawdzić, dlaczego dany ruch został wykonany i którzy strzelcy byli głównie odpowiedzialni za ten ruch
• Za pomocą narzędzi można utworzyć mapę ogólnego wyniku / rangi możliwych ruchów (jak na powyższym zrzucie ekranu)
• Stosując wyniki do sposobu, w jaki gra człowiek, można stworzyć „#AI_Mirror”, który próbuje wykonać ruchy, które według niego wykona człowiek

Niedogodności

• „Prawidłowe” dostosowanie konfiguracji wyników może być niezwykle trudne, aby sztuczna inteligencja grała tak dobrze, jak to możliwe.

pytania

• Czy system, który zbudowałem tutaj, jest powszechnie znany w świecie sztucznej inteligencji? Jak by to się nazywało w kategoriach AI?

• Czy to podejście ma sens, czy jest inne podejście, które byś polecił?

• Jakie są sposoby, które mogłyby ułatwić modyfikowanie konfiguracji partytury?

Jeśli chodzi o ostatnie pytanie, jestem świadomy możliwości zastosowania algorytmów genetycznych, jestem również umiarkowanie świadomy SARSA (i myślę, że moi strzelcy przypominają opis cech tej witryny z wagami, ale z mojego zrozumienia, że ​​nie jest to dokładnie to, co stworzyłem tutaj). Myślę, że problem z SARSA polega na tym, że nie znasz nagrody, dopóki gra się nie skończy. Najlepszy ruch to często ruch, który w ogóle nie daje nagrody (kopalni). Twoje obecne szanse na wygraną zależą zarówno od aktualnego wyniku (liczby min, które wziąłeś ty i twój przeciwnik), jak i od tego, jak wygląda aktualna mapa.

_{To pytanie zostało pierwotnie opublikowane na nieistniejącej już stronie sztucznej inteligencji .
Kod (Java) zastosowany w tym podejściu został teraz opublikowany w Code Review .}

Na odcinku jest to system ekspertowy (taki jak logika rozmyta). Ponieważ nie uruchamiasz algorytmu do przekazywania informacji zwrotnych na temat parametrów decyzji na podstawie danych wyjściowych, tak naprawdę nie uczy się. Jednak udzielanie informacji zwrotnej nie jest jedynym wskaźnikiem, czy alogirthm jest AI. Można argumentować, że jeśli działa w sposób, który wydaje się inteligentny, to wszystko ma znaczenie - szczególnie, gdy w grę gra ludzki przeciwnik.

Algorytm, który określiłeś, jest tak naprawdę sparametryzowanym równaniem, które znajdziesz w obliczeniach ubezpieczenia. Po każdym ruchu przestrzeń wejściowa zmienia się, ale algorytm nie potrzebuje pamięci z poprzedniego stanu, więc traktuje każdy ruch jako nową, oddzielną tablicę.

Korzystanie z algorytmów genetycznych

Istnieją dwie wyraźne opcje dla algorytmów genetycznych:

• Użyj parametrów dla genomu (jak zasugerowałeś). Zoptymalizujesz posiadane reguły, ale nadal masz system ekspercki.
• Użyj Learning Classifier System (LCS), aby wybrać reguły dla siebie. LCS jest rodzajem algorytmu genetycznego, w którym kodujesz reguły oraz parametry. Zbiegają się dłużej i są wrażliwe na funkcję fitness. Myślę, że wynikowy sposób gry może być dla niego bardziej interesujący.

Symulowanego wyżarzania

Innym sposobem rozwiązania tego problemu jest użycie symulowanego wyżarzania (SA). Twoim problemem jest ograniczona przestrzeń wejściowa i możesz analitycznie napisać funkcję, która znajdzie najlepszy kwadrat do wybrania w danym scenariuszu. Użycie symulowanego wyżarzania pozwoli znaleźć globalne optymalne parametry.

Na robienie tego zbyt dobrze

Wiem, że chcesz, aby algorytm był jak najlepszy, ale nie zapominaj, że człowiek gra przeciwko niemu. Istnieje taktycznie doskonały sposób na granie w tego rodzaju deterministyczne gry, a jeśli gracz AI go weźmie, będzie to tylko szczęście, co oznacza, że ​​gracz wygrywa.

Tak, technika przypisywania wyników na podstawie niektórych aspektów pozycji jest standardem w pisaniu AI do grania w gry. Na przykład prawie wszystkie programy szachowe działają, oceniając pozycje w oparciu o dostępne elementy, przy czym mniejsze premie zależą od ich pozycji (np. Pionki chroniące się nawzajem). Następnie próbują obliczyć najlepszy dostępny ruch za pomocą algorytmu wyszukiwania przeciwnika, takiego jak alfa-beta.

Wyszukiwanie przeciwników może być tutaj trudne ze względu na duży czynnik rozgałęziający - w dowolnej pozycji legalne ruchy mają na celu zaznaczenie lub odsłonięcie dowolnego nieznanego kwadratu. Z drugiej strony jest możliwe, że można znacznie zmniejszyć czynnik rozgałęzienia za pomocą heurystyki. Na przykład zaznaczenie lub odsłonięcie kwadratu, o którym nic nie wiesz, bardzo rzadko będzie najlepszym ruchem. I odwrotnie, jeśli znasz lokalizację niektórych nieoznakowanych min, oznaczenie jednej z nich będzie prawdopodobnie najlepszym ruchem przez większość czasu. Utrzymanie tabeli transpozycji prawdopodobnie również pomogłoby.