Keresés és problémamegoldás

Egy feladat mint térkép

A keresés alapötlete, hogy egy feladatot állapotok hálózataként írunk le. Az állapot a világ egy pillanatképe, például hogy hol tart éppen egy futárautó. Átmenetnek nevezzük az egyik állapotból a másikba vezető lehetséges lépést, költségnek pedig azt, amibe ez a lépés kerül, kilométerben, percben vagy forintban. Ezzel a három fogalommal a legkülönfélébb problémák ugyanarra a kérdésre egyszerűsödnek, melyik a legolcsóbb út a kiinduló állapotból a célállapotba.

Az Elements of AI ezt klasszikus fejtörőkön és útvonalkeresésen mutatja be. Egy ilyen fejtörőben az ember ösztönösen próbálgat, a gép viszont rendszerezetten végigjárja az összes lehetséges állapotot. Kis feladatnál ez pillanatok alatt megvan. Nagy feladatnál viszont a lehetőségek száma olyan gyorsan nő, hogy a vak végigpróbálás reménytelenné válik, és okosabb keresésre van szükség, amely becslések alapján előbb az ígéretes irányokat nézi meg.

Előregondolkodás a játékokban

A játékoknál a keresés különleges fordulatot kap, mert az ellenfél is lép, és ő a saját javát nézi. Ilyenkor a minimax módszer segít, amely felépíti a lehetséges lépések fáját néhány lépés mélységig, és feltételezi, hogy az ellenfél mindig a számára legjobb választ adja. Minden állást egy értékelő függvény pontoz, a saját lépéseinknél a legmagasabb, az ellenfél lépéseinél a legalacsonyabb pontszámot visszük tovább a fán felfelé. Így az a lépés nyer, amely a legrosszabb esetben is a legjobb eredményt biztosítja.

Az IBM Deep Blue nevű gépe 1997-ben ezen az elven, óriási számítási kapacitással és gondosan kézzel hangolt értékelő függvénnyel győzte le Garri Kaszparov világbajnokot. A góban ugyanez nem működött, ott túl sok a lehetséges lépés, és egy állás értékét kézzel írt szabályokkal szinte lehetetlen megbecsülni. Lee Sedolt 2016-ban a DeepMind AlphaGo rendszere úgy verte meg, hogy a keresést neurális hálókkal kombinálta, amelyek emberi és saját játszmákból tanulták meg értékelni az állásokat.

Ahol a keresés ma is dolgozik

A nyelvi modellek korában könnyű elfelejteni, hogy a vállalati AI jelentős része ma is keresés és optimalizálás. Egy kecskeméti logisztikai cégnél, ahol a túratervezést vizsgáltuk, a diszpécserek reggelente két órát töltöttek a napi útvonalak összerakásával. A cég vezetése nyelvi modellt szeretett volna erre, mert arról hallott a legtöbbet. Végül egy klasszikus útvonal optimalizáló került be, amely a címekből, az időablakokból és a járművek kapacitásából percek alatt kiszámolja a legolcsóbb beosztást. A nyelvi modell ott kapott szerepet, ahol valóban erős, a vevői levelekben érkező szállítási kérések értelmezésében és rendszerbe vitelében.

Ez a munkamegosztás a legtöbb jól működő rendszerben visszaköszön. Egyértelmű szabályoknál és mérhető célnál a keresés gyorsabb, olcsóbb és megbízhatóbb. Ahol viszont a bemenet zajos, emberi nyelven érkezik, vagy nincs rá szabály, ott a tanuló rendszerek hozzák a hasznot.

Források és további olvasnivaló

University of Helsinki és MinnaLearn, Elements of AI, 2. fejezet, Search and problem solving, Solving problems with AI és Search and games. Claude E. Shannon, Programming a Computer for Playing Chess, Philosophical Magazine, 1950. David Silver és társai, Mastering the game of Go with deep neural networks and tree search, Nature, 2016. A kereséstől a mai modellekig tartó utat ebben a cikkemben foglaltam össze.