Z Wikipedii

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

[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 . 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 Bayesa w obecności wcześniejszej dystrybucji Π. Estymator jest Bayesiań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.