minmax

Minmax – Schopenhauer wśród algorytmów

Rzadko kiedy mamy komfort braku przeciwników działających na naszą niekorzyść. A* spisywał się znakomicie w pustym labiryncie, ale co kiedy znajdziemy tam wrogie nam istoty? Albo jeśli świat gry jest niedeterministyczny? Zanim to, zastanówmy się nad prostszą grą – kółko i krzyżyk.

Zasady są wszystkim doskonale znane. Dwójka graczy na zmianę wykonuje swoje ruchy. Określony układ X i O na planszy nazwiemy stanem. W każdym stanie są dozwolone pewne akcje – różne dla różnych graczy (postawienie X oraz O na tym samym polu traktujemy jako dwie różne akcje). Niektóre stany są stanami końcowymi, tzn. takimi dla których nie ma dozwolonych akcji. Oczywiście są to sytuacje gdzie cała plansza jest już zapełniona oraz stany w których jeden z graczy odniósł zwycięstwo.

W jaki sposób należy podejść do problemu? Każdej naszej akcji będzie towarzyszyć reakcja ze strony przeciwnika, musimy ją przewidzieć i uwzględnić w procesie myślowym. Tradycyjnie można stworzyć drzewo. Korzeniem jest stan początkowy kiedy żaden ruch nie został wykonany. Załóżmy, że zaczyna gracz X. Na poziomie pierwszym znajdą się wszystkie możliwe stany po wykonaniu przez niego ruchu. Na poziomie drugim kontrolę przejmuje gracz O. I tak na zmianę aż dotrzemy do stanów końcowych.

Stany końcowe charakteryzują się posiadaniem pewnej liczby, którą będę nazywać oceną lub wartością. Mówi ona jak pożądany przez gracza jest taki stan. Łatwo zauważyć, że to co jest pożądane przez jednego gracza, będzie niepożądane przez drugiego. Niech wygrana gracza X będzie oznaczona jako +1, remis jako 0, a wygrana gracza O przez -1. Gracz X będzie dążył do maksymalizowania (max) a gracz O do minimalizowania (min).

Próbujemy podjąć decyzje, które doprowadzą do zmaksymalizowania wyniku (rozważamy przypadek gracza max). Spójrzmy na ilustrację przykładowego problemu (nie kółka i krzyżyka). Trójkąt skierowany w górę symbolizuje gracza max, w dół – min.

minmax1Analizę zacznijmy od lewego dolnego rogu. W tym punkcie gracz min ma do wyboru dwie decyzje. Jedna doprowadzi do końca gry z wynikiem +5, druga +7. Jako że chce zminimalizować ten wynik, wybierze +5. Po przejściu przez cały poziom wartości prezentują się następująco:

minmax2Poziom wyżej decyzje podejmuje max. Wie, że niezależnie co zrobi, przeciwnik zagra na jego niekorzyść. Spośród dostępnych opcji wybiera tą która będzie pomimo działań nieprzyjaciela doprowadzi do lepszego (z jego punktu widzenia) stanu. W ten sposób wypełniamy całe drzewo.

minmax3

Ścieżka pokazana na czerwono pokazuje ciąg decyzji. Max wybiera lewy węzeł. W odpowiedzi na to min wybierze prawy i tak do liścia z wartością. W ten sposób max uwzględnia co zrobi min aby mu przeszkodzić. Trudno jest tutaj mówić o maksymalizowaniu zysku, bliższe prawdy będzie minimalizowanie strat.

Całość da się zgrabnie zapisać w formie rekurencyjnej (nie jest tutaj uwzględnione zapamiętywanie decyzji do podjęcia – zależy to mocno od konkretnej implementacji.

minmax(stan):
1. jeśli stan jest stanem końcowym zwróć jego wartość.
2. Jeśli stan jest węzłem max
2.1. wywołaj na rzecz każdego potomka minmax, jako węzeł min
2.2. zwróć wartość maksymalną
3. w przeciwnym wypadku (węzeł min)
3.1. wywołaj na rzecz kazdego potomka minmax, jako węzeł max
3.2. zwróć wartość minimalną

Implementacja

Cały kod jest dostępny w repozytorium https://github.com/Xevaquor/aipac Przykład jest dla gry w kółko i krzyżyk, dla innych gier idea się nie zmienia.

Algorytm korzysta z obiektów state i game. Dostarczają one potrzebnych informacji na temat świata gry. Są to:
game.get_legal_moves – zwraca listę dozwolonych akcji w danym stanie gry
game.apply_move – zwraca stan po wykonaniu danej akcji
game.has_won/has_lose – informuje czy w danym stanie nastąpiło zwycięstwo/porażka gracza
game.is_terminal – czy dany stan jest stanem końcowym

Funkcja oceniająca liść:

def score(self, state, game):
	"""
	Computes state score.
	:type state: tictactoe.State
	:type game: tictactoe.TicTacToe
	:return: Score value, None if state is not terminal. (Is not leaf in tree)
	"""
	if game.has_won(state, self.symbol):
		return 1
	elif game.has_lose(state, self.symbol):
		return -1
	elif game.is_terminal(state):
		return 0
	else:
		return None

Operacje na węźle min (dla max jest analogicznie). Obliczamy wartości wszystkich potomków i wybieramy tego z najmniejszą.

def min(self, state, game):
	"""
	Processes min-node.
	:type state: tictactoe.State
	:type game: tictactoe.TicTacToe
	:return: tuple, node value, action taken
	"""
	# get legal moves for given state
	legal_moves = game.get_legal_moves(state, self.opponent_symbol)
	# compute score for current state
	state_score = self.score(state, game)
	# if state is unknown (None), continue. Return score otherwise.
	if state_score is not None:
		return state_score, None

	children = []
	# for every legal move
	for move in legal_moves:
		# get state after executing action
		next_state = game.apply_move(state, move)
		# get value of child node (for children of min node, it is a maximum).
		# action is irrelevant
		value, dumb = self.max(next_state, game)
		children.append((value, move))

	# select minimal successor
	return min(children)

I ostatecznie funkcja podejmująca decyzję. Przyjęliśmy że jesteśmy graczem max.

def make_move(self, state, game):
	"""
	Selects action to make in given state. Assumes max player.
	:type state: tictactoe.State
	:type game: tictactoe.TicTacToe
	:return: action to take
	"""
	score, move = self.max(state, game)
	return move

Własności

Minmax ma kilka ciekawych własności. Pierwszą z nich jest przeczesywanie całego drzewa. Nawet przy tak prostej grze decyzja jest podejmowana we względnie długim czasie. Proces można przyśpieszyć kończąc wywołania na pewnym poziomie zagnieżdżenia. Wtedy zamiast schodzić dalej, szacujemy wartość aktualnego stanu. Oczywiście za kolejnym wywołaniem zejdziemy o jeden poziom niżej poprawiając nasze szacunki, ale w ten sposób niestety tracimy gwarancję dokładnego rozwiązania. Aby ograniczyć wielkość przestrzeni można użyć alfa-beta cięć. Umożliwiają one ucięcie pewnych gałęzi drzewa, o których wiadomo, że na pewno nie wniosą nic nowego. Nie będę tego opisywać, gdyż nie przynosi to spektakularnej poprawy wydajności.

Drugą sprawą jest skrajny pesymizm (stąd tytuł posta). Weźmy takie drzewo:

minmax4

Wybierając lewą ścieżkę możliwe wyniki to +7 lub +6. Dla prawej są to +5 i +100. Minmax wybierze lewą, gdyż pesymistycznie założy optymalną grę przeciwnika, który nie pozwoli zdobyć +100. Jeżeli przeciwnik nie jest idealny mógłby się pomylić i pozwolić nam na pogrom. Gdybyśmy poszli w prawo, w najgorszym wypadku dostaniemy +5. Minmax pójdzie w lewo uzyskując +6 lub +7 (w zależności od decyzji przeciwnika). Cholera, może warto zaryzykować? Mamy w najgorszym razie 2 do stracenia (7 – 5), ale możemy zyskać 100 – 5 = 95. Tym problemem zajmiemy się w następnej kolejności – nie wiemy jak zachowają się wrogowie w labiryncie, przypuszczamy również, że nie zachowują się oni optymalnie.

Minmax można rozszerzyć dla większej ilości graczy. Np. jeden gracz max, dwóch graczy min (wtedy poziomy drzewa kształtują się: MAX-MIN-MIN-MAX-MIN-MIN…). Każdy z graczy może również maksymalizować/minimalizować inną wartość we wzajemnie powiązanej krotce danych. Przykład oraz ciekawy skutek uboczny – następnym razem.

Podsumowując: jeśli gra jest deterministyczna oraz wiemy że przeciwnik jest idealny, minmax pozwoli zachować się najlepiej jak to możliwe. Jeżeli nie – przygotuje się na najgorsze.

Reklamy