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 01:33] msl |
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 48: | Linia 48: | ||
| ===== Patrz o krok w przód ===== | ===== Patrz o krok w przód ===== | ||
| - | Bardziej ambitne algorytmy zakładają przeszukiwanie drzewa w celu wybrania najlepszego ruchu. Przykładowa strategia patrząca dwa kroki w przód mogłaby wyglądać następująca: | + | Bardziej ambitne algorytmy zakładają przeszukiwanie drzewa w celu wybrania najlepszego ruchu. Przykładowa strategia patrząca dwa kroki w przód mogłaby wyglądać następująco: |
| * Wybierz ruch, jeśli: | * Wybierz ruch, jeśli: | ||
| 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 82: | Linia 82: | ||
| * algorytm przerywa pracę, gdy przekroczy timeout --- bot GGP musi spełnić twarde wymagania czasowe | * algorytm przerywa pracę, gdy przekroczy timeout --- bot GGP musi spełnić twarde wymagania czasowe | ||
| - | * kolejny stan gry można zasymulować korzystając z metody: <code java>getNextState</code>, która jako argumenty przyjmuje poprzedni stan gry, oraz ruchy wykonane przez wszystkich graczy w danej turze. Dzięki temu, że w grach turowych, przeciwnik może wykonać tylko jeden ruch (''noop''), ruch wszystkich graczy można wygenerować używając metody <code java>getRandomJointMove</code> | + | * kolejny stan gry można zasymulować korzystając z metody: ''getNextState'' która jako argumenty przyjmuje poprzedni stan gry, oraz ruchy wykonane przez wszystkich graczy w danej turze. Dzięki temu, że w grach turowych, przeciwnik może wykonać tylko jeden ruch (''noop''), ruch wszystkich graczy można wygenerować używając metody ''getRandomJointMove''. |
| * <code java>isTerminal(stan);</code> sprawdza, czy dany stan kończy grę | * <code java>isTerminal(stan);</code> sprawdza, czy dany stan kończy grę | ||
| * <code java>getGoal(stan, rola);</code> zwraca wynik dla danego gracza w danym stanie. W przypadku stanów końcowych 100 oznacza, że gracz wygrał; 0, że zremisował. Wartości pośrednie (najczęściej 50) oznaczają, że gracz zremisował. W przypadku stanów niekońcowych wartość ta mówi, który gracz ma w danym stanie przewagę. | * <code java>getGoal(stan, rola);</code> zwraca wynik dla danego gracza w danym stanie. W przypadku stanów końcowych 100 oznacza, że gracz wygrał; 0, że zremisował. Wartości pośrednie (najczęściej 50) oznaczają, że gracz zremisował. W przypadku stanów niekońcowych wartość ta mówi, który gracz ma w danym stanie przewagę. | ||
| + | ==== Ćwiczenia ==== | ||
| - | ===== Min-Max ===== | + | * Przeprowadź pojedynek ''SampleSearchLightGamer.java'' vs ''SampleRandomGamer.java'' w kółko i krzyżyk |
| + | ===== MiniMax ===== | ||
| + | |||
| + | 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 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: | ||
| + | |||
| + | * [[http://www.flyingmachinestudios.com/programming/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. | ||
| + | |||
| + | ==== Ćwiczenia ==== | ||
| + | |||
| + | - Proszę na podstawie poniższego kodu, stworzyć bota, który gra stosując algorytm MinMax: <code java> | ||
| + | public class SampleMiniMaxGamer extends SampleGamer { | ||
| + | |||
| + | // indeks roli, używany, żeby z joint move wybrać ruch naszego gracza | ||
| + | Integer roleIndex = 0; | ||
| + | |||
| + | @Override | ||
| + | public Move stateMachineSelectMove(long timeout) | ||
| + | throws TransitionDefinitionException, MoveDefinitionException, | ||
| + | GoalDefinitionException { | ||
| + | long start = System.currentTimeMillis(); | ||
| + | |||
| + | // znajdź indeks naszego gracza | ||
| + | roleIndex = getStateMachine().getRoleIndices().get(getRole()); | ||
| + | // znajdź najlepszy ruch dla nas | ||
| + | Move selection = getBestMove(getCurrentState()); | ||
| + | |||
| + | |||
| + | // na potrzeby środowiska ggp-base | ||
| + | long stop = System.currentTimeMillis(); | ||
| + | List<Move> moves = getStateMachine().getLegalMoves(getCurrentState(), getRole()); | ||
| + | notifyObservers(new GamerSelectedMoveEvent(moves, selection, stop - start)); | ||
| + | return selection; | ||
| + | } | ||
| + | |||
| + | // znajduje najlepszy ruch, zakładając, ze przeciwnik gra najlepiej jak się da | ||
| + | private Move getBestMove(MachineState state) throws MoveDefinitionException, TransitionDefinitionException, GoalDefinitionException{ | ||
| + | List<List<Move>> moves = getStateMachine().getLegalJointMoves(state); | ||
| + | Integer score = 0; | ||
| + | Move bestMove = moves.get(0).get(roleIndex); | ||
| + | |||
| + | for(List<Move> move : moves){ | ||
| + | Integer result = getMinScore(move, getCurrentState()); | ||
| + | |||
| + | if (result > score){ | ||
| + | score = result; | ||
| + | bestMove = move.get(roleIndex); | ||
| + | } | ||
| + | } | ||
| + | return bestMove; | ||
| + | } | ||
| + | |||
| + | |||
| + | private Integer getMinScore(List<Move> jointMove, MachineState state) throws MoveDefinitionException, TransitionDefinitionException, GoalDefinitionException { | ||
| + | // TODO: | ||
| + | // 1) oblicz stan po ruchu | ||
| + | // 2) jeżeli stan jest końcowy, to zwróć jego wynik | ||
| + | // 3) przejrzyj dostępne ruchy | ||
| + | // 4) załóż, że wykonany zostanie taki ruch, który dla kolejnych ruchów da nam najmniej punktów | ||
| + | // 5) zwróć liczbę punktów uzyskaną przez nas w najlepszym wypadku po wykonaniu tego ruchu | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | private Integer getMaxScore(List<Move> jointMove, MachineState state) throws MoveDefinitionException, TransitionDefinitionException, GoalDefinitionException { | ||
| + | // TODO: | ||
| + | // 1) oblicz stan po ruchu | ||
| + | // 2) jeżeli stan jest końcowy, to zwróć jego wynik | ||
| + | // 3) przejrzyj dostępne ruchy | ||
| + | // 4) załóż, że wykonany zostanie taki ruch, który dla kolejnych ruchów da nam najwięcej punktów | ||
| + | // 5) zwróć liczbę punktów uzyskaną przez nas w najlepszym wypadku po wykonaniu tego ruchu | ||
| + | return 100; | ||
| + | } | ||
| + | }</code> | ||
| + | - przetestować, czy bot wygrywa z poprzednimi botami w grę kółko i krzyżyk | ||
| + | - przetestować, czy bot wygrywa z poprzednimi botami w warcaby ("Checkers") | ||
| + | - zaimplementować wsparcie dla przerywania algorytmu przed timeoutem | ||
| + | - 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 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 ==== | ||
| - | ===== Alpha-Beta Prunning ===== | + | - 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? | ||
