Algorytm min-max

Z Wikipedii

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

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 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]

[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 estymator $δ$ używany jest 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

Dane pijanych kierowców na Twitterze

Jeśli zostałeś złapany przez policję za jazdę „po pijaku” przejeżdżając przez Montgomery County, w stanie Teksas, o wydarzeniu tym mogą dowiedzieć z Twittera Twoi sąsiedzi.

7 najczęściej exploitowanych programów 2009 roku

Koniec roku to czas podsumowań. Pora więc także dowiedzieć się jakie aplikacje były najczęściej wykorzystywane przez cyberprzestępców. Oto lista 7 programów, które były najpopularniejsze

Cisco 2009 Annual Security Report

Firma Cisco opublikowała swój roczny raport na temat bezpieczeństwa komputerowego. Autorzy ostrzegają w nim przed zagrożeniami czyhającymi na użytkowników internetu.

Naukowcy zapowiadają koniec ataków na strony www

Badania przeprowadzone przez naukowców z University of Bristol\'s Department of Computer Science, które zostaną zaprezentowane na ASIACRYPT 2009 mają na celu położyć kres atakom na strony internetowe. Jak zapowiadają autorzy badań staną się one całkowicie niemożliwe

Włamanie na strony NASA

Dwie strony internetowe należące do NASA padły ofiarą włamania. Włamywacze wykorzystali metodę SQL Injection. Więcej informacji można przeczytac na stronie The Register

data center nieruchomo�ci w Lublinie Konto osobiste okna cieszyn Deweloper projekty wizytówek rachunki oszczędnościowe silosy No i gra - Budka Suflera programy do fakturowania

[0] Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928) 295-320

[Casti-1] 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.

[1]

[2]

gry.kompedium.net