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

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

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

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

Стања минимакс теореме

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

Ова теорема је прво објављена 1928 године. од John von Neumann, који је написао "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".

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

Пример 

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

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

Минимакс алгоритам је рекурзивни алгоритам за одабир следећег потеза у 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)

Минимакс третира два играча (максимизирањем играча и мининизирањем истог) подељено у два кода. На основу запажања да , минимакс може често да се упрости у негамакс(negamax) алгоритам.

Пример 

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

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

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

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

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

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

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

Алтернативни критеријум у доношењу теоријског оквира је Бајесов процењивач у присуству пре дистрибуције . Процењивач је Бајесов ако минимизира просечан ризик: : 

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

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

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

 Maximin у филозофији 

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

Види још 
 
 Alpha-beta pruning
 Claude Elwood Shannon
 Computer chess
 Expectiminimax
 Horizon effect
 Minimax Condorcet
 Minimax regret
 Negamax
 Negascout
 Sion's minimax theorem
 Transposition table
 Wald's maximin model

Референце

Литература

Спољашње везе 
 
 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 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

Графовски алгоритми
Оптимизациони алгоритми и методи
Алгоритми претраживања
Теорија игара
Теорија одлучивања
Теореме у дискретној математици
Минимакс је правило одлука који се користи у теорији одлучивања , теорији игара , статистици и филозофији за минимизирање могућих губитака у најгорим случајевима( највећи губитак ) . Алтернативно , може се посматрати као максимизирање минималне добити . Првобитно је формулисан за теорију нулте-суме два играча , који покрива оба случаја где играчи узимају алтернативне потезе и оне где чине симултане потезе , такође је проширена на више комплексних игара и na опште одлучивање у присуству неизвесности . Теорија игара У теорији симултаних игара , стратегија Минимакс је мешовита стратегија која је део решења до нултог збира игре . У нулта-сума игри , Минимакс решење је исто као и Неш еквилибријум . Минимакс теорема Стања минимакс теореме За сваке две особе , нулта-сума игра са коначно много стратегија , где постоји вредност V и мешана стратегија за сваког играча , као ( а ) С обзиром на стратегијуиграча , најбоља исплата за играчаје V , и ( б ) С обзиром на стратегијуиграча , најбоља исплата за играчаје -V . Еквивалентно , стратегија играчаму гарантује исплату од В без обзира на стратегију играча и слично играчможе себи гарантовати исплату од -В . Име Минимакс настаје јер сваки играч смањује максималну могућу зараду за друге - јер је игра са нултом сумом , он такође смањује своју максималну губитак ( тј. максимализује свој минимални губитак ) . Ова теорема је прво објављенагодине. од John von Neumann , који је написао " 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 " . Погледати Sion's minimax theorem и Parthasarathy's theorem за генерализацију ; Такође погледати example of a game without a value . Пример У овом примеру је игра нулта-сума , где A и B праве симултане потезе , илустујући минимакс решења . Претпоставимо да сваки играч има три могућа потеза и погледати матрицу исплате за A приказану са десне стране . Претпоставимо да је матрица исплате за B иста матрица са обрнутим знацима ( тј. ако су избори А1 и В1 онда B плаћаA ) . Онда , минимаксов избор за A је А2 како је тада најгори могући резултат платити док једноставни минимаксов избор за B је B2 и најгори могући резултат тада је да се не плати ништа . Наиме , ова ситуација није стабилна , јер ако B верује да ће A изабрати А2 онда ће B изабрати В1 да би освојио онда ако A верује да ће B изабрати B1 онда ће A изабрати A1 да освоји и онда ће B изабрати B2 ; и потенцијално ће оба играча схватити тежину самог избора . Самим тим нам је потребна стабилнија стратегија . Неки избори су доминантнији од других и могу бити елиминисани : A неће изабрати A3 како ни A1 ни A2 неће имати боље резултате , без обзира на избор који ће направити B ; B неће изабрати B3 како ће неке мешавине од В1 и В2 направити боље резултате , без обзира шта A изабере . A може да ибегне да направи очекивану исплату већу од3 бирајући А1 са вероватноћом6 и A2 са вероватноћом6 : Очекивана исплата за A ће бити( 1 /6 ) -1*( 5 /6 ) =-1 /3 у случају да B изабере B1 и( 1 /6 ) +0*( 5 /6 ) =-1 /3 у случају да B изабере B2. Слично , B може да осигура очекиван добитак од најмање3 , без обзира шта A изабере , користећи случајну стратегију одабира В1 са вероватноћом3 и B2 са вероватноћом3 . Ове мешане стратегије су сада стабилне и не могу се побољшати . Максмин Често , у теорији игара , максмин је другачије од минимакс . Минимакс се користи у нулта-сума играма да означи минимизирање противникове маскималне зараде . У нултим-сумама , ово је идентично са минимизовањем максималног губитка , и максимизовањем минималног добитка . " Максмин " је термин који се обично користи за ненулта-сума игре при објашњавању где се максимизује минимални добитак . У ненулта-сума играма , ово није генерално исто као минимизовање противниковог максималног добитка , као ни Неш еквилибријум стратегија . Комбинаторнна теорија игара У комбинаторној теорији игара ( combinatorial game theory ) , постоји минимакс алгоритам као ререшење игара . A једноставна верзија минимакс алгоритма , наведена у наставку , бавећи се играма као што су икс-окс , где сваки играч може да победи , изгуби , или изједначи . Ако играч A може да победи у једном потезу , његов најбољи потез је тај победнички потез . Ако играч В зна да ће тај један потез одвести до ситуације где А може да победи у једном потезу , док ће други потез одвести до тога да А може , у најбољем случају , да изједначи , онда ће најбољи потез играча В бити да одведе до изједнчења . Касније у игри , лако је видети који је " најбољи " покрет . Минимакс алгоритам помаже у проналаску најбољег потеза , гледањем уназад од почетка . У сваком кораку претпостављамо да је играч А покушао да максимизује шансе победе А , док на следећем кругу уграч Б покушава да минимизује шансе да А победи( тј. како би се играчу В повећала шанса да победи ) . Минимакс алгоритам са алтернативним покретима Минимакс алгоритам је рекурзивни алгоритам за одабир следећег потеза у 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 ( који побеђује Гари Каспаров ) гледао је унапредслојева , затим примењује хеуристике евалуационе функције . Алгоритам се може посматрати као истраживање чворова ( 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 <=then -- позитивне вредности су добре за максимизирање играча -- негативне вредности су добре за минимизирање играча return objective_value( node ) end -- максимизирање играча је ( +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 =or node is a terminal node return the heuristic value of node if maximizingPlayer bestValue \ := -∞ for each child of node val \ := minimax( child , depth - FALSE ) ) bestValue \ := max( bestValue , val ) ; return bestValue else bestValue \ := +∞ for each child of node val \ := minimax( child , depth - TRUE ) ) bestValue \ := min( bestValue , val ) ; return bestValue ( * Initial call for maximizing player * ) minimax( origin , depth , TRUE ) Минимакс третира два играча ( максимизирањем играча и мининизирањем истог ) подељено у два кода . На основу запажања да , минимакс може често да се упрости у негамакс( negamax ) алгоритам . Пример Претпоставимо да игра почиње , и да максимум два потеза по играчуу је по кругу . Алгоритам генерише дрво ( game tree ) надесно , где кругови престављају покрете играча који су покренули алгоритам ( maximizing player ) , и квадратна репрезентација покрета противника ( minimizing player ) . Из разлога лимитацијенад рачунарских ресурса , објашњено изнад , дрво је лимитирано на look-aheadпотеза . Алгоритам процењује сваки лист чвор користећи функцију хеуристичке евалуације , прибављањем добијених вредности . Потези где побеђују максимизирање играча су додељени са позитивном бесконачношћу , док су потези који доводе до победе на минимизирање играча се додељује са негативном бесконачношћу . На трећем нивоу , алгоритам ће изабрати , за сваки чвор , „ најмањи “ од дете чвор вредности и доделити га том истом чвору ( нпр . Чвор на левој страни ће изабрати миниму између „ 10 “ и „ +∞ " , дакле доделиће себи вредост „ 10 “ ) . Наредни корак , на другом новоу , састоји се од избора за сваки чвор у највећи од child node чвора вредности . Поново , вредности су додељене сваком родитељ чвор . Алгоритам се даље наставља оцењивањем највеће и најмање вредности од деце чворова наизменично док не достигне корен чвор где се бира потез са највећом вредношћу ( представљени на слици са плавом стрелицом ) . То је потез који играч треба да у циљу минимизирања ' на максимално могућу губитак ( loss ) . Минимакс за појединачне одлуке Минимакс у лице неизвесности Минимакс теорија је продужена до одлуке где не постоји други играч , али где последице одлука зависе од непознатих чињеница . На пример , одлучивање за изгледе трошкова минерала који ће бити узалудни уколико минерали не постоје , али ће донети значајно велике награде ако су присутни . Један приступ је да се ово посматра као игра против природе , ( погледај потез природе ( move by nature ) ) , и користећи сличан начин размишљања као Марфијев закон , користи приступ који минимизује максимални очекивани губитак , користећи исте технике као и у два играча , нулто- сума игара . Поред тога , expectiminimax tree су развијени , за игре за два играча у којима је вероватноћа ( на пример , коцкице ) је чинилац . Минимакс критеријум у теорији статистичког одлучивања У класичној статистичкој теорији доношења ( decision theory ) , имамо процењивач ( еstimator ) који се користи за процену параметра ( parameter ) <матх> \ тхета \ у \ тхета < / матх > . Такође претпостављамо функцију ризика ( risk function ) , најчешће је наведена као интеграл једне функције губитка ( loss function ) . У том оквиру , зове се ' Минимакс ако задовољава \ : Алтернативни критеријум у доношењу теоријског оквира је Бајесов процењивач у присуству пре дистрибуције \ . Процењивач је Бајесов ако минимизира просечан ризик : \ : Теорија доношења одлука базирана на не-вероватноћи Кључна карактеристика минимаксној одлучивања је постојање не-вероватноће : за разлику од одлука које користе очекивану вредност или Очекивану услужност , она не прави претпоставке о вероватноће различитих исхода , само сценарио анализе шта су могући исходи . Стога је robust промена у претпоставкама , као што ове друге технике доношења одлука нису . Разне екстензије овог приступа не-вероватноће постоје , посебно Минимакс жаљење и Инфо-јаз теорија одлука . Даље , Минимакс захтева само редно мерење ( да исходи могу бити упоредиви и рангирани ) , а не интервал “ мерења ( да исходи укључују " колико боље или глошије " ) , и враћа оригиналне податке , користећи само узорне исходе \ : закључак о минимакс анализи је : " ово је стратегија Минимакс , где је најгори случај ( исход ) , мање лош од било које друге стратегије " . Упоређујући са очекиваном вредношћу анализе , чији је закључак облика : " . Ово стратегија приноси E( X ) =n . " Минимакс тако може да се користи на редним података , а може бити транспарентнији . Maximin у филозофији У филозофији , термин " maximin " је често кориштен у контексту John Rawls's A Theory of Justice , где он реферише на ( Rawls pp. у контексту различитих принципа . Rawls је дефинисао овај принцип као корак који заузима социјалне и економске неуједначности морају да се организују . Другим речима , неуникатна дистрибуција се може користити када maxiмизирано the min''' имални . Бенефити онима који имају најмање алокације благостања додељивања ресурса . ( Који он реферисе као " примарна добра " ) . Види још Alpha-beta pruning Claude Elwood Shannon Computer chess Expectiminimax Horizon effect Minimax Condorcet Minimax regret Negamax Negascout Sion's minimax theorem Transposition table Wald's maximin model Референце Литература Спољашње везе 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 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 Графовски алгоритми Оптимизациони алгоритми и методи Алгоритми претраживања Теорија игара Теорија одлучивања Теореме у дискретној математици