Algorytm min-max

Brak wersji przejrzanej

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ść.

Spis treści

1 Teoria Minimax
2 Kółko i krzyżyk
3 Minimax w kryterium statystycznej teorii decyzji
4 Przypisy
5 Linki zewnętrzne

[edytuj] Teoria Minimax

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.

Odpowiednio 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 John'a von Neumann'a^[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]

[edytuj] Kółko i krzyżyk

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).

[edytuj] Minimax w kryterium statystycznej teorii decyzji

W klasycznej statystycznej teorii decyzji mamy estymatora $δ$ który jest używany do oszacowania parameteru $\theta \in \Theta$ . Zakłada się również funkcję ryzyka $R (θ,δ)$ , 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 $Π$ . Estymator jest Bayesiański, jeśli minimalizuje średnie ryzyko

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

Przypisy

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

[edytuj] Linki zewnętrzne

Źródło: „http://pl.wikipedia.org/wiki/Algorytm_min-max”

Kategorie: Teoria decyzji • Informatyka • Algorytmika