Zwykła skarga na sztuczną inteligencję w grach wideo brzmi: przeciwnicy podejmują złe decyzje. Z tego powodu bywa, że wprost oszukują, ale czasem dzieje się odwrotnie – AI prezentuje bardzo skuteczne strategie w grach, które można uznać za „proste”. Jednym z powodów jest zastosowanie twierdzenia Minimax, algorytmu mającego na celu minimalizację maksymalnej oczekiwanej straty w grach dwuosobowych z pełną informacją dla obu stron.
Wiele gier ukrywa informacje przed graczami jako część mechaniki. Wystarczy pomyśleć o „fog of war” w klasycznych grach (na myśl przychodzą StarCraft i Civilization). Ten zabieg pozwala AI przyzywać 20 czy 30 jednostek za pomocą magii, o czym nie masz pojęcia (między innymi). Jego wyeliminowanie jest kluczowe – zarówno przez wysyłanie jednostek na zwiady, jak i rozwijanie technologii znoszących ten efekt (np. Satelity w Civ).
Co jednak, gdy informacja jest pełna? Jak zachowuje się sztuczna inteligencja, gdy nie ma nic do ukrycia i wszystkie elementy partii są znane od początku? Jedną z wielu możliwości, jakie ma programista, jest wdrożenie twierdzenia Minimax. Oficjalny opis mówi o „metodzie decyzyjnej minimalizującej maksymalną oczekiwaną stratę” – to może brzmieć prosto, ale zasługuje na głębszą analizę.
Twierdzenie Minimax: optymalne rozwiązania dla gier o sumie zerowej
Kanał BitBoss świetnie podsumowuje algorytm Minimax, a najlepsze jest to, że zajmuje mu to mniej niż cztery minuty. Zasadniczo Minimax działa w grach o sumie zerowej, czyli takich, w których nasz zysk lub przewaga staje się stratą przeciwnika. Szachy to klasyczny przykład gry o sumie zerowej z pełną informacją, ale wideo prowadzi nas prostszą ścieżką, używając jako odniesienia kółka i krzyżyka.
Każdą fazę partii można opisać liczbą: dodatnią dla jednego gracza, a ujemną dla drugiego. Strategia algorytmu Minimax polega na wybraniu najlepszego możliwego ruchu, przy pełnym założeniu, że przeciwnik również wybierze najlepszy ruch przeciwko nam. Jeśli AI Minimax osiąga zwycięstwo z liczbą dodatnią, jej decyzje będą dążyć do trzymania się ścieżki, która sprzyja tej liczbie.
Wykres pokazuje ostatnie sześć możliwych ruchów sztucznej inteligencji w partii kółka i krzyżyka. Cztery z nich oznaczają zwycięstwo AI (na żółto) z wartością 1, a pozostałe dwa – zwycięstwo gracza (na niebiesko) z wartością -1. Ruchy analizuje się od dołu do góry, czyli od tyłu do przodu: skoro AI ma już tylko jeden ruch, wartości każdego z nich przesuwają się do poprzedniego kroku. Idąc tym samym tokiem rozumowania, gracz ma dwie możliwości gwarantujące -1 i trzecią, która zmusza go do wyboru 1. Dlatego AI zapewnia sobie zwycięstwo, wywierając nacisk na tę ścieżkę, która zaczyna się od krzyżyka na środku.
Oczywiście to zbyt prosty przykład, możliwy tylko dzięki naturalnym ograniczeniom kółka i krzyżyka. Jeśli przeniesiemy metodę Minimax do bardzo złożonych gier, takich jak szachy czy go, liczba stanów do sprawdzenia rośnie wykładniczo, a zastosowanie Minimax staje się niepraktyczne. Możliwym rozwiązaniem jest ograniczenie głębokości eksploracji – i z reguły wystarcza to, by zbić n00bów.
