Jak wybrać najlepszy algorytm dla gry planszowej, takiej jak warcaby?
Do tej pory rozważałem tylko trzy algorytmy, a mianowicie minimax, przycinanie alfa-beta i wyszukiwanie drzewa Monte Carlo (MCTS). Najwyraźniej zarówno przycinanie alfa-beta, jak i MCTS są rozszerzeniami podstawowego algorytmu minimax.
Odpowiedzi:
tl; dr:
Żaden z tych algorytmów nie jest praktyczny w nowoczesnej pracy, ale są dobrym miejscem do rozpoczęcia pracy pedagogicznej.
Zawsze powinieneś preferować przycinanie Alpha-Beta zamiast samego wyszukiwania minimax.
Powinieneś raczej użyć jakiejś formy heurystycznego wyszukiwania z przewodnikiem, jeśli możesz wymyślić przydatną heurystykę. Wymyślenie użytecznej heurystyki zwykle wymaga dużej wiedzy w dziedzinie.
Powinieneś raczej korzystać z wyszukiwania drzewa Monte Carlo, gdy brakuje ci dobrej heurystyki, gdy zasoby obliczeniowe są ograniczone i gdy błędy nie będą miały większych niż rzeczywiste konsekwencji.
Więcej szczegółów:
W wyszukiwaniu minimax nie staramy się być bardzo sprytni. Po prostu stosujemy standardowe podejście do programowania dynamicznego. Łatwo jest obliczyć wartość ruchów różnicowych, jeśli jesteśmy blisko końca gry (ponieważ gra zakończy się w następnym ruchu, nie musimy patrzeć daleko w przyszłość). Podobnie, jeśli wiemy, co zrobi nasz przeciwnik w ostatnim ruchu gry, łatwo jest ustalić, co powinniśmy zrobić w drugim ostatnim ruchu. Skutecznie możemy traktować drugi ostatni ruch jako ostatni ruch krótszej gry. Następnie możemy powtórzyć ten proces. Zastosowanie tego podejścia z pewnością odkryje najlepsze strategie w standardowej grze w rozbudowanej formie, ale będzie wymagało od nas rozważenia każdego możliwego ruchu, co jest niemożliwe do wykonania dla wszystkich gier oprócz najprostszych.
Przycinanie Alpha-Beta to ścisłe ulepszenie w wyszukiwaniu Minimax. Wykorzystuje fakt, że niektóre ruchy są oczywiście gorsze od innych. Na przykład w szachach nie muszę brać pod uwagę żadnego ruchu, który dałby ci szansę na umieszczenie mnie w szachach, nawet gdybyś mógł robić inne rzeczy z tej pozycji. Kiedy zobaczę, że ruch może doprowadzić do przegranej, nie będę się martwić myśleniem o tym, co jeszcze może się wydarzyć od tego momentu. Pójdę spojrzeć na inne rzeczy. Algorytm ten z pewnością da poprawny wynik i jest szybszy, ale nadal musi uwzględniać większość ruchów w praktyce.
Istnieją dwa typowe sposoby obejścia ekstremalnych obliczeniowych kosztów rozwiązania tego rodzaju gier:
Użyj heurystyki (wyszukiwanie A * jest zwykłym algorytmem do celów pedagogicznych, ale wyszukiwanie spoczynku jest podobnym pomysłem w grach dla dwóch graczy). To tylko funkcja, która pozwala oszacować wartość stanu gry. Zamiast brać pod uwagę wszystkie ruchy w grze, możesz po prostu rozważyć ruchy na pewną skończoną odległość, a następnie użyć wartości heurystyki, aby ocenić wartość osiągniętych stanów. Jeśli twoja heurystyka jest konsekwentna (w zasadzie: jeśli zawsze przecenia jakość stanów), to nadal da to prawidłową odpowiedź, ale w praktyce przyniesie ogromne przyspieszenie.
Używaj rolloutów (takich jak wyszukiwanie drzewa Monte Carlo). Zasadniczo zamiast rozważać każdy ruch, uruchom kilka tysięcy symulowanych gier między graczami działającymi losowo (jest to szybsze niż rozważenie wszystkich możliwych ruchów). Przypisz wartość do stanów równą średnemu wskaźnikowi wygranych gier, zaczynając od tego. To może nie dać poprawnej odpowiedzi, ale w niektórych rodzajach gier działa niezawodnie. Jest często stosowany jako rozszerzenie bardziej dokładnych technik, a nie stosowany samodzielnie.
Uwaga: Powodem, dla którego wybrałem tylko te trzy algorytmy, był czas, który miałem na ich zrozumienie. Z niewielkich badań odkryłem, że algorytmy te są zasadniczo wplecione w algorytm minimax. Więc jeśli uda mi się zrozumieć jedno, pozostałe dwa po prostu znajdą się na swoim miejscu.
Biorąc pod uwagę ten kontekst, poleciłbym zacząć od Minimax . Z trzech algorytmów Minimax jest najłatwiejszy do zrozumienia.
Alpha-Beta , jak inni wspominali w innych odpowiedziach, stanowi ścisłą poprawę w stosunku do Minimax. Minimax jest w zasadzie częścią implementacji Alpha-Beta, a dobre zrozumienie Alpha-Beta wymaga rozpoczęcia od dobrego zrozumienia Minimax. Jeśli zdarzy ci się mieć czas po zrozumieniu i wdrożeniu Minimaxa, zaleciłbym przejście do Alpha-Beta i zbudowanie go na Minimaxie. Zaczynając od wersji alfa-beta, jeśli jeszcze nie rozumiesz, Minimax naprawdę nie ma sensu.
Wyszukiwanie drzewa Monte-Carlo jest prawdopodobnie nieco bardziej zaawansowane i bardziej skomplikowane, aby naprawdę, dogłębnie zrozumieć. W ciągu ostatniej dekady MCTS naprawdę stał się znacznie bardziej popularny niż pozostałe dwa, więc z tego punktu widzenia zrozumienie MCTS może być bardziej „przydatne”.
Połączenie między Minimax i MCTS jest mniej bezpośrednie / oczywiste niż połączenie między Minimax i Alpha-Beta, ale nadal istnieje połączenie przynajmniej na poziomie koncepcyjnym. Twierdziłbym, że dobra znajomość Minimax jest nadal korzystna przed zanurzeniem się w MCTS ; w szczególności zrozumienie Minimax i jego wad / słabych punktów może zapewnić użyteczny kontekst / pomóc zrozumieć, dlaczego MCTS stał się „niezbędny” / popularny.
Podsumowując, moim zdaniem:
I musisz wybrać przycinanie Minimax i Alpha-Beta, powinieneś wybrać Alpha-beta. Jest bardziej wydajny i szybki, ponieważ może przycinać znaczną część twojego drzewa eksploracji. Ale musisz uporządkować działania od najlepszego do najgorszego, w zależności od maksymalnego lub minimalnego punktu widzenia, aby algorytm mógł szybko zrozumieć, czy eksploracja jest konieczna.