Մինիմաքս

Այս հոդվածը կարող է վիքիֆիկացման կարիք ունենալ Վիքիպեդիայի որակի չափանիշներին համապատասխանելու համար։ Դուք կարող եք օգնել հոդվածի բարելավմանը՝ ավելացնելով համապատասխան ներքին հղումներ և շտկելով բաժինների դասավորությունը, ինչպես նաև վիքիչափանիշներին համապատասխան այլ գործողություններ կատարելով։

Մինիմաքս (երբեմն մինմաքս) որոշումներ ընդունելու կանոն է, որը օգտագործվում է որոշումների թեորեմում, խաղային թեորեմում, վիճակագրությունում և փիլիսոփայությունում, հնարավոր կորուստը, վատագույն դեպքում՝ մաքսիմալ կորուստը, քչացնելու համար։ Որպես այլընտրանք, այն կարող է մաքսիմալացնել մինիմումի ստացումը (մաքսիմին)։ Սկզբնապես այն նախատեսված էր երկու խաղացողների զրո-գումար խաղային թեորեմ, լուսաբանելով երկու դեպքերն էլ, երբ խաղացողն ինքն է ընտրում այլընտրանքային շարժումներ և դրանց միջոցով ստեղծում միաժամանակյա շարժումներ։ Այն նաև կիրառվում է ավելի շատ բաղադրյալ խաղերի և, անորոշության առկայությամբ, գլխավոր որոշումների ընդունման համար։

Միաժամանակյա խաղերի խաղային թեորեմում, մինիմաքսի ռազմավարությունը խառը ռազմավարություն է, որը զրո-գումարային խաղերի լուծման մասերից է։ Զրո-գումարային խաղերում, մինիմաքսի խնդիրը նույնպիսին է, ինչպես Նեշի հավասարակշռությանը։

Մինիմաքս խաղային թեորեմը^[1]

Ամեն երկու հոգու համար, զրո-գումարային խաղը ռազմավարության վերջնական քանակությամբ, գոյություն ունի V արժեքը և խառը ռազմավարություն յուրաքանչյուր խաղացողի համար, ինչպիսին են՝

(a) Տրված է խաղացողին 2-րդ ռազմավարության, լավագույն հնարավոր հետադարձը 1-ին խաղացողի համար V-է,

(b) Տրված է 1-ին ռազմավարությունը, լավագույն հնարավոր հետադարձը 2-րդ խաղացողի համար −V է։

Հավասարապես, առաջին խացաղողի ռազմավարությունը երաշխավորում է հաղթանակ V-ով անկախ երկրորդ խաղացողից, և նույնապես երկրորդ խաղացողը կարող է երաշխավորել իր հաղթանակը −V-ով։ Մինիմաքս անունը ծագում է քանի որ յուրաքանչյուր խաղացող մինիմալի է հասցնում դիմացինի մաքսիմում ելքի հնարավորությունը, և քանի որ խաղը զրո-գումարային է, նա նվազեցնում է իր սեփական մաքսիմում կորուստը (այսինքն մաքսիմալացնում է իր մինիմալ ելքը)։

Այս թեորեմը հայտնագործվել է, Ջոն վոն Նյուման-ի կողմից^[2], ով հայտնի է իր "Ինչքան հեռուն, որ ես կարող եմ տեսնել, չի կարող լինել խաղերի թեորեմ, առանց այս թեորեմի։ Ես կարծում եմ, որ որինչ չարժեն մինչև Մինիմաքսի թեորեմը լույս տեսածները" խոսքերով.^[3]

Տե՛ս Սիոնի մինիմաքսի թեորեմը և Parthasarathy-ի թեորեմը ընդհանրացման համար; տե՛ս նաև առանց արժեքի մի խաղի օրինակ.

Սա զրո-գումարային խաղի օրինակ է, որտեղ A և B կատարում են համաշարժ գործողություններ՝ լուսաբանելով մինիմաքսի լուծումները։ Ենթադրենք յուրաքանչյուր խաղացող ունի երեք ընտրություն և որոշում է ելքային մատրիցը-ը A -ի համար և ցուցադրում է այն աջից։ Ենթադրենք որ, ելքային մատրիքսը B-ի համար նույն մատրիքսն է արտացոլվող սիմվոլի հետ միասին (այսինքն եթե ընտրանքներն են A1-ը և B1-ը ուրեմնք B-ն A-ին տալիս է 3 արժեքը)։ Հետո, մինիմաքս ընտրությունը A-ի համար A2-ն է, քանի որ հնարավոր վատագույն արդյունքը, հետո ստիպված է տալ 1, մինչդեռ պարզագույն մինիմաքս ընտրանքը B-ի համար B2-է, որը հետադարձում հնարավոր վատագույն արդյունքը չի ունենում։ Այնուամենայնիվ, այս լուծումը ստաբիլ չէ, քանի որ եթե B հավատում է, որ A-ն կընտրի A2-ը, ապա B-ն կընտրի B1-ին ստանալու համար 1 արժեքը; հետո եթե A հավատում է, որ B-ն կընտրի B1-ին, ապա A-ն կընտրի A1-ին ստանալու համար 3 արժեքը; և հետո B կընտրի B2-ին; և վերջնական արդյունքում խաղացողներից երկուսնել կգիտակցեն որոշում կայացնելու դժվարությունը։ Այսպիսով ավելի ստաբիլ ռազմավարությունն է անհրաժեշտ։

Որոշ ընտրություններ գերակշռում են մյուսների կողմից և կարող են վերացվել։ A չի ընտրի A3-ին մինչև կամ A1-ը, կամ A2-ը, ավելի լավ արդյունք կտան, անկախ B-ի ընտրանքից; B-ն չի ընտրի B3-ին մինչ B1-ը և B2-ը չարտադրեն ավելի լավ արդյունք, անկախ A-ի ընտրանքը։

A -ն կարող է խուսափել ավելի քան 1/3 դեպքերում սպասված ելքը որոշելուց, ընտրելով A1-ը 1/6 հավանականությամբ և A2-ը 5/6 հավանականությամբ, կապ չունի B-ի ընտրությունը։ Սպասված ելքը A -ի համար կլինի 3*(1/6), 1*(5/6)=-1/3 B-ի B1 ընտրության դեպքում և -2*(1/6)+0*(5/6)=-1/3՝ B2 ընտրության դեպքում։ Նմանապես B-ն կարող է ապահովել 1/3՝ սպասված ելքը, անկախ A -ից, օգտագործելով 1/3 հավանականությամբ B1-ի ընտրության և 2/3 հավանականությամբ B2-ի ընտրության պատահական ռազմավարություն։ Այս զուգակցված մինիմաքսի ռազմավարություններն այժմ ստաբիլ են և չեն կարող բարելավվել։

Հաճախ, խաղի տեսությունում, մաքսիմինը մինիմաքսից տարբեր է։ Մինիմաքսն օգտագործվում է զրո-գումարային խաղերում, որ նվազագույնի հասցնի մրցակցի առավելագույն անսպասելի ելքը։ Զրո-գումարային խաղում սա նույնն է. այսինքն նվազագույնի է հասցվում սեփական առավելագույն կորուստը, և առավելագույնի՝ սեփական նվազագույն շահը։

"Մաքսիմին" տերմինը լայնորեն կիրառվում է ոչ զրո-գումարային խաղերի ռազմավարության նկարագրման համար, որը առավելագույնի է հասցնում սեփական նվազագույն ելքը։ Ոչ զրո-գումարային խաղերում, սա ընդհանուր առմամբ մրցակցի առավելագույն կորուստը նվազագույնի հասցնելը չէ, ոչ էլ Նեշի հավասարակշռությունն է։

Ստորև բերված Մինիմաքս ալգորիթմի պարզ տարբերակը, համագործակցում է տիկ-տակ-տո խաղերի հետ, որտեղ ամեն խաղացող կարող է հաղթել, պարտվել կամ ոչ ոքի խաղալ։ Եթե A խաղացողը կարող է հաղթել մեկ քայլով, իր լավագույն քայլը կլինի հենց այդ՝ հաղթական քայլը։ Եթե B խաղացողը գիտի, որ այդ մեկ քայլը կհանգեցնի այն իրավիճակին, որտեղ A խաղացողը կարող է հաղթել մեկ քայլով, երբ այլ քայլը կհանգեցնի իրավիճակին, երբ A խաղը կարող է, լավագույն դեպքում, ոչ ոքի խաղալ, ապա B-ի լավագույն քայլը կլինի այդ ոչ ոքիյին հանգեցնող քայլը։ Ավելի ուշ խաղում, հեշտ է նկատել, թե որն է "լավագույն" քայլը։ Մինիմաքս ալգորիթմը օգնում է գտնել լավագույն քայլը, աշխատելով հետընթաց՝ խաղի վերջից սկիզբ։ Յուրաքանչյուր քայլում դա ենթադրում է, որ A խաղացողը փորձում է առավելագույնի հասցնել A-ի հաղթանակի շանսերը, երբ հաջորդ քայլում B խաղացողը փորձում է նվազագույնի հասցնել A-ի հաղթանակի շանսերը (այսինքն, առավելագույնի հասցնելով B-ի հաղթանակի շանսերը)։

Մինիմաքս ալգորիթմը^[4] ռեկուրսիվ ալգորիթմ է, n-խաղացողներով, սովորաբար 2 խաղացողներով, խաղում հաջորդ քայլը ընտրելու համար։ Արժեքը կապված է խաղի յուրաքանչյուր դիրքից կամ փուլից։ Այս արժեքը հաշվարկվում է դիրքի գնահատման ֆունկցիայի միջոցով, և դա նշում է, թե որքան լավ կլինի խաղացողի համար հասնել այդ դիրքին։ Հետո խաղացողը կատարում է քայլը, որը մրցակցի հնարավոր հաջորդ քայլերի արդյունքում մեծացնում է դիրքի նվազագույն արժեքը։ Եթե A-ի հերթն է քայլ կատարելու, A-ն իր յուրաքանչյուր օրինական քայլի արժեքը ցույց կտա։

Հնարավոր առանձնացման մեթոդը կայանում է A-ի հաղթանակը +1-ով և B-ինը −1-ով նշանակելու մեջ. Սա հանգեցնում է համակցային խաղի թեորեմի, որը հայտնագործել է Ջոն Հորթոն Քոնվեյը։ Այլընտրանքայինը մի կանոն է օգտագործում, որ եթե քայլի արդյունքը A-ի ուղղակի հաղթանակի է բերում, դա նշանակվում է +∞ ,և եթե դա ուղղակի հաղթանակի է բերում B-ի համար՝ -∞։ Արժեքը, մինչև A-ի այլ ցանկացած քայլի արժեք նվազագույնն է B-ի հնարավոր պատասխանների յուրաքանչյուր արժեքից. Այս պատճառով է, որ A-ն անվանվում է մաքսիմումին ձգտող խաղացող և B-ն անվանվում է մինիմումին ձգտող խաղացող, այստեղից էլ Մինիմաքս ալգորիթմ անունը։ Վերևի ալգորիթմը ցանկացած դիրքի համար կնշանակի դրական կամ բացասական անվերջությունների արժեքը, քանի որ յուրաքանչյուր դիրքի արժեքը կլինի ինչ-որ վերջնական հաղթանակի կամ պարտության արժեք։ Համակցված խաղերի, ինչպիսին է շախմատը, ամենավերջում հիմնականում հենց սա է միակ հնարավորը, քանի որ սա հաշվարկորեն իրագորժելի չէ, որքան էլ այնքան հեռու նայենք, որ խաղն ավարտվի, բցառությամբ դեպի վերջ, և դիրքերի փոխարեն տրված են վերջավոր արժեքներ, որոնք գնահատում են հավատի այն աստիճանը, որ կհանգեցնեն մեկ կամ մյուս խաղացողի հաղթանակին։

Սա կարող է շարունակվել, եթե մենք կարողանանք մուտքագրենք էվրիստիկյան գնահատման ֆունկցիան, որը արժեքներ կտա ոչ վերջնական խաղային փուլում առանց հաշվի առնելու բոլոր հնարավոր ամբողջական հերթականությունները։ Այսպիսով մենք կարող ենք սահմանապակել մինիմաքս ալգորիթմը, քչացնելով դիտարկվող քայլերի քանակը։ Այս քանակը կոչվում է "հայացք առաջ", և չափվում է "փլայերով": Օրինակ, շախմատային համակարգիչ Deep Blue-ն (որը հաղթեց Գարրի Կասպարովին) նախատեսված էր նվազագույնը 12 փլայերով, հետո կիրառվեց էվրիստիկյան գնահատման ֆունկցիայով։

Ալգորիթմը կարող է մտածված լինել, քանի որ ուսումնասիրել է խաղային ծառի հանգույցը. Ծառի էֆֆեկտիվ ճյուղավորվող գործոնը յուրանքաչյուր հանգույցի ժառանգողների միջին թիվն է (այսինքն, մի դիրքում թույլատրվող քայլերի միջին թիվն է). Ուսումնասիրված հանգույցների քանակը սովորաբար, փլայերի քանակի հետ համապատասխանաբար, աճում է էականորեն ( դա ավելի քիչ է, քան գնահատման էական հարկադրված քայլերը կամ կրկնված դիրքերը)։ Խաղի վերլուծության համար ուսումնասիրվող հանգույցների քանակը մոտավորապես է, ճյուղավորման գործոնը բարձրացված և հասցված է փլայերի քանակին։ Ուստի դա անպետք է, այնպիսի խաղերն, ինչպիսին է շախմատը, որ օգտագործում է մինիմաքս ալգորիթմը, ամբողջականորեն վերլուծելու համար։

Պատահական մինիմաքս ալգորիթմի ներկայացումը կարող է կտրուկ բարելավված լինել, առանց արդյունքի վրա ազդելու, օգտագործելով ալֆա-բետա բաժանումը. Նաև այլ էվրիստիկյան բաժանման մեթոդները կարող են օգտագործվախ լինել, բայց նրանցից ոչ բոլորն են երաշխավորված, որ նույն արդյունքը կտան, ինչ չբաժանված փնտրումը։ Պատահական մինիմաքս ալգորիթմը կարող է առօրեապես ձևափոխված լինել լրացուցիչ լրիվ վերադարձի Գլխավոր փոփոխություն մինիմաքսի նշանների երկայնքով։

function minimax(node,depth)
   if depth <= 0 then
      -- positive values are good for the maximizing player
      -- negative values are good for the minimizing player
      return objective_value(node)
   end
   -- maximizing player is (+1)
   -- minimizing player is (-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

Մինիմաքս ալգորիթմի Նեգամաքս տեսակի համար ծածկաբառը (օգտագործվում է էվրիստիկյան գնահատումը, տրված մակարդակում ավարտվելու համար) բերված է ստորև։

Կոդը հիմնված է այս հետազոտությունների վրա՝ ${\displaystyle \max(a,b)=-\min(-a,-b)}$։ Սա վերացնում է այն ալգորիթմի անհրաժեշտությունը, որը դիտարկում էր երկու խաղացողներին առանձին - առանձին, սակայն չի կարող օգտագործվել այն խաղերին, որտեղ խաղացողը կարող է ունենալ հաջորդական երկու քայլ։

function integer minimax(node, depth)
if node is a terminal node or depth <= 0։
return the heuristic value of node
α = -∞
for child in node։ # evaluation is identical for both players 
α = max(α, -minimax(child, depth-1))
return α

Ենթադրենք խաղացվող խաղը, ունի առավելագույնը միայն երկու հնարավոր քայլ, յուրաքանչյուր խաղացողի համար, յուրաքանչյուր հերթի ժամանակ։ Ալգորիթմը աջ մասում առաջացնում է ծառ, որտեղ շրջանները ցույց են տալիս այն խաղացողի քայլերը, ով կառավարում է ալգորիթմը (մաքսիմայզի խաղացող), և քառակուսիները ցույց են տալիս մրցակցի քայլերը (մինիմայզի խաղացող)։ Հաշվարկային ռեսուրսների սահմանափակ լինելու պատճառով, ինչպես բացատրված էր վերևում, ծառը սահմանափակված է հայացք դեպի առաջի 4 քայլերով։

Ալգորիթմը գնահատում է յուրաքանչյուր հագույց օգտագործելով էվրիստիկյան գնահատման ֆունկցիան, ստանալով ցուցադրված արժեքները։ Այն քայլերը, որտեղ մաքսիմայզի խաղացողը հաղթում է, նշանակվում են +∞-ով, միաժամանակ այն քայլերը, որոնք հանգեցնում են մինիմայզի խաղացողի հաղթանակին, նշանակվում են -∞։ 3-րդ մակարդակում, ալգորիթմը յուրաքանչյուր հանգույցի համար ընտրում է ժառանգորդ հանգույցների արժեքներից փոքրագույնը, և նշանակում դա նույն հանգույցին (այսինքն ձախ կողմի հանգույցը կընտրի նվազագույնը "10"-ի և "+∞" միջև, այսպիսով ինքն իրեն վերագրելով "10" արժեքը)։ Հաջորդ քայլում՝ 2-րդ մակարդակում, յուրաքանչյուր հանգույցի համար ընտրվում է ժառանգորդ հանգույցների արժեքներից մեծագույնը։ Եվս մեկ անգամ արժեքները նշանակվում են յուրաքանչյուրի ծնող հանգույցից։ Ալգորիթմը շարունակում է ժառանգորդ հանգուցների հաջորդաբար մեծագույն և փոքրագույն արժեքների գնահատումը, մինչը այն հասնում է արմատային հանգույցին, որտեղ նա ընտրում է մեծագույն արժեքով քայլը (ներկայացված է կապույտ գծով)։ Սա այն քայլն է, որ պետք է խաղացողն անի, որպեսզի նվազեցնի առավելագույն հնարավոր կորուստը։

Մինիմաքսի տեսությունը ներառում է տարբերակներ, որտեղ ոչ մի խաղացող չկա, բայց որտեղ որոշումների հետևանքներւ կախված են անհայտ փաստերից։ Օրինակ՝ որոշումը, հանքանյութի որոնումը կհանգեցնի ապարդյուն ծախսերի, եթե նրանք ներկայացված չեն, բայց կբերի գերշահույթ, եթե նրանք ներկայացված լինեն։ Մի մոտեցումը կնշանակի, որ սա խաղ է բնության դեմ (տես շարժվիր բնությամբ), և օգտագործելով նմանատիպ մտածողություն, ինչպես Մերֆիյի օրենքն է, և այսպիսի մոտեցումը կհանգեցնի առավելագույն սպասվող կորստի նվազման, օգտագործելով նույն տեխնիկան, որն օգտագործվում էր երկու խաղացողների համար զրո-գումարային խաղերում։

Դասական վիճակագրական որոշումների տեսությունում, մենք ունենք մեկ գնահատող ${\displaystyle \delta }$, որն օգտագործվում է ${\displaystyle \theta \in \Theta }$ պարամետրը հաշվելու համար։ Մենք հաշվում ենք ռիսկի գործոնը նույնպես ${\displaystyle R(\theta ,\delta )}$, սովորաբար հաշվարկված որպես կորստի գործոնի ինտեգրալ։ Այս շրջանակներում, ${\displaystyle {\tilde {\delta }}}$-ն անվանվում է մինիմաքս եթե դա բավարարում է։

${\displaystyle \sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\sup _{\theta }R(\theta ,\delta ).}$

Որոշումների տեսության շրջանակներում այլընտրանքային չախանիշ է Բայեսի գնահատողը՝ նախնական բաշխման ${\displaystyle \Pi }$ պարագայում։ Գնահատողը կոչվում է Բեյեսի, եթե դա փոքրացնում է ռիսկի միջին մակարդակը։

${\displaystyle \int _{\Theta }R(\theta ,\delta )\,d\Pi (\theta ).}$

Մինիմաքսի որոշումների կայացման հիմնական հատկությունը ոչ հավանական լինելն է. ի հակադրություն, այն տարբերակին, որն օգտագործում էր սպասված արժեքը կամ սպասվաժ օգտակարությունը, դա ոչ մի ենթադրություններ չի կազմում տարբեր ելքերի մասին, ընդամենը վերլուծություն է հնարավոր ելքերի մասին։ Այսպիսով սա It is thus դիմացկուն է ենթադրվող փոփոխությունների նկատմամբ, ի տարբերություն այլ որոշումների տեխնիկաների։

Բացի այդ, մինիմաքսը պահանջում է միայն հերթական չափում (որ ելքերը համեմատված և տեղակարգավորված լինեն), անդադար չափումներ, ( որ ելքերը ներառում են "որքան լավ կամ վատ"), և վերադարձնում են հերթական տվյալները, օգտագործելով միայն մոդելավորված ելքերը. մինիմաքսի վերլուծության եզրակացությունն է. " այս մարտավարությունը մինիմաքս է, քանի որ վատագույն տարբերակն (ելքն) է, որն ավելի քիչ վատն է, քան այլ ցանկացած մարտավարությունը"։ Համեմատելով սպասված արժեքների վերլուծության հետ, որի եզրահանգումն է. "այս մարտավարության արդյունքն է E(X)=n." Այսպիսով մինիմաքսը կարող է օգտագործված լինել հերթական տվյալներում, և կարող է լինել ավելի պարզ։

Փիլիսոփայությունում "մաքսիմին" տերմինը հաճախ օգտագործվում է Ջոն Ռոուլզի Արդարության տեսություն-ում, որտեղ նա հղում է կատարում դրան (Ռոուլզ (1971, էջ. 152)) Սկզբունքների տարբերությունում։ Ռոուլզը հայտնաբերեց այս օրինաչափությունը որպես օրենք, ըստ որի սոցիալ և տնտեսական անհավասարությունները պետք է կազմակերպված լինեն այնպես, որ " դրանք պետք է լինեն մեծագույն օգուտը հասարակության ցածր խավի համար"։ Այլ կերպ ասած, անհավասար բաշխում կարող է լինել հենց այն ժամանակ, երբ դա մաքսիմալի է հասցնում մինիմում օգուտը նրանց, ովքեր ունեն ամենացածր տարանջատումը, բարեկեցության շնորհման գործում (որոնց նա համարում է "առաջնային ապրանքներ").^[5][6]

• A visualization applet
• "Maximin principle" from A Dictionary of Philosophical Terms and Names. Արխիվացված 2006-03-07 Wayback Machine
• 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) Արխիվացված 2009-03-10 Wayback Machine
• CLISP minimax - game. (in Spanish)
• Maximin Strategy from Game Theory Արխիվացված 2013-06-30 Wayback Machine