Autor Wątek: MiniMax - Drzewo ruchów (Piłkarzyki)  (Przeczytany 5995 razy)

Offline norbipal

  • Użytkownik

# Czerwiec 03, 2007, 12:59:05
Witam.

Mam pewien problem i nie wiem jak go rozwiązać. Pisze grę w której gra sie w Piłkarzyki (Takie co sie gra na kartce papieru w kratkę). W internecie szukałem podpowiedz jak napisać AI i znalazłem dwie strony gdzie autorzy stosowali właśnie algorytm MiniMax... Pomysł wydaje sie nawet dobry. Tym bliżej bramki tym większa ocena ruchu do tego dochodzą inne czynniki ale to na razie nie ważne. Problem mam ponieważ nie wiem jak przedstawić drzewo ruchów. Nie jest to takie proste jak np. w warcabach gdzie ma sie jeden ruch i potem ruch przeciwnika. W piłkarzykach często ruch sie wykonuje tak aby się odbić i wykonywać go dalej. Człowiek często wykonuje wiele ruchów blokujących drogę i dopiero potem wychodzi do przodu tracąc swoją kolej. Nie wiem w jaki sposób przedstawić to drzewo... czasem może być nawet kilkadziesiąt ruchów. Każdy ruch może mieć kilka odnóg itd.
Druga sprawa to jak zrobić aby algorytm działał dość szybko...

Nie proszę o cały algorytm lecz tylko o obraz jak to ma działać. Ja już mam mętlik w głowie...

Offline Mr. Spam

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

Offline mINA87

  • Użytkownik

# Czerwiec 03, 2007, 13:29:15
Co do samego zbudowania drzewa gry to ja nie widzę problemu. Musisz wiedzieć że przede wszystkim drzewo gry może mieć różną ilość dzieci na każdym poziomie i teraz tak - jesteś w danym punkcie i analizujesz wszystkie możliwe ruchy rekurencyjnie odbijając się jesli się da, robiąc nawroty jeśli z jednego odbicia można kilka ruchów nowych wykonać i zapisujesz ostatecznie tylko pozycje końcowe, które nie mogą już produkować nowych ruchów. Przypuścmy że możesz się ruszyć w lewo i nie odbić, to zapisujesz to, ponadto możesz się ruszyć w prawo, to jedziesz i teraz z tej pozycji możesz pójść w górę lub w lewo, to idziesz w lewo, okazuje się, że kończymy imprezkę, to zapisujesz pozycję końcową, wracasz jeden ruch do tyłu (zwijasz rekurencję) i wykonujesz ruch do góry, tam znowu zapisujesz pozycję i tyle. W ten sposób zbudujesz sobie drzewko gry.
Żeby działało to szybko musisz po prostu budować drzewo tylko do odpowiedniej głębokości. Z tą głębokością warto rozważyć nawet kompletne przerwanie dalszej rekurencji mimo że możemy się dalej ruszać - spowodować to może pewne błędy, jednak dzięki temu będzie to miało szansę w ogóle działać :P

Offline Złośliwiec

  • Użytkownik
    • Dark Cult

# Czerwiec 03, 2007, 13:32:20
Jeśli dobrze zrozumiałem, to chodzi ci o samą strukturę zwaną drzewem. Najprościej zrobić to w ten sposób, że do struktury z informacją o ruchu dorzucasz wektor dzieci oraz - dla wygody - jakąś metodę do "doczepiania" dzieci do danego elementu, np:

class CTreeNode
{
 protected:
  CPoint m_Coords;
  vector<CTreeNode> m_Children;
 public:
  void AddChild (const CTreeNode& child)
  {
   m_Children.push_back (child);
  }
}

Offline MoN

  • Użytkownik

# Czerwiec 03, 2007, 14:14:57
Dzieci mozna zreszta trzymac jako lista cykliczna doczepiona do parenta ;) kazdy node trzyma wtedy wskaznik do parenta, swojego dziecka (jeden wystarczy) i do prawego/lewego sasiada, czyli brata/siostry ;)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 03, 2007, 15:33:02
Złośliwiec, MoN: Pierwszy raz widzę, żeby ktoś rzeczywiście budował drzewo w MiniMax'ie. W praktyce drzewa się nie trzyma, bo jest duże i nikomu niepotrzebne. Potrzebne są jedynie pewne informacje, które można zebrać podczas przechodzenia tego drzewa. Samą strukturę drzewa mamy zadaną pośrednio, na podstawie reguł gry. :)

Co do pytania o piłkarzyki: Po prostu jeżeli gracz ma się odbić, to dostaje następny ruch (czyli jeżeli byłeś w węźle Min, to dalej jesteś w węźle typu Min). Nalezy tylko uważać, aby nie przerwać poszukiwania w momencie gdy gracz ma do wykonania odbicie. :)

Offline Liosan

  • Moderator

# Czerwiec 03, 2007, 16:21:01
Zamiast list proponuje używać tablic - są szybsze.

Krzysiek K. ma rację - nie ma potrzeby pamiętać całego drzewa. Wystarczy pamiętać pojedyńczą ścieżkę oraz najlepszy do tej pory znaleziony ruch razem z wagą na każdym poziomie.

Proponuję jeszcze poczytać o alfa-beta obcięciu (powinno przyspieszyć działanie programu o jakieś 30%, i gwarantuje optymalność znalezionych ruchów) i różnych heurystyka przyspieszających. Najprostsze heurezy do zaimplementowania to killer-heuristic (pamiętanie ruchów, które w sąsiednich ścieżkach na danym poziomie okazały się optymalne, i wykonywanie ich najpierw) i sortowanie ruchów przed przeszukiwaniem na każdym poziomie wg funkcji oceniającej.

Liosan

EDIT: tak sobie mysle, ze ciag ruchow jednego gracza moze byc cholernie dlugi i miec cholernie duzo potencjalnych rozgalezien (tak bylo jak gralem na kartce :P). To moze byc glowny czynnik majacy wplyw na czas dzialania programu. Z jednej strony, nie mozna uciac ruchu zanim nie dojdzie do konca, z drugiej duzo wazniejsze jest zwiedzanie rozgalezien niz drazenie drzewa wglab. Zaintrygowales mnie... spytam sie jutro na uczelni :)
« Ostatnia zmiana: Czerwiec 03, 2007, 23:24:02 wysłana przez Liosan »

Offline M-Art

  • Użytkownik

# Czerwiec 10, 2007, 22:51:07
jestem początkujący więc nie wiem jak możnaby to było rozwiązac programistycznie, ale wiem (z własnego doświadczenia), że w tej grze lepiej nie komplikowac sobie ruchów. Zawsze idę prosto do bramki, bez żadnych "siateczek" po drodze. Wcześniej zdążę wbic gola niż dojdzie do jakiejś skomplikowanej sytuacji. Tak że sam algorytm nie musi byc skomplikowany i nie musi szukac jakichś "cudownych ruchów". Pamiętajmy również że gra ma byc przyjemna, a nie powodowac ból głowy (chociaż zapewne nie wszyscy się ze mną zgodzą)...

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Czerwiec 11, 2007, 15:54:59
Te zapamiętywane dane bez budowania prawdziwego drzewa można przekazywać jako parametry do funkcji, która wywołuje rekurencyjnie samą siebie analizując każdy ruch, ruchy następne z niego itd.

To że pojedyncze ruchy dwóch graczy nie następują naprzemian po sobie to przecież nie jest większy problem. Kto powiedział, że w tym (nieistniejącym) drzewie wszystkie węzły na poziomie 1 muszą być ruchami gracza pierwszego, wszystkie wychodzące z nich gracza drugiego, wszystkie poniżej znów gracza pierwszego itd.

To czy najlepsza strategia to iść prosto do bramki czy coś innego to jest kwestia napisania tzw. funkcji heurystycznej oceniającej liczbowo jakość danego ruchu czy raczej danej sytuacji na planszy i możesz to rozpatrywać oddzielnie od całej reszty algorytmu, czyli od tego o co pytasz - jak zorganizować implementację całości.

Jeszcze jedno - powodzenia w tym projekcie! Nie wiem czy ktoś zrobił to przed Tobą. Xion napisał na komputer tą grę w piłkarzyki - Pen Soccer - ale tam zdaje się była tylko gra na dwóch graczy, bez AI. Poza tym jego strona już od dawna nie działa :)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Czerwiec 11, 2007, 19:40:55
Cytuj
EDIT: tak sobie mysle, ze ciag ruchow jednego gracza moze byc cholernie dlugi i miec cholernie duzo potencjalnych rozgalezien (tak bylo jak gralem na kartce :P). To moze byc glowny czynnik majacy wplyw na czas dzialania programu. Z jednej strony, nie mozna uciac ruchu zanim nie dojdzie do konca, z drugiej duzo wazniejsze jest zwiedzanie rozgalezien niz drazenie drzewa wglab. Zaintrygowales mnie... spytam sie jutro na uczelni :)
Tego nie przeskoczysz. :)

Cytuj
jestem początkujący więc nie wiem jak możnaby to było rozwiązac programistycznie, ale wiem (z własnego doświadczenia), że w tej grze lepiej nie komplikowac sobie ruchów. Zawsze idę prosto do bramki, bez żadnych "siateczek" po drodze.
Nie zawsze. Czasem warto trochę pokręcić, żeby zablokować przeciwnikowi mozliwośc powrotu na swoją połowę. :)

Cytuj
Te zapamiętywane dane bez budowania prawdziwego drzewa można przekazywać jako parametry do funkcji, która wywołuje rekurencyjnie samą siebie analizując każdy ruch, ruchy następne z niego itd.
W ten sposób zapewnisz sobie sporo kopiowania w każdym kroku (chyba że przekażesz referencję) i w efekcie wolniejsze przeglądanie drzewa. Najlepiej jest tutaj skorzystać z globalnej tablicy, wskaźników (ewentualnie vectora i iteratorów) i budować stos ruchów samemu. :)

Cytuj
Jeszcze jedno - powodzenia w tym projekcie! Nie wiem czy ktoś zrobił to przed Tobą.
Zrobił, zrobił i własnie Ci odpisuje. Poza tym gdzieś w sieci tez już coś takiego widziałem. :)