Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:ggp:game_tree [2016/05/11 02:40] msl |
pl:dydaktyka:ggp:game_tree [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| 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? | ||
