Jak wybrać najlepszy algorytm dla gry planszowej, takiej jak warcaby?


15

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:


18

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:

  1. 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.

  2. 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.


A * tak naprawdę nie pasuje do gry dwuosobowej, tak jak inne algorytmy? Uwaga na temat MCTS: typowe implementacje „nie uwzględniają wszystkich ruchów do określonej stałej głębokości”, a następnie rozpoczynają wdrażanie; zamiast tego typowe implementacje dynamicznie, stopniowo rosną drzewo wyszukiwania drzewa, zwiększając je bardziej w bardziej obiecujących częściach (części, w których wiele wdrożeń jest popychanych przez strategię wyboru), zmniejszając je w mniej obiecujących częściach.
Dennis Soemers

1
@JohnDoucette, dlaczego powiedziałbyś „Żaden z tych algorytmów nie jest praktyczny w nowoczesnej pracy, ale są dobrym miejscem do rozpoczęcia pracy pedagogicznej”. W przypadku MCTS wydaje się bardzo odpowiednie dla nowoczesnej pracy, nawet dla wyszukiwania dla jednego gracza, gdy przejście do następnego stanu przy danym stanie i akcji jest dobrze zdefiniowane. Zgodziłbyś się?
Miguel Saraiva

1
@MiguelSaraiva Sam MCTS nie jest czymś, czego zwykle używa się w nowoczesnej aplikacji. W połączeniu z czymś takim jak DNN w celu zapewnienia wyuczonej heurystyki byłoby jednak całkiem dobre.
John Doucette

1
@JohnDoucette „MCTS nie jest czymś, czego zwykle używa się w nowoczesnej aplikacji”. Po pierwsze, „nowoczesność”, o której mówisz, przeżyła wielki przełom w 2016 r. (MCTS + DNN) i wydaje się, że sugerujesz, że wszystko przedtem jest przestarzałe (oczywiście fałszywe). W rzeczywistości może nawet bardziej prawdopodobne jest stwierdzenie, że MCTS zwykle nie jest używany z przeciwnej strony: jest zbyt zaawansowany: Istnieje mnóstwo aplikacji w przemyśle, które są naprawdę przestarzałe i mogą zostać zaktualizowane do MCTS. Dla wielu z tych MCTS + DNN jest tylko odległym marzeniem, ponieważ przedtreningowość jest prawie nie do pomyślenia.
Johan

1
@Johan To brzmi dobrze dla aplikacji przemysłowych , ale pytanie dotyczy „gry planszowej takiej jak warcaby”. W przypadku problemów z zabawkami uważam, że MCTS nie jest właściwym nowoczesnym podejściem. Zdecydowanie istnieje wiele problemów w świecie rzeczywistym, w których byłoby to ogromne ulepszenie istniejących wdrożonych systemów.
John Doucette

7

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:

  • Alpha-Beta jest zdecydowanie lepsza niż Minimax, ale także silnie powiązana / zbudowana na minimaksie; więc zacznij od Minimax, a później wybierz Alpha-Beta, jeśli czas na to pozwoli
  • MCTS ma różne mocne / słabe strony, jest często lepszy niż Alpha-Beta w „nowoczesnych” problemach (ale nie zawsze), dobre zrozumienie Minimax prawdopodobnie będzie korzystne przed rozpoczęciem nurkowania w MCTS

Czy jest jakiś inny algorytm, który sugerowałbyś, że mógłbym również użyć? To na poziomie przycinania wersji beta beta
Joey

@Joey Hmm nie, naprawdę nie. Minimax jest bardzo naturalnym punktem wyjścia, bardzo gorąco polecam, jeśli dopiero zaczynasz. Był to w zasadzie pierwszy algorytm opracowany dla gier takich jak szachy / warcaby / kółko i krzyżyk / cokolwiek innego. Następnie opracowano setki, jeśli nie tysiące ulepszeń, z których wiele prawdopodobnie można znaleźć na stronie chessprogramming.wikispaces.com/Search . Alpha-Beta jest najbardziej naturalnym ulepszeniem, na które można patrzeć na Minimax.
Dennis Soemers,

@Joey Monte-Carlo Wyszukiwanie drzewa jest nieco inne (niekoniecznie opiera się na Minimaxie), jest interesujące, zabawne, popularne i bardzo przydatne w „nowoczesnej” sztucznej inteligencji. Mimo to fundamenty są ważne, nie poleciłbym rozpoczęcia od MCTS natychmiast, jeśli jeszcze nie rozumiesz Minimax + Alpha-Beta, nawet jeśli jest to technicznie możliwe.
Dennis Soemers,

Dziękuję za tę stronę. To bogactwo wiedzy, które mogę teraz przeczytać. Najtrudniejsze w nauce nowych rzeczy jest znalezienie odpowiedniego materiału, który pomoże ci zrozumieć. Jeszcze raz dziękuję za stronę
Joey,

@Joey Nie jestem w 100% pewien, czy chessprogramming jest najłatwiejszą stroną, z której można się uczyć (a na górze wydaje się być przerażające powiadomienie, że witryna może znikać pod koniec lipca). Jeśli dobrze pamiętam, wiele opisów jest raczej krótkich / prawdopodobnie niełatwych do zrozumienia, jeśli jesteś początkującym w tej dziedzinie. Będzie to jednak przynajmniej dobry, wszechstronny zbiór nazw wszelkiego rodzaju algorytmów / ulepszeń, a ty możesz spróbować poszukać oryginalnych źródeł lub google wszystkie te nazwy, aby uzyskać bardziej szczegółowe informacje w innym miejscu.
Dennis Soemers,

1

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.