Autor Wątek: Jak stworzyć prostą grę z SI.  (Przeczytany 4179 razy)

Offline Shusty

  • Użytkownik

# Grudzień 20, 2013, 15:15:01
Gra powinna być z wiedzą pełną. Czyli tak jak np. w warcabach.
Chciałbym to zrobić w oparciu o zadanie wyszukiwania strategii gry w jej drzewie stanów. Czyli ogólnie chodzi o algorytm min-max. Do optymalizacji dodałbym może później algorytm alfa-beta.

Po pierwsze nie wiem jaką prostą grą się zająć. Nie mogą to być na pewno warcaby, piłkarzyki, go, szachy, reversi, gomoku.

Nie wiem jednak jaką prostą w implementacji grę wykonać oraz jak się do tego tematu zabrać.

Offline Mr. Spam

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

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Grudzień 20, 2013, 15:45:25
Może Mankala? (albo jakiś wariant)

Cały gamestate to garstka liczb, zasady relatywnie proste, a funkcja oceny (przynajmniej taka na start) trywialna - różnica wyników. :)

No i niebagatelny jest fakt, że sama gra całkiem ciekawa. :)

Offline Xender

  • Użytkownik

# Grudzień 20, 2013, 16:31:47
Jakaś modyfikacja gry w kółko i krzyżyk z większą planszą?

Offline Shusty

  • Użytkownik

# Grudzień 20, 2013, 17:22:21
Mankala wydaje się ciekawą grą. Wielkie dzięki, nawet nie wiedziałem o jej istnieniu.

Pewnie będę miał jeszcze trochę pytań odnośnie tego, a na razie moje wnioski. Powiedzcie czy słuszne.

Przechodząc drzewo min-max ocena to zawsze ilość punktów. Zawsze mamy do wyboru 6 ruchów (albo mniej jeśli mamy puste pola po swojej stronie).

Offline Xender

  • Użytkownik

# Grudzień 20, 2013, 17:32:10
Przechodząc drzewo min-max ocena to zawsze ilość punktów.
To byłby algorytm zachłanny, a nie min-max. Drzewo przechodzi się rekurencyjnie, a ocena to:
- Dla liścia - liczba punktów.
- Dla nie-liścia - "przekopiowana" ocena potomka, który ma najlepszą ocenę.

Oczywiście całe drzewo da się przejść tylko dla najprostszych gier, jak np. klasyczne kółko i krzyżyk na planszy 3x3. W bardziej skomplikowanych należy znaleźć jakąś heurystykę dla oceny, która pozwali zatrzymać przeszukiwanie na niepełnej głębokości. Liczba punktów będzie tu najprostsza, ale niekoniecznie najlepsza.

Offline Shusty

  • Użytkownik

# Grudzień 20, 2013, 17:43:29
Oczywiście szkoda czasu obliczania dla pełnego rozwiązania. Głębokość drzewa może być np. tutaj stopniem trudności komputerowego gracza.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Grudzień 20, 2013, 18:01:00
Cytuj
Przechodząc drzewo min-max ocena to zawsze ilość punktów.
Dokładniej to różnica punktów graczy. Na początek taka ocena powinna być jak najbardziej w porządku, ale nie jest to jedyna możliwa funkcja oceniająca. Później można się pokusić o bardziej wymyślne techniki, oczywiście sprawdzając czy to pomaga czy przeszkadza.

Warto myślę do oceny, przynajmniej w początkowym stadium, dodawać jakiegoś niewielkiego randoma, żeby początek gry SI nie był w 100% przewidywalny.

Cytuj
Zawsze mamy do wyboru 6 ruchów (albo mniej jeśli mamy puste pola po swojej stronie).
Tak mi też to wygląda.

Offline Shusty

  • Użytkownik

# Grudzień 20, 2013, 18:52:31
http://wolfey.110mb.com/GameVisual/launch.php

Znalazłem fajną stronę pokazującą ideę minmaxa i kiedy jaką wartość kopiujemy wyżej. W minmaxie idziemy od dołu znając wartości oceny. Co jednak zrobić, żeby osiągnąć ten punkt wyjścia, gdzie mamy te wartości w liściach?

Czy najpierw powinienem zbudować drzewo od góry wszystkich możliwych kombinacji, gdzie w węzłach będzie ocena po danym ruchu i gdy dojdziemy do ustalonej głębokości wszystkie wartości z liści  zaczytujemy.

Później robimy puste drzewo o danej głębokości i do liści przypisujemy dane wartości i już minmaxem od dołu idziemy i kopiujemy wartość min/max wyżej.

Dobrze myślę?

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Grudzień 20, 2013, 19:10:59
Cytuj
Dobrze myślę?
Niedobrze. Nigdzie tutaj nie tworzysz fizycznie drzewa, tylko po nim przechodzisz.

Offline Shusty

  • Użytkownik

# Grudzień 20, 2013, 19:24:12
To ja już nie rozumiem chyba tego do końca.

Edit: Pewnie miałeś na myśli, że rekurencyjnie idąc przechodzimy po drzewie, ale struktura tworzy się jakby sama z siebie.

« Ostatnia zmiana: Grudzień 20, 2013, 20:33:52 wysłana przez Shusty »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Grudzień 20, 2013, 23:14:50
Edit: Pewnie miałeś na myśli, że rekurencyjnie idąc przechodzimy po drzewie, ale struktura tworzy się jakby sama z siebie.
Mniej więcej. Struktura się nigdzie nie tworzy.

Algorytm operuje na drzewie, ale to drzewo jest tylko "logicznie". Wystarczy że potrafisz po nim przechodzić, oraz że trzymasz dane o tych paru węzłach, które jeszcze Ci są potrzebne (np. w zmiennych lokalnych po jednym zestawie dla każdego rekurencyjnego wywołania funkcji).

Offline koirat

  • Użytkownik

# Grudzień 20, 2013, 23:33:47
@Shusty
A na wiki już byłeś ?
http://en.wikipedia.org/wiki/Minimax
W szczególności mowa o tym gif-ie:
http://en.wikipedia.org/wiki/File:Plminmax.gif

Offline Xender

  • Użytkownik

# Grudzień 21, 2013, 00:23:28
A tak przy okazji optymalizacji (samego algorytmu, na poziomie konceptualnym, nie implementacji) - z tego co pamiętam, najwydajniejszą (i dla mnie najbardziej zrozumiałą, choć miałem problem z implementacją) odmianą jest Negascout, polecam się zapoznać.

Offline Shusty

  • Użytkownik

# Grudzień 21, 2013, 01:04:21
Koncepcję min-maxa rozumiem, ale żeby iść od dołu coś w liściach już musimy mieć na starcie, jakąś ocenę.

Offline koirat

  • Użytkownik

# Grudzień 21, 2013, 01:19:17
Swoją drogą mogą cię zainteresować mniej deterministyczne metody.
Na myśli mam dokładniej metodę "Upper Confidence bounds in Monte Carlo Tree search" ktoś już kiedyś nawet na tym forum o tym wspominał.