A feladat mint állapotok tengere
Sok probléma úgy írható le, hogy van egy kiinduló helyzet, van egy kívánt végállapot, és vannak lépések, amelyekkel egyik helyzetből a másikba juthatunk. Egy kirakós játéknál a kiinduló helyzet a felkevert állapot, a végállapot a kirakott kép, a lépések pedig az egyes elemek mozgatásai. A lehetséges helyzetek összességét állapottérnek nevezzük. A gép feladata, hogy ebben a térben megtalálja az utat a kiindulástól a célig. Ezt hívjuk keresésnek, és meglepően sok látszólag különböző probléma vezethető vissza rá.
A kulcs az, hogy a gép nem érti a játékot úgy, ahogy mi. Egyszerűen végigpróbál lépéseket, és nézi, közelebb jutott-e a célhoz. Az emberi ötletesség helyett a rendszer módszeres átvizsgálásra támaszkodik. Ha az állapottér nem túl nagy, ez az egyszerű megközelítés önmagában elegendő ahhoz, hogy a gép megbízhatóan megoldja a feladatot.
A döntési fa
Amikor a lépéseket rajzban ábrázoljuk, egy elágazó szerkezet, egy fa alakul ki. A tetején a jelenlegi helyzet áll. Ebből ágaznak le a lehetséges lépések, mindegyik egy új helyzethez vezet. Minden új helyzetből újabb lépések nyílnak, és így tovább. Ezt nevezzük döntési fának. Minél mélyebbre megyünk, annál több elágazás keletkezik, és annál messzebbre látunk előre a játékban.
A döntési fa azért hasznos, mert láthatóvá teszi a jövő lehetőségeit. Egy lépés önmagában nem jó vagy rossz, csak abban az összefüggésben, hogy hova vezet néhány lépéssel később. A fa segít abban, hogy ne csak a következő lépést nézzük, hanem annak a folytatásait is. A gond csak az, hogy a fa robbanásszerűen nő. Néhány lépés előre nézve a lehetőségek száma már milliós nagyságrendű lehet, ezért a gépnek okos módszerre van szüksége, hogy ne kelljen mindent végignéznie.
A minimax gondolata
A kétszemélyes, felváltva lépő játékoknál, mint a sakk vagy az amőba, van egy elegáns ötlet a legjobb lépés megtalálására. Ez a minimax. A neve két törekvést takar. A gép a saját lépéseivel a legjobb eredményre törekszik, tehát maximalizál. Közben feltételezi, hogy az ellenfél a lehető legjobban játszik ellene, vagyis a gép szempontjából a legrosszabb helyzetet választja, tehát minimalizál. A gép tehát nem naiv reményben lép, hanem abból indul ki, hogy a másik fél is tökéletesen játszik.
A módszer úgy dolgozik, hogy a döntési fa mélyére néz, egészen a lehetséges kimenetelekig. Ott értékeli, mennyire jó az adott végállapot a gép számára. Ezután visszafelé haladva minden szinten kiválasztja azt a lépést, amelyik a másik fél legjobb játéka mellett is a legkedvezőbb eredményt hozza. Amire a fa tetejére ér, a gép kezében ott a lépés, amely a legrosszabb esetben is a legjobbat garantálja.
A gép köre
- Célja a legjobb kimenetel
- A számára legmagasabb értékű ágat választja
- Ez a maximalizálás
Az ellenfél köre
- A gép feltételezi, hogy tökéletesen játszik
- A gép számára legrosszabb ágat választaná
- Ez a minimalizálás
Miért fontos ez a mai AI szempontjából
A minimax és a keresés a mesterséges intelligencia korai korszakának alapja volt, és sokan ezt tartják a klasszikus, szabályalapú megközelítés csúcsának. Fontos látni, hogy itt semmi nem tanult. A gép nem példákból okosodott, hanem a lépések gépies végignézéséből. Ez a megközelítés ott működik jól, ahol a szabályok pontosan ismertek és a lehetőségek kezelhetők, mint a táblás játékok esetében.
A mai, adatból tanuló rendszerek másképp működnek, de a keresés gondolata nem tűnt el. A legerősebb játékprogramok a tanulást és a keresést ötvözik, és az ügynökként viselkedő AI is gyakran mérlegel több lehetséges lépést, mielőtt dönt. Ha megértjük az állapottér, a döntési fa és a minimax logikáját, akkor sokkal tisztábban látjuk, mit jelent az, hogy egy gép előre gondolkodik. A következő leckében ott folytatjuk, ahol a szabályalapú megközelítés határa van, és megnézzük, hogyan tanul egy rendszer példákból.
A jó tipp, amely lerövidíti a keresést
Láttuk, hogy a döntési fa robbanásszerűen nő, és a gép nem képes minden ágat végignézni, ha a feladat nagy. Itt jön be egy fontos ötlet, a jó becslés, amelyet a szakma heurisztikának nevez. A heurisztika egy hasznos ökölszabály, amely megmondja, melyik irány tűnik ígéretesnek anélkül, hogy végig kellene járni. Egy útkeresésnél például jó becslés a célhoz húzott egyenes távolság. Nem pontos, hiszen utakon kell menni, de megbízhatóan jelzi, melyik lépés visz nagyjából a jó irányba. A gép így nem vaktában próbálgat, hanem a biztatóbb ágakat nézi meg előbb.
Van egy másik trükk is, amely sokat gyorsít. Ha a gép menet közben rájön, hogy egy ág biztosan rosszabb, mint egy már megtalált lehetőség, akkor azt az ágat egyszerűen abbahagyja, nem is nézi tovább. Fölösleges olyan irányt végigszámolni, amelyről már tudjuk, hogy nem verheti a jelenlegi legjobbat. Ez a szemlélet, a nyilvánvalóan rossz irányok elhagyása, teszi lehetővé, hogy a keresés a gyakorlatban is kezelhető maradjon. A jó tipp és a fölösleges ágak elhagyása együtt fordítja a végtelennek tűnő fát megoldható feladattá.
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 →