Autor Wątek: RTS -> AI = Czego używać ???  (Przeczytany 8550 razy)

Offline Cris_eM

  • Użytkownik

# Lipiec 17, 2007, 23:18:19
Witam wszystkich  ;D
jako nowy  :D
Na wstepie chcialem zadac wam pytanie na temat czego waszym zdaniem najlepiej uzywac w celu uzyskania "inteligecji" w grach RTS ??

Zastanawiam sie co i kiedy jest bardziej wydajne i efektywne , czy automaty skonczone , czy logika rozmyta , a moze sieci neuronowe ( choc to chyba ciezko wdrozyc z sukcesem do RTS) . Moze wskazane sa jakies mieszane rozwiazania?


jakie jest wasze zdanie?

moze wiecie jakie rozwiazania stosowali niektorzy produceci w swoich grach?

Pozdrawiam jeszcze raz wszystkich ;D

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Tarains

  • Gość
# Lipiec 18, 2007, 00:03:36
Ja stawiałbym na automaty stanów. :)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Lipiec 18, 2007, 00:56:18
moze wiecie jakie rozwiazania stosowali niektorzy produceci w swoich grach?
Z tego, co wiem, przede wszystkim heurystyki - myślisz, jak Ty byś zagrał, a potem to opisujesz kodem. Im więcej różnych sytuacji przewidzisz w ten sposób, tym lepiej. :)

Tarains

  • Gość
# Lipiec 18, 2007, 01:06:58
moze wiecie jakie rozwiazania stosowali niektorzy produceci w swoich grach?
Z tego, co wiem, przede wszystkim heurystyki - myślisz, jak Ty byś zagrał, a potem to opisujesz kodem. Im więcej różnych sytuacji przewidzisz w ten sposób, tym lepiej. :)

Można też po prostu grać wiele razy i zaprząc program do opisywania sytuacji skryptem, tak by uczył się przez obserwację (w którymś tomie Perełek wypisane są założenia czegoś takiego)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Lipiec 18, 2007, 01:16:36
Można też po prostu grać wiele razy i zaprząc program do opisywania sytuacji skryptem, tak by uczył się przez obserwację (w którymś tomie Perełek wypisane są założenia czegoś takiego)
To nie przejdzie. RTS'y są na tyle złożone, że w ogólności taki system będzie niewykonalny przynajmniej na razie, ponieważ system sam z siebie na podstawie obserwacji nie będzie w stanie stworzyć poprawnej interpolacji danych uczących. Co do Perełek - założenia można wypisać nawet dla teorii budowy tuneli czasoprzestrzennych (co zresztą i fizycy teoretyczni czynią), więc jest to jedynie idea. Nie wystarczy wiedzieć, jak można zareagować w danej sytuacji - żeby dobrze grać trzeba wiedzieć dlaczego. :)

Offline Liosan

  • Moderator

# Lipiec 18, 2007, 01:18:01
1. automaty skończone będą dobre dla poszczególnych jednostek, ew. możesz ułożyć "hierarchie stanów" - zmiana stanu dla grupy jednostek jest sygnałem dla wszystkich jednostek z grupy (albo wymusza im zmianę stanu). Są dość popularne, nawet jeśli koder nie pisze "finite state automaton" to zwykle jego kod działa w sposób, który ładnie i elegancko dałby się zapisać jako automat.

2. Logika rozmyta jest jednym z najczęstszych rozwiązań (na 100% w Kohanie, prawie na pewno w kilku innych), bo wymaga najmniej wysiłku od programisty i jest w miarę wydajna. Plus jeśli masz mnóstwo mocy obliczeniowej możesz ją łatwo ewoluować (i tak nie zastąpi to twoich intuicji).

3. Sieci neuronowe są przede wszystkim modne :P Nie są takie suuuper jak się mówi. Na pewno same nie wystarczą - są albo mało skuteczne (w pojedynkę), albo wymagają dużo mocy obliczeniowej. Ale mają też zalety: nieźle się uczą (algorytm back-propagation), potrafią rozpoznawać rzeczy trudne do opisania przez programistę (np. styl gry gracza) i stanowią całkiem niezłe uzupełnienie logiki rozmytej. Możesz ich użyć razem z logiką rozmytą do określania indywidualnego stylu gry poszczególnych AI, albo starać się przewidzieć zachowanie gracza (dość zaawansowane featuresy...). Polecam bibliotekę FANN (Fast Artificial Neural Network).

4. Sieci bayessowskie: na pierwszy rzut oka podobne do logiki rozmytej, ale operują na czym innym: logika rozmyta mówi o "Stopniu prawdziwości", a sieci b. o "prawdopodobieństwie zajścia". Posługując się wzorem Bayessa i siecią zależnych zdarzeń można wnioskować o p-stwie zdarzeń w przyszłości na podstawie decyzji. Mogą stanowić niezłe wsparcie procesu podejmowania decyzji.

5. Systemy regułowe / drzewa decyzyjne: zestaw zasad typu "jeśli coś i coś to coś".  Np. "jeśli przeciwnik ma dużo kopalń, zróbmy wojnę podjazdową" albo "jeśli przeciwnik ma kawalerię, zróbmy włóczników" etc. Chyba widać czemu przydatne :)

Najważniejsze: powyższe rzeczy są fajowe, ale muszą na czymś operować. Potrzebna jest pewna abstrakcja danych gry. Można to podzielić na dwie kategorie (podział własny :P):

- heurystyczne funkcje oceniające: jak dobra jest sytuacja na mapie? kto ma najlepszą ekonomię? kto ma największą armię? gdzie widziano najwięcej wroga? co mi się najbardziej opłaca zescoutować?

- cele i podcele: wyznaczane przez systemy 1-6 na podstawie wartości f-cji oceniających. Wypada mieć jasno i precyzyjnie wyabstrahowane, że celem AI może być "zdobycie miasta", "polepszenie ekonomii", "ocalenie tej jednostki", "styl walki podjazdowej", "okopanie się i rozbudowa" etc. Zarówno ogólne, jak i konkretne.

Uff. Koniec wypracowania :P
Pozdrawiam,

Liosan

Offline Cris_eM

  • Użytkownik

# Lipiec 18, 2007, 01:40:25
Można też po prostu grać wiele razy i zaprząc program do opisywania sytuacji skryptem, tak by uczył się przez obserwację (w którymś tomie Perełek wypisane są założenia czegoś takiego)
Cos takiego przypomina koncepcje sieci neuronowej ;-)

To nie przejdzie. RTS'y są na tyle złożone, że w ogólności taki system będzie niewykonalny przynajmniej na razie, ponieważ system sam z siebie na podstawie obserwacji nie będzie w stanie stworzyć poprawnej interpolacji danych uczących. Co do Perełek - założenia można wypisać nawet dla teorii budowy tuneli czasoprzestrzennych (co zresztą i fizycy teoretyczni czynią), więc jest to jedynie idea. Nie wystarczy wiedzieć, jak można zareagować w danej sytuacji - żeby dobrze grać trzeba wiedzieć dlaczego. :)
Wiesz wydaje mi sie ze napewno trzeba bylo by uwzglenic jakies kryterium oceny wynikow uczenia ktore rozwiazanie jest lepsze gorsze . Ale masz racje problem wydaje mi sie bardzo zlozony.
Pozatym jest pytanie : jak uczyc Automat stanow , przebudowujac graf ?

Z innej strony czy heurystyki ( uwzgledniajace wiele wariantow ktore przyjda do glowy tworcom ) nie powoduja powstawania bardzo rozleglych skryptow sztucznej inteligecji ??
 
tu nasuwa mi sie jeszcze jedno Pytanie uzupelniajace .
Czy wiecie moze jak mozna szacowac zlozonosc obliczeniowa kazdego z tych rozwiazan ?
Z tego co pamietam w grze Shogun kierowalo sie jednostkami ktorych ilosc szla w tysiace (choc to byla troche inna specyfika strategi -formacje szyki itp) natomiast w StarCraft  zadko przekracza to setke .

Cris_eM

Offline Cris_eM

  • Użytkownik

# Lipiec 18, 2007, 02:04:32
Liosan dzieki za wyczerpujaca odpowiedz  ;D

Mam pytanie do Sieci neuronowej ;-)
Zgadzam sie wiele osob bardzo lubie uzywac tego terminu jak sie da ;-)

(jesli sie myle to prosze o skorygowanie )
Funkcjonowanie sieci neuronowej mozna podzielic na dwa etapy - Uczenie i "uzywanie"
do uczenia mozna stosowac wiele metod lacznie z genetycznymi
natmioast "uzywanie" nauczonej juz sieci nie wiele sie wedlug mnie rozni od uzywania logiki rozmytej w ktorej wartosci wszystkie funkcje zostaly zadane w wyniku uczenia (zamiast zadane przez tworce). (pomijam kwestie roznej budowy sieci neur.= warstw ,ilosci neuronow)

Czy nie jest tak ze samo uczenie pochlania duza moc (aby wyszkolic ja w pewnym stylu gry gracza) a samo jej uzywanie nie jest juz tak obciazajace??

hmmm ale tez nawiazujac do tego co pisal Krzysiek.K Heurystyki = zauwazenie i zaimplemetowanie pewnych zaleznosci , znacznie potrafi obnizyc koszt obliczeniowy takiej inteligecji niz uzycie nauczonej sieci ktora aby reagowac "Inteligetnie"-> wydajnie musi skladac sie z paru warstw po kilkanascie neuronow  :/

ps. czy jakas Gra RTS uzywa uczenia jednostek ? czy opieraja sie na heurystykach??   ( moze StarCraft2 albo Spore ???)

Cris_eM

Offline Liosan

  • Moderator

# Lipiec 18, 2007, 02:42:14
ciekawy temat to sie produkuję :P

to jeszcze parę komentarzy:

Heurystyki rządzą :) Im więcej heurystyk zaimplementujesz i przetestujesz, tym lepiej. Wybierzesz najlepszy zestaw, resztę odrzucisz. To jest definitywnie najlepsze rozwiązanie. Dodaj do tego logikę rozmytą i IMHO wystarczy. Łatwo można tweakować i widać jak wszystko działa.

Złożoność wszystkich tych rozwiązań jest mniej więcej podobna, najwięcej mocy będą żreć sieci neuronowe albo bayessowskie (zależne od ilości połączeń pomiędzy węzłami, czyli kwadratowe w ogólności).

Akurat przykład z Shogunem jest kiepski - tam gracze mieli typowo po 10 jednostek - no, maks kilkadziesiąt. Co z tego że ludków jest po 100 w każdym? z punktu widzenia "globalnego" AI (tego dla całego gracza) to nie ma znaczenia. A algorytmy sterowania pojedynczymi jednostkami są raczej proste obliczeniowo, niedawno był nawet topic w tym temacie. Dużo ciekawsze pod tym względem są chociażby Darwinia (choć to taki mało-rtsowy twór...) albo Heroes of Annihilated Empires (czy jakoś tak). W obu grach bywa po kilkaset samodzielnych jednostek. Niestety mało mi wiadomo na temat użytych technik :)

Co do uczenia sieci neuronowych - zależy. Mając daną strukturę sieci, możesz użyć algorytmu back-propagation, który działa niewiele wolniej (w sensie: tylko kilka razy) niż zwykłe wykorzystanie sieci. Z drugiej strony, jeśli nie masz struktury sieci, to musisz ją skądś dostać - to wchodzi ewolucja, iteracyjne poprawianie i Bóg wie jeszcze jakie metody rozwiązywania problemów NP-zupełnych. A projektowanie sieci neuronowych "z ręki" to sztuka bardzo piękna, niestety cholernie trudna :)

Nie widziałem nigdy RTSa uczącego się od żywego gracza. Być może analiza przebiegów rozgrywki jest jednym ze sposobów tworzenia AI w fazie produkcji.

W sumie polecam heurezy + logika rozmyta, ew. jakieś reguły dla dynamicznego reagowania na działania wroga. Reszta to sfera eksperymentów :)

A tak zupełnie na marginesie: chyba większość RTSów po prostu daje AI fory :P rozwiązanie głupie bo głupie, ale gra się trochę lepiej sprzeda...

Liosan

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Lipiec 18, 2007, 11:44:23
Co bym radził przede wszystkim, to pomyśleć o AI na kilku, co najmniej dwóch poziomach - określaniu ogólnej strategii (teraz zaatakujemy bazę wroga tutaj, teraz poszukamy nowych surowców tam) i jej realizowaniu (teraz tą grupę jednostek przesunę w tamto miejsce, teraz każe im atakować). Do tego dochodzi jeszcze poziom zachowania poszczególnych jednostek, które sprawdzają kolizje, szukają drogi itd. Takie wielopoziomowe podejście sprawdza się z resztą w różnych grach - mnie na przykład sprawdziło się do sterowania samochodami w grze w stylu GTA :)

StarCraft miał o ile pamiętam coś takiego jak skrypty sterujące Build-Upem bazy, mówiące co po kolei budować (5 robotników, barak, gazownia, farma, 2 żołnierzy itp.). Jest co prawda tendencja żeby w nowoczesnych grach jak najwięcej AI "samo" powstawało, bez oskryptowania, ale to też jakaś propozycja.

Sieci neuronowe i algorytmy genetyczne... wiem że to modny temat i każdy lubi się pochwalić że się na nim zna, ale pokażcie gry w których naprawdę zostały użyte :)

Offline Cris_eM

  • Użytkownik

# Lipiec 18, 2007, 13:30:17
Co bym radził przede wszystkim, to pomyśleć o AI na kilku, co najmniej dwóch poziomach - określaniu ogólnej strategii (teraz zaatakujemy bazę wroga tutaj, teraz poszukamy nowych surowców tam) i jej realizowaniu (teraz tą grupę jednostek przesunę w tamto miejsce, teraz każe im atakować). Do tego dochodzi jeszcze poziom zachowania poszczególnych jednostek, które sprawdzają kolizje, szukają drogi itd. Takie wielopoziomowe podejście sprawdza się z resztą w różnych grach - mnie na przykład sprawdziło się do sterowania samochodami w grze w stylu GTA :)

StarCraft miał o ile pamiętam coś takiego jak skrypty sterujące Build-Upem bazy, mówiące co po kolei budować (5 robotników, barak, gazownia, farma, 2 żołnierzy itp.). Jest co prawda tendencja żeby w nowoczesnych grach jak najwięcej AI "samo" powstawało, bez oskryptowania, ale to też jakaś propozycja.

Sieci neuronowe i algorytmy genetyczne... wiem że to modny temat i każdy lubi się pochwalić że się na nim zna, ale pokażcie gry w których naprawdę zostały użyte :)

Wiesz nie chodzi mi o to by sie chwalic ze sie znam ( bo wedlog mojego mniemania mam na ten temat pojecie ale do znania sie to jeszcze daleko ;-) )

 ;D Chodzi mi przedewszystkim to czy ktos probowal zastosowac cos bardziej uniwersalnego i jak to sie sprawdzilo, jak wiadomo Ustalony staly system dzialan mozna w koncu rozgryzc , a zmieniajacy sie i rozwijajacy trudniej rozwalic ;) ( o ile sie preznie i sprawnie rozwija ;) ). Poprostu ciekawi mnie uniwersalnosc  AI w RTS bez ograniczania sie do wariantow ktore sie wymyslilo i zaimplemetowalo. Wkoncu pojawi sie sytuacja w ktorej ktos czegos nie przewidzial (choc czesto ogranicza sie gre by nie dalo sie zrobic czegos czego nie mozna bylo przewidziec lub zaimplemetowac)

Swoja droga z tego co pamietam jakas rajdowka wykozystala sieci neuronowe do nauczenia komputera perfekcyjnego przejezdzania okreslonych torow wyscigowych, Ale to wciaz jest uczenie przed puszczeniem tego do rywalizacji z graczem , i specjalizacja do okreslonych warunkow.
Niepamietam czy ktores boty Quaka nie uczyly sie sposobu gry gracza , jednak to byly pojedyncze boty a nie RTSowe hordy majace oprocz wlasnej inteligecji jeszcze strategie dzialania. ;)

Czy ktos z was probowal robic np szukanie drogi dla obiektu opartego calkowicie o logike rozmyta?

pozdrawiam:-)

Offline Goliatus

  • Użytkownik
    • Warsztat - tworzenie gier

# Lipiec 18, 2007, 13:40:38
W rajdówce wystarczy zrobić ghost car i to nie na całą trasę, ale na poszczególne odcinki. Komputer zapamiętuje najlepsze czasy na tych odcinkach i już masz efekt uczenia się bez żadnych wymyślnych technik.

Nad czymś podobnym możnaby pomyśleć w przypadku RTSów. Np. budowanie bazy jest takim miejscem, gdzie można to zastosować. Komputer zapamiętuje kolejność budowy, układ i wynik tzn. wydajność produkcji.

Offline sobol

  • Użytkownik

# Lipiec 29, 2007, 01:45:53
Hmm ciekawy temat ;)
@goliatus: załóżmy, że komputer nauczy się rozbudowywać bazę (choć i tak nie wiem jak to do końca rozwiązać - co, samą kolejność rozbudowy ma zapamiętać? No bo przecież często rozstawienie jest kluczowe, a w 2 różnych miejscach to rozstawienie musi być inne - to zresztą chyba jeden z największych problemów jeśli chodzi o AI rozbudowywujące), ale co dalej ? Dalej będzie heurystyka znowu? Jak to widzicie, jak można by coś takiego zrobić?

tak czytając ten topic naszło mnie rozmyślanie o zastosowaniu algorytmów genetycznych w grach RTS. Czy mają one w ogóle jakieś zastosowania? Dajmy taką grę w deseń AoE, AI tworzy randomowo część populacji, potem "powiela" najliczniejsze osobniki (oczywiście z pewnymi zasadami, żeby nie mieć samych wieśniaków ;P), czyli jak na pole bitwy wyślemy 20 łuczników i 20 zbrojnych z czego zginie 15 zbrojnych i 10 łuczników to AI uzna, że łucznicy są silniejsi i będzie ich tworzyć więcej (to oczywiście tylko przykład, dla zobrazowania o co mi chodzi) - co o czymś takim myślicie? Widzicie zastosowania jakiekolwiek ?

A w urpl'u zaimplementowałem proste drzewo decyzyjne, BARDZO prymitywne :) Dosłownie jeśli nic innego nie potrzeba i masz za co to zbuduj wojownika... etc ;)

Offline Goliatus

  • Użytkownik
    • Warsztat - tworzenie gier

# Lipiec 29, 2007, 02:20:39
Skoro jest baza to jest konkretna produkcja, wiadomo co taka baza produkuje, znamy ilość i proporcje. Znamy skład wojska i od tego trzeba uzależnić plan ataku. Tutaj też można zastosować ghost car.

Nagrywasz rozgrywkę i jedna strona przeprowadza atak na bazę drugiej strony. Jeśli jest on skuteczny to zapamiętujesz plan działania i początkowy skład armii(proporcje poszczególnych rodzajów jednostek).

Następnie dobierasz plan ataku do tego co opisałem na początku. Więcej ciężko cokolwiek napisać, bo by trzeba było jasno określić o jakiej grze mówimy.

Offline k_b

  • Użytkownik
    • Blog

# Lipiec 29, 2007, 10:36:36
Skoro jest baza to jest konkretna produkcja, wiadomo co taka baza produkuje, znamy ilość i proporcje. Znamy skład wojska i od tego trzeba uzależnić plan ataku. Tutaj też można zastosować ghost car.

Nagrywasz rozgrywkę i jedna strona przeprowadza atak na bazę drugiej strony. Jeśli jest on skuteczny to zapamiętujesz plan działania i początkowy skład armii(proporcje poszczególnych rodzajów jednostek).

Następnie dobierasz plan ataku do tego co opisałem na początku. Więcej ciężko cokolwiek napisać, bo by trzeba było jasno określić o jakiej grze mówimy.

Perełki, tom 3, str. 283 - 291 - Game Observation Capture (GoCap). Thor Alexander świetnie tam ukazał jak można niewielkim wysiłkiem zrobić 'fajny' system uczenia komputera - akurat w tym przykładzie nauka komputerowego gracza jazdy samochodem-zabawką. Polecam przeczytać. (Co prawda mi nie odpowiada samo ukazanie tego systemu w klasach [tzn. nie tego, że wszystko jest w obiektach - bo oczywiście sam bym tak zrobił - ale tego co klasy 'ze sobą' robią i co konkretnie zawierają], ale dokładna teoria całego współdziałania, itd. jest naprawdę godna polecenia - aż mnie skręca, żeby napisać coś takiego ;). )
« Ostatnia zmiana: Lipiec 29, 2007, 10:38:50 wysłana przez k_b »