Algorytm Minimax

Question

Mam proste pytanie dotyczące algorytmu Minimax: na przykład dla gry kółko i krzyżyk, jak określić funkcję użyteczności dla każdego odtwarzacza? Nie robi tego automatycznie, prawda? Muszę zakodować wartości w grze, nie mogę ich samemu nauczyć, prawda?

Answer 1

Nie, MiniMax się nie nauczy. Jest to sprytniejsza wersja wyszukiwania drzewa brute-force.

Answer 2

Tic-Tac-Toe jest na tyle mała, aby uruchomić grę do końca i przypisać 1 dla Win, 0 za remis i -1 do stracenia.

W przeciwnym razie musisz podać funkcję, która określa wartość pozycji heurystycznie. W szachach na przykład dużym czynnikiem jest wartość materiału, ale także kto kontroluje centrum lub jak łatwo poruszają się kawałki.

Co do nauki, można dodać czynniki wagi do różnych aspektów pozycji i staramy się optymalizować te, poprzez wielokrotne odtwarzanie gier.

Answer 3

Jak ustalić funkcję narzędzia dla każdego odtwarzania?

Ostrożnie ;-) Ten article pokazuje, jak nieznacznie wadliwa funkcja oceny (jedna dla przykładu, która albo nie jest wystarczająco "głęboka", aby patrzeć w przyszłość na drzewo możliwych warstw, albo taka, która nie przechwytuje względna siła niektórych pozycji na planszy) powoduje ogólnie słaby algorytm (taki, który traci częściej).

nie można nauczyć je przez siebie, prawda?

Nie, nie ma. Istnieją jednak sposoby, aby komputer nauczył się względnej siły pozycji na planszy. Na przykład, patrząc na Donald Mitchie and his MENACE program zobaczysz, jak proces stochastyczny może być użyty do nauki planszy bez wiedzy, ale z zasadami gry. Zabawne jest to, że chociaż można to zaimplementować w komputerach, wystarczy kilkaset kolorowych kulek i pudełek dopasowanych, dzięki stosunkowo niewielkim rozmiarom przestrzeni gry, a także dzięki różnym symetriom.

Po nauczeniu taki fajny sposób nauczania komputer, jak grać, nie może być tak zainteresowany wracając do MinMax w zastosowaniu do Kółko i krzyżyk. Ostatecznie MinMax jest stosunkowo prostym sposobem przycinania drzewka decyzyjnego, co jest mało potrzebne w małej przestrzeni do gry w kółko i krzyżyk. Ale jeśli musimy ;-) [wróć do MinMax] ...

Możemy zajrzeć do "pudełka do gry" związanego z kolejną grą (np. Nie wchodząc głęboko) i użyć procentu powiązanych kulek z każdym kwadratem, jako dodatkowy czynnik. Możemy wtedy ocenić tradycyjne drzewo, ale tylko iść, powiedzmy 2 lub 3 ruchy głęboko (płytka głębokość, która zwykle kończy się zwykle w stratach lub losowaniach) i oceniać każdy następny ruch na podstawie prostej -1 (strata), 0 (losowanie/nieznane), +1 (wygrana) ocena. Łącząc w ten sposób procent kulek i prostą ocenę (np. Dodając, na pewno nie przez mnożenie), jesteśmy w stanie efektywnie wykorzystać MinMax w sposób bardziej zbliżony do sposobu, w jaki jest stosowany w przypadkach, gdy nie jest możliwe oszacowanie drzewo gry do końca.

Dolna linia: w przypadku Kółko i krzyżyk, MinMax staje się tylko bardziej interesujący (na przykład pomagając nam zbadać skuteczność danej funkcji użyteczności), gdy usuniemy deterministyczny charakter gry, związany z łatwa ocena pełnego drzewa. Innym sposobem na to, aby gra była [matematycznie] interesująca, jest granie z przeciwnikiem, który popełnia błędy ...

Answer 4

Zazwyczaj można zaimplementować funkcję narzędzia bezpośrednio. W tym przypadku algorytm nie nauczyłby się grać w grę, użyłby informacji, które zostały wyraźnie zakodowane w implementacji.

Jednak możliwe byłoby użycie genetic programming (GP) lub innej równoważnej techniki, aby automatycznie uzyskać funkcję użyteczności. W takim przypadku nie trzeba kodować żadnej jawnej strategii. Zamiast tego ewolucja odkryłaby własny sposób grania w grę.

Możesz połączyć swój kod minimax i kod GP w jeden (prawdopodobnie bardzo powolny) program adaptacyjny, lub możesz uruchomić GP jako pierwszy, znaleźć dobrą funkcję użyteczności, a następnie dodać tę funkcję do swojego kodu minimax, tak jak miałbyś jakąś funkcję zakodowaną ręcznie.