Minimax - какво е това, определение и концепция

В теорията на игрите минимаксът е метод, който има за цел да сведе до минимум очакваната загуба. За целта играчът приема, че решението, взето от противника му, ще бъде неблагоприятно. Тоест, най-лошият сценарий се очаква преди движението на противника.

Казано по друг начин, методът minimax се състои в това как да вземете най-доброто решение, като приемете, че другият играч ще избере най-лошия сценарий за вас.

Трябва да вземем предвид, че този метод е приложим в игра за двама души (двама играчи) и че не е кооперативна, а игра с нулева сума. Това означава, че това, което печели един играч, се губи от другия и обратно. Следователно, всеки агент ще се интересува от увеличаване на собствената си полезност, дори ако това вреди на другия.

На този етап трябва да помним също, че теорията на игрите е клон на математиката и икономиката, който изучава избора, който оптимизира ситуацията на индивида, когато разходите и ползите не са предварително фиксирани, а зависят от решенията на другите.

Алгоритъм на Minimax в дърво за вземане на решения

Можем да видим как методът minimax се прилага в дървото за вземане на решения с няколко възли. Играта започва отдолу и завършва с резултат на най-горното ниво.

В основата на дървото противникът прави първия ход, така че се очаква най-лошият резултат. След това, на второ ниво, зависи от играч x, който ще се стреми да увеличи печалбата си, като вземе предвид решението, взето преди това от противника.

На третото ниво отново е ред на противника и така нататък. Ще покажем пример по-долу.

Пример за алгоритъм на Minimax

В следващото дърво на решенията показваме резултатите, получени от играч x във всеки момент от играта. В основата, на първо ниво, противникът взема решението. Поради тази причина са дадени сценариите, при които играчът може да загуби -10 или да спечели 5.

На второ ниво зависи от играч x, така че той ще увеличи печалбата си максимално. Между загубата на 10 или спечелването на 1 ще спечелите 1. По същия начин, между спечелването на 5 или 7, ще спечелите 7.

След това отново е ред на противника, така че ще бъдат дадени сценариите, при които играч x има най-лошия резултат -3 и 4, в зависимост от случая. И накрая, между загуба 3 или победа 4, играч x ще вземе решението, което ще позволи на последния.

Трябва да вземем предвид, че стойностите на всеки възел ще зависят от полезна функция.

За да разберем по-добре дървото, да предположим, че в основата на решението е разпределението на продукта. Състезателят (противникът) може да възложи разпределението на външни изпълнители (вижте лявата страна на дървото). В този случай той трябва да избере, например, между дилър А и Б. По този начин той избира първия, причинявайки на играча х да загуби 10 (Ако е избрал Б, играч х ще спечели 12).

Въпреки това, може би противникът предпочита да разпространява стоките си сам, като може да наеме моторизирани превозни средства или да купи камион. И от двата сценария изберете първия, който е по-малко ласкателен за играч x, защото той печели 5, а не 10.