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 08:31] msl [Ćwiczenia] |
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 102: | Linia 102: | ||
| <WRAP center round tip 60%> | <WRAP center round tip 60%> | ||
| - | Interaktywna wizualizacja algorytmu jest [[http://sandbox.thimbleby.net/algorithms/doku.php?id=minimax_search|dostępna tutaj]]. | + | Interaktywna wizualizacja algorytmu jest [[https://thimbleby.gitlab.io/algorithm-wiki-site/wiki/minimax_search/|dostępna tutaj]]. |
| </WRAP> | </WRAP> | ||
| Linia 183: | Linia 183: | ||
| ===== Alpha-Beta Pruning ===== | ===== Alpha-Beta Pruning ===== | ||
| - | {{ :pl:dydaktyka:ggp:tree_pruning.jpg?300|}}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. | + | {{ :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. | 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%> | ||
| - | Interaktywna wizualizacja algorytmu jest [[http://will.thimbleby.net/algorithms/doku.php?id=minimax_search_with_alpha-beta_pruning|dostępna tutaj]]. | + | 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. Prunning drzew jest bardzo popularną metodą ograniczania przestrzeni przeszukiwania w problemach optymalizacyjnych. | + | 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 ==== | ||
