Минимакс (алгоритам)

Минимакс је правило одлука који се користи у теорији одлучивања, теорији игара, статистици и филозофији за минимизирање могућих губитака у најгорим случајевима(највећи губитак). Алтернативно, може се посматрати као максимизирање минималне добити. Првобитно је формулисан за теорију нулте-суме два играча, који покрива оба случаја где играчи узимају алтернативне потезе и оне где чине симултане потезе, такође је проширена на више комплексних игара и na опште одлучивање у присуству неизвесности.

Теорија игара уреди

У теорији симултаних игара, стратегија Минимакс је мешовита стратегија која је део решења до нултог збира игре. У нулта-сума игри, Минимакс решење је исто као и Неш еквилибријум.

Минимакс теорема уреди

Стања минимакс теореме^[1]

За сваке две особе, нулта-сума игра са коначно много стратегија, где постоји вредност V и мешана стратегија за сваког играча, као
(а) С обзиром на стратегију 2 играча, најбоља исплата за играча 1 је V, и

(б) С обзиром на стратегију 1 играча, најбоља исплата за играча 2 је -V.

Еквивалентно, стратегија играча 1 му гарантује исплату од В без обзира на стратегију играча 2, и слично играч 2 може себи гарантовати исплату од -В. Име Минимакс настаје јер сваки играч смањује максималну могућу зараду за друге - јер је игра са нултом сумом, он такође смањује своју максималну губитак (тј. максимализује свој минимални губитак).

Ова теорема је прво објављена 1928 године. од John von Neumann,^[2] који је написао "As far as I can see, there could be no theory of games … without that theorem … I thought there was nothing worth publishing until the Minimax Theorem was proved".^[3]

Погледати Sion's minimax theorem и Parthasarathy's theorem за генерализацију; Такође погледати example of a game without a value.

Пример уреди

	B бира B1	B бира B2	B бира B3
A бира A1	+3	−2	+2
A бира A2	−1	0	+4
A бира A3	−4	−3	+1

У овом примеру је игра нулта-сума, где A и B праве симултане потезе, илустујући минимакс решења. Претпоставимо да сваки играч има три могућа потеза и погледати матрицу исплате за A приказану са десне стране. Претпоставимо да је матрица исплате за B иста матрица са обрнутим знацима (тј. ако су избори А1 и В1 онда B плаћа 3 A). Онда, минимаксов избор за A је А2 како је тада најгори могући резултат платити 1, док једноставни минимаксов избор за B је B2 и најгори могући резултат тада је да се не плати ништа. Наиме, ова ситуација није стабилна, јер ако B верује да ће A изабрати А2 онда ће B изабрати В1 да би освојио 1; онда ако A верује да ће B изабрати B1 онда ће A изабрати A1 да освоји 3; и онда ће B изабрати B2; и потенцијално ће оба играча схватити тежину самог избора. Самим тим нам је потребна стабилнија стратегија.

Неки избори су доминантнији од других и могу бити елиминисани: A неће изабрати A3 како ни A1 ни A2 неће имати боље резултате, без обзира на избор који ће направити B; B неће изабрати B3 како ће неке мешавине од В1 и В2 направити боље резултате, без обзира шта A изабере.

A може да ибегне да направи очекивану исплату већу од 1/3 бирајући А1 са вероватноћом 1/6 и A2 са вероватноћом 5/6: Очекивана исплата за A ће бити 3*(1/6)-1*(5/6)=-1/3 у случају да B изабере B1 и -2*(1/6)+0*(5/6)=-1/3 у случају да B изабере B2. Слично, B може да осигура очекиван добитак од најмање 1/3, без обзира шта A изабере, користећи случајну стратегију одабира В1 са вероватноћом 1/3 и B2 са вероватноћом 2/3. Ове мешане стратегије су сада стабилне и не могу се побољшати.

Максмин уреди

Често, у теорији игара, максмин је другачије од минимакс. Минимакс се користи у нулта-сума играма да означи минимизирање противникове маскималне зараде. У нултим-сумама, ово је идентично са минимизовањем максималног губитка, и максимизовањем минималног добитка.

"Максмин" је термин који се обично користи за ненулта-сума игре при објашњавању где се максимизује минимални добитак. У ненулта-сума играма, ово није генерално исто као минимизовање противниковог максималног добитка, као ни Неш еквилибријум стратегија.

Комбинаторнна теорија игара уреди

У комбинаторној теорији игара (combinatorial game theory), постоји минимакс алгоритам као ререшење игара.

A једноставна верзија минимакс алгоритма, наведена у наставку, бавећи се играма као што су икс-окс, где сваки играч може да победи, изгуби, или изједначи. Ако играч A може да победи у једном потезу, његов најбољи потез је тај победнички потез. Ако играч В зна да ће тај један потез одвести до ситуације где А може да победи у једном потезу, док ће други потез одвести до тога да А може, у најбољем случају, да изједначи, онда ће најбољи потез играча В бити да одведе до изједнчења. Касније у игри, лако је видети који је "најбољи" покрет. Минимакс алгоритам помаже у проналаску најбољег потеза, гледањем уназад од почетка. У сваком кораку претпостављамо да је играч А покушао да максимизује шансе победе А, док на следећем кругу уграч Б покушава да минимизује шансе да А победи(тј. како би се играчу В повећала шанса да победи).

Минимакс алгоритам са алтернативним покретима уреди

Минимакс алгоритам^[4] је рекурзивни алгоритам за одабир следећег потеза у n-играча играма, углавном за два играча. Вредност је повезана са сваком позицијом или стањем игре. Ова ведност се израчунава помоћу функције евалуације позиције и показује колико та позиција може значити играчима. Играч онда прави потез који максимизује минималну вредност положаја противникових могућих потеза. Ако се A покренуо, A даје вредност сваком од његових легалних потеза.

Могућа алокација метода се састоји из додељивања победе за A као +1 и за B као −1. Ово води на комбинаторну теорију игара развијену од стране John Horton Conway. Алтернативно коришћење правила је ако је резултат потеза победа за A додељује се позитивна бесконачност и, ако је резултат победа за B, додељује се негативна бесконачност. Вредност A било ког следећег потеза је минимум вредности које су настале од сваког од B's могућих одговора. Из овог разлога, A зовемо maximizing player и B зовемо minimizing player, отуда назив минимакс алгоритам. Алгоритам изнад ће доделити вредност позитивне или негативне бесконачности свакој позицији док вредност сваке позиције не постане вредност финалне позиције победе или пораза. Ово је генерално могуће на крају компликоване игре као што је шах или го, како није рачунски изводљиво видети крај игре, осим при крај игре, и уместо позиција које дају крајње вредности као процена степени веровања да они воде до победе једног играча или другог.

Ово може бити проширено ако можемо да пружимо хеуристичну евалуацију функција које додељују вредности не завршном потезу без узимања у обзир све могућности пратећих комплетних секвенци. Тако можемо ограничити минимакс алгоритам тако што гледамо само одређени број потеза напред. Овај број се зове "look-ahead", мерен у "plies (Ply (chess))". На пример, шах рачунар IBM Deep Blue (који побеђује Гари Каспаров) гледао је унапред 12 слојева, затим примењује хеуристике евалуационе функције.

Алгоритам се може посматрати као истраживање чворова (node (computer science)) код дрвета игара(game tree). Ефикасан фактор гранања (branching factor) дрвета је средња вредност дете чвора сваког чвора (тј. средња вредност легалних потеза на позицију). Број чворова који се углавном истражују се повећавају експоненцијално (exponential growth) са бројем слојева(мање је од експоненцијалног ако се евалуира груб потез или понављање позиција). Број чворова који се истражују за анализе игре је дакле приближно фактор гранања повећао до јачине броја слојева. Он је дакле непрактичан (Computational complexity theory#Intractability) да би се завршила анализа игара као што је шах користећи минимакс алгоритам.

Перформансе наивног минимакс алгоритма могу бити драматично унапређене, без одражавања на резултат, користећи алфа-бета претрага. Остале хеуристичке методе могу такође да се користе, али не може се за све њих гаратновати да ће дати резултате као непромењена претрага.

Наивни минимакс алгоритам може тривијално измењен да додатно врати целу главну варијацију (Variation (game tree)#Principal variation) заједно са максималним резултатом.

Lua example уреди

function minimax(node,depth)
   if depth <= 0 then
      -- позитивне вредности су добре за максимизирање играча
      -- негативне вредности су добре за минимизирање играча
      return objective_value(node)
   end
   -- максимизирање играча је (+1)
   -- минимизирање играча је (-1)
   local alpha = -node.player * INFINITY
   
   local child = next_child(node,nil)
   while child ~= nil do
      local score = minimax(child,depth-1)
      alpha = node.player==1 and math.max(alpha,score) or math.min(alpha,score)
      child = next_child(node,child)
   end

   return alpha
end

Псеудокод уреди

Псеудокод за дубину ограничену минимакс алгоритмом је у наставку.

function minimax(node, depth, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        bestValue := -∞
        for each child of node
            val := minimax(child, depth - 1, FALSE))
            bestValue := max(bestValue, val);
        return bestValue
    else
        bestValue := +∞
        for each child of node
            val := minimax(child, depth - 1, TRUE))
            bestValue := min(bestValue, val);
        return bestValue

(* Initial call for maximizing player *)
minimax(origin, depth, TRUE)

Минимакс третира два играча (максимизирањем играча и мининизирањем истог) подељено у два кода. На основу запажања да $\max(a,b)=-\min(-a,-b)$ , минимакс може често да се упрости у негамакс(negamax) алгоритам.

Пример уреди

Анимиран педагошки пример који покушава да буде људско-пријатељски зааменом почетне бесконачости (или произвољно велика) вредност за празнину и избегавање коришћења (coding simplifications).

Претпоставимо да игра почиње, и да максимум два потеза по играчуу је по кругу. Алгоритам генерише дрво (game tree) надесно, где кругови престављају покрете играча који су покренули алгоритам (maximizing player), и квадратна репрезентација покрета противника (minimizing player). Из разлога лимитацијенад рачунарских ресурса, објашњено изнад, дрво је лимитирано на look-ahead 4 потеза.

Алгоритам процењује сваки лист чвор користећи функцију хеуристичке евалуације, прибављањем добијених вредности. Потези где побеђују максимизирање играча су додељени са позитивном бесконачношћу, док су потези који доводе до победе на минимизирање играча се додељује са негативном бесконачношћу. На трећем нивоу, алгоритам ће изабрати, за сваки чвор, „најмањи“ од дете чвор вредности и доделити га том истом чвору (нпр. Чвор на левој страни ће изабрати миниму између „10“ и „+∞", дакле доделиће себи вредост „10“ ). Наредни корак, на другом новоу, састоји се од избора за сваки чвор у највећи од child node чвора вредности. Поново, вредности су додељене сваком родитељ чвор. Алгоритам се даље наставља оцењивањем највеће и најмање вредности од деце чворова наизменично док не достигне корен чвор где се бира потез са највећом вредношћу (представљени на слици са плавом стрелицом). То је потез који играч треба да у циљу минимизирања на максимално могућу губитак (loss).

Минимакс за појединачне одлуке уреди

Минимакс у лице неизвесности уреди

Минимакс теорија је продужена до одлуке где не постоји други играч, али где последице одлука зависе од непознатих чињеница. На пример, одлучивање за изгледе трошкова минерала који ће бити узалудни уколико минерали не постоје, али ће донети значајно велике награде ако су присутни. Један приступ је да се ово посматра као игра против природе, (погледај потез природе (move by nature)), и користећи сличан начин размишљања као Марфијев закон, користи приступ који минимизује максимални очекивани губитак, користећи исте технике као и у два играча, нулто- сума игара.

Поред тога, expectiminimax tree су развијени, за игре за два играча у којима је вероватноћа (на пример, коцкице) је чинилац.

Минимакс критеријум у теорији статистичког одлучивања уреди

У класичној статистичкој теорији доношења (decision theory), имамо процењивач (еstimator) $\delta$ који се користи за процену параметра (parameter) <матх> \ тхета \ у \ тхета </ матх >. Такође претпостављамо функцију ризика (risk function) $R(\theta ,\delta )$ , најчешће је наведена као интеграл једне функције губитка (loss function). У том оквиру, ${\tilde {\delta }}$ зове се 'Минимакс' ако задовољава : $\sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\sup _{\theta }R(\theta ,\delta ).$

Алтернативни критеријум у доношењу теоријског оквира је Бајесов процењивач у присуству пре дистрибуције $\Pi$ . Процењивач је Бајесов ако минимизира просечан ризик: : $\int _{\Theta }R(\theta ,\delta )\,d\Pi (\theta ).$

Теорија доношења одлука базирана на не-вероватноћи уреди

Кључна карактеристика минимаксној одлучивања је постојање не-вероватноће: за разлику од одлука које користе очекивану вредност или Очекивану услужност, она не прави претпоставке о вероватноће различитих исхода, само сценарио анализе шта су могући исходи. Стога је robust промена у претпоставкама, као што ове друге технике доношења одлука нису. Разне екстензије овог приступа не-вероватноће постоје, посебно Минимакс жаљење и Инфо-јаз теорија одлука.

Даље, Минимакс захтева само редно мерење (да исходи могу бити упоредиви и рангирани), а не интервал“ мерења (да исходи укључују "колико боље или глошије"), и враћа оригиналне податке, користећи само узорне исходе : закључак о минимакс анализи је: "ово је стратегија Минимакс, где је најгори случај (исход), мање лош од било које друге стратегије". Упоређујући са очекиваном вредношћу анализе, чији је закључак облика: ". Ово стратегија приноси E(X)=n." Минимакс тако може да се користи на редним података, а може бити транспарентнији.

Maximin у филозофији уреди

У филозофији, термин "maximin" је често кориштен у контексту John Rawls's A Theory of Justice, где он реферише на (Rawls (1971, pp. 152)) у контексту различитих принципа. Rawls је дефинисао овај принцип као корак који заузима социјалне и економске неуједначности морају да се организују. Другим речима, неуникатна дистрибуција се може користити када maxiмизирано the minимални. Бенефити онима који имају најмање алокације благостања додељивања ресурса. (Који он реферисе као "примарна добра").^[5]^[6]

Види још уреди

Референце уреди

^ Osborne, Martin J., and Ariel Rubinstein. A Course in Game Theory. Cambridge, MA: MIT, 1994. Print.
^ Von Neumann, J: Zur Theorie der Gesellschaftsspiele Math. Annalen. 100 (1928) 295-320
^ John L Casti (1996). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. стр. 19. ISBN 978-0-471-00261-1.
^ Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd изд.), Upper Saddle River, New Jersey: Prentice Hall, стр. 163—171, ISBN 0-13-790395-2
^ Arrow, "Some Ordinalist-Utilitarian Notes on Rawls's Theory of Justice, Journal of Philosophy 70, 9 (May 1973). pp. 245-263.
^ Harsanyi, "Can the Maximin Principle Serve as a Basis for Morality? a Critique of John Rawls's Theory, American Political Science Review 69, 2 (June 1975). pp. 594-606.

Литература уреди

John L Casti (1996). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. стр. 19. ISBN 978-0-471-00261-1.

Спољашње везе уреди

Hazewinkel Michiel, ур. (2001). „Minimax principle”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104.
A visualization applet
"Maximin principle" from A Dictionary of Philosophical Terms and Names.
Play a betting-and-bluffing game against a mixed minimax strategy
[1] The Dictionary of Algorithms and Data Structures entry for minimax.
Minimax Архивирано на сајту Wayback Machine (24. март 2015) (with or without alpha-beta pruning) algorithm visualization — game tree solving (Java Applet), for balance or off-balance trees.
CLISP minimax game. (in Spanish)
Maximin Strategy from Game Theory
Minimax Tutorial with a Numerical Solution Platform

[Osborne-1] Osborne, Martin J., and Ariel Rubinstein. A Course in Game Theory. Cambridge, MA: MIT, 1994. Print.

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

[Casti-3] John L Casti (1996). Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience. стр. 19. ISBN 978-0-471-00261-1.

[4] Russell, Stuart J.; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd изд.), Upper Saddle River, New Jersey: Prentice Hall, стр. 163—171, ISBN 0-13-790395-2

[5] Arrow, "Some Ordinalist-Utilitarian Notes on Rawls's Theory of Justice, Journal of Philosophy 70, 9 (May 1973). pp. 245-263.

[6] Harsanyi, "Can the Maximin Principle Serve as a Basis for Morality? a Critique of John Rawls's Theory, American Political Science Review 69, 2 (June 1975). pp. 594-606.

[1]

[2]

[3]

[4]

[5]

[6]