Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:ggp:game_tree [2016/05/11 02:40] msl |
pl:dydaktyka:ggp:game_tree [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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|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. | ||
| - | |||
| - | W przypadku turowych gier dla dwóch graczy, każda gałąź drzewa składa się z krawędzi naprzemiennie reprezentujące ruchy graczy. Poniżej widoczne jest przykładowe drzewo gry dla gry kółko i krzyżyk, rozpoczynającej się w stanie na trzy ruchy przed zapełnieniem planszy. | ||
| - | |||
| - | {{ :pl:dydaktyka:ggp:tic-tac-toe-tree.png?500 | }} | ||
| - | |||
| - | Podczas laboratorium zadaniem będzie zaimplementowanie botów korzystających z framework'a ggp-base poznanego na poprzednich zajęciach. Boty będą używały standardowych strategii przeszukiwania drzewa gry. | ||
| - | |||
| - | ===== Ruch pierwszy z brzegu ===== | ||
| - | |||
| - | Najprostszą strategią, jaką można zaimplementować, jest wybranie pierwszego ruchu z brzegu. Obrazuje ją poniższy pseudokod: | ||
| - | |||
| - | <code python> | ||
| - | ruch = pierwszy_ruch_z_brzegu() | ||
| - | wykonaj(ruch) | ||
| - | </code> | ||
| - | |||
| - | Implementację tego skomplikowanego kawałka kodu można znaleźć w projekcie ''ggp-base'' w paczce ''org.ggp.base.player.gamer.statemachine.sample'' w klasie ''SampleAlphabetGamer.java''. Bot ten sortuje ruchy alfabetycznie i wybiera pierwszy z brzegu. | ||
| - | |||
| - | Warto zauważyć kilka rzeczy: | ||
| - | |||
| - | * klasa ta dziedziczy po klasie ''SampleGamer.java'', która implementuje całą nudną komunikację | ||
| - | * żeby bot działał, wystarczy zaimplementować metodę: <code java>public Move stateMachineSelectMove(long timeout) throws Something</code> Zwraca ruch podejmowany przez bota w danej turze | ||
| - | * <code java>getStateMachine();</code> zwraca maszynę stanową, która potrafi symulować grę | ||
| - | * <code java>getCurrentState();</code> zwraca aktualny stan gry | ||
| - | * <code java>getRole();</code> zwraca rolę gracza (proszę przypomnieć sobie predykat role w gdl) | ||
| - | * metoda maszyny stanowej <code java>getLegalMoves(<stan>,<rola>)</code> zwraca listę dostępnych ruchów dla danego stanu i danego gracza | ||
| - | |||
| - | ==== Testowanie gracza ==== | ||
| - | |||
| - | Testowania bota może być wykonane na dwa sposoby: | ||
| - | |||
| - | - poprzez aplikację Kiosk (paczka: ''org.ggp.base.apps.kiosk''), która została wprowadzona na poprzednich zajęciach. Z jej poziomu można wybrać grę oraz bota z listy, następnie zagrać z nim sparing. | ||
| - | - poprzez aplikacje GameServer (''org.ggp.base.app.server'') oraz Player (''org.ggp.base.app.player''). Należy przy tym: | ||
| - | - uruchomić GameServer i wybrać z listy grę, | ||
| - | - uruchomić aplikację Player i z jej poziomu stworzyć dwóch graczy określonego typu (przycisk ''Create'') | ||
| - | - w aplikacji GameServer rozpocząć rozgrywkę (przycisk ''Start new match!'') | ||
| - | |||
| - | ==== Ćwiczenia ==== | ||
| - | |||
| - | - bazując na kodzie ''SampleAlphabetGamer.java'' stwórz bota ''SampleRandomGamer.java'', który zawsze wykonuje losowy ruch. | ||
| - | - prześledź przebieg pojedynku ''SampleAlphabetGamer.java'' vs ''SampleRandomGamer.java'' w kółko i krzyżyk | ||
| - | |||
| - | ===== 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ąco: | ||
| - | |||
| - | * Wybierz ruch, jeśli: | ||
| - | * wygrywasz dzięki niemu grę, | ||
| - | * lub przynajmniej nie przegrywasz od razu gry, | ||
| - | * lub przynajmniej nie ma prowadzi do sytuacji, gdy kolejny ruch przeciwnika kończy grę jego zwycięstwem | ||
| - | |||
| - | W pseudokodzie: | ||
| - | |||
| - | <code python> | ||
| - | aktualny kandydat na ruch = null | ||
| - | |||
| - | dla każdego możliwego ruchu: | ||
| - | jeżeli ruch kończy grę zwycięstwem: | ||
| - | wybierz ten ruch | ||
| - | jeżeli ruch kończy grę porażką: | ||
| - | nie analizuj tego ruchu dalej | ||
| - | jeżeli ruch daje gorze wyniki niż aktualny kandydat: | ||
| - | nie analizuj tego ruchu dalej | ||
| - | | ||
| - | dla każdego ruchu przeciwnika: | ||
| - | jeżeli ruch przeciwnika kończy grę twoją porażką: | ||
| - | nie analizuj tego ruchu dalej | ||
| - | | ||
| - | aktualny kandydat na ruch = możliwy ruch | ||
| - | |||
| - | wykonaj(aktualny kandydat na ruch) | ||
| - | </code> | ||
| - | |||
| - | Implementację tej strategii można znaleźć w klasie ''SampleSearchLightGamer.java''. | ||
| - | |||
| - | Warto zauważyć kilka rzeczy: | ||
| - | |||
| - | * algorytm przerywa pracę, gdy przekroczy timeout --- bot GGP musi spełnić twarde wymagania czasowe | ||
| - | * 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>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 ==== | ||
| - | |||
| - | * Przeprowadź pojedynek ''SampleSearchLightGamer.java'' vs ''SampleRandomGamer.java'' w kółko i krzyżyk | ||
| - | ===== MinMax ===== | ||
| - | |||
| - | 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). | ||
| - | 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ć. | ||
| - | |||
| - | 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://neverstopbuilding.com/minimax]] | ||
| - | |||
| - | 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 SampleMinMaxGamer 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: | ||
| - | - 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 | ||
| - | |||
| - | |||
| - | ===== Alpha-Beta Prunning ===== | ||
