Jak stworzyć AI w grach: przewodnik dla początkujących

Natknąłem się na interesujący materiał o sztucznej inteligencji w grach. Z wyjaśnieniem podstawowych rzeczy o AI na prostych przykładach oraz z wieloma przydatnymi narzędziami i metodami do wygodnego rozwoju i projektowania. Jak, gdzie i kiedy ich używać — również jest.

Większość przykładów jest napisana w pseudokodzie, więc nie są wymagane głębokie znajomości programowania. Pod tym linkiem 35 stron tekstu z obrazkami i gifami, więc przygotujcie się.

UPD. Przepraszam, ale już zrobiłem własny przekład tego artykułu na Habra. PatientZero. Można przeczytać jego wersję tutaj, ale jakoś artykuł umknął mojej uwadze (korzystałem z wyszukiwarki, ale coś poszło nie tak). A ponieważ piszę na blogu poświęconym grom, postanowiłem zostawić swoją wersję przekładu dla subskrybentów (niektóre momenty u mnie są ujęte inaczej, inne — celowo pominięte na radę twórców).

Co to jest AI?

AI w grach koncentruje się na tym, jakie działania powinien podejmować obiekt w zależności od warunków, w jakich się znajduje. Zwykle nazywa się to zarządzaniem „inteligentnymi agentami”, gdzie agentem jest postać w grze, środek transportu, bot, a czasem coś bardziej abstrakcyjnego: cała grupa bytów lub nawet cywilizacja. W każdym przypadku chodzi o to, że coś musi dostrzegać swoje otoczenie, podejmować na jego podstawie decyzje i działać zgodnie z nimi. To nazywa się cyklem Sense / Think / Act (Czuj / Myśl / Działaj):

• Czuj: agent znajduje lub otrzymuje informacje o rzeczach w swoim otoczeniu, które mogą wpłynąć na jego zachowanie (zagrożenia w pobliżu, przedmioty do zebrania, interesujące miejsca do zbadania).
• Myśl: agent decyduje, jak zareagować (rozważa, czy zbierać przedmioty, czy najpierw stawić czoła zagrożeniu / schować się).
• Działaj: agent wykonuje działania w celu wdrożenia poprzedniej decyzji (rozpoczyna ruch w stronę przeciwnika lub przedmiotu).
• …teraz sytuacja zmieniła się z powodu działań postaci, dlatego cykl powtarza się z nowymi danymi.

Sztuczna inteligencja koncentruje się zazwyczaj na części cyklu Sense. Na przykład autonomiczne samochody wykonują zdjęcia drogi, łączą je z danymi radarowymi i lidarowymi oraz je interpretują. Zwykle robi to uczenie maszynowe, które przetwarza dane wejściowe i nadaje im sens, wydobywając informacje semantyczne, takie jak „jest jeszcze jeden samochód 20 jardów przed tobą”. To tak zwane problemy klasyfikacyjne.

Gry nie potrzebują skomplikowanego systemu do wydobywania informacji, ponieważ większość danych jest już ich nieodłączną częścią. Nie ma potrzeby uruchamiania algorytmów rozpoznawania obrazów, aby stwierdzić, czy przed nami znajduje się wróg — gra już wie i przekazuje informacje bezpośrednio w procesie podejmowania decyzji. Dlatego część cyklu Sense jest zwykle znacznie prostsza niż Think i Act.

Ograniczenia AI w grach

AI ma szereg ograniczeń, które należy uwzględnić:

• AI nie musi być wcześniej szkolone, jak algorytm uczenia maszynowego. Nie ma sensu tworzyć sieci neuronowej w trakcie rozwoju, aby obserwować dziesiątki tysięcy graczy i uczyć się, jak najlepiej grać przeciwko nim. Dlaczego? Ponieważ gra nie została wydana, a graczy nie ma.
• Gra powinna zapewniać rozrywkę i stawiać wyzwania, dlatego agenci nie powinni znajdować najlepszego podejścia do ludzi.
• Agenci muszą wyglądać realistycznie, aby gracze czuli, że grają przeciwko prawdziwym ludziom. Program AlphaGo przewyższył człowieka, ale wybrane ruchy były dalekie od tradycyjnego rozumienia gry. Jeśli gra imituje przeciwnika-ludzkiego, takie odczucie nie powinno zostać wywołane. Algorytm musi zostać zmieniony, aby podejmował prawdopodobne decyzje, a nie idealne.
• AI musi działać w czasie rzeczywistym. Oznacza to, że algorytm nie może monopolizować procesora przez długi czas na podejmowanie decyzji. Nawet 10 milisekund na to to zbyt długo, ponieważ większość gier potrzebuje od 16 do 33 milisekund na przetworzenie wszystkiego i przejście do następnej klatki grafiki.
• Idealnie, jeśli przynajmniej część systemu jest zarządzana danymi, aby „nieprogramiści” mogli wprowadzać zmiany, a modyfikacje odbywały się szybciej.

Rozważmy podejścia AI, które obejmują cały cykl Sense/Think/Act.

Podejmowanie podstawowych decyzji

Zacznijmy od najprostszej gry — Pong. Cel: przesunąć platformę (paddle) tak, aby piłka odbijała się od niej, a nie przechodziła obok. To jak w tenisie, w którym przegrywasz, jeśli nie odbijesz piłki. Tutaj AI ma stosunkowo łatwe zadanie — ustalić, w którym kierunku przesunąć platformę.

Operatory warunkowe

Dla AI w Pong jest najbardziej oczywistym rozwiązaniem — zawsze starać się umieścić platformę pod piłką.

Prosty algorytm do tego, zapisany w pseudokodzie:

co klatkę/aktualizację, gdy gra trwa:
jeśli piłka jest po lewej stronie platformy:
przesuń platformę w lewo
w przeciwnym razie, jeśli piłka jest po prawej stronie platformy:
przesuń platformę w prawo

Jeśli platforma porusza się z prędkością piłki, to idealny algorytm dla AI w Pong. Nie ma potrzeby komplikować, jeśli dane i możliwe działania dla agenta nie są zbyt liczne.

Podejście to jest na tyle proste, że cały cykl Sense/Think/Act jest ledwie zauważalny. Ale on istnieje:

• Część Sense znajduje się w dwóch operatorach if. Gra wie, gdzie jest piłka, a gdzie platforma, więc AI korzysta z tych informacji.
• Część Think także zawiera dwa operatory if. Reprezentują one dwa rozwiązania, które w tym przypadku są wzajemnie wykluczające. W efekcie wybierane jest jedno z trzech działań — przesunięcie platformy w lewo, w prawo lub nic nie robienie, jeśli już jest prawidłowo ustawiona.
• Część Act znajduje się w operatorach Move Paddle Left i Move Paddle Right. W zależności od projektu gry, mogą one przesuwać platformę natychmiastowo lub z określoną prędkością.

Takie podejścia nazywane są reagującymi — istnieje prosty zestaw reguł (w tym przypadku operatory if w kodzie), które reagują na aktualny stan świata i działają.

Drzewo decyzyjne

Przykład z grą Pong równoznaczny jest formalnej koncepcji AI, zwanej drzewem decyzyjnym. Algorytm przechodzi przez nie, aby osiągnąć «liść» — decyzję, jakie działanie podjąć.

Zróbmy schemat blokowy drzewa decyzyjnego dla algorytmu naszej platformy:

Każda część drzewa nazywa się node (węzeł) — AI wykorzystuje teorię grafów do opisu podobnych struktur. Istnieją dwa typy węzłów:

• Węzły decyzyjne: wybór między dwoma alternatywami na podstawie sprawdzenia pewnego warunku, gdzie każda alternatywa reprezentowana jest w postaci oddzielnego węzła.
• Węzły końcowe: działanie do wykonania, reprezentujące ostateczną decyzję.

Algorytm zaczyna się od pierwszego węzła („korzenia” drzewa). Decyduje on, do którego węzła potomnego przejść, lub wykonuje działanie zapisane w węźle i kończy działanie.

Jakie są korzyści, skoro drzewo decyzyjne wykonuje tę samą pracę, co operatory if z poprzedniej sekcji? Istnieje tu wspólny system, w którym każda decyzja ma tylko jeden warunek i dwa możliwe wyniki. Pozwala to programiście na tworzenie AI z danych reprezentujących decyzje w drzewie, unikając jego twardego zakodowania. Możemy to przedstawić w formie tabeli:

Po stronie kodu otrzymasz system do odczytu wierszy. Utwórz węzeł dla każdego z nich, połącz logikę podejmowania decyzji na podstawie drugiej kolumny oraz węzły potomne na podstawie trzeciej i czwartej kolumny. Nadal musisz zaprogramować warunki i działania, ale teraz struktura gry stanie się bardziej złożona. Dodasz dodatkowe decyzje i działania, a następnie dostosujesz całe AI, po prostu edytując plik tekstowy z definicją drzewa. Następnie przekażesz plik projektantowi gier, który będzie mógł zmienić zachowanie bez rekompilacji gry i zmiany kodu.

Drewa decyzyjne są bardzo użyteczne, gdy są automatycznie budowane na podstawie dużego zestawu przykładów (na przykład z użyciem algorytmu ID3). Sprawia to, że są one efektywnym i wydajnym narzędziem do klasyfikacji sytuacji na podstawie uzyskiwanych danych. Jednak wykraczamy poza prosty system do dobierania działań przez agentów.

Scenariusze

Omówiliśmy system drzewa decyzyjnego, który wykorzystywał wcześniej ustalone warunki i działania. Osoba projektująca AI może zorganizować drzewo tak, jak chce, ale wciąż musi polegać na programiście, który to wszystko zaprogramował. Co by było, gdybyśmy mogli dać projektantowi narzędzia do tworzenia własnych warunków lub działań?

Aby programista nie musiał pisać kodu dla warunków Is Ball Left Of Paddle i Is Ball Right Of Paddle, może stworzyć system, w którym projektant zapisze warunki do sprawdzenia tych wartości. Wówczas dane drzewa decyzyjnego będą wyglądać tak:

W zasadzie jest to to samo, co w pierwszej tabeli, ale rozwiązania mają własny kod, trochę przypominający warunkową część if-operatora. W kodzie byłoby to odczytywane w drugiej kolumnie dla węzłów podejmowania decyzji, ale zamiast szukać konkretnego warunku do spełnienia (Is Ball Left Of Paddle), ocenia wyrażenie warunkowe i zwraca true lub false odpowiednio. Odbywa się to za pomocą języka skryptowego Lua lub Angelscript. Dzięki nim deweloper może przyjmować obiekty w swojej grze (ball i paddle) i tworzyć zmienne, które będą dostępne w skrypcie (ball.position). Ponadto, język skryptowy jest prostszy niż C++. Nie wymaga pełnego etapu kompilacji, co czyni go idealnym do szybkiej korekty logiki gry i pozwala „nieprogramistom” na samodzielne tworzenie wymaganych funkcji.

W podanym przykładzie język skryptowy jest używany tylko do oceny wyrażenia warunkowego, ale można go również wykorzystać do działań. Na przykład dane Move Paddle Right mogą stać się operatorem skryptowym (ball.position.x += 10). Tak, aby działanie było także definiowane w skrypcie, bez potrzeby programowania Move Paddle Right.

Można pójść jeszcze dalej i całkowicie napisać drzewo decyzji w języku skryptowym. To będzie kod w postaci twardo zaprogramowanych operatorów warunkowych, ale będą one znajdować się w zewnętrznych plikach skryptu, to znaczy mogą być zmienione bez rekompilacji całego programu. Często można zmienić plik skryptu w trakcie gry, aby szybko przetestować różne reakcje AI.

Reagowanie na zdarzenia

Podane przykłady idealnie pasują do Pong. Nieprzerwanie uruchamiają cykl Sense/Think/Act i działają na podstawie ostatniego stanu świata. Jednak w bardziej skomplikowanych grach trzeba reagować na poszczególne zdarzenia, a nie oceniać wszystko naraz. W takim przypadku Pong jest już nietrafionym przykładem. Wybierzmy inny.

Wyobraź sobie strzelankę, w której wrogowie są nieruchomi, dopóki nie zauważą gracza, po czym działają w zależności od swojej „specjalizacji”: niektórzy zaczną „rushować”, inni będą atakować z daleka. To wciąż podstawowy system reagujący — „jeśli gracz jest zauważony, to zrób coś” — ale można go logicznie podzielić na zdarzenie Player Seen (gracz zauważony) i reakcję (wybierz odpowiedź i ją wykonaj).

To wracamy do cyklu Sense/Think/Act. Możemy stworzyć część Sense, która w każdej klatce będzie sprawdzać, czy AI widzi gracza. Jeśli nie — nic się nie dzieje, ale jeśli widzi, tworzy się zdarzenie Player Seen. Kod będzie miał osobną sekcję, w której będzie napisane: „gdy nastąpi zdarzenie Player Seen, zrób ”, gdzie to odpowiedź, której potrzebujesz do odwołania do części Think i Act. W ten sposób skonfigurujesz reakcje na zdarzenie Player Seen: dla „szarżującego” bohatera — ChargeAndAttack, a dla snajpera — HideAndSnipe. Te powiązania można stworzyć w pliku danych do szybkiej edycji bez potrzeby ponownego kompilowania. Tu też można użyć języka skryptowego.

Podejmowanie złożonych decyzji

Choć proste systemy reakcji są bardzo skuteczne, jest wiele sytuacji, w których są niewystarczające. Czasami trzeba podejmować różne decyzje w zależności od tego, co agent robi w danym momencie, ale przedstawienie tego jako warunek jest trudne. Czasami istnieje zbyt wiele warunków, aby efektywnie przedstawić je w drzewie decyzji lub skrypcie. Czasami trzeba z wyprzedzeniem ocenić, jak zmieni się sytuacja, zanim podejmie się decyzję o następnym kroku. Do rozwiązania tych problemów potrzebne są bardziej złożone podejścia.

Maszyna stanów skończonych

Maszyna stanów skończonych, czyli FSM (Finite State Machine) — to sposób na powiedzenie, że nasz agent w danym momencie znajduje się w jednym z kilku możliwych stanów i że może przechodzić z jednego stanu do drugiego. Takich stanów jest określona ilość — stąd nazwa. Najlepszym przykładem z życia jest sygnalizacja świetlna. W różnych miejscach różne sekwencje świateł, ale zasada jest ta sama — każdy stan reprezentuje coś (stój, idź itd.). Sygnalizator świetlny znajduje się tylko w jednym stanie w danym momencie i przechodzi z jednego do drugiego na podstawie prostych zasad.

W przypadku NPC w grach mamy podobną historię. Na przykład weźmy strażnika z takimi stanami:

• Patrolujący (Patrolling).
• Atakujący (Attacking).
• Uciekający (Fleeing).

I takimi warunkami do zmiany jego stanu:

• Jeśli strażnik widzi przeciwnika, atakuje.
• Jeśli strażnik atakuje, ale już nie widzi przeciwnika, wraca do patrolowania.
• Jeśli strażnik atakuje, ale jest poważnie ranny, ucieka.

Możesz również napisać operatory if z zmienną stanu strażnika oraz różnymi kontrolami: czy wróg jest blisko, jaki poziom zdrowia ma NPC itp. Dodajmy jeszcze kilka stanów:

• Bezczynność (Idling) — między patrolami.
• Poszukiwanie (Searching) — gdy zauważony wróg ukrył się.
• Prosząc o pomoc (Finding Help) — gdy wróg został zauważony, ale jest zbyt silny, aby walczyć z nim samodzielnie.

Wybór dla każdego z nich jest ograniczony — na przykład strażnik nie pójdzie szukać ukrywającego się wroga, jeśli ma niskie zdrowie.

Ostatecznie ogromna lista „jeśli <x и y, но не z>, to <p>„ może stać się zbyt nieporęczna, dlatego należy sformalizować metodę, która pozwoli nam mieć na uwadze stany i przejścia między nimi. Aby to zrobić, weźmiemy pod uwagę wszystkie stany i pod każdym stanem zapiszemy na liście wszystkie przejścia do innych stanów, wraz z wymaganymi dla nich warunkami.

To jest tabela przejść stanów — złożony sposób przedstawienia FSM. Narysujmy diagram i uzyskamy pełny przegląd tego, jak zmienia się zachowanie NPC.

Diagram odzwierciedla sedno podejmowania decyzji przez tego agenta w oparciu o aktualną sytuację. Każda strzałka pokazuje przejście między stanami, jeśli warunek obok niej jest prawdziwy.

Podczas każdej aktualizacji sprawdzamy aktualny stan agenta, przeglądamy listę przejść, a jeśli warunki przejścia są spełnione, przejmuje on nowy stan. Na przykład, w każdej klatce sprawdzamy, czy 10-sekundowy timer minął, a jeśli tak, strażnik przechodzi ze stanu Bezczynności do Patrolowania. W ten sam sposób stan Atakujący sprawdza zdrowie agenta — jeśli jest niskie, przechodzi do stanu Uciekającego.

To jest przetwarzanie przejść między stanami, ale co z zachowaniem związanym z samymi stanami? Jeśli chodzi o implementację faktycznego zachowania dla konkretnego stanu, zazwyczaj istnieją dwa typy „haków”, które przypisujemy działaniom do FSM:

• Działania, które okresowo wykonujemy dla aktualnego stanu.
• Działania, które podejmujemy przy przejściu z jednego stanu do innego.

Przykłady dla pierwszego typu. Stan Patrolowania co klatkę przesuwa agenta po trasie patrolu. Stan Atakujący co klatkę próbuje rozpocząć atak lub przejść do stanu, gdy to możliwe.

Dla drugiego typu rozważmy przejście „jeśli wróg jest widoczny i jest zbyt silny, to przejdź do stanu Znalezienie Pomocy. Agent musi wybrać, gdzie pójść po pomoc, a następnie zapisać tę informację, aby stan Znalezienie Pomocy wiedział, gdzie się udać. Gdy pomoc zostanie znaleziona, agent wraca do stanu Atakowania. W tym momencie będzie chciał powiadomić sojusznika o zagrożeniu, więc może nastąpić akcja PowiadomienieSojusznikaOzagrożeniu.

I znów możemy spojrzeć na ten system przez pryzmat cyklu Sense/Think/Act. Sense urzeczywistnia się w danych wykorzystywanych przez logikę przejścia. Think - to przejścia dostępne w każdym stanie. A Act polega na działaniach podejmowanych okresowo w ramach stanu lub podczas przejść między stanami.

Czasami ciągłe sprawdzanie warunków przejścia może być kosztowne. Na przykład, jeśli każdy agent miałby wykonywać złożone obliczenia w każdej klatce, aby określić, czy widzi wrogów i czy może przejść z stanu Patrolowania do Atakowania – to zajmie zbyt dużo czasu procesora.

Ważne zmiany w stanie świata można traktować jako zdarzenia, które będą przetwarzane, gdy się pojawią. Zamiast tego, aby FSM sprawdzał warunek przejścia „czy mój agent widzi gracza?” w każdej klatce, można skonfigurować oddzielny system, aby przeprowadzać kontrole rzadziej (na przykład 5 razy na sekundę). A wynikiem byłoby Gracz Widoczny, gdy kontrola przechodzi.

To jest przekazywane do FSM, który teraz musi przejść do warunku wydarzenia Otrzymano Gracz Widoczny i odpowiednio zareagować. Ostateczne zachowanie pozostaje takie samo, z wyjątkiem prawie niedostrzegalnego opóźnienia w odpowiedzi. Dzięki temu wydajność została poprawiona w wyniku odłączenia części Sense od głównej części programu.

Hierarchiczna maszyna stanów skończonych

Jednak praca z dużymi FSM nie zawsze jest wygodna. Jeśli zechcemy rozwinąć stan ataku, zastępując go oddzielnymi MeleeAttacking (atak w zwarciu) i RangedAttacking (atak z dystansu), będziemy musieli zmienić przejścia ze wszystkich innych stanów prowadzących do stanu Atakowania (zarówno bieżących, jak i przyszłych).

Z pewnością zauważyliście, że w naszym przykładzie jest wiele powtarzających się przejść. Większość przejść w stanie Idling jest identyczna z przejściami w stanie Patrolling. Dobrze byłoby uniknąć powtórzeń, szczególnie jeśli dodamy więcej podobnych stanów. Ma sens, aby zgrupować Idling i Patrolling pod wspólną etykietą „nienażeniowe”, gdzie jest tylko jeden wspólny zbiór przejść do stanów bojowych. Jeśli przedstawimy tę etykietę jako stan, to Idling i Patrolling staną się podstanami. Przykład użycia osobnej tabeli przejść dla nowego nienażeniowego podstanu:

Główne stany:


Stan poza walką:


I w formie schematu:

To ten sam system, ale z nowym nienażeniowym stanem, które obejmuje Idling i Patrolling. Z każdym stanem, który zawiera FSM z podstanami (a te podstany z kolei zawierają własne FSM — i tak dalej, ile potrzebujesz), otrzymujemy Hierarchical Finite State Machine lub HFSM (hierarchiczna maszyna stanów skończonych). Grupując nienażeniowy stan, wyeliminowaliśmy mnóstwo zbędnych przejść. To samo możemy zrobić dla wszelkich nowych stanów z wspólnymi przejściami. Na przykład, jeśli w przyszłości rozszerzymy stan Attacking na stany MeleeAttacking i MissileAttacking, będą one podstanami, przechodzącymi między sobą w zależności od odległości do wroga i dostępności amunicji. W rezultacie skomplikowane modele zachowania i podmodele zachowania można przedstawić przy minimalnej liczbie powtarzających się przejść.

Drzewo zachowań

Z HFSM można tworzyć skomplikowane kombinacje zachowań w prosty sposób. Niemniej jednak, jest mała trudność, że podejmowanie decyzji w postaci zasad przejścia jest ściśle związane z aktualnym stanem. I w wielu grach jest to właśnie to, czego potrzeba. A staranne wykorzystanie hierarchii stanów może zmniejszyć liczbę powtórzeń podczas przejścia. Ale czasem potrzebne są zasady, które działają niezależnie od tego, w jakim stanie jesteś lub które mają zastosowanie prawie w każdym stanie. Na przykład, jeśli zdrowie agenta spadło do 25%, będziesz chciał, aby uciekał, niezależnie od tego, czy był w walce, bezczynny czy rozmawiał — musisz dodać ten warunek do każdego stanu. A jeśli twój projektant później zechce zmienić próg niskiego zdrowia z 25% na 10%, znów będziesz musiał się tym zająć.

W idealnym przypadku do tej sytuacji potrzebny jest system, w którym decyzje o tym, w jakim stanie powinien być system, są poza samymi stanami, co pozwala na wprowadzanie zmian w jednym miejscu i nie dotykanie warunków przejścia. Tu pojawiają się drzewa zachowań.

Istnieje kilka sposobów ich realizacji, ale istota jest dla wszystkich mniej więcej taka sama i przypomina drzewo decyzji: algorytm zaczyna się od węzła 'korzeniowego', a w drzewie znajdują się węzły, które reprezentują albo decyzje, albo działania. Istnieją jednak pewne kluczowe różnice:

• Teraz węzły zwracają jedną z trzech wartości: Succeeded (jeśli praca została zakończona), Failed (jeśli nie można uruchomić) lub Running (jeżeli nadal działa i nie ma ostatecznego wyniku).
• Nie ma już węzłów decyzyjnych do wyboru między dwiema alternatywami. Zamiast nich są węzły Decorator, które mają jeden węzeł potomny. Jeśli zakończą się powodzeniem, wykonują swój jedyny węzeł potomny.
• Węzły wykonujące działania zwracają wartość Running, aby reprezentować wykonywane działania.

Ten niewielki zestaw węzłów można połączyć w celu stworzenia dużej liczby złożonych modeli zachowań. Przedstawmy HFSM strażnika z poprzedniego przykładu w formie drzewa zachowań:

Z tą strukturą nie powinno być bezpośredniego przejścia od stanów Idling/Patrolling do stanu Attacking lub jakiegokolwiek innego. Jeśli wrogowie są widoczni, a zdrowie postaci jest niskie, wykonanie zatrzymuje się na węźle Fleeing, niezależnie od tego, który węzeł był wcześniej wykonywany - Patrolling, Idling, Attacking lub jakikolwiek inny.

Drzewa zachowań są skomplikowane - istnieje wiele sposobów ich konstruowania, a znalezienie właściwej kombinacji dekoratorów i węzłów złożonych może być problematyczne. Są też pytania o to, jak często sprawdzać drzewo - czy chcemy przechodzić przez nie za każdym razem, czy tylko wtedy, gdy jeden z warunków się zmieni? Jak przechowywać stan odnoszący się do węzłów - jak dowiedzieć się, kiedy byliśmy w stanie Idling przez 10 sekund lub jak dowiedzieć się, które węzły były wykonywane ostatnio, aby prawidłowo obsługiwać sekwencję?

Dlatego istnieje wiele różnych implementacji. Na przykład w niektórych systemach węzły dekoratora zastępują wbudowane dekoratory. Powtarzają one ocenę drzewa w momencie zmiany warunków dekoratora, pomagają łączyć węzły i zapewniają okresowe aktualizacje.

System oparty na użyteczności

W niektórych grach występuje wiele różnych mechanik. Pożądane jest, aby wszystkie skorzystały z prostych i ogólnych zasad przejść, ale niekoniecznie w formie pełnego drzewa zachowań. Zamiast mieć wyraźny zestaw wyborów lub drzewo możliwych działań, łatwiej jest zbadać wszystkie działania i wybrać najbardziej odpowiednie w danym momencie.

System oparty na użyteczności pomoże w tym. To system, w którym agent ma wiele działań i sam decyduje, które wykonać, opierając się na względnej użyteczności każdego z nich. Użyteczność to dowolna miara tego, jak ważne lub pożądane jest wykonanie tego działania przez agenta.

Obliczoną użyteczność działania na podstawie aktualnego stanu i środowiska agent może sprawdzić i wybrać najbardziej odpowiedni inny stan w dowolnym momencie. Jest to podobne do FSM, z wyjątkiem tego, że przejścia są określane przez ocenę dla każdego potencjalnego stanu, w tym aktualnego. Należy zauważyć, że wybieramy najbardziej użyteczne działanie do przejścia (lub pozostajemy w tym samym stanie, jeśli już je wykonaliśmy). Dla większej różnorodności może to być ważony, ale przypadkowy wybór z małej listy.

System przydziela dowolny zakres wartości użyteczności — na przykład od 0 (zupełnie niepożądane) do 100 (całkowicie pożądane). Każde działanie ma szereg parametrów wpływających na obliczenie tej wartości. Wracając do naszego przykładu z strażnikiem:

Przejścia między działaniami są niejednoznaczne — dowolny stan może następować po każdym innym. Priorytety działań są ustalane na podstawie zwracanych wartości użyteczności. Jeśli wróg jest widoczny, a ten wróg jest silny, a zdrowie postaci jest niskie, zarówno Fleeing, jak i FindingHelp zwrócą wysokie wartości różne od zera. Jednak FindingHelp zawsze będzie wyższe. Podobnie, działania niewalczące nigdy nie zwracają więcej niż 50, dlatego zawsze będą niższe od działań walczących. Należy wziąć to pod uwagę przy tworzeniu działań i obliczaniu ich użyteczności.

W naszym przykładzie działania zwracają albo stałą, niezmienną wartość, albo jedną z dwóch stałych wartości. Bardziej realistyczny system zakłada zwrot oceny w nieprzerwanym zakresie wartości. Na przykład działanie Fleeing zwraca wyższe wartości użyteczności, gdy zdrowie agenta jest niskie, natomiast działanie Attacking zwraca niższe wartości, gdy wróg jest zbyt silny. Z tego powodu działanie Fleeing ma priorytet nad Attacking w każdej sytuacji, gdy agent czuje, że nie ma wystarczająco dużo zdrowia, aby pokonać przeciwnika. To pozwala na zmianę priorytetów działań na podstawie różnych kryteriów, co czyni takie podejście bardziej elastycznym i zmiennym niż drzewo behawioralne czy FSM.

Każde działanie ma wiele warunków do obliczenia programu. Można je zapisać w języku skryptowym lub w postaci serii formuł matematycznych. W The Sims, który modeluje codzienny rozkład dnia postaci, dodawany jest dodatkowy poziom obliczeń — agent otrzymuje szereg „motywacji”, które wpływają na oceny użyteczności. Jeśli postać jest głodna, to z czasem będzie głodniejsza, a wynik użyteczności działania EatFood będzie rósł, aż postać je, zmniejszając poziom głodu i przywracając wartość EatFood do zera.

Idea wyboru działań na podstawie systemu ocen jest dość prosta, dlatego systemy oparte na użyteczności można stosować jako część procesów podejmowania decyzji AI, a nie jako ich całkowitą alternatywę. Drzewo decyzyjne może zażądać oceny użyteczności dwóch węzłów podrzędnych i wybrać wyższą. Podobnie drzewo behawioralne może mieć złożony węzeł Utility do oceny użyteczności działań w celu podjęcia decyzji, który element podrzędny zrealizować.

Ruch i nawigacja

W poprzednich przykładach mieliśmy platformę, którą poruszaliśmy w lewo lub w prawo, oraz strażnika, który patrolował lub atakował. Jak jednak dokładnie przetwarzamy ruch agenta w określonym czasie? Jak ustalamy prędkość, jak omijamy przeszkody i jak planujemy trasę, jeśli dotarcie do celu jest trudniejsze niż po prostu poruszanie się w linii prostej? Przyjrzyjmy się temu.

Zarządzanie

Na początkowym etapie możemy założyć, że każdy agent ma wartość prędkości, która obejmuje, jak szybko się porusza i w jakim kierunku. Może być mierzona w metrach na sekundę, kilometrach na godzinę, pikselach na sekundę itd. Przypominając cykl Sense/Tink/Act, możemy wyobrazić sobie, że część Think wybiera prędkość, a część Act stosuje tę prędkość do agenta. Zwykle w grach istnieje system fizyki, który wykonuje to zadanie za ciebie, badając wartość prędkości każdego obiektu i regulując ją. Dlatego można pozostawić AI z jednym zadaniem — zdecydować, jaką prędkość powinien mieć agent. Jeśli wiadomo, gdzie agent ma być, należy przenieść go w odpowiednim kierunku z ustaloną prędkością. Bardzo trywialne równanie:

desired_travel = destination_position – agent_position

Wyobraź sobie świat 2D. Agent znajduje się w punkcie (-2,-2), a punkt docelowy znajduje się gdzieś na północnym-wschodzie w punkcie (30, 20), a wymagany ruch, aby agent mógł się tam znaleźć, wynosi (32, 22). Załóżmy, że te pozycje są mierzone w metrach — jeśli przyjmiemy prędkość agenta na poziomie 5 metrów na sekundę, to będziemy skalować nasz wektor przemieszczenia i uzyskamy prędkość około (4.12, 2.83). Przy takich parametrach agent dotarłby do miejsca przeznaczenia prawie po 8 sekundach.

Wartości można przeliczyć w dowolnym momencie. Jeśli agent był w połowie drogi do celu, przemieszczenie wynosiłoby połowę długości, ale ponieważ maksymalna prędkość agenta wynosi 5 m/s (to ustaliliśmy wcześniej), prędkość będzie taka sama. Działa to również dla ruchomych celów, pozwalając agentowi na wprowadzenie drobnych zmian podczas ich poruszania się.

Ale chcemy większej zmienności — na przykład powoli zwiększać prędkość, aby symulować postać, która przechodzi z pozycji stojącej do biegu. To samo można zrobić na końcu przed zatrzymaniem. Te funkcje są znane jako zachowania sterujące, z których każde ma swoje specyficzne nazwy: Seek (szukanie), Flee (ucieczka), Arrival (przybycie) itd. Idea polega na tym, że siły przyspieszenia mogą być stosowane do prędkości agenta, na podstawie porównania pozycji agenta i jego aktualnej prędkości z punktem docelowym, aby zastosować różne sposoby poruszania się w kierunku celu.

Każde zachowanie ma nieco inny cel. Seek i Arrival to sposoby na przemieszczenie agenta do punktu docelowego. Obstacle Avoidance (omijanie przeszkód) i Separation (separacja) korygują ruch agenta, aby unikać przeszkód na drodze do celu. Alignment (współdziałanie) i Cohesion (spójność) utrzymują agentów w ruchu razem. Dowolna liczba różnych zachowań sterujących może być sumowana, aby uzyskać jeden wektor ścieżki, uwzględniający wszystkie czynniki. Agent używa zachowań Arrival, Separation i Obstacle Avoidance, aby trzymać się z dala od ścian i innych agentów. To podejście dobrze działa w otwartych lokalizacjach bez zbędnych szczegółów.

W trudniejszych warunkach, sumowanie różnych zachowań działa gorzej - na przykład, agent może utknąć w ścianie z powodu konfliktu Arrival i Obstacle Avoidance. Dlatego należy rozważyć opcje, które są bardziej skomplikowane niż tylko sumowanie wszystkich wartości. Taki sposób: zamiast sumowania wyników każdego zachowania, można rozważyć ruch w różnych kierunkach i wybrać najlepszą opcję.

Jednak w skomplikowanym środowisku z zaułkami i wyborem kierunku, w jaką stronę iść, potrzebujemy czegoś jeszcze bardziej zaawansowanego.

Wyszukiwanie ścieżki

Zachowania sterujące doskonale nadają się do prostego poruszania się na otwartej przestrzeni (boisko piłkarskie lub arena), gdzie dotarcie od A do B to bezpośrednia droga z niewielkimi odchyleniami przy omijaniu przeszkód. Dla skomplikowanych tras potrzebujemy pathfinding (wyszukiwania ścieżki), który jest sposobem na zgłębianie świata i podejmowanie decyzji dotyczących trasy przez niego.

Najprostszy sposób to nałożenie siatki na każdy kwadrat obok agenta i ocena, w których z nich można się poruszać. Jeśli którykolwiek z nich jest celem, to podążaj za nim z każdego kwadratu do poprzedniego, aż dojdziesz do początku. To jest trasa. W przeciwnym razie powtarzaj proces z najbliższymi innymi kwadratami, aż znajdziesz miejsce docelowe lub skończą się kwadraty (co oznacza, że nie ma możliwej trasy). To, co formalnie znane jest jako przeszukiwanie wszerz (Breadth-First Search, BFS). Na każdym kroku patrzy we wszystkich kierunkach (stąd breadth, "szerokość"). Przestrzeń przeszukiwania przypomina falę, która porusza się, aż dotrze do miejsca, które jest szukane — obszar przeszukiwania rozszerza się z każdym krokiem, aż dotrze do punktu końcowego, po czym można śledzić drogę do początku.

W rezultacie otrzymasz listę kwadratów, według których zostanie stworzona potrzebna trasa. To jest ścieżka (stąd pathfinding) — lista miejsc, które agent odwiedzi, podążając do celu.

Mając na uwadze, że znamy położenie każdego kwadratu w świecie, możemy użyć zachowań sterujących, aby poruszać się po ścieżce — od węzła 1 do węzła 2, następnie od węzła 2 do węzła 3 i tak dalej. Najprostsza opcja to skierowanie się do środka następnego kwadratu, ale jeszcze lepszym pomysłem jest zatrzymanie się na środku krawędzi między bieżącym kwadratem a następnym. Dzięki temu agent będzie mógł skracać zakręty na ostrych zakrętach.

Algorytm BFS ma też swoje wady — bada tyle samo kwadratów w "niewłaściwym" kierunku, ile w "właściwym". Tutaj pojawia się bardziej zaawansowany algorytm nazwany A* (A star). Działa on podobnie, ale zamiast ślepo badać sąsiednie kwadraty (potem sąsiadów sąsiadów, potem sąsiadów sąsiadów sąsiadów itd.), zbiera węzły na liście i sortuje je tak, że następny badany węzeł jest zawsze tym, który poprowadzi do najkrótszej trasy. Węzły są sortowane na podstawie heurystyki, która bierze pod uwagę dwie rzeczy — "koszt" hipotetycznej trasy do docelowego kwadratu (w tym wszelkie koszty przemieszczania się) oraz ocenę, jak daleko ten kwadrat znajduje się od miejsca docelowego (przesuwając przeszukiwanie w odpowiednim kierunku).

W tym przykładzie agent bada jeden kwadrat na raz, za każdym razem wybierając najbliższy, który jest najbardziej obiecujący. Otrzymana ścieżka jest taka sama jak w przypadku BFS, ale w procesie rozważono mniej kwadratów — co ma ogromne znaczenie dla wydajności gry.

Ruch bez siatki

Jednak większość gier nie jest osadzona w siatce i często nie można jej stworzyć bez utraty realizmu. Wymagana jest równowaga. Jakie powinny być rozmiary kwadratów? Zbyt duże — nie będą w stanie odpowiednio przedstawić małych korytarzy czy zakrętów, zbyt małe — będzie zbyt wiele kwadratów do przeszukania, co ostatecznie zajmie mnóstwo czasu.

Pierwsze, co należy zrozumieć — siatka daje nam graf powiązanych węzłów. Algorytmy A* i BFS faktycznie działają na grafach i w ogóle nie interesuje je nasza siatka. Moglibyśmy umieścić węzły w dowolnych miejscach świata gry: przy istnieniu połączenia między dowolnymi dwoma połączonymi węzłami, a także między punktem początkowym i końcowym oraz przynajmniej jednym z węzłów — algorytm będzie działał tak samo dobrze jak wcześniej. Często nazywa się to systemem punktów kontrolnych (waypoint), ponieważ każdy węzeł reprezentuje znaczącą pozycję w świecie, która może być częścią dowolnej liczby hipotetycznych ścieżek.

Przykład 1: węzeł w każdym kwadracie. Wyszukiwanie zaczyna się od węzła, w którym znajduje się agent, i kończy w węźle żądanego kwadratu.

Przykład 2: mniejszy zestaw węzłów (punktów kontrolnych). Wyszukiwanie zaczyna się w kwadracie z agentem, przechodzi przez odpowiednią liczbę węzłów, a następnie kontynuuje do miejsca docelowego.

To dość elastyczny i potężny system. Ale wymagana jest ostrożność w decyzjach, gdzie i jak umieścić waypoint, w przeciwnym razie agenci mogą po prostu nie zobaczyć najbliższego punktu i nie będą mogli rozpocząć drogi. Byłoby łatwiej, gdybyśmy mogli automatycznie ustawić punkty kontrolne w oparciu o geometrię świata.

Tutaj wchodzi do gry siatka nawigacyjna lub navmesh. Jest to zazwyczaj 2D-mapa trójkątów, która nakłada się na geometrię świata — wszędzie tam, gdzie agent ma prawo chodzić. Każdy z trójkątów w siatce staje się węzłem w grafie i ma do trzech sąsiednich trójkątów, które stają się sąsiednimi węzłami w grafie.

Ten obraz jest przykładem z silnika Unity — przeanalizował on geometrię w świecie i stworzył navmesh (na zrzucie ekranu w jasnoniebieskim kolorze). Każdy poligon w navmesh to obszar, na którym agent może stać lub poruszać się z jednego poligonu do drugiego. W tym przykładzie poligony są mniejsze niż piętra, na których się znajdują — zrobiono to, aby uwzględnić rozmiary agenta, które będą wychodziły poza jego nominalne położenie.

Możemy szukać trasy przez tę siatkę, ponownie korzystając z algorytmu A*. Da nam to praktycznie idealną trasę w świecie, który uwzględnia całą geometrię i nie wymaga dodatkowych węzłów ani tworzenia punktów kontrolnych.

Zagadnienie pathfindingu jest zbyt obszerne, by zmieścić się w jednym rozdziale artykułu. Jeśli chcesz zgłębić ten temat, pomoże w tym strona Amita Patela.

Planowanie

Przekonaliśmy się, że czasami wystarczy nie tylko wybrać kierunek i iść — musimy wybrać trasę i wykonać kilka zwrotów, aby dotrzeć do celu. Możemy uogólnić tę myśl: osiągnięcie celu to nie tylko następny krok, ale cała sekwencja, gdzie czasem trzeba zajrzeć do przodu na kilka kroków, aby dowiedzieć się, jaki powinien być pierwszy. Nazywa się to planowaniem. Pathfinding można traktować jako jedno z wielu uzupełnień planowania. Z perspektywy naszego cyklu Sense/Think/Act, to jest to miejsce, gdzie część Think planuje kilka części Act na przyszłość.

Zanotujmy to na przykładzie gry planszowej Magic: The Gathering. Zaczynamy mając następujący zestaw kart w ręku:

• Swamp — daje 1 czarną manę (karta ziemi).
• Forest — daje 1 zieloną manę (karta ziemi).
• Fugitive Wizard — wymaga 1 niebieskiej many do przywołania.
• Elvish Mystic — wymaga 1 zielonej many do przywołania.

Ignorujemy trzy pozostałe karty dla uproszczenia. Zgodnie z zasadami gracz może zagrać 1 kartę ziemi w swojej turze, może 'tapnąć' tę kartę, aby uzyskać manę, a następnie użyć zaklęć (w tym przywołania stworzenia) zgodnie z ilością uzyskanej many. W tej sytuacji gracz-ludzki wie, że powinien zagrać Forest, 'tapnąć' 1 zieloną manę, a następnie przywołać Elvish Mystic. Ale jak ma to odgadnąć sztuczna inteligencja gry?

Proste planowanie

Tradycyjnego podejścia — próbować każde działanie po kolei, aż nie pozostaną odpowiednie. Patrząc na karty, AI widzi, że może zagrać Swamp. I gra go. Czy są inne akcje w tej turze? Nie może zagrać ani Elvish Mystic, ani Fugitive Wizard, ponieważ ich zagraniu potrzebna jest odpowiednio zielona i niebieska mana, a Swamp daje tylko czarną manę. I już nie może zagrać Forest, bo już zagrał Swamp. Tak więc, AI zagrał zgodnie z zasadami, ale zrobił to źle. Można to poprawić.

Planowanie może znaleźć listę działań, które prowadzą do pożądanego stanu gry. Tak jak każda kwadrat na ścieżce miała sąsiadów (w pathfinding), każda akcja w planie ma również sąsiadów lub następców. Możemy wyszukiwać te działania i następne, aż osiągniemy pożądany stan.

W naszym przykładzie, pożądany wynik to „wezwać stworzenie, jeśli to możliwe”. Na początku tury widzimy tylko dwa możliwe działania, dozwolone przez zasady gry:

1. Zagrać Swamp (wynik: Swamp w grze)
2. Zagrać Forest (wynik: Forest w grze)

Każde podjęte działanie może prowadzić do dalszych działań i zablokować inne, znowu w zależności od zasad gry. Wyobraź sobie, że zagraliśmy Swamp — to usunie Swamp jako następny krok (już go zagraliśmy), a także usunie Forest (ponieważ według zasad można zagrać jedną kartę lądów na turę). Następnie AI dodaje jako następny krok — otrzymanie 1 czarnej many, ponieważ nie ma innych opcji. Jeśli pójdzie dalej i zdecyduje się na Tap the Swamp, otrzyma 1 jednostkę czarnej many i nic z nią nie będzie mógł zrobić.

1. Zagrać Swamp (wynik: Swamp w grze)
1.1 „Tапнуть” Swamp (wynik: Swamp „tапнута”, +1 jednostka czarnej many)
Brak dostępnych działań – KONIEC
2. Zagrać Forest (wynik: Forest w grze)

Lista działań okazała się krótka, utknęliśmy w martwym punkcie. Powtarzamy proces dla następnego działania. Gramy Forest, otwieramy działanie „otrzymać 1 zieloną manę”, które z kolei otworzy trzeci krok — wezwanie Elvish Mystic.

1. Zagrać Swamp (wynik: Swamp w grze)
1.1 „Tапнуть” Swamp (wynik: Swamp „tапнута”, +1 jednostka czarnej many)
Brak dostępnych działań – KONIEC
2. Zagrać Forest (wynik: Forest w grze)
2.1 „Tапнуть” Forest (wynik: Forest „tапнута”, +1 jednostka zielonej many)
2.1.1 Wezwać Elvish Mystic (wynik: Elvish Mystic w grze, -1 jednostka zielonej many)
Brak dostępnych działań – KONIEC

W końcu zbadaliśmy wszystkie możliwe działania i znaleźliśmy plan wzywający stworzenie.

To bardzo uproszczony przykład. Najlepiej wybierać najlepszy możliwy plan, a nie byle jaki, który spełnia jakieś kryteria. Zazwyczaj można ocenić potencjalne plany na podstawie ostatecznego wyniku lub całkowitych korzyści z ich realizacji. Można zdobyć 1 punkt za zagrane pole ziemi i 3 punkty za przywołanie istoty. Zagrana Swamp dałaby 1 punkt. A zagranie Forest → Taping Forest → przywołując Elvish Mystic — od razu dałoby 4 punkty.

Tak działa planowanie w Magic: The Gathering, ale ta sama logika stosuje się również w innych sytuacjach. Na przykład przesunięcie piona, aby zrobić miejsce dla ruchu gońca w szachach. Lub schowanie się za ścianą, aby bezpiecznie strzelać w XCOM. W skrócie, rozumiesz o co chodzi.

Ulepszone planowanie

Czasami jest zbyt wiele potencjalnych działań, aby rozważać każdą możliwą opcję. Wracając do przykładu z Magic: The Gathering: powiedzmy, że w grze masz kilka kart ziemi i istot — ilość możliwych kombinacji ruchów może sięgać dziesiątek. Istnieje kilka rozwiązań tego problemu.

Pierwszy sposób — backwards chaining (wsteczne formowanie łańcucha). Zamiast przeszukiwać wszystkie kombinacje, lepiej zacząć od ostatecznego wyniku i próbować znaleźć bezpośrednią trasę. Zamiast przechodzić od korzenia drzewa do określonego liścia, poruszamy się w przeciwnym kierunku — od liścia do korzenia. Ten sposób jest prostszy i szybszy.

Jeśli przeciwnik ma 1 punkt zdrowia, możesz znaleźć plan „zadać 1 lub więcej punktów obrażeń”. Aby to osiągnąć, musisz spełnić szereg warunków:

1. Obrażenia mogą zadać czary — muszą być w ręce.
2. Aby zagrać czar — potrzebna jest mana.
3. Aby uzyskać manę — musisz zagrać kartę ziemi.
4. Aby zagrać kartę ziemi — musisz mieć ją w ręce.

Inny sposób — best-first search (najlepsze pierwsze wyszukiwanie). Zamiast przeszukiwać wszystkie ścieżki, wybieramy najodpowiedniejszy. Najczęściej ten sposób daje optymalny plan bez zbędnych kosztów na poszukiwania. A* — to forma najlepszego pierwszego wyszukiwania — badając najbardziej obiecujące trasy od samego początku, może już znaleźć najlepszą drogę bez potrzeby sprawdzania pozostałych opcji.

Interesującą i coraz bardziej popularną opcją wyszukiwania best-first jest Monte Carlo Tree Search. Zamiast zgadywania, które plany są lepsze od innych przy wyborze każdego kolejnego działania, algorytm wybiera losowych następców na każdym kroku, aż dojdzie do końca (gdy plan prowadzi do zwycięstwa lub porażki). Następnie ostateczny wynik jest używany do zwiększenia lub zmniejszenia oceny „wagi” wcześniejszych opcji. Powtarzając ten proces wielokrotnie, algorytm dostarcza dobrego oszacowania tego, jaki następny krok będzie najlepszy, nawet jeśli sytuacja się zmieni (jeśli przeciwnik podejmie działania, aby przeszkodzić graczowi).

W opowieści o planowaniu w grach nie można pominąć Goal-Oriented Action Planning lub GOAP (planowanie działań zorientowane na cel). To szeroko stosowana i omawiana metoda, ale oprócz kilku wyróżniających się detali jest to właściwie metoda backwards chaining, o której rozmawialiśmy wcześniej. Jeśli zadanie brzmi „zniszczyć gracza”, a gracz znajduje się za osłoną, plan może wyglądać następująco: zniszcz granatami → weź je → rzuć.

Zwykle istnieje kilka celów, z których każdy ma swój priorytet. Jeśli cel o najwyższym priorytecie nie może być zrealizowany (żadna kombinacja działań nie tworzy planu „zniszczyć gracza”, ponieważ gracz jest niewidoczny), AI wróci do celów o niższym priorytecie.

Uczenie się i adaptacja

Już wcześniej wspomnieliśmy, że AI w grach zazwyczaj nie korzysta z uczenia maszynowego, ponieważ nie nadaje się to do zarządzania agentami w czasie rzeczywistym. Ale to nie znaczy, że nie można niczego pożyczyć z tej dziedziny. Chcemy, aby nasz przeciwnik w strzelance mógł się czegoś nauczyć. Na przykład dowiedzieć się o najlepszych pozycjach na mapie. Lub przeciwnik w bijatyce, który blokowałby często używane przez gracza kombinacje, motywując do używania innych. Tak więc uczenie maszynowe w takich sytuacjach może być bardzo przydatne.

Statystyka i prawdopodobieństwa

Zanim przejdziemy do bardziej złożonych przykładów, przyjrzyjmy się, jak daleko możemy zajść, biorąc kilka prostych pomiarów i wykorzystując je do podejmowania decyzji. Na przykład, strategia w czasie rzeczywistym — jak możemy określić, czy gracz będzie mógł rozpocząć atak w pierwszych minutach gry i jak przygotować obronę przeciwko temu? Możemy zbadać wcześniejsze doświadczenia gracza, aby zrozumieć, jak może wyglądać jego przyszła reakcja. Zaczniemy od tego, że nie mamy takich danych wyjściowych, ale możemy je zebrać — za każdym razem, gdy AI gra przeciwko człowiekowi, może zapisywać czas pierwszego ataku. Po kilku sesjach uzyskamy średnią wartość czasu, po którym gracz zaatakuje w przyszłości.

Średnie wartości mają także swoją wadę: jeśli gracz 20 razy atakował szybko, a 20 razy grał wolno, to potrzebne wartości będą gdzieś pośrodku, a to nam nie pomoże. Jednym z rozwiązań jest ograniczenie danych wejściowych — możemy uwzględnić ostatnie 20 przypadków.

Podobne podejście jest stosowane przy ocenie prawdopodobieństwa określonych działań, zakładając, że wcześniejsze preferencje gracza będą takie same w przyszłości. Jeśli gracz atakował nas pięć razy kulą ognia, dwa razy błyskawicą i jeden raz w walce wręcz, to oczywiste, że preferuje on kulę ognia. Ekstrapolując, widzimy prawdopodobieństwo użycia różnych rodzajów broni: kula ognia = 62,5%, błyskawica = 25% i walka wręcz = 12,5%. Nasze grające AI musi przygotować się na obronę przed ogniem.

Inną interesującą metodą jest użycie Naive Bayes Classifier (naivnego klasyfikatora Bayesa) do analizy dużych zbiorów danych wejściowych i klasyfikowania sytuacji, aby AI reagowało w odpowiedni sposób. Klasyfikatory Bayesa są najbardziej znane z zastosowania w filtrach spamowych poczty elektronicznej. Tam analizują słowa, porównują je z tym, gdzie te słowa pojawiały się wcześniej (w spamie czy nie), a następnie wyciągają wnioski na temat nadchodzących wiadomości. Możemy zrobić to samo nawet przy mniejszej ilości danych wejściowych. Na podstawie wszystkich użytecznych informacji, które widzi AI (np. jakie jednostki wroga zostały stworzone, jakie zaklęcia są używane lub jakie technologie zostały zbadane) oraz wyniku końcowego (wojna czy pokój, „atakować” czy bronić się itd.) — wybierzemy odpowiednie zachowanie AI.

Wszystkie te metody uczenia są wystarczające, ale najlepiej stosować je na podstawie danych z testów. AI nauczy się dostosowywać do różnych strategii, które stosowali twoi testerzy gry. AI, które dostosowuje się do gracza po premierze, może stać się zbyt przewidywalne lub odwrotnie — zbyt trudne do pokonania.

Dostosowanie na podstawie wartości

Biorąc pod uwagę zawartość naszego świata gry i zasady, możemy zmienić zestaw wartości, które wpływają na podejmowanie decyzji, a nie tylko używać danych wejściowych. Robimy to w ten sposób:

• Niech AI zbiera dane o stanie świata i kluczowych wydarzeniach w trakcie gry (jak wspomniano powyżej).
• Zmienimy kilka ważnych wartości na podstawie tych danych.
• Wdrażamy nasze decyzje, oparte na przetwarzaniu lub ocenie tych wartości.

Na przykład, agent ma kilka pokoi do wyboru na mapie strzelanki z pierwszej osoby. Każdy pokój ma swoją wartość, która określa, jak bardzo jest pożądany do odwiedzenia. AI losowo wybiera, do którego pokoju pójść, bazując na wartości. Następnie agent zapamiętuje, w którym pokoju został zabity i zmniejsza jego wartość (prawdopodobieństwo, że tam wróci). Podobnie w przypadku odwrotnej sytuacji — jeśli agent zabije wielu przeciwników, wartość pokoju wzrasta.

Model Markowa

Co jeśli użyjemy zebranych danych do prognozowania? Jeśli zapamiętamy każdy pokój, w którym widzimy gracza przez określony czas, będziemy mogli przewidzieć, do którego pokoju gracz może przejść. Śledząc i zapisując ruchy gracza po pokojach (wartości), możemy je prognozować.

Weźmy trzy pokoje: czerwony, zielony i niebieski. A także obserwacje, które zapisaliśmy podczas oglądania sesji gry:

Liczba obserwacji dla każdego pokoju jest prawie równa — jeszcze nie wiemy, gdzie stworzyć dobre miejsce do zasadzki. Zbieranie statystyk jest również utrudnione przez respawn graczy, którzy pojawiają się równomiernie na całej mapie. Ale dane o następnym pokoju, do którego wchodzą po pojawieniu się na mapie, są już przydatne.

Widać, że zielony pokój zadowala graczy - większość osób z czerwonego przechodzi do niego, z czego 50% pozostaje tam dłużej. Niebieski pokój z kolei nie cieszy się popularnością, prawie nikt do niego nie chodzi, a jeśli już, to nie zatrzymuje się tam.

Jednak dane mówią nam coś bardziej istotnego - gdy gracz znajduję się w niebieskim pokoju, następny pokój, w którym najprawdopodobniej go zobaczymy, będzie czerwony, a nie zielony. Pomimo że zielony pokój jest bardziej popularny niż czerwony, sytuacja się zmienia, gdy gracz znajduje się w niebieskim. Następny stan (czyli pokój, do którego gracz przejdzie) zależy od poprzedniego stanu (czyli pokoju, w którym gracz obecnie się znajduje). Dzięki badaniu zależności będziemy w stanie przewidywać dokładniej, niż gdybyśmy po prostu liczyli obserwacje niezależnie od siebie.

Przewidywanie przyszłego stanu na podstawie danych z przeszłego stanu nazywa się modelem Markowa (Markov model), a takie przykłady (z pokojami) nazywane są łańcuchami Markowa. Ponieważ modele przedstawiają prawdopodobieństwo zmian między kolejnymi stanami, wizualizuje się je w postaci FSM z prawdopodobieństwem przy każdym przejściu. Wcześniej używaliśmy FSM do przedstawienia stanu behawioralnego, w którym znajdował się agent, ale ta koncepcja rozciąga się na każdy stan, niezależnie od tego, czy jest związany z agentem, czy nie. W tym przypadku stany reprezentują pokój, który zajmuje agent:

To prosty sposób przedstawienia względnego prawdopodobieństwa zmian stanów, dający SI pewną możliwość przewidywania następnego stanu. Można przewidywać kilka kroków naprzód.

Jeśli gracz jest w zielonym pokoju, istnieje 50% szans, że tam zostanie przy następnej obserwacji. Ale jakie jest prawdopodobieństwo, że nadal tam będzie nawet później? Istnieje nie tylko szansa, że gracz pozostał w zielonym pokoju po dwóch obserwacjach, ale również szansa, że odszedł i wrócił. Oto nowa tabela uwzględniająca nowe dane:

Z niej wynika, że szansa na zobaczenie gracza w zielonym pokoju po dwóch obserwacjach wyniesie 51% - 21% szans, że przybędzie z czerwonego pokoju, 5% z nich, że gracz odwiedził niebieski pokój pomiędzy nimi, oraz 25%, że gracz w ogóle nie opuścił zielonego pokoju.

Tabela — to po prostu czytelne narzędzie — proces wymaga tylko mnożenia prawdopodobieństw na każdym kroku. Oznacza to, że możesz zajrzeć daleko w przyszłość, z jednym zastrzeżeniem: zakładamy, że szansa na wejście do pokoju w pełni zależy od aktualnego pokoju. Nazywa się to właściwością Markowa (Markov Property) — przyszły stan zależy tylko od teraźniejszości. Ale nie jest to w 100% pewne. Gracze mogą zmieniać decyzje w zależności od innych czynników: poziom zdrowia lub ilość amunicji. Ponieważ nie rejestrujemy tych wartości, nasze prognozy będą mniej dokładne.

N-Gramy

A co z przykładem walki i przewidywaniem kombinacji ruchów gracza? To to samo! Ale zamiast jednego stanu lub zdarzenia będziemy badać całe sekwencje, z których składa się kombinasja ciosów.

Jednym ze sposobów, aby to zrobić, jest przechowywanie każdego wejścia (np. Kick, Punch lub Block) w buforze i zapisanie całego bufora jako zdarzenie. Gracz wielokrotnie naciska Kick, Kick, Punch, aby użyć ataku SuperDeathFist, system AI przechowuje wszystkie wejścia w buforze i zapamiętuje ostatnie trzy, używane na każdym kroku.

(Pogrubione linie, gdy gracz uruchamia atak SuperDeathFist.)

AI zobaczy wszystkie możliwości, gdy gracz wybrał Kick, następnie kolejny Kick, a potem zauważy, że następne wejście to zawsze Punch. To pozwoli agentowi przewidzieć kombinację SuperDeathFist i zablokować ją, jeśli to możliwe.

Te sekwencje zdarzeń nazywają się N-gramami (N-grams), gdzie N to liczba przechowywanych elementów. W poprzednim przykładzie była to 3-grama (trigram), co oznacza: pierwsze dwa zapisy są używane do przewidywania trzeciego. Odpowiednio w 5-gramie pierwsze cztery zapisy przewidują piątą i tak dalej.

Programista musi starannie dobierać rozmiar N-gramów. Mniejsza liczba N wymaga mniej pamięci, ale przechowuje mniejszą historię. Na przykład 2-gram (bigram) zapisze Kick, Kick lub Kick, Punch, ale nie będzie w stanie przechować Kick, Kick, Punch, dlatego AI nie zareaguje na kombinację SuperDeathFist.

Z drugiej strony, większe liczby wymagają więcej pamięci i AI będzie trudniej się nauczyć, ponieważ pojawi się znacznie więcej możliwych wariantów. Jeśli masz trzy możliwe wejścia Kick, Punch lub Block, a używaliśmy 10-gramy, to powstanie około 60 tysięcy różnych wariantów.

Model bigramy to prosta łańcuch Markowa — każda para „stan przeszły/stanu obecnego” jest bigramem i można przewidzieć drugi stan na podstawie pierwszego. 3-gramy i większe N-gramy również można traktować jako łańcuchy Markowa, gdzie wszystkie elementy (z wyjątkiem ostatniego w N-gramie) wspólnie tworzą pierwszy stan, a ostatni element — drugi. Przykład z walką pokazuje szansę przejścia od stanu Kick i Kick do stanu Kick i Punch. Rozpatrując wiele zapisów historii wejściowej jako jedną jednostkę, zasadniczo przekształcamy sekwencję wejściową w część całego stanu. Daje nam to właściwość Markowa, która pozwala na użycie łańcuchów Markowa do przewidywania następnego wejścia i zgadywania, jaki ruch combo będzie następny.

Podsumowanie

Omówiliśmy najczęściej używane narzędzia i podejścia w rozwijaniu sztucznej inteligencji. Przeanalizowaliśmy także sytuacje, w których należy je stosować i gdzie są one szczególnie przydatne.

To powinno wystarczyć do zrozumienia podstawowych rzeczy w AI w grach. Oczywiście to nie wszystkie metody. Do mniej popularnych, ale wciąż skutecznych zaliczają się:

• algorytmy optymalizacji, w tym wspinaczka po wzgórzach, spadek gradientowy i algorytmy genetyczne
• konkurencyjne algorytmy wyszukiwania/planningu (minimax i przycinanie alpha-beta)
• metody klasyfikacji (perceptrony, sieci neuronowe i maszyny wektorów nośnych)
• systemy do przetwarzania percepcji i pamięci agentów
• architektoniczne podejścia do AI (systemy hybrydowe, podzbiory architektur i inne sposoby nakładania systemów AI)
• narzędzia animacji (planowanie i synchronizacja ruchu)
• czynniki wydajności (poziom szczegółowości, algorytmy anytime i timeslicing)

Zasoby internetowe na ten temat:

1. Na GameDev.net znajduje się sekcja z artykułami i samouczkami na temat AI, a także forum.
2. AiGameDev.com zawiera wiele prezentacji i artykułów na szeroki zakres tematów związanych z rozwojem AI w grach.
3. The GDC Vault zawiera tematy z szczytu GDC AI, z których wiele dostępnych jest za darmo.
4. Przydatne materiały można również znaleźć na stronie AI Game Programmers Guild.
5. Tommy Thompson, badacz AI i deweloper gier, publikuje filmy na YouTube-канале AI and Games z wyjaśnieniami i badaniami AI w komercyjnych grach.

Książki na ten temat:

1. Seria książek Game AI Pro to zbiory krótkich artykułów, wyjaśniających, jak wdrażać konkretne funkcje lub jak rozwiązywać specyficzne problemy.

Game AI Pro: Zgromadzona mądrość profesjonalistów AI w grach
Game AI Pro 2: Zgromadzona mądrość profesjonalistów AI w grach
Game AI Pro 3: Zgromadzona mądrość profesjonalistów AI w grach

2. Seria AI Game Programming Wisdom to poprzednik serii Game AI Pro. Zawiera starsze metody, ale niemal wszystkie są aktualne nawet dzisiaj.

AI Game Programming Wisdom 1
AI Game Programming Wisdom 2
AI Game Programming Wisdom 3
AI Game Programming Wisdom 4

3. Sztuczna inteligencja: nowoczesne podejście — to jedna z podstawowych książek dla wszystkich, którzy chcą zrozumieć ogólną dziedzinę sztucznej inteligencji. To książka, która nie dotyczy tworzenia gier, a naucza podstawowych zasad AI.

Źródło: habr.com