Ugrás a tartalomhoz

Alkalmazott Mesterséges Intelligencia

Dudás László (2011)

Kempelen Farkas Hallgatói Információs Központ

Játékágensek tanuló módszerei

Játékágensek tanuló módszerei

A következőkben Millington és Funge (2009) művére támaszkodva rövid áttekintést adunk a számítógépes játékágensekben alkalmazott tanuló algoritmusokról, az egyszerű paramétermódosítástól az összetett mesterséges neurális hálókig. Meg kívánjuk jegyezni, hogy az összetettebb algoritmusok saját kiterjedt irodalommal bírnak.

Paraméter módosítás

A játék valamely paramétere kihat a játék minőségére, de a paraméterérték és a játékminőség közötti összefüggés előre nem ismert. A függvény pontjai a játék során állnak elő. Mivel a függvénygörbe nem folytonos és nem differenciálható, diszkrét állapottereken is működő optimumkereső algoritmusokat szükséges használni. Lehetnek a diszkrét pontokkal adott függvények többdimenziósak is, azaz több paraméter értékét kell keresni a függvényoptimum megtalálásához.

A legegyszerűbb módszer a mindenkori legjobb függvényértéket eredményezett paraméterértékek elmentése és alkalmazása a későbbiek során. Amennyiben kellő mennyiségű lejátszott játékból rendelkezésre áll egy diszkrét állapottéren kapott pontsokaság alapjában a játszmák jóságának függvénye, de valamilyen ok miatt a függvénypontok keletkezésével párhuzamosan nem tároltuk el az extremális értéket adó helyet, akkor megpróbálhatjuk megkeresni valamilyen lokális kereső algoritmussal. Leggyakrabban alkalmazott a hegymászó keresés, mely azonban gyakran csak lokális optimumot ad. Nagyobb esélyt adnak a globális optimum fellelésére a momentum módszer, vagy a többszörös indítású hegymászó algoritmus. A momentum módszernél a függvény bemenő értékét egy darabig még azután is szisztematikusan továbbléptetjük, amikor a függvényérték rossz irányba változik. Ezáltal átlendülhetünk rövid lefelé vivő függvényszakaszokon és találhatunk a lokális csúcstól jobb függvényértékű helyet. A többszörös indítású hegymászó algoritmus azáltal növeli meg a globális optimum megtalálásának esélyét, hogy a ’hegyre’ több hegymászót helyez véletlenszerű pontokra. Így megnő az esélye, hogy a globális optimum hegyoldalára is jut hegymászó.

Nagyobb eséllyel találja meg a globális optimumot a szimulált hűtést alkalmazó, vagy a tabu algoritmus, lásd pl. (Dudás, 2006). Ezen utóbbi algoritmusok megfelelő paraméterezés esetén képesek a globális optimum fellelésére, a gond csak az, hogy a megfelelő paraméterek megtalálása egy újabb keresési feladat… Sokszor azonban kompromisszumot kötünk, a keresés hatékonysága érdekében megelégszünk gyakorlatilag jó kvázioptimális, esetleg lokálisan optimális megoldással is.

Akció előrejelzés

A játékágens felruházása az előrelátás képességével. A játékok többségében a gép és az emberjátékos között vetélkedés folyik. Ilyenkor előnyös a gépi ágens számára, ha előre látja az ember cselekedeteit. Ez a fajta gépi intelligencia arra alapoz, hogy az emberekre jellemző a megszokás, a járt út el nem hagyása, a cselekvések ismétlése.

A továbbiak egyszerűbb követhetősége érdekében az emberjátékos által kivitelezett lépéseket jelöljük az ABC nagybetűivel, ahol ugyanaz a betű jelöljön ugyanolyan tevékenységet. Például egy négylépéses tevékenységsorozat jelölése lehet: BKLT.

Ezek után tételezzük fel, hogy rendelkezésre áll az emberjátékos játékára a korábbi játékrészben megtett lépéseinek a listája egy karaktersorozat, sztring formájában. A következő tevékenységét jól valószínűsítheti a gépi ágens, ha a karaktersorozatban meghatározza az egyes karakterek előfordulási gyakoriságát. Ha pl. a K cselekvés kétszer olyan gyakori, mint a B, akkor felteheti, hogy célszerűbb a K cselekvés bekövetkeztére számítani. Ennek az egyszerű valószínűségen alapuló módszernek az a hátránya, hogy az emberjátékos könnyen kifigyelheti és kihasználhatja a további játékában.

A cselekedetek gyakoriságának mintájára a gépi ágens megfigyelheti többlépéses cselekvéssorozatok előfordulási gyakoriságát is az emberjátékos játékában. Ha a többlépéses sorozat lépésszáma N, akkor az N hosszú mintázatok, ún. N-gramok előfordulási gyakoriságára alapozva, ha az emberjátékos utolsó N-1 lépése adott, akkor az azokkal kezdődő N-gramok gyakorisága megadja a következő lépés közelítő valószínűségét. Így az ágens a legvalószínűbb lépésre készülhet. Konkrét játékokban különböző hosszúságú N-gramok statisztikáját felvéve, megfigyelhető, hogy az előrejelzések jósága egy adott N esetén tetőzik, azaz ilyen hosszúságú N-gramokra alapozva teljesít az ágens legjobban. Ugyanakkor az is érthető, hogy nagyobb variációban előforduló N hosszúságú mintázatok esetén az előrejelzés hatékonysága csökken.

Az is érezhető, hogy kevés korábbi esetre támaszkodó N-gram statisztikák rossz előrejelzést tesznek lehetővé. Minél nagyobb az N, annál inkább így van. Mivel a hosszabb minták nagyobb variációszámban fordulhatnak elő, kis esethalmaz esetén megnő a valószínűsége, hogy egyes mintákra nulla gyakoriságot kapunk, ami gyenge játékteljesítményt eredményez. Ebből a megfigyelésből ered az alkalmazott N-gram hossz változtatása a játék előrehaladtával, azaz a játék kezdetén csak a rövid N-gramok adnak elfogadható előrejelzést, majd a korábbi esetszám növekedésével a hosszabb N-gramok jutnak szóhoz. Ezt az N-gram hosszt változtató technikát Millington és Funge (2009) Hierarchikus N-gram technikának nevezi. A technika párhuzamosan kiértékeli a különböző hosszúságú N-gramokat, majd megpróbál a hosszabb alapján dönteni. Ha az nem ad eléggé megbízható döntést, mert kevés esetre támaszkodik, akkor rövidebb N-grammal próbálkozik. Az hogy hány esetre alapozhat az N-gram megbízhatóan, függ a konkrét játéktól. On-line játékok hajlamosak kisebb esetszámra alapozó statisztikákkal is működni.

Az N-gram alapú akció előrejelzés a tapasztalatok alapján nagyon hatékonyan növeli a játékágens intelligenciáját, mindamellett egyszerű implementálni is. Leginkább az akciójátékokban terjedt el, lehetővé téve, hogy az ágens előre lássa az emberjátékos lépését és hatékony ellenakciót indíthasson.

Döntés tanulás

Az előzőekben említett módszerek viszonylag korlátozott tartományon működtek, megelégedtek néhány paraméter értékének javításával, vagy az adott szituációban legalkalmasabbnak tűnő tevékenységsorozat előválasztásával. Ebben a részben a tanulás is előtérbe kerül, melynek révén a játékágens döntéshozó képessége megnő. A játékágenseknél alkalmazott tanuló technikák a mesterséges intelligencia általános tanuló algoritmusainak specializált változatai. A tanulás alapvetően asszociálás, dolgok társítása. Játékágenseknél a játék adott állásánál felgyűlt és rendelkezésre álló információk alapján kell a lehetőségek közül választani, azaz a lehetőségeket az információkhoz társítani. Az asszociációk felhasználása növeli az ágens sikerességét. A megfigyelésből felgyűlt információk egy magasabb szinten vonatkozhatnak az asszociációk sikerességére is, megerősítve, vagy gyengítve azokat.

A tanulás fajtái alapvetően két csoportba sorolhatók: felügyelt és felügyelet nélküli tanulás. A felügyelt tanulás esetén az ágens megfigyeléseihez társítandó akcióiról az embernek határozott elképzelései vannak, és ezt elvárt tevékenységek formájában az ágens tudtára is hozza. Az ágens feladata ezek után olyan asszociációk kiépítése, melyek a felügyelő elvárásaival egyeznek. Ebben a folyamatban gyakran dicsérő, illetve büntető visszajelzések érik az ágenst az elvárást képviselő felügyelő, tanár részéről. Vagy történhet a társítás oly módon is, hogy az ágens a tanár lépéseit, válaszait megfigyelve igyekszik utánozni azokat. A másik, felügyelet, elvárás nélküli tanulásnál nem a konkrét választevékenységre van előírás, hanem az információkra, megfigyelésekre válaszként adott tevékenység minőségére, hasznosságára. Egy off-line formában a megítélés jöhet a játék fejlesztőjétől a fejlesztési folyamat során, de az igazi esetben a játék működése közben, egy beépített minősítő algoritmus fütyül, vagy tapsol. A visszajelzés minősíthet hosszabb idő alatt végzett működést is. Az implementálás könnyűsége szempontjából a felügyelt tanítás van előnyben, míg a felügyelet nélküli mellett a rugalmassága és a sokszínűsége, kiszámíthatatlansága, adaptivitása szól.

Játékágenseknél felmerül az a kérdés, mit tanuljon? Különösen a felügyelet nélküli tanulás esetén célszerű az általánostól a speciális felé tartó fokozatosság alkalmazása. Sokkal elfogadhatóbb egy olyan gépi játékos, amely minden helyzetben elfogadhatóan és néha egész jól dönt, mint egy olyan, amely egyes esetekben briliáns, de máskor teljesen rosszul lép. Bár a mai játékokban alkalmazott tanuló algoritmusok egyre jobbak, az emberi okosság elérése tanulás révén még nem várható tőlük.

A következőkben négy tanulási módszert ismerünk meg, a Naiv Bayes osztályozót, a döntési fa tanulását és két, inkább a jövőre nézve nagy lehetőségeket rejtő technikát, a megerősítő tanulást és a mesterséges neurális hálókat jellemző technikát. Az első kettőt könnyű implementálni, és a befektetett munkához képest jó eredményt adnak, míg az utóbbi kettő igen szerteágazó és mély elméleti hátérrel rendelkező technika, melyek külön könyvekből ismerhetők meg mélységükben és hatékony alkalmazásuk a játékprogramozásban még a kezdeti lépéseknél tart, bár nagyon ígéretesek.

A Naiv Bayes osztályozót (Millington és Funge, 2009) példáján keresztül érthetjük meg. Tételezzük fel, hogy egy autóverseny játékot készítünk, és azt szeretnénk, ha az ágens megtanulná az emberjátékosoktól a kanyar bevételekor követendő technikát.

Kanyarbevétel a játékprogramban

A kanyarodás stílusát több tényező is meghatározza, de az egyszerűség kedvéért csak azt tekintsük, amikor a játékos a kanyartól való távolsága és pillanatnyi sebessége alapján dönt a fékezésről. Az elinduláshoz rögzítenünk kell olyan adatokat, melyekből az ágens tanulni fog. Egy ilyen adathalmaz a következőképpen nézhet ki:

A táblázatot célszerű olyan egyszerűen megfogalmazni, amennyire csak lehet, hogy elkerüljük a sokféle mintából eredő hosszú számítási időt és sok adatot. Ezért alkalmazzuk most a következő egyszerűsítést: a távolság legyen csak kétféle, ’közel’, vagy ’messze’, attól függően, hogy az érték 10 alatti, vagy sem, a sebesség pedig 20 alatt legyen ’lassú’, ellenkező esetben pedig ’gyors’. Ezekkel az egyszerűsített tanító halmaz:

Nemcsak az ember számára áttekinthetőbbek a viszonyok a feltételek és a döntés között, hanem gyorsabb tanulásban is bízhatunk.

Komolyabb konkrét esetekben az adatok sokszínűségének redukálására és a statisztikailag jelentős kategóriák beazonosítására szóba jönnek osztályozó, klaszterező matematikai eszközök is, mivel az ésszerű attribútumok alkalmazása a gépi tanulás sikerének alapja.

Most pedig meg kell adni, mit is kell az ágensnek megtanulnia. Annak a feltételes valószínűségét akarjuk megtanítani, hogy mikor fékezzen a távolság és a sebesség ismeretében. Ezen feltételes valószínűség formulája:

P(fékez? | távolság, sebesség)

És itt van segítségünkre a Bayes szabály:

P(A|B) = P(B|A)P(A) / P(B)

A szabályban az a jó, hogy megkaphatjuk az A esemény bekövetkezésének valószínűségét, ha tudjuk, hogy B bekövetkezett abból is, ha éppen a B bekövetkezési valószínűsége ismert az A bekövetkezése esetére. Fogjuk látni, miért fontos ez, amikor majd megpróbáljuk alkalmazni. De előbb alakítsuk át egy kissé a szabályt:

P(A|B) = αP(B|A)P(A)

ahol α = 1 / P(B). Később látni fogjuk, hogy ezt az alakot könnyebb a mi céljainkra használni.

Itt a mi példánkra alkalmazott új alakja a Bayes szabálynak:

P(fékez? | távolság, sebesség) = αP(távolság, sebesség | fékez?)P(fékez?)

A következőkben egy naiv feltételezéssel fogunk élni, hogy megadjuk:

P(távolság, sebesség | fékez?) = P(távolság | fékez?) P(sebesség | fékez?)

Valószínűleg láttunk már példát összetett esemény valószínűségének ilyen módon való kiszámítására, független eseményeknél.

Egyesítve a Bayes szabályt a független események valószínűségére előbb megadottal, kapjuk:

P(fékez? | távolság, sebesség) = αP(távolság | fékez?) P(sebesség | fékez?) P(fékez?)

Az a jó ebben a végső formulában, hogy használhatjuk a szükséges valószínűségek meghatározására, helyesebben közelítésére a korábbiakban adott táblázatunkat. Hogy hogyan, arra nézzük azt a példát, amikor a játékágens próbál dönteni a fékezés szükségességéről a kanyartól 79,2 távolságra, miközben 12,1-es sebességgel halad. A döntéshozáshoz ki akarjuk számítani azt a feltételes valószínűséget, amellyel egy ember játékos fékezne hasonló szituációban és azt használni.

Csak két valószínűség van, azé, hogy fékezünk és azé, hogy nem. Annak a valószínűsége, hogy fékezünk:

P(fékez?=I | távolság=79,2, sebesség=12,1).

A pontos értékeket kategorizálva a korábbiaknak megfelelően írható:

P(fékez?=I | távolság=messze, sebesség=lassú).

És most alkalmazzuk az előbb levezetett végső formulát:

P(fékez?=I | messze, lassú) = αP(messze | fékez?=I) P(lassú | fékez?=I) P(fékez?=I)

Az értéktáblázatból közelíthetjük a szükséges valószínűségeket az esetek relatív gyakoriságával:

P(messze | fékez?=I) = 2/5; P(lassú | fékez?=I) = 2/5; P(fékez?=I) = 5/7.

A továbbiakban a táblázatos adatokból számított relatív gyakoriságokat is valószínűségnek fogjuk nevezni az egyszerűség kedvéért, de tudjuk, hogy azok csak többé-kevésbé jó közelítései a valószínűségnek.

A fékezés 5/7-es értékét apriori, előzetes valószínűségnek nevezhetjük, mivel anélkül adja meg a fékezés valószínűségét, hogy bármit tudnánk az aktuális szituációról. Az apriori valószínűségek jó becsléssel szolgálnak az események konkrét bekövetkezésének esélyére. Behelyettesítve az arányszámokat a képletünkbe, meghatározhatjuk, mekkora a feltételes valószínűsége annak, hogy egy emberjátékos fékezne egy hasonló szituációban:

P(fékez?=I | messze, lassú) = α∙4/35.

De mit mondhatunk az α-ról? Úgy tűnik, α értéke nem túl fontos. Hogy lássuk, miért nem, határozzuk meg a valószínűségét a nem fékezésnek!

P(fékez?=N | messze, lassú) = α∙1/14.

Az α értéke nem szól bele a fékezés? nem fékezés? kérdésébe, mivel kiesik. (α mindig pozitív, mert a valószínűségek nem negatív értékek.)

α∙4/35 > α∙1/14 = 4/35 > 1/14 = 0,11 > 0,07

Azaz a fékezés valószínűsége nagyobb, mint a nem fékezésé. Ha a mesterséges ágens emberhez hasonlóan akar viselkedni, akkor fékezni fog, hiszen az emberről gyűjtött adatokat veszi alapul.

A számításokban a gyakran nulla közeli kis valószínűségek összeszorzása alulcsordulást okozhat a számábrázolás véges precizitása miatt, ezért a valószínűségek szorzata helyett a valószínűségek logaritmusainak összegét szokták számítani.

A Döntési fa tanulása a hatékony döntéshozáshoz szükséges szerkezetű fagráf felépítését jelenti a különböző döntési esetek ismeretében. A megkonstruált fa esetében a megtanult szabályoknak megfelelő döntések meghozatala a legkevesebb lépésben valósul meg. Ezt a tanuló, azaz fa-konstruáló algoritmus azáltal éri el, hogy a korábbi döntési, választási pontokhoz rendeli a legnagyobb információtartalmú döntéseket. A következőkben a szerző által kidolgozott példán keresztül megismerhetjük az algoritmus működését. Tételezzük fel, hogy a játékágens az emberjátékos viselkedése alapján a következő megfigyeléseket tette az erőnlétE, erőnlétJ, fegyverE, fegyverJ attribútumok konkrét értékei függvényében arra vonatkozóan, hogy az emberjátékos inkább támad, vagy védekezik:

A tanítóminták táblázatában E jelöli az emberjátékost, J pedig a játékágenst. Bár a tapasztalat felírható egyetlen összetett logikai kifejezés formájában is, a Döntési fa attól hatékonyabb döntést eredményez. A támadás feltétele így fogalmazható meg:

if ((erőnlétE = jó ÉS erőnlétJ = gyenge ÉS fegyverE = hibátlan ÉS fegyverJ=hibátlan) VAGY (erőnlétE = jó ÉS erőnlétJ = közepes ÉS fegyverE = hibátlan ÉS fegyverJ=sérült) VAGY (erőnlétE = jó ÉS erőnlétJ = közepes ÉS fegyverE = hibátlan ÉS fegyverJ=hibátlan) VAGY (erőnlétE = közepes ÉS erőnlétJ = gyenge ÉS fegyverE = hibátlan ÉS fegyverJ=hibátlan) VAGY (erőnlétE = gyenge ÉS erőnlétJ = gyenge ÉS fegyverE = hibátlan ÉS fegyverJ=sérült)) then (TámadE? = igen)

Hasonlóan adható meg, hogy mikor nem támad az emberjátékos.

A példában az attribútumok értékeinek függvényében adódó támadás, vagy nem támadás választása a feladat, azaz osztályozás. Az alkalmazott módszer az ID3 (Inductive Decision Tree Learning Algorithm) nevet viseli, algoritmusa a következő:

  1. A legtöbb információt szolgáltató attribútum választása

  2. A választott attribútummal egy gráfcsomópont képezése, majd értékeinek megfelelő elágazások berajzolása

  3. Az értékeknek megfelelő tanítópéldáknak a levelekhez adása

  4. Az ily módon adódott levelek megvizsgálása:

    • ha a csatolt tanítóminták a levélen azonos tevékenységet kaptak, akkor ennek az értéknek a levélhez rendelése és leállás ezen az ágon

    • egyébként az 1-4 lépés ismétlése a redukált táblázattal.

A legtöbb információt szolgáltató attribútumot információelméleti módszerrel, Shannon informatikai entrópia fogalmának felhasználásával határozzuk meg. Eszerint az I eset bekövetkezésének ’híre’ az eset bekövetkezésének P(I) valószínűségétől függően az

E(I) = -P(I)∙log2P(I)

’hírértékkel’, entrópiával bír.

Az összes lehetséges esetből, hírből álló S = {A, B, ..., I, ...,N} készlet összentrópiája:

E(S) = -Σ P(I)∙log2P(I)

Ha mindig biztosan ugyanaz az eset következik be, az E(S) entrópia nulla, mivel a biztos eset valószínűsége 1, a többié nulla, és akkor maximális, ha a bekövetkezhető esetek egyforma P(I) = 1/n valószínűséggel adódhatnak: E(S) = -Σ(1/n)∙log2(1/n) = -log2(1/n)∙Σ(1/n) =-log2(1/n)∙1 = log2((1/n)-1) = log2n. (Ahol n = |S| a készlet számossága, azaz a készlet elemeinek száma.)

Pl. A fenti táblázatban szereplő támadE kétféle esettel, kimenetellel teljesülhet: igen, vagy nem. A 13 soros táblázatban az igen-ek aránya 14 féle lehet, amint az ábra mutatja:

Kedvező entrópia 5/13 értéknél

Látható, hogy a konkrét tanítóminták esetén az entrópia a 13-ból 5 igen esettel közel van a maximális 1 értékhez:

E(támadE) = -P(támadE=igen)∙log2P(támadE=igen) - P(támadE=nem)∙log2P(támadE=nem) = -(5/13)∙log2(5/13) -(8/13)∙log2(8/13) = 0,530 + 0,431 = 0,961

Attribútumválasztás

A döntési fa adott ágán még fel nem használt attribútumok közül válasszuk azt, amelyik a leginkább csökkenti az entrópiát, a bizonytalanságot, azaz a legnagyobb információnyereséggel jár. A G információnyereség egy adott attr attribútum esetén, ha az attribútumnak m féle értéke lehet és ezek közül a j-edik érték esetén idbattr,j jelöli az igen döntések darabszámát és ndbattr,j jelöli a nem döntések darabszámát:

G(attr) = E(támadE) - Σ(idbattr,j + ndbattr,j) / (idb + ndb)∙E(támadEattr,j)

A szummázást az attr attribútum esetében j= 1..m esetére kell végezni.

A fa gyökerénél a négy attribútum (erőnlétE, erőnlétJ, fegyverE, fegyverJ) közül kell a legnagyobb nyereséget adót kiválasztani. Nézzük meg részletesen a nyereség értékét az attr= erőnlétE esetén:

G(erőnlétE) = E(támadE) - ((idberőnlétE,jó + ndberőnlétE,jó) / (idb + ndb)∙E(támadEerőnlétE,jó) + (idberőnlétE,közepes + ndberőnlétE,közepes) / (idb + ndb)∙E(támadEerőnlétE,közepes) + (idberőnlétE,gyenge + ndberőnlétE,gyenge)/(idb+ndb)∙E(támadEerőnlétE,gyenge)) = 0,961 - ((3+0)/(5+8)∙0 + (1+4)/(5+8)∙0,722 + (1+4)/(5+8)∙0,722) = 0,406

Ahol pl. E(támadEerőnlétE,közepes) = -(1/5)∙log2(1/5) -(4/5)∙log2(4/5) = 0,722

Hasonló számítással

G(erőnlétJ) = 0,192

G(fegyverE) = 0,496

G(fegyverJ) = 0,000

Azaz a fegyverE szerint hozva meg első szinten a döntést, nyerjük a legtöbb információt, ezt az attribútumot vesszük gyökér csomópontnak.

Ez az attribútum olyan erős, hogy a ’sérült’ értéke esetén nem is kell további attribútumokat vizsgálni, mert azok értékétől függetlenül nem érdemes támadni.

A másik ágon viszont nem ilyen egyértelmű a helyzet, emiatt az algoritmust folytatni kell, de csak azokkal a tanítóminta sorokkal, ahol a fergyverE=hibátlan érték szerepel, hiszen ezen az ágon vagyunk.

És mivel a fegyverE attribútum már nem vesz részt a további döntések megalapozásában, az oszlopát is törölhetjük:

A fentekhez hasonlóan adódó információnyereség értékek:

G(erőnlétE) = 0,292

G(erőnlétJ) = 0,292

G(fegyverJ) = 0,006

Az erőnlétE és az erőnlétJ egyforma információnyereséggel jár, és mindkettőnél egy ágon (erőnlétE=jó: igen; erőnlétJ=gyenge: igen) végső döntéshez jutunk. Válasszuk az erőnlétJ attribútumot következő csomópontként, mert ennél csak egy ágon kell továbbmennünk!

Az erőnlétJ=közepes sorokra redukált tanítóminta táblázat:

Az információnyereség értékek:

G(erőnlétE) = 1

G(fegyverJ) = 0

Az erőnlétE attribútumot választjuk csomópontként:

Az ágakat berajzolva és a döntési értékeket hozzájuk rendelve látható, hogy a nagy információnyereség mind a három attribútumérték esetén egyértelmű döntést eredményez.

Mivel ez a döntési fa azt mutatja, hogy az emberjátékos mikor támad, a gép számára alkalmas fát az E és J cseréjével, azaz a játékosnak az ember szemszögébe helyezésével kapunk.

Amennyiben az attribútumok folytonos értékekkel bírnak, célszerűen választott intervallumokat vezethetünk be, ’egy kalap alá véve’ ilymódon az intervallumba eső értékeket.

A Megerősítő tanulásról (Millington és Funge, 2009), (Sutton és Barto, 1998) és (Stefán, 1999) alapján adunk egy tömör összefoglalást, a hangsúlyt a játékágens tanuló működésére helyezve. A megerősítő tanulás a felügyelt és a felügyelet nélküli tanuló módszerek között elhelyezkedő, a tapasztalatra építő, különösen dinamikusan változó állapotterekben zajló folyamatok optimálására alkalmazható algoritmus. A felügyelt rendszerek esetén a környezet instruktív visszajelzésekkel korrigálja a tanulórendszer belső struktúráját, illetve paramétereit. Ez azt jelenti, hogy a módosítás iránya a rendszeren kívülről befelé haladó; azaz a környezet megmondja, a belső állapottól kvázi függetlenül, hogy melyek a rendszer ’helyes’, ’megkívánt’ kimeneti jellemzői. A rendszer módosítása pedig éppen az előbbi állapotok elérése felé irányul. Koncepciójában különbözik ettől az a megoldás, amikor a tanulás belülről jövő. Ez azt jelenti, hogy a rendszer maga úgy van felépítve, hogy ’felfedezi’, ’feltérképezi’ környezetét. Más kifejezéssel élve cselekvéseket, akciókat hajt végre, amelyek hatással vannak a környezetre, és aminek következtében a környezet visszajelzést ad, hogy a választott akciókat a környezet hogyan jutalmazta. A visszacsatolt érték, a megerősítő-jel, egy skaláris szám, melynek értéktartománya rendszerint problémafüggő. Általában egy nagy pozitív szám a környezet akcióra adott ’jutalmát’, míg a nagy negatív szám ’büntetését’ szimbolizálja. – írja (Stefán, 1999).

A tanuló rendszer és a környezete közötti hatásokat szemlélteti az alábbi ábra:

A játék ágens és a környezet viszonya

A módszert előszeretettel alkalmazzák mesterséges intelligencia alapú tanuló eljárásként a számítógépi játékokban, a játékágens alkalmazkodó, tanuló képességének megvalósítására. A játékágens teljes környezetének ismeretét feltételező dinamikus programozási eljárások, a környezettel szemben ilyen elvárást nem támasztó Monte Carlo módszerek mellett a Q-tanulás algoritmus az a tanulóalgoritmus, melyet a játékprogramozók leginkább alkalmaznak. Az algoritmus előnyei között említhető, hogy egyszerű implementálni, széles körben tesztelték nem játék célú alkalmazásokban is és tuningolható mélyebb elméleti megértés nélkül is.

A probléma a következő: azt szeretnénk, ha a játékágens egyre jobban működne, egyre jobb akciókat választana céljai elérésére a játék előrehaladása során. Hogy a játék későbbi szakaszában mi fog jó választásnak, akciónak bizonyulni, a program tervezője által előre nehezen elképzelhető. Függhet az emberjátékos tevékenységétől, illetve a játékban előforduló véletlen mintázatoktól, melyekre nem lehet felkészülni. Emiatt a játékágens számára szeretnénk lehetővé tenni, hogy szabadon választhasson a lehetséges akciók közül a játék bármely szituációjában és megtanulja, hogy az egyes helyzetekben melyik a legjobb választás. Bár sok szituációban a választott akció jósága azonnal megítélhető, azonban vannak olyan helyzetek, amikor ez csak később derül ki, valamilyen szignifikáns történés révén. Ezen esetekre a játékágensnek meg kellene tudni tanulni azokat a megelőző cselekvéseket is, amelyek elvezettek a szignifikáns eredményhez.

A Q-tanulás algoritmus

A Q-tanulást a minőségi információról (quality values, Q-values) nevezték el, melyet a játékban előforduló állapotokról és az állapotokban kivitelezhető akciókról tárol.

Ez az algoritmus a probléma speciális reprezentációjára támaszkodik. Letárolja, aktualizálja a releváns információkat, amint általa megtehető új akciókat derít fel. Nézzük meg ezt a reprezentációt először!

A játék-világ reprezentációja a Q-tanulás algoritmusban egy állapotgéppel történik. A játék algoritmus minden időpillanatban valamilyen állapotban van. Egy ilyen állapotnak minden vonatkozó részletet tárolnia kell a játékágens környezetéről és belső állapotáról.

Azaz, ha az ágens egészsége fontos a tanulás szempontjából, és az ágens két azonos szituációban találja magát, melyben csak az egészsége tér el, akkor azokat különböző állapotoknak kell tekintenie. Semmi nem tanulható meg, ha nincs bevéve az állapot jellemzői közé.

A játékban az állapotok számtalan jellemzővel bírhatnak: hely, ellenség közelsége, egészség szintje, és így tovább. A Q-tanulás algoritmusa nem igényli, hogy az állapot jellemzőit értsük. Az algoritmus szempontjából ezek egyszerűen egy egész számban jelennek meg: az állapot számban.

A játékalgoritmusnak viszont képesnek kell lennie az aktuális állapotot egy állapotszámra lefordítva megadni, hogy a tanuló algoritmus azt használhassa. Szerencsére a fordított irányú leképezésre nincs szükség, nem kell soha az állapotszám alapján konkrét játékjellemzőkről nyilatkozni.

A Q-tanulást modell-mentes algoritmusnak mondjuk, mert nem próbál felépíteni egy modellt a világ működéséről. Mindent egyszerűen állapotokként kezel. A nem modell-mentes algoritmusok megpróbálják a meglátogatott állapotokból rekonstruálni, mi történik a játékban. A modell-mentes algoritmusokat, mint amilyen a Q-tanulás is, sokkal könnyebb implementálni.

Az algoritmusnak minden egyes állapot esetére meg kell tudnia a rendelkezésre álló akciókat. Sok játék esetében minden akció alkalmazható bármely állapotban, a komplexebb játékokban azonban a választható akciók készlete függhet az ágens pillanatnyi helyétől (pl. meghúz egy kart), attól, hogy birtokában van-e bizonyos dolog (pl. egy kulcs az ajtó kinyitásához) vagy attól, hogy egyéb akciókat megfelelően kivitelezett-e megelőzően (pl. átment-e a kinyitott szobán?).

Azután, hogy az ágens kivitelezett egy akciót a konkrét állapotban, a megerősítő függvénynek visszacsatolást, visszajelzést kell arról adnia. A visszacsatolás pozitív, vagy negatív, sőt gyakran nulla, ha nincs tiszta információ arról, milyen jó volt a végrehajtott akció. Nincs korlát a megerősítő függvény által visszaadott értékekre, de általánosan elfogadott, hogy a [-1, +1] tartományba esnek.

Nem elvárás a megerősítő értékkel szemben, hogy mindig ugyanolyan érték legyen egy bizonyos állapotban kivitelezett akció esetén. Lehetséges eltérő környezeti információ, melyet nem használtunk az algoritmus állapotának létrehozásakor. Amint előbb láttuk, az algoritmus nem tudja megtanulni a hasznosítását olyan információnak, amelyet nem vettünk figyelembe az állapot jellemzői között, de tolerálni fogja a hatásait és meg fogja tanulni az általános sikerességét az akciónak, inkább, mint a sikerre való hatását egyetlen próbálkozás alapján.

Egy akció kivitelezése után az ágens valószínűleg egy új állapotba kerül. Ugyanazon akció kivitelezése egy pontosan ugyanolyan állapotban eltérő állapotokra is vezethet. Más játékágensek és az emberjátékos szintén kihathat az új állapotra. Pl. egy térbeli lövöldözős (FPS, First Personal Shooter) játékban a játékágens egy erőnlét-frissítő csomagot keres, és nem kíván ütközetbe bocsátkozni, ezért egy oszlop mögé rejtőzik az ellenség elől, mely a szoba kijáratát éppen elállja. Az ágens aktuális állapota: 1.szobában, rejtőzködik, ellenség_közel, halálveszély. Az ágens az „elbújás” akciót választja a rejtőzködés folytatására. Az ellenség ottmarad, emiatt az „elbújás” akció visszavezet ugyanahhoz az állapothoz. Azaz az ágens az „elbújás” akciót ismétli. Amikor az ellenség elmegy, a megváltozott helyzetben az „elbújás” akció már más állapotra vezet: 1.szobában, rejtőzködik, ellenség_nincs, halálveszély_nincs.

A Q-tanulás (és a legtöbb más megerősítő algoritmus) egyik kiemelkedő jellemzője, hogy ilyesfajta bizonytalanságot képesek kezelni.

Ez a négy összetevő – kiinduló állapot, alkalmazott akció, megerősítő érték, bekövetkezett állapot – alkotja a tapasztalati négyest, melyet (s, a, r, s’) alakba szoktak írni.

Az algoritmus minden egyes, a játékban kipróbált állapothoz és akcióhoz tárol egy értéket. A Q-érték azt mutatja, milyen jónak érzi azt az akciót választani, ha abban az állapotban van.

A tapasztalati négyes két részből áll. Az első két elem (az állapot és az akció, state, action) szolgál egy tárolt Q-érték kikeresésére. A második két elem (a megerősítő érték, jutalom és az új állapot, reward, state’) használatos a Q-érték javítására, frissítésére, attól függően, hogy milyen jó volt az akció és milyen jó lesz majd az új állapotban.

A frissítés a Q-tanulási szabály alapján megy végbe:

Q(s,a) = (1-α)Q(s,a)+α(r+γmax(Q(s’,a’)),

ahol 0≤α≤1 a tanulási együttható, 0≤γ≤1 pedig a diszkont faktor, elhanyagolási tényező, a távolabbi megerősítő értékek, jutalmak hatásának csökkentésére, mivel azok kevésbé fontosak. Mindkettő az algoritmus paramétere.

Hogy működik ez a szabály?

A Q-tanulás algoritmus két összetevő lineáris kombinációja, az arányokat az α tanulási paraméter értéke határozza meg. A Q(s,a) első komponens egyszerűen az adott állapothoz és akcióhoz tartozó aktuális Q-érték. Az (1-α) tényezővel megtartva bizonyos ennek részét, azt fejezzük ki, hogy soha nem dobunk el teljesen korábban megszerzett információt. A második komponens két tagból áll. Az r érték az új megerősítés, jutalom a tapasztalati négyesből. Ha a megerősítő szabály a

Q(s,a) = (1-α)Q(s,a)+αr

lenne, akkor a régi Q-értéket kombinálná az akcióra kapott r jutalommal.

A második összetevő második tagja, γmax(Q(s’,a’) az új állapotot nézi a tapasztalati négyesből. Veszi az abból az állapotból megléphető összes akciót és a legmagasabb megfelelő Q-értéket választja. Ez segíti figyelembe venni egy későbbi akció sikerességét (azaz a Q-értékét) a korábbi akciónál: ha a következő állapot egy jó állapot, akkor az lehetőséget kap a nagyszerűségének a megosztására.

A diszkont faktor, elhanyagolási tényező szabályozza, hogy mennyire függjön a kurrens állapot és akció Q-értéke annak az állapotnak a Q-értékétől, amelyhez vezet. Nagy érték nagy figyelmet szentel a jó állapotoknak, nagyon kis érték pedig csak azokat az állapotokat fogja figyelembe venni, melyek közel vannak a sikerhez. Egytől nagyobb érték állandóan növő Q-értékeket eredményezne és a tanuló algoritmus soha nem konvergálna a legjobb megoldáshoz. Valós alkalmazásban megfigyelhető a diszkont faktor hatása, amint a tanulás halad előre, a magas Q-értékek fokozatosan terjesztik a hatásukat visszafelé, az állapothoz vezető akciók lánca mentén, végül az akciók láncán található értékek növekvő Q-érték sorozattal fognak elvezetni a magas Q-értékű állapothoz.

Összefoglalva, a Q-érték egy kombinációja az aktuális értéknek és az új értéknek, mely új érték egyesíti az akció megerősítésének hatását és annak az állapotnak a jóságát, amelyikhez az akció vezet.

A következőkben a megerősítő tanulás fontos összetevőjét, a felderítési fázist fogjuk megvizsgálni. Az eddigiekben megismertük a megerősítő függvényt, a tanulási szabályt és az algoritmus belső szerkezetét. Tudjuk, hogyan végezzük a tanulást a tapasztalati négyes alapján, és hogyan generáljuk ezt a négyest az állapotokból és akciókból. A megerősítéses tanuló rendszerek egy felderítési stratégiát is igényelnek: egy választási iránymutatást arra, hogy az egyes állapotokban melyik akciót alkalmazzák. Ezt gyakran egyszerűen csak stratégiának (policy) nevezik.

A felderítési stratégia nem szorosan vett része a Q-tanulás algoritmusnak. Ámbár a következőkben vázolt stratégia nagyon gyakran használatos a Q-tanulásban, léteznek mások is saját jó és rossz tulajdonságaikkal. Egy játékban egy erőteljes alternatíva lehet az emberjátékos akcióinak figyelembevétele és a tapasztalati négyesnek az ő játékán alapuló képzése.

Az Q-tanulás alap felderítő stratégiája részben véletlenszerű. Az esetek nagy részében az algoritmus az aktuális állapot legnagyobb Q-értékű akcióját fogja választani. A maradékában véletlenszerűen fog választani. A véletlen akciók aránya egy ρ paraméterrel szabályozható.

Fontos kérdés az algoritmus konvergenciája. Ha a probléma állandó és a megerősítő értékek (jutalmak) következetesek (ami gyakran nem teljesül, ha a játékbeli véletlen eseményekre támaszkodnak), akkor a Q-értékek konvergálni fognak. További futtatása a tanuló algoritmusnak nem fog megváltoztatni egyetlen Q-értéket sem. Ekkor az algoritmus a problémát teljesen megtanulta. Nagyon kis játékok esetén ez elérhető pár ezer iterációval, de valós feladatoknál hatalmas iterációs számok adódhatnak. A Q-tanulás egy gyakorlati alkalmazásában nem lehet elérni elfogadható idő alatt a konvergenciát, emiatt a Q-értékek konvergálódásuk előtt felhasználásra kerülnek. Általános dolog az, hogy már a tanulás befejeződése előtt a részlegesen megtanult értékek hatása alatt zajlik a cselekvés.

Az algoritmus konvergenciájára, a tanulás gyorsaságára és minőségére nagy mértéken kihatnak az algoritmus hangolását lehetővé tevő paraméterek. Az α tanulási együttható azt szabályozza, hogy milyen hatása legyen az aktuális visszacsatolási értéknek a tárolt Q-értékre. Nulla érték mellett nem történne tanulás, a Q-értékek változatlanok maradnának. A másik véglet, az 1 érték nem venne figyelembe semmilyen előzetes tapasztalatot.

Tapasztalatok szerint a 0,3 érték egy érzékeny kezdést nyújtó érték, de tuningolást igényel a tanulás folyamán. Általában az állapotátmenetek nagyfokú véletlensége (pl. ha egy akció választásával elért jutalom-, vagy végállapot mindig drámaian különböző) alacsonyabb tanulási együtthatót igényel. Másrészről, ha csak kevesebb iteráció lehetséges, akkor nagyobb értékre van szükség.

A tanulási együttható csökkenő tuningolása szokásos a folyamat előrehaladtával, pl. 0,7-ről 0,1-re.

A γ diszkont faktor az állapotnak a rákövetkező állapottól való függését fejezi ki. Nulla érték esetén csak az akcióra kapott jutalom befolyásolná az állapotot. Az egyes érték a kivitelezett akcióra kapott jutalmat ugyanolyan fontossággal venné figyelembe, mint azon állapot jóságát, amelybe vezet.

Nagyobb értékek hosszabb akcióláncolatok kialakulását támogatják, de hosszabb tanulást is jelentenek. Egy javasolható induló érték a 0,75. Ez, ha a jutalomérték 1, 0,05-nyi részben fog beleszólni a tíz lépéssel korábbi akció Q-értékébe.

A felderítés véletlenszerűségét szabályozó ρ paraméter határozza meg, milyen gyakran választ az algoritmus véletlenül akciót a legjobb helyett. Az érték [0, 1] között változik. Nulla érték a korábbi tudás felhasználását jelenti, megerősítve amit már tud. Az egyes érték tiszta felderítő stratégiát eredményez: mindig új dolgokat fog kipróbálni, soha nem támaszkodva a már megszerzett tudására. Online játékokban a korábbi tudás révén hamarabb mutathat intelligensnek tűnő viselkedést, míg offline játékokban inkább a minél alaposabb tanuláson van a hangsúly. Ez utóbbihoz bevált a 0,2 kezdőérték.

A kalandozás hosszát, azaz a kapcsolódó akciósorozattal megtett iterációszámot a ν paraméter szabályozza. Nulla érték azt jelenti, az algoritmus mindig az előző iterációban elért állapotot használja a következő iteráció startállapotaként. Ez azzal az előnnyel jár, hogy az algoritmus áttekint olyan akciósorozatokat, melyek végül is sikerhez vezethetnek. Hátránya, hogy az algoritmus egy viszonylag kevés elemű állapothalmazba ragadhat, amiből nincs kijutás, vagy csak alacsony Q-értékű állapotokon keresztül, amelyeket éppen emiatt nem választ. Az egyes érték azt jelenti, hogy minden iteráció egy véletlen állapotból indul. Ha minden akció és állapot egyformán valószínű, akkor ez az optimális stratégia: ez fedi le a legszélesebb tartományt és akcióhalmazt a legrövidebb idő alatt. A valóságban azonban egyes állapotok és akciók sokkal gyakoribbak. Egyes állapotok vonzáspontként működnek, melyekhez nagyszámú különböző akciósorozat vezet. Ezeket az állapotokat a többi előtt célszerű feltárni és lehetővé tenni az algoritmus számára olyan akciósorozatok feltárását, melyek ilyen állapotban végződnek. Sok feltárási stratégia ezen paraméter nélkül működik. Ezek mindig az akciók egy láncolata mentén haladnak. Online játékokban, az algoritmus által használt állapot közvetlenül a játék állapota által meghatározott, azaz lehetetlen egy új véletlen állapotba mozogni. Ilyen esetekben kötelező a nulla paraméterérték. Tapasztalat szerint ahol kevés iteráció lehetséges, a 0,1 érték megfelelő. Ez átlagosan kilenc akcióból álló láncot hoz létre.

A megerősítő érték, azaz jutalom kulcsfontosságú az algoritmus helyes működésében. Tipikusan a jutalmat két ok miatt használjuk: a cél elérésére és hogy végrehajtsunk pár más előnyös tevékenységet. Hasonlóan, a negatív érték, a büntetés szolgál a játék elvesztésének kiváltására, vagy néhány nem kívánatos akció elvégzésére. Mindenképpen a cél elérése egy nagyon előnyös akció, és az ágensnek a saját halálát nemkívánatosnak kellene éreznie. A legtöbb irodalom feltételezi, hogy a feladatnak van megoldása és a célállapot elérése egy jól definiált tevékenység. A játékokban nem ez a helyzet. Lehetséges sok eltérő megoldás, különböző minőséggel, vagy lehetséges, hogy egyáltalán nincs megoldás, csak száz, vagy ezer különféle akció, melyek előnyösek, vagy problematikusak. Egy egyetlen megoldással rendelkező játékban adhatunk egy nagy jutalmat (pl. 1) az akciónak, mely a célhoz vezet és semmit a többi akció esetén. Elegendő iteráció után kapunk egy, a célhoz vezető Q-érték sorozatot, mely az állapotok hálózatán bármely külső állapotból a jutalomcsúcshoz vezet kiegyenlített, monoton növekvő jutalomértékeken keresztül, hasonlóan egy hegymászó kereséshez.

Amennyiben azonban további jutalmakat adunk egyes állapotokba vezető akciókhoz, az egy csúcsos hegymodell helyett több lokális csúccsal rendelkező jóságeloszlás is adódhat, amelyen egyes állapotokból indulva az akciósorozatok nem visznek el a kívánt célállapotba, hanem lokális csúcsokra vezetnek.

A helyzet csak romolhat többszörös megoldást tartalmazó állapotterek vagy sok jutalommal is ellátott állapot esetén. Ámbár a jutalmak gyorsítják a tanulást, az gyakran válik sikertelenné. Megoldást adhat egy finomabb kiegyensúlyozás. Nem célállapot helyeken nagyon kis jutalmak adása segíthet, de nem mindig ad ez sem tökéletes megoldást. Célszerű egyetlen céllal rendelkezőre egyszerűsíteni az állapotteret és más állapotokban nem alkalmazni jutalmazást. Ha a tanulás túl hosszú, megpróbálkozhatunk kis jutalmak adásával is.

A gyakorlati tapasztalatok előhozták a kombinatorikus robbanás gondját, mind a memória, mind az idő esetében. A helyszínek * karakterek * életképességi_szintek * fegyverszintek szorzata egy komolyabb játék esetén hamar csillagászati értékké válik.

Emiatt célszerű ahol csak lehet, összevonásokat, egyszerűsítéseket alkalmazni. Gyakorlati tapasztalatok az offline tanulás korlátait 100000 állapot, 10 akció/állapot, 5 000 000 iteráció értékben húzzák meg, Online játékok esetében ezek töredéke, pl. 100 állapot, tűnik reálisnak.

A legsikeresebb alkalmazások a táblás játékok terén adódtak, de jó lehet az ellenfél akcióinak ismeretében taktika tanulására, egy karakter kifejlesztésére (egyszerűen megadva neki a célt és az akciói halmazát), szereplő, vagy jármű mozgásának korlátozott szabályozására, többjátékos környezetben a kölcsönhatások megtanulására, hogy meghatározzuk hogyan és mikor alkalmazunk egy speciális viselkedést (pontos ugrás, vagy tüzelés megtanulása), és további hasonló valósidejű alkalmazásokhoz. Megtanulható és utánozható egy játékos játékstílusa.

Esettanulmány: Védekező pozíciók elfoglalásának megtanulása

A szituáció: három játékágens katona véd egy katonai bejáratot az emberjátékos ellen. Cél az emberjátékos behatolásának megakadályozása. Eszközök mindkét félnél a rejtőzködés, lövés, mozgás. Az állapottér reprezentáció: védő pozíciók, vagy nincs pozíció, ha éppen mozog, vagy halott (15+1+1) és két láthatósági lehetőség (az emberjátékos látható, vagy sem), azaz 34 állapot katonánként, összesen közel 40 000 állapot. Az akciók: minden állapotban, ha nincs katona mozgásban, akkor valamelyik mozoghat – egyszerűsítés, hogy egyszerre csak egy -, ily módon 56 lehetséges akció, és nem lehet akció, ha bármelyik katona mozog. Jutalmazás: ha az emberjátékost kilőtték (a katonák lövik, ha látják), büntetés, ha bármely katona meghalt, vagy az emberjátékos bejutott. Vegyük észre, hogy nem reprezentáljuk az ember pozícióját, ha látszik. Bár igen nagy jelentősége van, hol tartózkodik az ember, a büntetés, amikor az ember behatol, azt jelenti, a stratégiának meg kellene tanulnia, hogy a bejárathoz közelebb lenni kockázatosabb.

Az megerősítő tanulás algoritmust futtatva egy egyszerű játékos viselkedést modellezünk: véletlen utak a bejárathoz, és ez alapján állapotok generálása.

Grafika nélkül egy eseménysorozat gyorsan számítható. Paraméterek: α= 0,3, γ= 0,7, ρ= 0,3, ν=0,0. Mivel a modellállapot egy aktív játékállapothoz kötött a ν értéke nulla lesz. Mindig ugyanabból az állapotból indítjuk újra az algoritmust, amikor az ember meghalt, vagy bejutott. Kb. 20 000 iteráció után észrevehető taktikák jelennek meg: a katonák fedezéket keresnek; kezdetben a bejárattól távolabb helyezkednek el, de visszarohannak, ha a játékos feltűnik.

Mesterséges neurális hálók

A mesterséges neurális hálók az emberi idegrendszer modellezésének igényével születtek. Széleskörű alkalmazásuk kiterjed a számítógépi játékokra is. Egyik lehetséges alkalmazásuk a döntési képesség megtanulása és alkalmazása játékágensekben. A neurális hálók tudománya igen kiterjedt. A bekezdésben hivatkozunk a számtalan, magyarul is megjelent szakkönyvre. A neurális hálózatokban alkalmazott alapelvek felfrissítése után egy multilayer, többrétegű Perceptron elvű kereskedelmi alkalmazással kivitelezett neurális háló alapú amőbajáték alkalmazás bemutatásával szemléltetjük a lehetőségek egy szeletét.

A mesterséges neurális hálózatok három fő összetevője a

  • mesterséges neuron

  • a hálózat topológiája és a

  • tanulási-működési algoritmus.

A biológiai neuront modellező mesterséges neuron a (Lawrence, 1993) bemutató műve alapján rajzolt ábra szerinti oj (j= 1..m) inputot fogadó bemenetekből, a bemeneteken a szinaptikus kapcsolatok erősségét, gerjesztő/gátló jellegét modellező wi,j (i=1..n, j=1..m) súlyokból, a neti gerjesztést számító belső skalárszorzóból, a gerjesztésből a belső aktivációs potenciált számító aktivációs függvényből, mely gyakran egy 1 értékű szorzó, azaz elmarad és a minden-vagy-semmi elvű kisülést modellező átviteli függvényből áll. Az aktivációs függvény modellezheti a gerjesztés időbeni lecsengését, de gyakran elmarad.

Mesterséges neuron

Az átviteli függvény a küszöb aktiválást elérő neuron tüzelését modellezi, az egyszerű lépcsős függvénnyel, vagy ferdeátmenetes, hibavisszaterjesztésre is alkalmas függvényekkel, mint pl. a gyakori szigmoid függvény. Az alábbi ábra θi = 0 aktivációs küszöbbel, vízszintes eltolás nélkül mutatja a függvényeket.

Átviteli függvény típusok

A szigmoid függvény a k meredekséget szabályozó szorzóval és a θi küszöbértékkel:

A további részletek megismerhetők pl. (Horváth, 1995; Horváth, 2007; Smith, 2003, Haykin, 2009) írásaiból.

A hálózat topológiája alapvetően előrecsatolt és hátracsatolt lehet. Az előrecsatolt hálózaton a bemenet hatása egyetlen ciklusban átterjed a kimenetre. A visszacsatolt hálókban a jelek előre-hátra áramlanak, amíg egy időben már nem változó állapot be nem áll. Ez, a gyakran nem konvergens és emiatt nem használható folyamat időigényesebb és összetettebb számítással jár, lásd pl. (Haykin, 2009). A mi példánkban többrétegű, multilayer Perceptront alkalmazunk, amely használatakor előrecsatolt hálóként működik, az ábráról leolvasható módon:

Előrecsatolt neurális háló

A jelek a csak elosztó szerepű ’neuronokat’ tartalmazó input réteg felől az output réteg felé áramlanak.

A topológia mellett a tanulási algoritmus az, ami alapvetően megkülönbözteti a sokféle neurális hálót. A többrétegű Perceptron hálók hiba-visszaterjesztéses, Backpropagation módszerrel tanulnak, felügyelt módon, aminek a lényege hogy az adott számú input és output mintapárból álló tanító adathalmaz soron következő input mintáját a háló bemenetére ráadva, a nem tökéletes wij súlyok miatt a kimeneten nem pontosan a mintapár elvárt output értékének megfelelő kimenet adódik. Az eltérés vezérli a háló súlyainak kismértékű olyan változtatását, hogy legközelebb a kimenet már egy kissé jobban közelítse az elvárt kimenetet. A háló súlyainak ilyen vezérelt megváltoztatása a kimenet oldali súlyokon kezdve, a bemenet oldali súlyok felé, a hibának tekintett eltérés hatását visszafelé terjesztve történik. A mintafájl mintapárjait több iterációs ciklusban bemutatva a hálónak, a háló wij súlyai és θi küszöbértéke olyan irányba változnak kis mértékben, hogy a hiba nullához tartson. A feladat matematikailag a wij dimenziók többváltozós terében a mintapárok összességére adódó hiba legkisebb értékét eredményező pont, azaz súlyértékek megtalálását igényli, mely pl. gradiens módszerrel elérhető konvergens feladatok esetén.

A következőkben egy többrétegű Perceptron háló segítségével működő amőbázó (GoMoku) játék kialakítását mutatjuk be.

Neuronháló alapú Amőba játék-alkalmazás

Az amőba játék játszására készült neurális háló alkalmazások tudományos publikációkban is megjelentek (Freisleben, 1992, 1995; Freisleben & Luttermann, 1996).

A következőkben a szerző oktatási célú saját megoldását mutatjuk be.

A feladat: offline betanítással létrehozott neurális háló alkalmazása amőba játék programban. Az amőbaprogramban a felek célja nyerés elérése azáltal, hogy a saját jeléből ötöt közvetlenül egymás mellé helyez a rácsos játékmező rácspontjain vízszintes, függőleges, vagy átlós irányban. Az ábra a játékot mutatja, egy utolsóként lerakott X jellel nyerő ötöst adó szóbajöhető ágakkal, kiemelve ezen ágak közül a baloldali vízszintes ágat. Ez a csillag alakzat a későbbiekben kiemelt szerepet játszik a neurális háló betanításában.

Kiértékelő csillag alakzat

Az alábbi videón a betanítóminták generálását követhetjük: video lejátszás

A program a következő fő részekből áll:

  • A játékteret megjelenítő és az emberjátékos lépéseit bevevő, valamint mindkét játékos lépéseit megjelenítő modul, benne a nyerés észlelésével és kijelzésével

  • A gépi játékos, a programágens állásfelmérő és döntéshozó tevékenységét realizáló modul.

A program C nyelven íródik, mivel a rendelkezésre álló Brainmaker™ neuronháló modellező program csatolt függvénykönyvtára is C nyelvű függvényeket nyújt. A C nyelvű beágyazó programkörnyezet az előző első pontban adott feladatokat látja el a következő részletezésben:

  1. Betölti az offline betanításban létrehozott súlymátrixot és neuronháló paramétereket a többrétegű Perceptron háló konkretizálásához

  2. Megjelenít egy 20x20-as játékmezőt

  3. Lehetővé teszi az emberjátékos számára a kurzor pozicionálását és a jelének (O) a lerakását

  4. Nyeréstesztet végez, nyerés esetén vége: Nyert az emberjátékos.

  5. Az emberjátékos lépése után meghatározza a gép lépését, ehhez egy ciklusban a játékmező minden egyes üres rácspontjára elvégzi a következőket:

    • leteszi a saját X tesztjelét, és egy csillag alakzatban megnézi, milyen jelek találhatók a teszthely környezetében. Ebből a csillag alakzatból a középső tesztjelet kihagyva, az ágakat beforgatva egy 4x8-as mátrixot képez. (Erre a lépésre amiatt van szükség, mert a Brainmaker csak téglalap alakú ’kép’-inputot fogad.) A mátrixot bemutatja a neuronhálónak, mely visszaad egy számértéket, ami arányos azzal, mennyire lenne jó támadó lépés X számára, ha az adott helyre lépne.

    • A tesztjelet kicseréli az emberjátékos O jelére, majd megismétli az előző lépéseket, ezáltal kap egy olyan számértéket, mely azt mutatja, mennyire lenne jó lépés az ember számára, ha az adott helyre lépne. Mivel a gép lép, ez számára azt jelenti, mennyit rontana az ember lehetőségein, ha a számára kedvező helyre belépve azt a lehetőségét az embernek elrontaná. Mivel mind a támadást, mind a védekezést egyaránt nézi, ezért a két értéket együtt kezeli. Az egyszerű összegzés helyett a saját lépés értékét egy egynél kevéssel nagyobb szorzóval szorozva veszi, és így összegez, hogy egyforma helyzetben inkább támadjon, mint védekezzen.

    Ha jobb érték adódott a vizsgált helyre, mint a korábbiak legjobbja, akkor azt tárolja el eddigi legjobbként.

  6. A ciklus lefutása után előáll az a játékmező, amelyre a támadást és védekezést egyaránt érvényesítő összegzett számérték a legnagyobb volt. Ide lép a gép.

  7. Nyeréstesztet végez, nyerés esetén vége: Nyert a gép.

  8. Ismétli a 3. ponttól.

Az alkalmazásban kulcsszerep jut a többrétegű Perceptron hálónak a gép lépésének meghatározásában, ezért nézzük meg általánosan, hogyan jutunk el a háló esetében a betanítási feladat megfogalmazásától a háló hasznosításáig! Az ábra a felügyelt tanítással működő neurális hálók betanításának tipikus lépéseit mutatja.

Perceptron hálók betanítási folyamata

A betanítási feladat a jelen esetben: 4x8-as, X, O és üres mezőkből álló mátrixképből és a kép által leképezett amőbaállás jóságát X (illetve a másik betanításban O) számára megadó számértékből álló mintapárokból álló mintafájl betanítása a hálónak.

A betanításhoz szükséges információ egy mintapár esetén a 4x8-as mátrix és a 0..65535 értéktartományba beleférő jósági érték. A háló kimenetén elvárt jósági értéket nem egyetlen neuron 0-1 tartományára, hanem 16 darab neuronra fogjuk leképezni. Az egyes kimeneti neuronok a jósági érték bináris értékének bitjeit fogják ábrázolni, így a kimeneteken adódó kisebb hiba nem lesz annyira zavaró. Ismeretes, hogy a mesterséges neurális hálók nem tökéletesen pontos kimeneteket adnak, ezért előnyös ez a szétosztott kimenet. Ennél egy 0.3-as kimenő értéket 0-nak, egy 0.75-öset 1-nek fogunk venni.

Tehát a háló 4x8= 32 inputtal és 16 output neuronnal fog rendelkezni. Az egy alkalmazott rejtett rétegbeli neuronok számának meghatározására csak ökölszabályok léteznek, így azt módszeres próbálgatással fogjuk meghatározni. Az egyszerűség kedvéért azt a darabszámot részesítjük előnyben, amellyel a háló gyorsabban betanulja a mintafájlt. Ez a próbák során 384-re adódott.

Komolyabb probléma a betanításhoz a mintapárok összegyűjtése. A betanításhoz ténylegesen lejátszott játszmák lépéseit és azok jósági értékét fogjuk felhasználni. A mintapár input oldalát egy üres mezőre letett X, vagy O tesztjelre, mint középpontra illesztett csillag alakzat téglalap alakra transzformált alakja fogja adni, de ki fogja megbízhatóan megmondani nagyszámú állásra, hogy az mennyire előnyös a tesztjel lerakója számára? Éppen bízhatnánk ezt a feladatot emberekre is, de az értékek nem lennének eléggé megbízhatóak. Másrészt nehéz olyan embert találni, aki a sok érték megadását vállalná. Ezért az adott helyre lerakott tesztjel jóságát számítógéppel fogjuk kiértékeltetni. Erre a célra egy elég erősen játszó heurisztikus elvű amőbázó programot módosítottunk úgy, hogy gép gép elleni játékban generálja az input mintázatokat és mentse le hozzájuk a jósági értékeket is. A programmal a több száz mintát és azok jósági értékét tartalmazó betanítófájl előállítása gyors és egyszerű. A program lehetővé teszi, hogy válasszunk a játék „sűrűjéből”, vagy az üres területeken található mezők teszteléséből adódó mintapárok mentése között, hogy a betanított neurális hálónak legyen képe, ismerete a játék szempontjából nem érdekes üres területek mezőinek alacsony jósági értékéről is.

A betanítófájl összeállításakor kihasználtuk a Brainmaker neurális háló betanító program azon jellemzőjét, hogy a .def betanítófájl fejrésze tartalmazza a neurális háló szerkezeti jellemzőit és a mintapárok külön láncolható .fct kiterjesztésű fájlokban adhatók meg. A .def állományt mutatja az ábra:

A betanítófájl fejrésze

Látható, hogy a mintapárokat a facts kulcsszó vezeti be, és egyetlen mintapár után a láncolt .fct fájl nevének megadása található. A láncolt fájl kezdete alább látható. A fájlban több ezer mintapár is lehet. A minták ismétlődése nem okoz gondot.

Tényfájl részlet

A neurális háló betanítása a Brainmaker™ programmal történik, melynek a fenti definíciós fájlt megadva és a tanítást elvégezve az alábbi kép fogad:

A betanító program

Az ábráról több minden leolvasható: Az utolsó minta input része két O jelet tartalmazott, a hozzá tartozó elvárt bináris jósági érték: 0000000001011000, azaz 88. A lerakott tesztjel szintén O volt. A neuronháló által számítottkimeneti értékek 0.1 tűrésen belüliek, a betanítás megadott tűrése (Tolerance) ugyanis ennyi volt. A betanítás után a háló az összes mintapár inputjához ilyen hibahatáron belül számítja a kimenetet. Soha nem látott mintákra azonban nagyobb hibával rendelkező kimenetet is ad. Látható még, hogy egy kis, 251 mintapárt tartalmazó fájlt 67-szer mutatott be a hálónak, míg az a 0.1-es tűrésen belül betanulta azokat (Fact, Run).

A súlymátrix lementése

A betanult súlyokat a Print/Weight Matrices to File ... menüponttal menthetjük egy .mtx kiterjesztésű fájlba.

A beágyazó C programban a Brainmaker szoftvercsomagban található runtime könyvtár programjai közül a súlyfájl-betöltő és a neuronháló futtató függvényekre van szükség. Az elkészült program egy 5-7 éves gyerek szintjén játszik, bár néha megcsillantja a tehetségét, de a nyerő helyzetek megakadályozásában még nem erős. A működését a következő animáción követhetjük:

Neurális háló alapú amőbajáték

video lejátszás