Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:dydaktyka:ggp:game_tree [2016/05/11 02:39]
msl [Min-Max]
pl:dydaktyka:ggp:game_tree [2019/06/27 15:50] (aktualna)
Linia 1: Linia 1:
 ====== Klasyczne algorytmy oparte o drzewo gry ====== ====== Klasyczne algorytmy oparte o drzewo gry ======
  
-Poniższe laboratorium na celu przedstawić podstawowe algorytmy grające dla gier przeznaczonych dla dwóch graczy, o sumie zerowej. Suma zerowa oznacza, że zwycięstwo jednego gracza jest równocześnie porażką drugiego (suma nagród i kar jest stała i symetryczna,​ równa zeru, jak sama nazwa wskazuje). Wszystkie opisane algorytmy będą bazować na jednej reprezentacji rozgrywki --- tzw. [[https://​en.wikipedia.org/​wiki/​Game_tree|drzewu ​gry (ang. game tree)]].+Poniższe laboratorium na celu przedstawić podstawowe algorytmy grające dla gier przeznaczonych dla dwóch graczy, o sumie zerowej. Suma zerowa oznacza, że zwycięstwo jednego gracza jest równocześnie porażką drugiego (suma nagród i kar jest stała i symetryczna,​ równa zeru, jak sama nazwa wskazuje). Wszystkie opisane algorytmy będą bazować na jednej reprezentacji rozgrywki --- tzw. [[https://​en.wikipedia.org/​wiki/​Game_tree|drzewie ​gry (ang. game tree)]].
  
 Drzewo gry, jak sama nazwa wskazuje, jest drzewem, czyli spójnym acyklicznym grafem. Wierzchołki drzewa reprezentują możliwe stany gry, gdzie korzeń drzewa jest początkowym stanem gry. Krawędzie natomiast reprezentują ruchy graczy, prowadzące z jednego stanu do drugiego. Drzewo gry, jak sama nazwa wskazuje, jest drzewem, czyli spójnym acyklicznym grafem. Wierzchołki drzewa reprezentują możliwe stany gry, gdzie korzeń drzewa jest początkowym stanem gry. Krawędzie natomiast reprezentują ruchy graczy, prowadzące z jednego stanu do drugiego.
Linia 65: Linia 65:
   jeżeli ruch kończy grę porażką:   jeżeli ruch kończy grę porażką:
     nie analizuj tego ruchu dalej     nie analizuj tego ruchu dalej
-  jeżeli ruch daje gorze wyniki niż aktualny kandydat:+  jeżeli ruch daje gorsze ​wyniki niż aktualny kandydat:
     nie analizuj tego ruchu dalej     nie analizuj tego ruchu dalej
   ​   ​
Linia 89: Linia 89:
  
   * Przeprowadź pojedynek ''​SampleSearchLightGamer.java''​ vs ''​SampleRandomGamer.java''​ w kółko i krzyżyk   * Przeprowadź pojedynek ''​SampleSearchLightGamer.java''​ vs ''​SampleRandomGamer.java''​ w kółko i krzyżyk
-===== MinMax ​=====+===== MiniMax ​=====
  
-Algorytm [[https://​en.wikipedia.org/​wiki/​Minimax|Min-Max]] jest klasycznym algorytmem przeszukiwania drzew gier, gwarantującym wykonanie optymalnego ruchu (o ile uda nam się doprowadzić algorytm do końca). +Algorytm [[https://​en.wikipedia.org/​wiki/​Minimax|MiniMax]] jest klasycznym algorytmem przeszukiwania drzew gier, gwarantującym wykonanie optymalnego ruchu (o ile uda nam się doprowadzić algorytm do końca). 
-Zakłada on, że przeciwnik zawsze będzie ruszał się w sposób dla niego najlepszy (dla nas najgorszy). Gracz MinMax ​wybiera taki ruch, żeby przeciwnik mógł mu jak najmniej zaszkodzić. ​+Zakłada on, że przeciwnik zawsze będzie ruszał się w sposób dla niego najlepszy (dla nas najgorszy). Gracz MiniMax ​wybiera taki ruch, żeby przeciwnik mógł mu jak najmniej zaszkodzić. ​
  
 Szczegółowe prezentacje tego algorytmu wraz z pseudokodem można znaleźć na poniższych stronach: Szczegółowe prezentacje tego algorytmu wraz z pseudokodem można znaleźć na poniższych stronach:
  
-  * [[https://​www.ocf.berkeley.edu/​~yosenl/​extras/​alphabeta/​alphabeta.html]] 
   * [[http://​www.flyingmachinestudios.com/​programming/​minimax/​]]   * [[http://​www.flyingmachinestudios.com/​programming/​minimax/​]]
   * [[http://​neverstopbuilding.com/​minimax]]   * [[http://​neverstopbuilding.com/​minimax]]
 +  * [[http://​wazniak.mimuw.edu.pl/​index.php?​title=Sztuczna_inteligencja/​SI_Modu%C5%82_8_-_Gry_dwuosobowe]]
 +  * [[https://​www.youtube.com/​watch?​v=OkP8BAwfO24|nagranie prezentujące algorytm]]
 +
 +<WRAP center round tip 60%>
 +Interaktywna wizualizacja algorytmu jest [[https://​thimbleby.gitlab.io/​algorithm-wiki-site/​wiki/​minimax_search/​|dostępna tutaj]].
 +</​WRAP>​
  
 Proszę upewnić się, że rozumieją Państwo działanie algorytmu. Proszę upewnić się, że rozumieją Państwo działanie algorytmu.
Linia 105: Linia 110:
  
   - Proszę na podstawie poniższego kodu, stworzyć bota, który gra stosując algorytm MinMax: <code java>   - Proszę na podstawie poniższego kodu, stworzyć bota, który gra stosując algorytm MinMax: <code java>
-public class SampleMinMaxGamer ​extends SampleGamer {+public class SampleMiniMaxGamer ​extends SampleGamer {
  
         // indeks roli, używany, żeby z joint move wybrać ruch naszego gracza         // indeks roli, używany, żeby z joint move wybrać ruch naszego gracza
Linia 169: Linia 174:
   - przetestować,​ czy bot wygrywa z poprzednimi botami w grę kółko i krzyżyk   - przetestować,​ czy bot wygrywa z poprzednimi botami w grę kółko i krzyżyk
   - przetestować,​ czy bot wygrywa z poprzednimi botami w warcaby ("​Checkers"​)   - przetestować,​ czy bot wygrywa z poprzednimi botami w warcaby ("​Checkers"​)
-  - zaimplementować wsparcie dla przerywania algorytmu przed timeoutem+  - zaimplementować wsparcie dla przerywania algorytmu przed timeoutem
-    - poprzez ograniczenie czasowe jak w poprzednim bocie +
-    - poprzez ograniczenie poziomu zagłębiania w drzewo (przeglądanie tylko kilka ruchów wprzód) ​+
   - przetestować poprawionego bota grając w warcaby   - przetestować poprawionego bota grając w warcaby
 +  - ZADANIA DODATKOWE:
 +    - proszę dać możliwość ograniczenia poziomu zagłębiania w drzewie (przeglądanie tylko kilku ruchów wprzód) --- jest to klasyczna metoda skalowania siły AI. Jest to jedna z klasycznych metod modyfikacji mocy AI w grach. Jaką przewagę ma to podejście nad zwykłym timeoutem?  ​
 +    - proszę zaimplementować wersję NegaMax pokazaną na [[http://​sandbox.thimbleby.net/​algorithms/​doku.php?​id=minimax_search|poniższej stronie]]
    
  
-===== Alpha-Beta ​Prunning ​=====+===== Alpha-Beta ​Pruning ​===== 
 + 
 +{{ :​pl:​dydaktyka:​ggp:​tree_pruning.jpg?​200|}} 
 +Algorytm MiniMax przeszukuje wszystkie węzły drzewa gry, to poważny błąd. W prawdziwych grach jest to najczęściej niemożliwe. Dużym usprawnieniem algorytmu są tak zwane cięcia [[https://​en.wikipedia.org/​wiki/​Alpha%E2%80%93beta_pruning|Alpha-Beta]]. Idea tego usprawnienia polega na tym, że MiniMax nie musi przeszukiwać węzłów, co do których jest pewien, że nie zawierają one rozwiązania lepszego od tego, który już posiada.  
 + 
 +Więcej szczegółów na końcówkach materiałów o MiniMax. [[https://​www.youtube.com/​watch?​v=Ewh-rF7KSEg|Ten filmik]] pokazuje przykład zastosowania algorytmu Alpha-Beta. 
 + 
 +<WRAP center round tip 60%> 
 +Interaktywna wizualizacja algorytmu jest [[https://​thimbleby.gitlab.io/​algorithm-wiki-site/​wiki/​minimax_search_with_alpha-beta_pruning/​|dostępna tutaj]]. 
 +</​WRAP>​ 
 +  
 +Proszę się upewnić, że rozumieją Państwo działanie cięć Alpha-Beta. Należą one do szerokiej rodziny algorytmów [[https://​en.wikipedia.org/​wiki/​Branch_and_bound|branch and bound]], używanych w szczególności w optymalizacji. 
 + 
 +==== Ćwiczenia ==== 
 + 
 +  - Proszę zaimplementować gracza ''​SampleAlphaBetaGamer.java''​ bazującego na graczu MiniMax z ograniczeniem czasowym. 
 +  - Proszę przeprowadzić serię pojedynków ''​SampleAlphaBetaGamer.java''​ vs ''​SampleMiniMaxGamer.java''​ w warcaby lub podobną grę. Czy po kilku rozgrywkach widać jakąś przewagę nowego bota?
pl/dydaktyka/ggp/game_tree.1462927179.txt.gz · ostatnio zmienione: 2019/06/27 15:52 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0