Amikor van ellenfél
Az eddigi keresésekben a világ türelmesen várt ránk. A labirintus nem mozgott, a térkép nem alakult át, miközben terveztünk. Egy játékban viszont van egy másik szereplő, akinek pontosan az ellenkezője a célja, mint nekünk. Amit mi nyereségnek látunk, azt ő veszteségnek, és mindent megtesz, hogy megakadályozzon. Ez alapjaiban változtatja meg a keresést. Nem elég jó lépést találni, olyat kell találni, amely akkor is jó marad, ha az ellenfél a lehető legügyesebben válaszol rá.
Ezt hívjuk versengő keresésnek. A tipikus terep a kétszemélyes, váltakozó lépésű, teljes rálátású játék, mint az amőba vagy a sakk. Ketten lépnek felváltva, mindketten látják a teljes állást, és nincs benne szerencse. Ilyenkor a gép nem csak a saját lehetőségeit tervezi meg, hanem beleszámol az ellenfél legjobb válaszaiba is.
Két játékos, két ellentétes cél
A minimax alapötlete, hogy a játék végállásaihoz értéket rendelünk a mi szemszögünkből. A győzelem legyen a legmagasabb érték, a vereség a legalacsonyabb, a döntetlen valahol középen. Az egyik játékos, nevezzük őt a mi oldalunknak, ezt az értéket akarja a lehető legnagyobbra tolni. A másik, az ellenfél, a lehető legkisebbre. Innen jön a név is. Az egyik maximalizál, a másik minimalizál, felváltva.
A gép ezért nem egyszerűen a legmagasabb értékű lépést választja. Végiggondolja, hogy minden saját lépésére mi lenne az ellenfél legjobb válasza, arra megint mi lenne a mi legjobb válaszunk, és így tovább, egészen a játék végéig. Csak azután dönt, hogy ezt a teljes gondolatsort lejátszotta magában. A saját lépését ahhoz igazítja, hogy az ellenfél tökéletes játéka mellett is a legjobb kimenetelt érje el.
Az érték felszivárog a fában
A minimax úgy dolgozik, hogy a játék lehetséges folytatásaiból fát épít, aztán alulról felfelé tölti ki az értékeket. A fa alján a végállások vannak, ezeknek ismerjük az értékét, hiszen tudjuk, ki nyert. Egy szinttel feljebb az ellenfél döntene, ő a hozzá tartozó lehetőségek közül a legkisebb értékűt választja, mert az a rossz nekünk. Még egy szinttel feljebb mi döntünk, mi a legnagyobb értékűt választjuk. Ez a felfelé szivárgás addig folytatódik, amíg vissza nem érünk a jelenlegi álláshoz.
A tetején minden lehetséges első lépésünkhöz tartozik egy szám, amely megmondja, milyen kimenetelt garantál, ha mindketten a legjobban játszanak. A gép egyszerűen azt a lépést választja, amelyiknél ez a szám a legnagyobb. Így a döntés nem reménykedésen alapul, hanem azon a feltételezésen, hogy az ellenfél sem hibázik.
A tökéletesség ára
A minimax elvben tökéletesen játszik, ha a játék végéig végig tudja gondolni a lehetőségeket. Az amőbánál ez könnyen megy, mert kevés a lehetséges állás. A sakknál vagy a gónál viszont a lehetőségek száma annyira felrobban, hogy a világ összes számítógépe sem tudná a játék végéig végigszámolni. Itt jön a gyakorlati kompromisszum. A gép csak néhány lépésnyi mélységig gondolkodik előre, és a még nem befejezett állásokat egy értékelő becsléssel pontozza, ahelyett hogy a végkifejletig menne.
Ez a becslés hasonló szerepet játszik, mint a keresésnél a heurisztika. Segít eldönteni, mennyire jó egy állás, anélkül hogy a végét kivárnánk. A minimax logikája azonban változatlan marad. A gép mindig azt feltételezi, hogy az ellenfél is a legjobbat lépi, és ehhez igazítja a saját döntését. A következő leckében megnézzük, hogyan lehet ezt a keresést jelentősen felgyorsítani anélkül, hogy a döntés romlana.
A minimax mindig a legjobb ellenfelet feltételezi. Nem abban bízik, hogy a másik hibázik, hanem a legerősebb válaszra készül. Éppen ez teszi a döntését megbízhatóvá. Aki a legrosszabb esetre is felkészül, azt nem éri meglepetés.
Workshop
AI Transformation Day
Egésznapos, vezetőknek szóló program. Feltérképezzük, hol tart a szervezet, mi az első reális lépés, és milyen belső feltételek szükségesek a sikerhez. A nap végén konkrét, prioritizált cselekvési lista.
Érdekel a program →