Egyszer egy palyazatra kezdtem el irni egy novellat Spiral cimmel, amit vegul nem fejeztem be. Nemreg megtalaltam a vinyomon egy takaritas alkalmaval, es ujraolvastam.

A tortenet a kozeli jovoben jatszodik, ennek megfeleloen megprobaltam nehany trendet megjosolni. Egy igen erdekes otlet, amit akar mar jelenleg is konnyen meg lehetne olvasni, egy hirolvaso agent.

A tortenetben a fohos elokap egy kis kutyut (kb. okostelefon) es elkezd rajta hireket olvasni. Az agent (bocs, nem akarom a ugynok vagy az agens szot hasznalni) pedig – on the fly – a fohos olvasasi szokasai es mas, kezzel hozzaadott kriteriumok alapjan atszinezgeti bizonyos hirek (valojaban focimek) hatteret, kiemelve azokat, amik erdekesek lehetnek.

Az alkalmazas technikai resze, eltekintve a szakertoi rendszer / AI vonulattol, aranylag konnyen megirhato lenne. Atszinezni a hattereket a szovegelemzes eredmenyetol fuggoen nem egy bonyolult dolog a html-ben.
Az agent lehetne egy bongeszoben futo – akar javascript alapu, vagy greasemonkey – kiegeszites, vagy egy webes app, ami egy sima formazo/rendezo filterkent mukodne, es egyebkent csak a normalis hirolvaso oldalunk tartalmat szurne at magan. Es termeszetesen hasznalhatnank pl. a google readerben felvett feed-eket alapul.

Ehhez valamennyire hasonlo – amennyit tudok rola – a reader-nek a magic alapu rendezese a google readerben. Alapvetoen csak ket problemam van vele: a sorrendet nem szeretem megvaltoztatni, raadasul az egesz eleg homalyos, nemigen van kozvetlen rahatasom arra, hogy miket szeretnek es nem szeretnek latni – eltekintve a like es not interested gomboktol, amik az egesz cikkre vonatkoznak, nem egy adott, specifikus, altalam meghatarozott temara.

Ha idom es kitartasom lenne, szerintem neki is allnek megirni ezt az alkalmazast. Erdekelnek az AI vonzatai, es hasznos tool is lenne.

Elgondolkoztam a minap azon, hogy hogyan kellene megoldani a “szovegdobozok automatikus elrendezese” funkciot. A feladat – mint azt mar rengeteg toolban lathattuk – nem trivialis. Reszben azert, mert mindenkinek masfele elrendezes a jo, reszben pedig azert, mert nehez szavakba onteni, hogy egy graf mitol “nez ki jol”.

Az elso megkozelitesem pusztan matematikai: megprobalom azokat a dobozokat kozepre hozni, amiknek sok kapcsolata van, es periferiara rakni azokat, amiknek keves. Mindezt azon feltetelezes alapjan, hogy sok kapcsolattal a fontos otletek rendelkeznek, es azokat megilleti a kozponti hely. A problema itt mindossze annyi, hogy a kesobbi boviteseknel siman van arra esely, hogy a fontos otletek tovabbi kapcsolatokat kapjanak, amihez viszont nem lesz eleg hely.

Elgondolkoztam azonban a jatekok AI-ahoz hasonlo, a felhasznalo viselkedeset figyelo es elemzo kodon is. Ez osszessegeben nyilvan hihetetlenul bonyolult, de aranylag konnyen ki lehet olyasmit deriteni, hogy az uj elemek letrahozasakor milyen tavol helyezi a felhasznalo az ujat a meglevoktol, valamint olyanokat is, hogy elre igazitva szereti a dolgokat, vagy csak ugy szethanyva, egymastol fuggetlenul. Egy erdekes gondolat ennek kapcsan, hogy ezt az extra infot le is kellene menteni a graf melle, amikor a felhasznalo menti azt, hiszen egyebkent ket szerkesztes kozott elveszne a history.. Ami viszont egybol elvezet a tobb felhasznalo altal mahinalt grafokhoz..

De eloszor is baby steps. Addig ugyse lesz szukseg erre a funkciora, amig nincs egy mukodo alkalmazas, mondjuk a v0.4.

2010 feb. 10

For English please go here.

Az idei Google AI Challenge feladata, hogy irj egy botot, ami Tront jatszik. Mas botok ellen. Batyam, tudva, h erdekel az ilyesmi, adott egy linket.

Fejest ugrottam bele. Nem erdekeltek a strategiai guide-ok, mivel eleg jol ertek hozza, raadasul nem is nyerni akartam, hanem kicsit kiserletezgetni. Termeszetesen a kiserletezgetes egyik fokmeroje az, hogy milyen eredmenyt erek el, es ebben sokat segit, hogy folyamatosan versenyeztetik a botokat, bar a konkret verseny csak valamikor a honap vegen zajlik majd.

Nehany eve mar erlelgetem magamban a tobb retegu AI gondolatat, ahol a lenyeg az, hogy a donteshozas tobb, kulonbozo szerepkort illetve nezopontot megvalosito retegen fut keresztul, amik hozzaadnak es elvesznek lehetosegeket, illetve sulyozzak a meglevoket. (ertelemszeruen: az elso retegek osszegyujtik, az utana kovetkezoek megszurik oket.) Ezt az alap0tletet hasznaltam most fel, amikor megirtam a botomat.

Mivel stilusdijra is gyurok (nem mintha lenne ilyen) a botom kodja azt az elkepzelest tartja a kozeppontban, hogy a kiraly akar egy falat epiteni, es mindig, amikor elkeszul egy resze a falnak, akkor tanacskozik a tanacsosaival, hogy a kovetkezo lepest merre tovabb. A kovetkezo megjegyzesben mutatok erre kodot is, itt csak az alapstrukturat irom le:

- Az elso reteg a Master of War. Tisztaban van vele, hogy messzirol nem lehet harcolni, de tul kozel sem akar menni, igy aszerint sulyozza a lehetosegeket, hogy mindig egy bizonyos tavolsagra legyen a masik falepitotol. (elvegre ot szeretnenk letolni a terkeprol.)

- A masodik reteg (bar lehetne az elso is) a Master of Geography. O az, aki kikuldi a felderitoket, hogy kitalaljak, merre all sok hely a rendelkezesunkre. A korabbi valtozata csak felment a hegytetore es korulnezett egy latcsovel, de ez nem mukodott olyan jol, ugyhogy ot kirugta a kiraly.

- A harmadik reteg a Master of Spies. O az ellenfel mozgasat figyeli, es probalja kitalalni, hogy hogyan zarhatnank ot el magunktol.

A kiraly bolondjat kirugtak. O csak annyit akart, hogy februar 14-en rajzoljunk egy szivet, de ez nem tunt megvalosithatonak a rendelkezesre allo terulet jellege miatt.

Jelenleg a 91. vagyok a korulbelul 600-bol. Magyarazat a fenti diagrammhoz: Az elejen az alapcsomag volt csak benevezve, ami, ahogy nott a nevezok szama es megszulettek az elso igazi botok, szepen vesztett a helyezesebol. Feb 8-an beneveztem az elso kesz valtozatot a botombol (meg a regi Master of Geography-val) ekkor szepen felugrottam a 250. hely kornyekere. Ott el is vegetalgattam egeszen ma reggelig, amikor is feltoltottem az uj verziot – ami tegnap este kesz volt mar, de egy oran keresztul hiaba probaltam feltolteni, technikai okok miatt nem sikerult. Az uj verzio a felderitokkel lathatoan sokkal jobb eredmenyeket er el, miota feltoltottem, a 90-100. hely kornyeken vagyok.

Íme az első screenshot az “legközelebbi felé mozgunk és ha odaértünk, megállunk” viselkedéshez:

Egyszerű szomszédvizsgálat

A kék az alapszín, a világoskék a megtett utat jelzi, a sárgák pedig a “végpontok”, ahol a kis szigetek megállapodtak. A következő kísérletben megpróbálok egy olyan vizsgálatot beillesztni, ahol a kis szigetek mindig a környéken lévő legnagyobb sziget felé igyekeznek..

Mondanom sem kell, ez a kép is nagyszerűen mutatja, hogy ebből a szabályrendszerből csak egy valamivel rendezettebb káosz alakul ki, de egészen távol van attól, hogy egy valódi sziget alakuljon ki..

Egy MMO-hoz kapcsolódó cikk kapcsán olvastam a fenti kifejezést: Emergence. Mivel nem tudtam, mit is jelent pontosan, rákerestem, és találtam egy nagyon jó definíciót a wikipedian:

“In philosophy, systems theory and science, emergence is the way complex systems and patterns arise out of a multiplicity of relatively simple interactions. Emergence is central to the theories of integrative levels and of complex systems.”

Azaz, a lényeg magyarul az, hogy amikor viszonylag egyszerű cselekvésekből valami minta, összetett dolog következik, azt hívják így. Ez valahol pont a fordítottja annak, amire én törekszem, de hiszen én egy mintából szeretnék egy egyszerű viselkedést kihozni, de biztos, hogy van helye a játékok világában. Részletesebben ki fogom fejteni később, milyen szituációkat tudok én elképzelni, ahol ezt hasznosítani lehet..

Mennyire lehet nehéz előre megjósolni egy játékos viselkedését? A csapdaállítás kapcsán már kiderült, hogy ahhoz, hogy a csapdánk hatékonyan működjön, szükségünk van arra, hogy a játékos mozgását befolyásoljuk. Ha egy kicsit általánosítunk, akkor azt is mondhatjuk, hogy a stratégiánk helyes viselkedéséhez tudnunk kell, hogy a játékos mit fog csinálni.

A kiszámítás nyilván nem egyszerű dolog, hiszen a legtöbb esetben maga a játékos sincs tisztában azzal, hogy mit akar csinálni, mintahogy az sem biztos, hogy ha elkezd egy terv szerint dolgozni, akkor azt be is fejezi. A legnyilvánvalóbb megoldás az, hogy ha a gép tanul, és a korábbi viselkedési minták alapján megmondja, hogy jó eséllyel mi következik. Ennek azonban több hátránya is van: nehéz megcsinálni, rengeteg információt kell hozzá nyomon követni, számításigényes és nem elég dinamikus, mivel a játékos viselkedését meg kell tanulni mielőtt reagálni tudnánk rá.

Ennek a gyorsabb, de kevésbé rugalmas változata a játékosmodellek alkalmazása, ahol többféle viselkedési sémánk van, és csak azt próbáljuk meghatározni, hogy a játékos ezek közül melyikhez áll legközelebb. Ennek sikeressége nagyban függ a modellek részletességétől, a játékos besorolásának pontosságától és attól, hogy a játékos ne legyen tisztában azzal, hogy milyen modellek vannak, hiszen akkor arra alapozva tud csalni. Cserébe ez a megoldás sokkal gyorsabban alkalmazható az aktuális helyzetekre, és gyorsabban lehet vele reagálni a stratégia váltásra is – ám sokkal kevésbé precízen.

Ez a két technika kombinálható is, nyilván, és ha elég ügyesek vagyunk, akkor mindkettőből a lehető legtöbb pozitív tulajdonságot átvisszük.

Ugyanakkor van egy olyan lehetőség is, ami ennél sokkal egyszerűbb. Mi van akkor, ha nem sokat foglalkozunk a játékos besorolásával és a predikcióval – hanem inkább megpróbáljuk befolyásolni a viselkedését? Feltételezzük, hogy bizonyos helyzetekre miként reagál, és megpróbáljuk annak megfelelően irányítani. Például egy RTS játékban ha a játékost folyamatosan légi egységekkel támadjuk és csak névleges földi erőt vonultetunk fel ellene, akkor ő várhatóan légi egységek ellen fog felkészülni. Ha ezek után indítunk ellene egy szinte kizárólag földi egységekből álló offenzívát, akkor találhatunk rést a védelmén. – feltételezve, hogy a játékosnak feltűnt a légi egységek fokozott használata.

Régi vesszőparipám a csapdaállítás a szerepjátékokban. Háromféle lehetőség van erre: A pályatervező készít csapdát, a játékos készít csapdát illetve az ellenfél készít csapdát. Ebből az első általában jól sikerül – nyilvánvaló, hiszen a pálya maga úgy készül, hogy el tudják helyezni benne a csapdát. A játékos csapdaállítása többnyire haszontalan, hiszen a játékok alapvetően progresszívek, a játékos mozog, a környezet reagál, ebbe nem illik igazán bele az, hogy a játékos elhelyez egy nem mozgó objektumot. A hangsúly azonban ebben a bejegyzésben a harmadik ponton van.

Az első játék, ami a csapdaállítással kapcsolatban eszembe jut, a guild wars. Emlékeim szerint ott a gépi ellenfél képes volt egészen hatékonyan csapdát állítani – a saját lábánál. Gondolkozzunk el azért inkább azon, hogy milyen szempontokat lenne érdemes a csapdaállításnál figyelembe venni:

- Alapfeltételeink: Az ellenfél 1 egyed, ami bár kommunikációképes, de nem irányítja a többi ellenfelet. Az ellenfél nem csal, azaz a saját maga által állított csapdába ő is bele tud lépni.

- Először is határozzuk meg a csapda jellegét: A játékost egy szerkezettel/mágiával/etc. akarjuk elkapni/sebezni/mérgezni/sít vagy tőrbe akarjuk csalni, egy várakozó csoporthoz, akik majd jól megtámadják.

- Mindkét esetben a játékos mozgását kell irányítanunk, hogy egy adott ponthoz elérkezzen vagy áthaladjon rajta. Ez lehet vonzó vagy taszító jellegű irányítás, azaz a játékos valami felé vagy valamitől elfelé mozog. Mivel az ellenfél 1 egyed, ezeket is neki kell valamiképpen megoldania: maga után csalhatja a játékost, vagy éppen egy nyilvánvaló csapdát állíthat valahol, amit a játékos kikerül, és emiatt mozog bele az igazi csapdába.

- A mechanikus/mágikus csapdát olyan helyre érdemes állítani, ahol a játékos nehezen kerüli ki, azaz pl. a folyosó egy szűkületében, vagy éppen egy ajtóban. Ugyancsak jó ötlet lehet egy könyvespolc elé rakni, ha tudjuk, hogy a játékos vsz. úgyis odamegy és megvizsgálja. A csoportok olyan helyen jók, ahol a játékos körülzárható vagy a menekülése valamilyen más módon megakadályozható.

- A csapdaállításnak akkor van értelme, ha aránylag ritka, emiatt a játékos nemigen számít rá.

Ez a logika meglehetősen bonyolult, így nem feltétlenül van értelme megvalósítani egy játékban. Ugyanakkor mégiscsak színesíti a dolgot, meg a programozó számára érdekes a kihívás is..

A fentiek, mint az írtam is, elsősorban a szerepjátékok világára igazak. Kis módosítással azonban a csapdaállítás egy csomó más játékműfajban is használható: FPS-ben vannak a falra tapasztható lézeres aknák; stratégiai játékokban a települések köré vonhatunk aknamezőt, illetve a gerillák is aláaknázhatnak utakat; harci szimulátor játékokban a tőrbe csalásnak van helye. Összességében véve úgy gondolom, ebben elég sok kiaknázatlan lehetőség van (no pun intended.).

A többlépéses minta alapú AI kapcsán jutott eszembe, hogy lenne értelme egyfajta visszacsatolást beépíteni a minták használatába. Ahhoz, hogy az AI eldöntse, hogy melyik mintát alkalmazza, valamilyen értékelési rendszert kell követnie, és a minták pontszámai alapján kell kiválasztania, hogy az adott helyzetben melyik a megfelelő. Ebbe az értékelési rendszerbe lehetne integrálni egy olyan mutatót is, hogy az adott játszmában/környezetben alkalmazott minták közül melyik hányszor volt sikeres, illetve hányszor bukott el. A sikerességnél természetesen lehet egy olyan fokmérő is, hogy mennyire volt sikeres, de ezt nem minden esetben könnyű mérni, nyilvánvalóan.

A sikeresség fokmérője lehet egy sima skála. Középről indul, a sikeresen használt minta növeli, a sikertelen/félbeszakított minta csökkenti a mutatót. Ha tudunk a sikerhez-sikertelenséghez fokmérőt/pontszámot rendelni, akkor annyival növelhetjük-csökkenthetjük az adott értéket, ellenkező esetben pedig csak eggyel.

Ugyanakkor van értelme annak is, hogy két értékben tároljuk a sikerek és hibák számát. Ebből az előző érték ugyanis számolható, ugyanakkor a szórást, azaz a minta esetében a kockázatot is meg lehet belőle határozni. Nyilvánvalóan, ha rossz az aktuális helyzetünk, akkor nem akarunk nagyon kockázatos lépésekbe belevágni – vagy minden mindegy alapon éppen bele is vághatunk, de ez már személyiség kérdése. Igen, az AInak is lehet személyisége, mint azt már sok stratégiai játékban láthattuk is.

Egy probléma van ezzel a módszerrel: a nehézségi szint beállítása. A tanuló ellenfélnél nehéz beállítani egy nehézségi szintet, hiszen tanul, ennél fogva folyamatosan fejlődik, és egyre erősebb lesz. Valószínűleg fogok azon is elmélkedni a közeljövőben, hogy milyen módon lehet megoldani egy önszabályozást, amitől sem túl buta, sem túl okos nem lesz az ellenfél.

Egy pár éve, azt hiszem, az egyik Mérő könyv kapcsán az egyik bátyám mondta, hogy szeretne egy olyan táblás játékot fejleszteni – már nem emléxem, melyik volt az – amiben nem elsősorban az aktuális helyzet értékelése alapján dönti el a gép, hogy mit lép, hanem alkalmaz többlépéses patterneket is. Tudtommal manapság a sakk programok is alkalmaznak hasonló stratégiákat.

Felmerült azonban bennem a kérdés, hogy mi van akkor, ha hasonló alapon próbálunk összetettebb játékokhoz írni AI-t. Azon túl, hogy az AI-nak fel kell ismernie, hogy az adott helyzetben melyik pattern használható egyáltalán, és azon felül, hogy képesnek kell lennie egy patternből kilépni, ha megváltozik a szituáció, vannak kevésbé nyilvánvaló kérdések is.

Egyrészt, ki kell találni, hogy milyen jellegű, és egyáltalán, milyen hosszú (hány lépésből álló) mintákról beszélünk. Az sem mindegy, hogy milyen, az aktuális kontextusnak megfelelő változókat illesztünk bele – ha túl kevés van, akkor nem elég rugalmas, ha túl sok van, akkor nem elég értékes – és nyilván az is elég fontos, hogy egyáltalán milyen jellegű játékról beszélünk, hiszen egy stratégiai játékban egészen más sablonok vannak, mint egy lövöldözősben vagy egy szimulátorban.

Az elkövetkező napokban szerintem sokat fogom ezen jártatni az agyam, és ha bármi értékeset szülök, azt szerintem megosztom majd itt..

A grafikában már egészen jól ismert fogalom a shader: gyakorlatilag egy pixelre vagy képegységre eső árnyalatot tudunk vele kiszámolni nagyon gyorsan, hardveres támogatással, és ha jól tudom, párhuzamosan.

Mivel a napokban a játékok AI részével kezdtem el foglalkozni, elgondolkoztam rajta, lenne-e létjogosultsága egy olyan hardvereszköznek, amivel AI behaviour-t lehetne párhuzamosan számolni. Mivel napjaink játékaiban egyre nagyobb szerepet kap a realisztikus viselkedés, az AI egyre bonyolultabb lesz, ami viszont azt jelenti, hogy sok egységre kiszámolni a viselkedést bizony elég megterhelő lehet a processzor számára. Ugyanakkor az AI-k (legalábbis a döntéshozó rész; itt nem vonom bele a szenzoros inputot) nagyon gyakran egy viszonylag könnyen leírható logika szerint működnek: állapot átmenetek vagy feltétel vizsgálatok, esetenként véletlenszerű módosításokkal. Ez azt jelenti, hogy az AI programozáshoz egy viszonylag egyszerű nyelvet lehetne alkotni.

A fentiekből számomra az következik, hogy simán meg lehetne csinálni, és talán érdemes is lenne. Az is nyilvánvaló, hogy ez nem egy egy emberes vállalkozás. Azért kíváncsian várom, mikor és ki fogja ezt kitalálni