Minimax elv

A Wikipédiából, a szabad enciklopédiából

A minimax elv a döntéselméletben, a játékelméletben és a statisztikában alkalmazott döntési szabály, ami szerint azt a lehetőséget kell választani, ami minimalizálja a maximális veszteséget. Felfogható a minimális nyereség maximalizálásaként is.

A két játékosú zéró összegű játékokkal kezdődött, ami magába foglalta a két játékos szimultán döntéseit és a felváltva tett lépéseit is, de bonyolultabb esetekre is kiterjesztették.

A játékelméletben[szerkesztés | forrásszöveg szerkesztése]

A minimax elv egy kevert stratégia, ami része a zéró összegű játékok megoldásának. A zéró összegű játékokban a minimax elv megadja a nyeregpontot.

Definíció: Legyen A és B nem üres halmaz, f: A \times B \to \mathbb R adott függvény. Az (x_0,y_0) pont nyeregpont, ha minden x \in A-ra és minden y\in B-re f(x,y_0) \leq f(x_0,y_0) \leq f(x_0,y).

Neumann-tétel: Minden olyan kétszemélyes, zéró összegű játéknak van nyeregpontja, amiben véges sok elemi stratégia van. Azaz a legjobb kevert stratégiával az első játékos várható nyereségének maximuma egyenlő a második játékos várható veszteségének minimumával.

Neumann János[1] szerint nem érdemes játékelméletet csinálni a minimax tételnek is nevezett tétel nélkül.[2]

A tétel általánosításai Sion minimaxtétele és Parthasarathy tétele.

Neumann-tétel[szerkesztés | forrásszöveg szerkesztése]

Definíció: Egy vektor tetején a vektor legnagyobb koordinátáját értjük; a vektor alja a legkisebb koordinátája.

Neumann-tétel: Minden olyan kétszemélyes, zéró összegű játéknak van nyeregpontja, amiben véges sok elemi stratégia van. Azaz a legjobb kevert stratégiával az első játékos várható nyereségének maximuma egyenlő a második játékos várható veszteségének minimumával.

A tétel egy másik alakban: Jelölje A a játék kifizetési mátrixát. Az A oszlopai által feszített politópban levő elemek minimuma egyenlő az A sorai által feszített politópban levő elemek aljának minimumával.

Bizonyítás: a dualitástétel segítségével.

A dualitástétel alkalmazásában a primál feladat: keresünk minimális w-t, amihez van x \geq 0, ex=1, Ax \leq we, ahol e azt a vektort jelöli, aminek minden koordinátája 1. Ez megfelel a \min \{ w: -Ax+we \geq 0, x \geq 0, ex=1\} lineáris programnak.

A duál feladat: keresünk maximális z-t, amihez van ey=1, yA \geq ze. Ez megfelel a \max \{ z: y(-A)+ze \leq 0, y \geq 0, ey=1\} lineáris programnak.

Maximin[szerkesztés | forrásszöveg szerkesztése]

Sokszor előfordul a játékelméletben, hogy a maximin különbözik a minimaxtól. A zéró összegű játékok elméletében a minimax az ellenfél nyereségének minimalizálását jelöli, ami a zéró összegű játékok esetén a saját veszteség minimalizálásának, azaz a saját nyereség maximalizálásának felel meg.

A maximin a nem zéró összegű játékok esetén használatos stratégiát jelenti, ami maximalizálja a saját nyereséget. Ez általában nem egyezik az ellenfél nyereségének a minimumával, vagy a nyeregponti stratégiával.

Példa[szerkesztés | forrásszöveg szerkesztése]

B1 B2 B3
A1     +3     −2     +2
A2     −1      0     +4
A3     −4     −3     +1

A következő példa egy zéró összegű játék. A két játékos, A és B szimultán lép.

Tegyük fel, hogy a játék kifizetési mátrixa az A játékos számára a fenti mátrix, és a B játékos számára az előjelek fordítottak. Ekkor A minimax választása A2, mivel itt a legrosszabb esetben 1-et kell fizetni, és B minimax választása B2, mert ekkor a legrosszabb esetben nincs nyeremény.

Ez a megoldás nem stabil. Ha B azt hiszi, hogy A A2-t választja, akkor B1 mellett dönt. Ha A azt hiszi, hogy B B1 mellett dönt, akkor megjátssza A1-et. Ha B azt hiszi, hogy A A1-et játssza meg, akkor B2-t választja. A determinisztikus stratégia kiismerhető, ezért csak nem determinisztikus stratégia lehet stabil.

A stabil kevert stratégiák: A 1/6 valószínűséggel választja A1-et, és 5/6 valószínűséggel A2-t. B 1/3 valószínűséggel választja B1-et, és 2/3 valószínűséggel B2-t. Ezek a stratégiák stabilak, és nem javíthatók.

A minimax elv korlátai[szerkesztés | forrásszöveg szerkesztése]

A minimax elv nem mindig vezet mindkét fél számára optimális megoldáshoz. Erre példa a fogolydilemma.

A klasszikus fogolydilemmában a kifizetési mátrix:

Egyik tagad Egyik vall
Másik tagad Mindketten 6 hónapot kapnak Egyik szabad, másik 10 évet kap
Másik vall Egyik 10 évet kap, másik szabad Mindkettő 6 évet kap

Ha mindkét fogoly abszolút önző és egyetlen céljuk saját büntetésük minimalizálása, akkor mindkét fogoly vallani fog, és mindketten 6 év börtönt kapnak, pedig a kooperáció lenne a legjobb stratégia.

Kombinatorikus játékelmélet[szerkesztés | forrásszöveg szerkesztése]

A kombinatorikus játékelméletben a minimax a következő lépésekre vezet:

Az egyszerű változatban minden játékos nyerhet, veszíthet, vagy döntetlent érhet el, mint a tic-tac-toe-ban. Ez az amőba egy háromszor hármas táblán játszott változata, ahol a cél három jel elhelyezése egy sorban, oszlopban, vagy átlón.

Ha az A játékos egy lépéssel nyerhet, akkor a legjobb lépése a nyerő lépés. Ha a B játékos tudja, hogy az egyik lépése után A nyerhet, viszont egy másik lépése után legfeljebb döntetlent érhet el, akkor az utóbbit választja.

A játék folyamán mindig látható, hogy mi a legjobb lépés. A minimax algoritmus segít megtalálni ezt. Módszere a játék elemzése az utolsó, nyerő lépéstől a kezdőlépésig. Felteszi, hogy A minden lépésben maximalizálni akarja A nyerési esélyeit, míg B csökkenteni igyekszik azokat, ezzel próbálva növelni saját esélyeit a győzelemre.

Minimax algoritmus váltakozó lépéses játékokra[szerkesztés | forrásszöveg szerkesztése]

A(z) (heurisztikus) értékelő függvény az angol alapján van magyarítva, és nem biztos, hogy az elfogadott szakszóhasználtatot tükrözi.

Rekurzív algoritmus a következő lépés meghatározására. A játékosok száma n, de többnyire kettő. A játék minden állásához tartozik egy érték, amit az értékelési függvény segítségével számítható. Ez jelzi, hogy mennyire kedvez egy játékosnak az az állás. A soron következő játékos maximalizálja az ellenfelek lépései után elérhető minimális értéket.

Az egyik módszer a biztos győzelmet +1 nyereségnek tekinti. Egy másik módszer szerint egy nyerő lépés nyeresége végtelen. A játékot A szempontjából tekintve A a maximalizáló, és B a minimalizáló játékos. A fenti algoritmus minden álláshoz plusz vagy mínusz végtelent rendel, mert minden állás a végső állás értékét veszi fel. Gyakran ez csak a játék vége után lehetséges, mert a számítógépes kapacitás nem elegendő a teljes játék áttekintésére. Ilyen például a sakk és a . Csak a végjátékot lehet így végigelemezni, így az egyes állásokhoz véges értékeket rendelnek, amik a nyerés bizonyosságát fejezik ki az egyik vagy a másik játékos számára.

Ez a módszer kiterjeszthető egy heurisztikus értékelő függvény segítségével, ami anélkül rendel véges értékeket az egyes állásokhoz, hogy áttekintené az összes lehetséges befejezést. Ehelyett csak bizonyos számú lépést elemez ki előre. A Deep Blue például 12 lépést tud átlátni, és erre alkalmazni a heurisztikus értékelő függvényt.

Az algoritmus a játékfa csúcsainak felkutatásaként képzelhető el. Az egy állásban megtehető lépések átlagos száma jó elágazási tényező. A csúcsok száma rendszerint exponenciálisan nő, ezért nem hatékony a teljes játék végigelemzéséhez.

A naiv minimax algoritmus hatékonysága nagymértékben javítható az alfa-béta vágással. Más heurisztikus metszési módszereket is használnak, de ezek nem tudják garantálni az eredményt.

Az alfa-béta vágás nem értékel ki teljesen olyan állásokat, amikről bebizonyosott, hogy rosszabbak egy korábban vizsgált állásnál.

A minimax algoritmus pszeudokódja[szerkesztés | forrásszöveg szerkesztése]

A minimax algoritmus pszeudokódja itt látható:

function minimax(csúcs, mélység)
    if a csúcs levél, or mélység = 0
        return a csúcs heurisztikus értéke
     else
        let α := -∞
        foreach gyerekére a csúcsnak
                      { a kiértékelés mindkét játékos számára ugyanaz }
            let α := max(α, -minimax(gyerek, mélység-1))
        return α

A kód felhasználja azt a megfigyelést, hogy \max(a,b) = -\min(-a,-b), így egységesen tudja kezelni a két játékost.

Példa[szerkesztés | forrásszöveg szerkesztése]

Minimax.svg

Tegyük fel, hogy egy játékban minden lépésben csak két választási lehetőség van. Az algoritmus a jobboldalt látható fát generálja. A fában a körök jelzik a maximalizáló játékost, és a négyzetek a minimalizálót. A számításigény miatt a fát négy lépésre korlátozzuk.

Az algoritmus a levelektől kezdve minden levelet kiértékel a heurisztikus értékelőfüggvény szerint, és a fenti értékeket adja. Azt, hogy maximalizáló játékos nyer, plusz végtelen jelöli, és mínusz végtelen látható, ha a minimalizáló játékos nyer. A harmadik szinten az algoritmus a gyerekek minimumát választja, és ezt írja a megfelelő csúcsba. A következő lépésben a harmadik szint maximális értékei kerülnek a második szintre. Az algoritmus felváltva veszi a maximumokat és a minimumokat, amíg a gyökérhez nem ér. Ott a nagyobb értéket választja (az ábrán kék nyíl jelöli). Ezt kell lépnie a játékosnak, hogy minimalizálja a maximális veszteséget.

Statisztikai döntéselmélet[szerkesztés | forrásszöveg szerkesztése]

Legyen \vartheta \in \Theta paraméter, és legyen a \vartheta paraméter becslése \delta. Jelölje R(\theta,\delta) a rizikófüggvényt, ami rendszerint a veszteségfüggvény integrálja. A \tilde{\delta} becslés minimax, ha

\sup_\theta R(\theta,\tilde{\delta}) = \inf_\delta \sup_\theta R(\theta,\delta).

A döntéselmélet egy alternatív elmélete a Bayes-becslés használatán alapul, ami a \Pi a becsülni kívánt paraméter feltételezett a priori eloszlásának ismeretében az a posteriori rizikót:

\int_\Theta R(\theta,\delta)\,d\Pi(\theta).

A bizonytalansággal szemben[szerkesztés | forrásszöveg szerkesztése]

A minimaxról szóló elméletet arra az esetre is kiterjesztették, amikor egy játékos van, de a döntések eredményei ismeretlen tényeken múlnak. Például az ásványok keresése lehet, hogy nagy veszteséggel jár, mert nincsenek ásványok, de lehet, hogy nagy nyereséget okoz, mert sok és értékes ásvány található.

Egy másik megközelítés szerint ez a természet elleni játék, és Murphy törvényeihez hasonló elgondolással minimalizálja a várható veszteség maximumát a két játékosú zéró összegű játékoknál használt algoritmussal.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. Von Neumann, J: Zur theorie der gesellschaftsspiele Math. Annalen. 100 (1928) 295-320
  2. John L Casti. Five golden rules: great theories of 20th-century mathematics – and why they matter. New York: Wiley-Interscience (1996). ISBN 0-471-00261-5