Algorytm min-max

Z Wikipedii

Ten artykuł jest teraz edytowany przez vkajot. Prosimy nie edytować strony do czasu zniknięcia tej wiadomości. Nazwa użytkownika, który dodał tę wiadomość, jest wyświetlona na stronie historii. Jeżeli ta strona nie była edytowana od paru godzin, prosimy usunąć szablon. Założeniem tego szablonu jest zmniejszenie konfliktów edycji.

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 dwuosobewej 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-go gwarantuje mu spłatę V niezależnie od strategii gracza 2-go, i podobnie Gracz 2gi może zagwawrantować sobie spłatę -V. Nazwa Minimax pojawiła się, ponieważ każdy gracz minimalizuje maksymalną możliwą spłatę dla grugiego--ponieważ gra jest o grą o sumie zerowej, także maksymalizuje swoją minimalna 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 byc ż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. by 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 . Zakłada się również funkcję ryzyka R(θ,δ), zwykle określoną jako integralną z utratą funkcji. W tym kontekście, jest nazwana minimax jeśli spełnia ona

.

Alternatywnym kryterium w decyzji ramowej jest estymator Bayes'a w obecności wcześniejszej dystrybucji Π. Estymator jest Bayes'iański jeśli minimalizuje średnie ryzyko

Przypisy

[edytuj] Linki zewnętrzne

• Simple explanation of the algorithm
• Minimax Analysis for Zero Sum Games
• A visualization applet
• "Maximin principle" from A Dictionary of Philosophical Terms and Names.
• Play a betting-and-bluffing game against a mixed minimax strategy
• The Dictionary of Algorithms and Data Structures entry for minimax
• Minimax (with or without alpha-beta pruning) algorithm visualization - game tree (Java Applet)
• CLISP minimax - game.