Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:dydaktyka:ggp:game_tree [2016/05/11 03:05] msl [Ćwiczenia] |
pl:dydaktyka:ggp:game_tree [2019/06/27 15:50] (aktualna) |
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 |
| |
* [[http://wazniak.mimuw.edu.pl/index.php?title=Sztuczna_inteligencja/SI_Modu%C5%82_8_-_Gry_dwuosobowe]] | * [[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]] | * [[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. |
- 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. | 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. | 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%> | <WRAP center round tip 60%> |
BONUS! [[http://will.thimbleby.net/algorithms/doku.php?id=minimax_search_with_alpha-beta_pruning|Tutaj]] można na żywo podziwiać wykonujący się algorytm Alpha-Beta :) | Interaktywna wizualizacja algorytmu jest [[https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/minimax_search_with_alpha-beta_pruning/|dostępna tutaj]]. |
</WRAP> | </WRAP> |
| |
Proszę się upewnić, że rozumieją Państwo działanie cięć Alpha-Beta. | 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 ==== | ==== Ćwiczenia ==== |
| |
- Proszę zaimplementować gracza ''SampleAlphaBetaGamer.java'' bazującego na graczu MiniMax z ograniczeniem czasowym. | - Proszę zaimplementować gracza ''SampleAlphaBetaGamer.java'' bazującego na graczu MiniMax z ograniczeniem czasowym. |
- Proszę zrobić pojedynek ''SampleAlphaBetaGamer.java'' vs ''SampleMiniMaxGamer.java'' w warcaby. Czy po kilku rozgrywkach widać jakąś różnicę? | - Proszę przeprowadzić serię pojedynków ''SampleAlphaBetaGamer.java'' vs ''SampleMiniMaxGamer.java'' w warcaby lub podobną grę. Czy po kilku rozgrywkach widać jakąś przewagę nowego bota? |