Aby skutecznie zastosować min / max do turowej gry strategicznej, musisz poprawnie zastosować wszystkie dostępne techniki szachowe ...
Funkcja oceny
Nawet silniki szachowe mają bardzo słabą siłę, jeśli twoje funkcje oceny są złe. Najprostsza wersja funkcji oceny to: 1 = gra wygrana przez kolor biały, -1 = gra wygrana przez kolor czarny, 0 = wszystkie pozostałe przypadki; Ale dałoby to bardzo słabą wydajność. To samo dzieje się z twoją grą turową! Jeśli chcesz używać min / max (z przycinaniem alfa / beta i tak dalej) jak w szachach, musisz także wdrożyć rozsądną funkcję oceny! Poza tym nie można porównywać wydajności tych algorytmów w grze strategicznej z przypadkiem, w którym stosuje się ją w szachach.
Funkcje funkcji silników szachowych polegają na ocenie rzeczy takich jak:
- Jak dobrze jest pozycja pionka na planszy?
- Ile razy atakowany jest kawałek?
- Ile razy element jest chroniony?
- Jak dobrze każdy element może swobodnie „poruszać się” na planszy? (lub: Ile płytek „kontroluje”)
Te części funkcji oceny muszą najpierw zostać „przetłumaczone” na twoją grę:
- Pozycja elementu: czy znajduje się np. Na wzgórzu, które zwiększa zasięg strzelania?
- Zaatakowany: Ile kosztuje każda sztuka? (np. suma wartości ataku jednostek zdolnych do ataku na jednostkę specjalną pomnożona przez pewne prawdopodobieństwo jej zaatakowania; prawdopodobieństwo wzrasta, jeśli jednostka jest już uszkodzona; zmniejsza się, jeśli wiele innych jednostek znajduje się w zasięgu jednostki atakującej)
- Własny atak: ile jednostek może zostać zaatakowanych przez tę jednostkę?
- Ochrona: ile własnych elementów jest obok (aby pomóc)? Być może jednostka nie może atakować jednostek w minimalnej odległości i lepiej jest chronić ją przez jednostkę mającą możliwość atakowania pobliskich jednostek.
- Mobilność: jak mobilna jest twoja jednostka? (czy może uciec?)
Różne oceny należy zsumować za pomocą funkcji ważenia (współczynnik_a * ocena_a + współczynnik_b * ranting_b + ...) dla wszystkich jednostek ...
W grach strategicznych należy również wziąć pod uwagę pozostałe zasoby (złoto, drewno, ...).
Jeśli funkcja oceny jest wystarczająca, w większości przypadków nie trzeba tak naprawdę szukać „głęboko” w drzewie. Prawdopodobnie musisz tylko przyjrzeć się 3 lub 10 najbardziej obiecującym wyborom. Zobacz następny rozdział ...
Możliwe ruchy w każdej pozycji
Najbardziej problematyczną rzeczą w używaniu min / max w grach strategicznych jest to, że możesz dowodzić wieloma jednostkami w jednej turze, podczas gdy w szachach możesz dowodzić tylko jedną jednostką (z wyjątkiem roszady, ale jest to wyraźnie zdefiniowana kombinacja ruchów). Powoduje to 5 ^ N możliwych ruchów dla N jednostek dla każdej „pozycji” (termin szachowy), jeśli zdecydujesz się tylko na „ruch na północ, południe, zachód, wschód lub zatrzymanie OR” dla każdej jednostki. Możesz rozwiązać ten problem, dzieląc złożone polecenie na polecenia niskiego poziomu: np. Wybierz akcję dla jednostki A, idź w głąb i wybierz jednostkę B .... wybierz jednostkę N ..., a następnie zakończ tę turę. Ale to samo nie zmienia złożoności! Musisz zoptymalizować kolejność przypisywania akcji do jednostek (np. Pierwsza jednostka B, C, D, a następnie jednostka A). Możesz zapisać wpływ decyzji dla każdej jednostki podczas ostatniego obliczenia, a następnie posortować według ważności. W ten sposób przycinanie alfa-beta można bardzo wcześnie wyciąć złą kombinację z drzewa wyszukiwania. Najwyższym priorytetem zawsze powinno być „nie rób nic więcej i kończ swoją turę” (przycinanie ruchu zerowego) w każdej iteracji. W ten sposób możesz „pominąć” przypisywanie większości zadań do większości jednostek i pozwolić im po prostu kontynuować to, co zrobili wcześniej. W ten sposób wyszukiwanie szybko się pogłębi, po prostu patrząc na „krytyczne” jednostki (np. Te, które naprawdę są teraz w walce). Upewnij się, że dowodzisz każdą jednostką tylko raz ... Możesz także użyć pewnej losowości, aby mieć pewność, że „ważne” jednostki również otrzymują od czasu do czasu polecenie. Szczególnie jednostki kończące jakąś pracę (np
Iteracyjne pogłębianie + buforowanie / tablica skrótu
Następnie możesz „pogłębiać interwencyjnie”, aby pogłębiać się coraz głębiej, aż do osiągnięcia określonego limitu czasu. Będziesz więc szukać głębiej, jeśli będzie mniej jednostek, i zawsze będziesz mieć „wynik”, jeśli przestaniesz szukać lepszego rozwiązania. Pogłębianie iteracyjne wymagałoby użycia tabeli skrótów do buforowania wcześniejszych wyników wyszukiwania. Umożliwia to także ponowne wykorzystanie niektórych wyników z wyszukiwania w ostatnich turach (gałąź drzewa wyszukiwania, która obejmuje polecenia faktycznie wykonane w ostatniej turze). Aby to zaimplementować, potrzebujesz bardzo dobrej funkcji skrótu (spójrz na „klucz zobrista”), którą można iteracyjnie aktualizować. Aktualizacja klucza skrótu oznacza, że możesz po prostu wziąć klucz skrótu ze starej „pozycji” i po prostu wprowadzić zmianę pozycji (np. wyjmij jednostkę w pozycji x i ustaw ją w pozycji y). W ten sposób obliczenie klucza skrótu jest szybkie i nie trzeba przetwarzać całej sytuacji na tablicach, aby go obliczyć, wystarczy sprawdzić, czy skrót zawiera poprzedni wpis dla tej pozycji. W pewien sposób musisz upewnić się, że nie dojdzie do kolizji skrótu.
Zachowanie niedeterministyczne
Zachowanie niedeterministyczne jest problemem dla wyszukiwań min / maks. Oznacza to, że nie jest pewne, czy trafisz zaatakowany cel (np. Prawdopodobieństwo wynosi 10%). Wtedy nie możesz tak po prostu zaplanować. W takim przypadku musisz zmodyfikować algorytm i umieścić warstwę „prawdopodobieństwa” pomiędzy nimi. To trochę tak, jakby „zmienił się prawdopodobieństwo”. Każdy niezależny wynik należy rozpatrywać osobno. Następnie należy pobrać próbkę oceny przez tę „warstwę” głębokości (próbkowanie Monte Carlo), a wynik szczegółowej oceny musi być ważony prawdopodobieństwem wystąpienia. Różne wyniki warstwy prawdopodobieństwa należy traktować jak różne ruchy przeciwne (ale zamiast min / max należy obliczyć „średnią”). To oczywiście zwiększy złożoność drzewa wyszukiwania.
streszczenie
Stosując wszystkie te techniki (wszystkie stosowane w obecnych silnikach szachowych) w deterministycznej grze, z pewnością będziesz w stanie osiągnąć rozsądne wyniki również w grze. W przypadku gier niedeterministycznych będzie to prawdopodobnie bardziej skomplikowane, ale myślę, że nadal jest to możliwe.
Dobrym źródłem informacji na temat tych technik (w szachach) jest http://chessprogramming.wikispaces.com/
Możesz nawet wdrożyć ukierunkowaną losowość w wyszukiwaniu min / maks. Zamiast deterministycznie badać najlepsze wyniki na początku każdej iteracji, możesz po prostu randomizować to i pozwolić na ustalenie jego kolejności na podstawie rozkładu prawdopodobieństwa opartego na bieżących ocenach ...