Algorytm min-max

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Minimax (czasami minmax) jest metodą w teorii decyzji do minimalizowania maksymalnych możliwych strat. Alternatywnie można je traktować jako maksymalizację minimalnego zysku (maximin). Wywodzi się to z teorii gry o sumie zerowej, obejmujących oba przypadki, zarówno ten, gdzie gracze wykonują ruchy naprzemiennie, jak i ten, gdzie wykonują ruchy jednocześnie. Zostało to również rozszerzone na bardziej skomplikowane gry i ogólne podejmowanie decyzji w obecności niepewności.

Teoria Minimax[edytuj | edytuj kod]

Teoria minimax:

Dla każdej dwuosobowej gry o sumie zerowej istnieje wartość V i mieszana strategia dla każdego gracza, takie, że (a) - biorąc pod uwagę strategię gracza drugiego, najlepszą możliwą spłatą dla gracza pierwszego jest V, i (b) - biorąc pod uwagę strategię gracza pierwszego, najlepszą możliwą spłatą dla gracza drugiego jest -V.

Odpowiednia strategia gracza 1. gwarantuje mu spłatę V niezależnie od strategii gracza 2. i podobnie gracz 2. może zagwarantować sobie spłatę -V. Nazwa Minimax pojawiła się, ponieważ każdy gracz minimalizuje maksymalną możliwą spłatę dla drugiego - ponieważ gra jest o grą o sumie zerowej, także maksymalizuje swoją minimalną spłatę.

Twierdzenie to zostało ustanowione przez Johna von Neumanna[1], którego powiedzenie jest cytowane "Jak do tej pory widzę, nie mogłoby być żadnej teorii gier… bez tej teorii… Myślałem, że nic nie było warte publikowania, aż Teoria Minimax została udowodniona".[2]

Kółko i krzyżyk[edytuj | edytuj kod]

Prosta wersja algorytmu minimax, określona poniżej, dotyczy gier takich jak kółko i krzyżyk, gdzie każdy gracz może wygrać, przegrać lub zremisować. Jeśli gracz A może wygrać w jednym ruchu, jego najlepszym ruchem jest właśnie ten wygrywający ruch. Jeśli gracz B wie, że jeden ruch doprowadzi do sytuacji, gdzie gracz A może wygrać w jednym ruchu, podczas gdy inny ruch doprowadzi do sytuacji, gdzie gracz A może, w najlepszym wypadku zremisować, wtedy najlepszy ruch gracza B jest ruchem prowadzącym do remisu.

Później podczas gry łatwo zobaczyć, który ruch był najlepszy.

Algorytm Minimax pomaga znaleźć najlepszy ruch, pracując od końca gry. Na każdym kroku zakłada, że gracz A próbuje zmaksymalizować szanse na wygraną gracza A, podczas gdy w następnym ruchu gracz B stara się zminimalizować szanse na wygraną gracza A (tzn. zmaksymalizować swoje szanse wygrania).

Minimax w kryterium statystycznej teorii decyzji[edytuj | edytuj kod]

W klasycznej statystycznej teorii decyzji estymator \delta używany jest do oszacowania parameteru \theta \in \Theta. Zakłada się również funkcję ryzyka R(\theta,\delta), zwykle określoną jako integralną z utratą funkcji. W tym kontekście \tilde{\delta} jest nazwana minimax, jeśli spełnia ona

\sup_\theta R(\theta,\tilde{\delta}) = \inf_\delta \sup_\theta R(\theta,\delta).

Alternatywnym kryterium w decyzji ramowej jest estymator Bayesa w obecności wcześniejszej dystrybucji \Pi. Estymator jest Bayesiański, jeśli minimalizuje średnie ryzyko

\int_\Theta R(\theta,\delta)\,d\Pi(\theta)

Przypisy

  1. Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928) 295-320
  2. John L Casti: Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience, 1996. ISBN 0-471-00261-5.

Linki zewnętrzne[edytuj | edytuj kod]